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 ${\displaystyle 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.^[1]

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