Toernooi (grafentheorie)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Een toernooi met vier deelnemers. Dit is een sterk toernooi.

Een toernooi of toernooigraaf in de grafentheorie is een complete graaf waarin men aan elke kant een richting toewijst, zodat het een gerichte graaf wordt.

De naam "toernooi" is afkomstig van de interpretatie van zo een graaf als het resultaat van een round-robin competitie waarin elke speler eenmaal tegen elke andere speler speelt, en waarin geen gelijke spelen mogelijk zijn. Een kant (ab) in zo een graaf stelt een wedstrijd voor en is gericht van de winnaar (a) naar de verliezer (b). Men zegt dan dat a b domineert en noteert dit als a \rightarrow b. De score van speler a is het aantal uitgaande kanten van a gericht naar andere spelers, oftewel het aantal spelers gedomineerd door a.

Toernooien zijn wellicht de best bestudeerde klasse van gerichte grafen.[1] Toernooigrafen zijn onder meer gebruikt bij de studie van de dominantierelaties bij dieren en van kiessystemen.

Formele definitie[bewerken]

Een toernooigraaf is een gerichte graaf (V,E), waarvoor geldt:

  • voor alle x,y \in V met x \not= y geldt (x,y) \in E of (y,x) \in E,
  • voor alle x,y \in V met x \not= y geldt (x,y) \not\in E of (y,x) \not\in E,
  • voor alle x \in V geldt (x,x) \not\in E.

Men kan een toernooi ook definiëren als een binaire relatie R op een verzameling E die irreflexief, antisymmetrisch en totaal is; dat wil zeggen dat voor elk paar (x, y) elementen uit E geldt: ofwel x = y, ofwel x\ R\ y, ofwel y\ R\ x.

Eigenschappen[bewerken]

Elke eindige toernooigraaf met n knopen bevat een oneven aantal Hamiltonpaden. Een Hamiltonpad is een gericht pad langs alle n knopen.

Dat elke toernooigraaf een Hamiltonpad bevat kan men bewijzen door inductie. n=2 is een triviaal geval. Stel dat de stelling waar is voor een waarde van n. Beschouw een toernooi T met n+1 knopen. Kies een knoop v_0 in T en beschouw een gericht pad v_1,v_2,\ldots,v_n in T\setminus \{v_0\}. Stel i \in \{0,\ldots,n\} de grootste index zodat voor elke j \leq i er een gerichte kant is van v_j naar v_0. Dan is

v_1,\ldots,v_i,v_0,v_{i+1},\ldots,v_n

een gericht pad met n+1 knopen oftewel een Hamiltonpad. Dit bewijs geeft meteen een algoritme voor het vinden van een Hamiltonpad, hoewel het niet het meest efficiënte algoritme is.

Sterk toernooi[bewerken]

Een toernooi is sterk of sterk verbonden (Engels: strongly connected) indien er tussen elk paar knopen x en y een pad bestaat dat begint in x en eindigt in y. Een stelling van Paul Camion uit 1959 stelt dat een toernooi sterk verbonden is als en slechts als het toernooi een Hamiltoncykel (een gesloten Hamiltonpad) bezit.

De knopen in een sterk toernooi zijn pancyclisch: elke knoop v van een sterk toernooi behoort tot een cykel (een gesloten pad) van lengte k voor  k = 3, 4 , \dots , n , met n \ge 3 het aantal knopen in de graaf.[2]

S(n), het aantal verschillende sterke toernooien met n knopen, met n = 3, 4, 5, 6, 7, 8, ... is 2, 24, 544, 22320, 1677488, 236522496, ...[3] (rij A054946 in OEIS)

Transitief toernooi[bewerken]

Een transitief toernooi met 8 deelnemers. v_a \rightarrow v_b als en slechts als a < b

Een toernooi waarvoor steeds geldt dat als a b domineert en b c domineert, dan ook a c domineert, is een transitief toernooi. Dit komt overeen met te zeggen dat de binaire relatie R transitief is. Deze relatie is dan meteen ook een totale orde.

Formeel wordt een transitief toernooi gedefinieerd als

Toernooi T = (V, E) is transitief als \forall (a,b, c) \in V^3, (a \rightarrow b \text{ en } b \rightarrow c) \Rightarrow a \rightarrow c

Elk transitief toernooi bevat exact één Hamiltonpad. Een transitief toernooi bevat geen cykels van lengte 3, het is zelfs acyclisch. Het is dus geen sterk toernooi.

De scores van de deelnemers aan een transitief toernooi, gerangschikt van klein naar groot, is de verzameling {0,1,2,...,n − 1}.

Paradoxaal toernooi[bewerken]

In een transitief toernooi is er een deelnemer die al zijn wedstrijden wint. In reële competities is dit echter vaak niet zo. Het voorbeeld met 4 deelnemers hierboven is bijvoorbeeld geen transitief toernooi. Een toernooi waarin elke speler minstens eenmaal verliest noemt men een 1-paradoxaal toernooi.

In het algemeen is toernooi T=(V, E) k-paradoxaal als voor elke deelverzameling S van k elementen uit V er een knoop v_0 in V \setminus S bestaat zo dat v_0 \rightarrow v voor alle knopen v in S.

Gelijkmatig toernooi[bewerken]

Een toernooi is gelijkmatig (Engels: regular) als elke knoop evenveel inkomende als uitgaande kanten heeft (dit zijn grafen met een Euleriaanse oriëntatie). Een gelijkmatig toernooi heeft per definitie een oneven aantal deelnemers (knopen), die alle dezelfde score hebben.

Het aantal verschillende gelijkmatige toernooien met 3, 5, 7, 9, 11... deelnemers is: 1, 1, 3, 15, 1223... rij A096368 in OEIS.

Alle gelijkmatige toernooien met hetzelfde aantal deelnemers hebben evenveel driehoeken en evenveel transitieve tripels. Een driehoek is een reeks van drie kanten (x,y), (y,z), (z,x) die een cykel vormen; een transitieve tripel bestaat uit drie kanten van de vorm (x,y), (y,z), (x,z).

Het aantal transitieve tripels in een gelijkmatig toernooi met n knopen is \frac {n(n-1)(n-3)}{8}.

Het aantal driehoeken is \frac{n(n^2-1)}{24}.[4]

Voorbeeld[bewerken]

7RegularTournament.png

Dit is een voorbeeld van een gelijkmatig toernooi met 7 deelnemers; elke knoop heeft drie in- en drie uitgaande kanten.

De 21 kanten zijn: AB, CA, DA, AE, AF, GA, BC, DB, BE, FB, BG, CD, CE, FC, GC, ED, DF, GD, EF, EG, FG.

De graaf heeft 14 driehoeken en 21 transitieve tripels.

De driehoeken zijn: AB-BC-CA, AB-BG-GA, AE-ED-DA, AE-EG-GA, AF-FC-CA, AF-FG-GA, BC-CD-DB, BE-ED-DB, BE-EF-FB, BG-GD-DB, CD-DF-FC, CE-EF-FC, CE-EG-GC, DF-FG-GD.

De transitieve tripels zijn: AB-BE-AE, CA-AE-CE, DA-AB-DB, DA-AF-DF, AE-EF-AF, AF-FB-AB, BC-CE-BE, BE-EG-BG, FB-BC-FC, FB-BG-FG, BG-GC-BC, CD-DA-CA, CE-ED-CD, GC-CA-GA, GC-CD-GD, ED-DF-EF, DF-FB-DB, GD-DA-GA, EF-FG-EG, EG-GD-ED, FG-GC-FC.

Reduceerbaar toernooi[bewerken]

Men noemt een toernooi reduceerbaar als de verzameling V van knopen kan gesplitst worden in twee disjuncte niet-lege verzamelingen S en T, die elk ook een toernooi zijn en waarbij elke knoop uit S elke knoop uit T domineert. Men schrijft dan  V = S + T waarbij  S \rightarrow T. Als dit niet mogelijk is, dan is het toernooi niet-reduceerbaar.

Een toernooi is niet-reduceerbaar als en slechts als het sterk verbonden is.

Een transitief toernooi is bijgevolg reduceerbaar. Het hierboven gegeven voorbeeld met 8 knopen kan men bijvoorbeeld splitsen in twee toernooien met respectievelijk de knopenverzamelingen {1,2,3} en {4,5,6,7,8}, of {1,2,3,4} en {5,6,7,8}, enzovoort.

Elk toernooi kan geschreven worden als de som van één of meerdere niet-reduceerbare toernooien.

Scoreverzamelingen en score-rijen[bewerken]

De score van een deelnemer aan een toernooi is het aantal door hem gewonnen wedstrijden. Dit is het aantal uitgaande kanten van een knoop in de toernooigraaf.

De scoreverzameling is de verzameling van het aantal uitgaande kanten van alle knopen. Het is eenvoudig om de scoreverzameling van een toernooi te bepalen, maar een toernooi construeren aan de hand van een gegeven scoreverzameling is een moeilijk probleem.

De score-rij of scorevector is de geordende rij van scores of aantal uitgaande kanten, gerangschikt van klein naar groot.

De stelling van Landau[5] zegt dat een rij (s_1, s_2, \cdots, s_n) van niet-negatieve gehele getallen een score-rij is als en slechts als:

  1. 0 \le s_1 \le s_2 \le \cdots \le s_n
  2. s_1 + s_2 + \cdots + s_i \ge C^2_i, \mbox{voor }i = 1, 2, \cdots, n - 1
  3. s_1 + s_2 + \cdots + s_n = C^2_n (dit is gelijk aan het totaal aantal kanten in de toernooigraaf).

Verschillende toernooien kunnen dezelfde score-rij hebben. Peter M. Gibson leidde in 1983 een uitdrukking af voor de bovengrens van het aantal toernooien met een gegeven score-rij (of scorevector).[6]

Het aantal mogelijke verschillende score-rijen van toernooien met n = 0, 1, 2, 3, ... deelnemers is (rij A000571 in OEIS) 1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ...

T.X. Yao[7] heeft bewezen dat elke willekeurige eindige verzameling van niet-negatieve gehele getallen de scoreverzameling van een zeker toernooi is. Kenneth Brooks Reid, Jr. had dit als een vermoeden geformuleerd in 1978 en bewezen voor verzamelingen van 1, 2 en 3 getallen.

Toernooimatrix[bewerken]

Een toernooi kan men ook voorstellen in matrixvorm. Een toernooimatrix is een matrix, waarin het element op rij i en kolom j 1 is als deelnemer i deelnemer j domineert (genoteerd als v_i \rightarrow v_j), en nul in de andere gevallen.

Een toernooimatrix is dus een vierkante Booleaanse n-bij-n-matrix [ai,j] waarvoor geldt:

a_{i,i} = 0  \mbox{ voor } i=1, 2, \cdots n
a_{i,j} + a_{j,i} = 1  \mbox{ voor } 1 \le i < j \le n

De toernooimatrix van het toernooi met vier deelnemers (in volgorde 1,2,3,4) hierboven is: 
\begin{bmatrix}
0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 
 \end{bmatrix}

De toernooimatrix van een transitief toernooi is, eventueel na verwisseling van kolommen en rijen wat neerkomt op het veranderen van de volgorde van de deelnemers, een bovendriehoeksmatrix. De score van deelnemer i is de som van rij i in de toernooimatrix.

Alternatieve notatie[bewerken]

Een andere manier om een toernooi in matrixvorm voor te stellen is de elementen a_{ij} de volgende waarden te geven:

1 indien v_i \rightarrow v_j
-1 indien v_j \rightarrow v_i
0 indien i = j.

Een dergelijke matrix  A is antisymmetrisch: de getransponeerde matrix van A is gelijk aan het tegengestelde van A:

A^T = -A

De toernooimatrix van het toernooi met vier deelnemers (1,2,3,4) hierboven wordt in deze notatie: 
\begin{bmatrix}
0 & 1 & -1 & 1 \\
-1 & 0 & -1 & 1 \\
1 & 1 & 0 & -1 \\
-1 & -1 & 1 & 0 
 \end{bmatrix}

Externe links[bewerken]

Bronnen, noten en/of referenties
  1. Jǿrgen Bang-Jensen, Gregory Gutin. "Generalizations of Tournaments: A Survey." Journal of Graph Theory, 1998, Vol. 28 nr. 4, p. 171 DOI:10.1002/(SICI)1097-0118(199808)28:4<171::AID-JGT1>3.0.CO;2-G
  2. J.M. Moon: "On subtournaments of a tournament". Canad. Math. Bull. (1966), vol. 9 nr. 3, blz. 297
  3. Denis Hanson, John W. Moon. "Weakening Arcs in Tournaments." Journal of Graph Theory, 2003, vol. 45 nr. 2, blz. 142 DOI:10.1002/jgt.10148
  4. Raphael Yuster. "Packing Triangles in Regular Tournaments." Journal of Graph Theory (2013), vol. 74 nr. 1, blz. 58-66. DOI:10.1002/jgt.21691
  5. H. G. Landau, "On dominance relations and the structure of animal societies. III. The condition for a score structure", Bulletin of Mathematical Biophysics, vol. 15, no 2, 1953, p. 143–148. DOI:10.1007/BF02476378
  6. Peter M. Gibson. "A bound for the number of tournaments with specified scores." Journal of Combinatorial Theory, Series B (1984), Vol. 36, blz. 240-243. DOI:10.1016/0095-8956(84)90030-3
  7. T. X. Yao, "On Reid Conjecture Of Score Sets For Tournaments", Chinese Sci. Bull., vol. 34, 1989, p. 804−808