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. 

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 . 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 , waarvoor geldt:
  heeft minimaal twee elementen  en ,
 voor alle  met  geldt  of ,
 voor alle  met  geldt  of ,
 voor alle  geldt .

Men kan een toernooi ook definiëren als een tweeplaatsige relatie  op een verzameling  die irreflexief, antisymmetrisch en totaal is. Dat wil zeggen dat voor elk paar  elementen uit  geldt: ofwel , ofwel , ofwel .

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

Dat betekent dat er in elke toernooigraaf ten minste één Hamiltonpad voorkomt. Dit laatste kan met volledige inductie naar het aantal knopen  van de toernooigraaf worden bewezen.
 Het inductiebegin, voor het geval , wijst zich vanzelf.  heeft of gewonnen of verloren van , het Hamiltonpad wijst van de winnaar naar de verliezer.
 De inductieveronderstelling is dat de stelling waar is voor een toernooigraaf met  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  met  knopen. Kies een knoop  in  en beschouw een gericht pad  in . Stel  de grootste index zodat voor elke  er een gerichte kant is van  naar .
 Als , dan is  een Hamiltonpad van .
 Als , dan is  een Hamiltonpad van .
 Het feit dat er een gerichte kant van  naar  gaat volgt uit het feit dat  de grootste index is zodat er voor elke  een kant van  naar  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  van een sterk toernooi behoort tot een cykel, een gesloten pad, van lengte  voor , met  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, ... , .

Transitief toernooi 

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  is transitief als

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  in  zijn, zo dat  .

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... .

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 . Het aantal driehoeken is .

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 . 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  van niet-negatieve gehele getallen een score-rij is dan en slechts dan als:
 
 
 

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, , 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 
 -1 wanneer 
 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:

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:

Externe link 
  

Grafentheorie
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 . 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 \ . 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 , waarvoor geldt : heeft minimaal twee elementen en , voor alle met geldt of , voor alle met geldt of , voor alle geldt\ . Men kan een toernooi ook definiëren als een tweeplaatsige relatie op een verzameling die irreflexief , antisymmetrisch en totaal is . Dat wil zeggen dat voor elk paar elementen uit geldt : ofwel , ofwel , ofwel\ . Eigenschappen Elke eindige toernooigraaf met knopen bevat een oneven aantal Hamiltonpaden . Een Hamiltonpad is een gericht pad langs alle knopen . Dat betekent dat er in elke toernooigraaf ten minste één Hamiltonpad voorkomt . Dit laatste kan met volledige inductie naar het aantal knopen van de toernooigraaf worden bewezen . Het inductiebegin , voor het geval , wijst zich vanzelf . heeft of gewonnen of verloren van , het Hamiltonpad wijst van de winnaar naar de verliezer . De inductieveronderstelling is dat de stelling waar is voor een toernooigraaf met 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 met knopen . Kies een knoop in en beschouw een gericht pad in \ . Stel de grootste index zodat voor elke er een gerichte kant is van naar \ . Als , dan is een Hamiltonpad van \ . Als , dan is een Hamiltonpad van \ . Het feit dat er een gerichte kant van naar gaat volgt uit het feit dat de grootste index is zodat er voor elke een kant van naar 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 uitstelt 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 van een sterk toernooi behoort tot een cykel , een gesloten pad , van lengte voor , met het aantal knopen in de graaf . S(n ) , het aantal verschillende sterke toernooien met n knopen , met n =\... is\...,\. Transitief toernooi 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 is transitief als 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 − . 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 metdeelnemers hierboven is bijvoorbeeld geen transitief toernooi . Een toernooi waarin elke speler minstens eenmaal verliest noemt men eenparadoxaal 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 in zijn , zo dat \ . 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 .. deelnemers is : ..\. 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 \ . Het aantal driehoeken is \. Voorbeeld Dit is een voorbeeld van een gelijkmatig toernooi metdeelnemers , elke knoop heeft drie in- en drie uitgaande kanten . Er zijnkanten , dat zijn de pijlen in de graaf,driehoeken , bijvoorbeeld AF-FC-CA , entransitieve 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 \ . 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 metknopen 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 van niet-negatieve gehele getallen een score-rij is dan en slechts dan als : is gelijk aan het totaal aantal kanten in de toernooigraaf . Verschillende toernooien kunnen dezelfde score-rij hebben . Peter M. Gibson leidde ineen 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 =\... deelnemers is ,, \... 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 ingeformuleerd . Toernooimatrix De resultaten van een toernooi kunnen ook met een matrix worden weergegeven : wanneer wanneer wanneer het resultaat tussen i en j nog niet bekend is en wanneer i=j . De elementen op de diagonaal blijven Een dergelijke matrix A is een antisymmetrische matrix : de getransponeerde matrix van A is gelijk aan het tegengestelde van 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 : Externe link Grafentheorie