Toernooigraaf

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

Een sterk toernooi met vier deelnemers.

De naam "toernooigraaf" is afkomstig van de interpretatie van zo een graaf als het resultaat van competitievorm, 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 keer dat a heeft gewonnen, oftewel het aantal uitgaande kanten van a gericht naar andere spelers, oftewel het aantal andere spelers dat a domineert.

Toernooien zijn wellicht de best bestudeerde klasse van gerichte grafen.

Formele definitie

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

• $V$ heeft minimaal twee elementen $x$ en $y$,
• 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 tweeplaatsige 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

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

Dat betekent dat er in elke toernooigraaf ten minste één Hamiltonpad voorkomt. Dit laatste kan met volledige inductie naar het aantal knopen $n$ van de toernooigraaf worden bewezen.

• Het inductiebegin, voor het geval $n=2$, wijst zich vanzelf. $x$ heeft of gewonnen of verloren van $y$, het Hamiltonpad wijst van de winnaar naar de verliezer.
• De inductieveronderstelling is dat de stelling waar is voor een toernooigraaf met $n$ knopen.
• De inductiestap gaat als volgt. Veronderstel dat in een toernooi alle wedstrijden zijn gespeeld en er in de toernooigraaf een Hamilton-pad is. Dat is gegeven. Wanneer een nieuwe speler een keer tegen alle eerdere spelers speelt, krijgt deze nieuwe speler zijn plaats tussen het Hamilton-pad van de andere, de eerste spelers.

Beschouw de toernooigraaf $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}$.

Als $i=n$, dan is $v_{1},v_{2},\ldots ,v_{n},v_{0}$ een Hamiltonpad van $T$.

Als $i<n$, dan is $v_{1},\ldots ,v_{i},v_{0},v_{i+1},\ldots ,v_{n}$ een Hamiltonpad van $T$.

Het feit dat er een gerichte kant van $v_{0}$ naar $v_{i+1}$ gaat volgt uit het feit dat $i$ de grootste index is zodat er voor elke $j\leq i$ een kant van $v_{j}$ naar $v_{0}$ gaat.

Sterk toernooi

Een toernooi is sterk of sterk verbonden 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 dan en slechts dan als het toernooi een Hamiltoncykel, een gesloten Hamiltonpad, bezit. Wanneer a van b wint en b van c wint, is het in een sterk toernooi niet zeker dat a ook van c wint. Met maar drie spelers is het juist alleen een sterk toernooi, wanneer c van a wint.

De knopen in een sterk toernooi heten pancyclisch: iedere knoop $v$ van een sterk toernooi behoort tot een cykel, een gesloten pad, van lengte $k$ voor $k=3,4,\dots ,n$, met $n\geq 3$ het aantal knopen in de graaf.

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, ... , rij A054946 in OEIS.

Transitief toernooi

Een transitief toernooi met 8 deelnemers. $v_{a}\rightarrow v_{b}\Leftrightarrow a<b$

Een toernooi waarvoor steeds geldt dat als a van b wint en b van c wint, a ook van c wint, is een transitief toernooi. In het toernooi heerst een totale orde. De figuur hiernaast is een voorbeeld van een transitief toernooi.

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$

In een transitief toernooi komt precies één Hamiltonpad voor. Een transitief toernooi bevat geen cykels. Het is het tegenovergestelde van een 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

In een transitief toernooi is er een deelnemer die al zijn wedstrijden wint. In echte competities komt dit maar weinig voor. Het voorbeeld in de figuur 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 een toernooi k-paradoxaal als voor elke deelverzameling S met k elementen uit V er voor alle knopen v in S er k andere knopen $v_{i}$ in $V\setminus S$ zijn, zo dat $v_{i}\rightarrow v$ .

Gelijkmatig toernooi

Een toernooi is gelijkmatig 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 of 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}}$.

Voorbeeld

Dit is een voorbeeld van een gelijkmatig toernooi met 7 deelnemers, elke knoop heeft drie in- en drie uitgaande kanten. Er zijn 21 kanten, dat zijn de pijlen in de graaf, 14 driehoeken, bijvoorbeeld AF-FC-CA, en 21 transitieve tripels, bijvoorbeeld CE-ED-CD.

Reduceerbaar toernooi

Men noemt een toernooi reduceerbaar als de verzameling V van knopen kan worden gesplitst in twee disjuncte toernooigrafen S en T, waarbij iedere knoop uit S iedere knoop uit T domineert. V = S + T, met $S\rightarrow T$. Als dit niet mogelijk is, dan is het toernooi niet-reduceerbaar.

Een toernooi is niet-reduceerbaar dan en slechts dan als het sterk is verbonden. Een transitief toernooi is 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. Ieder toernooi kan worden geschreven als de som van één of meer niet-reduceerbare toernooien. De deelnemers zijn dan te verdelen in groepen spelers, die ongeveer even goed zijn. Tussen de verschillende groepen spelers zijn wel duidelijke verschillen.

Scoreverzamelingen en score-rijen

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 zegt dat een rij $s_{1},s_{2},\cdots ,s_{n}$ van niet-negatieve gehele getallen een score-rij is dan en slechts dan als:

1. $0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}$
2. $s_{1}+s_{2}+\cdots +s_{i}\geq C_{i}^{2},{\mbox{voor }}i=1,2,\cdots ,n-1$
3. $s_{1}+s_{2}+\cdots +s_{n}=C_{n}^{2}$

$C_{n}^{2}$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.

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 heeft bewezen dat elke willekeurige eindige verzameling van niet-negatieve gehele getallen de scoreverzameling van een zeker toernooi is. K.B. Reid had dit als een vermoeden in 1978 geformuleerd.

Toernooimatrix

De resultaten van een toernooi kunnen ook met een matrix worden weergegeven:

1 wanneer $v_{i}\rightarrow v_{j}$

-1 wanneer $v_{j}\rightarrow v_{i}$

0 wanneer het resultaat tussen i en j nog niet bekend is en wanneer i=j.

De elementen op de diagonaal blijven 0.

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

$A^{T}=-A$

De definitie van een toernooi is zo gekozen, dat het volledig is gespeeld. De toernooimatrix van het toernooi met vier deelnemers in de figuur boven, wordt:

${\begin{bmatrix}0&1&-1&1\\-1&0&-1&1\\1&1&0&-1\\-1&-1&1&0\end{bmatrix}}$

Externe link

• (en) Mathworld, Tournament.

Bronnen, noten en/of referenties