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?
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
