bullockbefriending bard wrote:
> On Dec 4, 1:34 pm, "smartdude" <[EMAIL PROTECTED]> wrote:
> > In graph theoretical terms the problem is to find a minimal (or a
> > reasonably sized) vertex cover of a graph using complete multipartite
> > graphs.
>
> Thanks! You have given me much to think about.
>
> After some introductory reading on graph theory, I believe that I
> understand what you are saying. The concept of vertex cover, per se, is
> easy enough to grasp, although apparently it's non-trivial to find an
> optimal one for large data sets. Complete multipartite, I presume
> refers to the fact that there can be no edges connecting
> vertices/runners in the same race (and in fact, edges can only join
> vertices/runners in preceeding and succeeding races - so is somewhat
> further constrained than complete multipartite would imply).
>
> Let me see if I am conceptualising things correctly. Taking some
> example data and giving each runner in each race a vertex number in
> parentheses:
>
> RACE1 RACE2 RACE3 RACE4 RACE4 RACE6
> 1(1) / 1(5) / 1(7) / 1(10) / 1(13) / 1(14) - Input Bet 1
> 5(2) / 3(6) / 11(8) / 7(11) / 1(13) / 9(15) - Input Bet 2
> 7(3) / 3(6) / 11(8) / 7(11) / 1(13) / 9(15) - Input Bet 3
> 5(2) / 3(6) / 11(8) / 14(12) / 1(13) / 9(15) - Input Bet 4
> 7(3) / 3(6) / 11(8) / 14(12) / 1(13) / 9(15) - Input Bet 5
> 13(4) / 3(6) / 14(9) / 14(12) / 1(13) / 9(15) - Input Bet 6
>
> (Input Bet 1 obviously can't be grouped with any other bet. Input bets
> 2-6 can be grouped together. Input Bet 6 is a bit more tricky - it
> shares vertices 13 and 15 with four other bets, but does not have
> matching runners in Race 1 or Race 4 - hence cannot be grouped.)
>
> Working backwards, I need to be able to extract all the following
> information from whatever output is obtained after applying an an
> as-yet-unknown algorithm to the above input data:
>
> Bet Ticket 1 (Consists of only Input Bet 1)
> Runners: 1 / 1 / 1 / 1 / 1 / 1 =>
> Vertices: 1 / 5 / 7 / 10 / 13 / 14 =>
> V1:{1,5,7,10,13,14}
> E1:{{1,5},{5,7},{7,10},{10,13},{13,14}}
>
> Bet Ticket 2 (Consists of input bets 2-5 merged together)
> Runners: 5 + 7 / 3 / 11 / 7 + 14 / 1 / 9 =>
> Vertices: 2 + 3 / 6 / 8 / 11 + 12 / 13 / 15 =>
> V2:{2,3,6,8,11,12,13,15}
> E2:{{2,6},{3,6},{6,8},{8,11},{8,12},{11,13},{12,13},{13,15}}
>
> Bet Ticket 3 (Consists of only Input Bet 6)
> Runners: 13 / 3 / 14 / 14 / 1 / 9 =>
> Vertices: 4 / 6 / 9 / 12 / 13 / 15 =>
> V3:{4,6,9,12,13,15}
> E3:{{4,6},{6,9},{9,12},{12,13},{13,15}}
>
> OK, so these are complete multipartite graphs. I can grok this much.
>
> BUT, what are they a vertex cover of? Not to mention that I'm not sure
> how to represent my initial input. Assuming I read in a file of input
> data consisting of single ungrouped bets and (naively) attempted to
> represent them as a graph, what I would see would be this:
>
> V:{1..15}
> E:{
> #Input Bet 1# {1,5},{5,7},{7,10},{10,13},{13,14},
> #Input Bet 2# {2,6},{6,8},{8,11},{11,13},{13,15},
> #Input Bet 3# {3,6},{6,8},{8,11},{11,13},{13,15},
> #Input Bet 4# {2,6},{6,8},{8,12},{12,13},{13,15},
> #Input Bet 5# {3,6},{6,8},{8,12},{12,13},{13,15},
> #Input Bet 6# {4,6},{6,9},{9,12},{12,13},{13,15}
> }
>
> This representation has repeated edges between some vertices. So, I
> believe the correct term for this is a multigraph (without loops).
> Furthermore (even if I pruned repeated edges), it cannot be correct
> because there are now implied (but in reality non-existent) connections
> such 2-6-9-12-13-15 and 3-6-9-12-13-15... when in fact only
> 4-6-9-12-13-15 should exist. Similarly 4-6-8-11-13-14, etc. is/are
> spurious.
>
> So, I'm not totally convinced that I can represent all my single bet
> input data as vertices and edges because am going to get this problem
> of spurious implied connections.
>
> Perhaps my input data cannot be represented as *one* graph?
>
> Apologies for such a long post, but am I missing something very obvious
> about the way I should be modeling this data as a graph?
Sorry I didnt make myself clear. My modeling was different. Represent
each of the bet with one node in the graph. Then the problem is to
cover all the bets. Two nodes of the graph have an edge between them if
their (modified) hamming distance is 1 that is, the bets represented by
a node differ in only one race. Then the problem becomes one of finding
a vertex cover using certain kind of graphs. These graphs are not
complete multipartite graphs as I previously mentioned but product of
complete graphs (these are also known as Rook's Graph as I found out
today).
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
