© h.hofstede (h.hofstede@hogeland.nl)

Wie is de winnaar?
       
Als voorkennis voor deze les moet je een vorige les over verbindingsmatrices en meerstapsverbindingen hebben bestudeerd.
Vanaf noemen we V de verbindingsmatrix van een graaf.
We bekijken hier alleen toernooien en dan ook nog eens verbonden toernooien  (dus toernooien waarin elk punt vanuit elk ander punt is te bereiken.
De diameter  d  van een graaf is de afstand tussen de twee verst van elkaar gelegen punten in de graaf  (afstand = minimale aantal verbindingslijnen dat je moet passeren om van de één bij de ander te komen). Een verbonden toernooi heeft dus altijd een eindige diameter  (immers alles is vanaf alles te bereiken).

Stelling 1.

Als D een verbonden toernooi is met minstens 5 knooppunten,
dan heeft Vd+3  geen nullen. 

       
Simpeler gezegd: "Tussen elk paar knopen bestaat een wandeling van lengte precies d + 3"

Bewijs.
Houd daarbij stelling 4 uit deze les in gedachten. Die luidde:
"als D een verbonden toernooi is met n knooppunten  (n ≥ 3), 
dan is elk knooppunt van D deel van een  3-cykel, een 4-cykel,  .... , een  n-cykel"

Stel de lengte van het kortste pad P tussen Ki en Kj  gelijk aan dij.
Dan is  0 < dij  < d < K - 1  dat is nogal logisch  (het kortste pad is kleiner dan het langste, en het langste pad kan niet meer knopen bevatten dan er zijn, dûh).

0 < dij  < d < K - 1
Daaruit volgt   0 < d - dij < K - 1
Tel nu overal 3 bij op:   3 < d - dij + 3 < K + 2
Dat splitsen we in drie gevallen:

  1. d - dij + 3 = K + 2
Daaruit volgt  d + 3 = K + 2 + dij
Volg nu pad P  (lengte dij)  gevolgd door een (K-1)-cykel door Kj  (die bestaat volgens stelling 4)  en daarna nog gevolgd door een  3-cykel  door Kj.
Samen geeft dat een wandeling van lengte  dij + K - 1 + 3 =  K + 2 + dij = d  + 3
  2. d - dij + 3 = K + 1
Daaruit volgt  d + 3 = K + 1 + dij
Volg nu pad P  (lengte dij) gevolgd door een  (K-2)-cykel door Kj  en daarna weer een 3-cykel. Ook dat levert samen weer een pad van lengte d + 3 op.
  3. d - dij + 3 £ K
Volg nu pad P  gevolgd door een  (d - dij + 3)-cykel door Kj  (die bestaat want dat is £ K).
Dat levert direct een pad van lengte d + 3 op.
 
Samengevat:  "met pad P plus een geschikt aantal cykels kun  je altijd op lengte d + 3 uitkomen"
■      
       
Stelling 2.

D is verbonden en  K ≥  4      ⇔    er is een Vn  zonder nullen   

       
Bewijs.
Omdat de stelling twee kanten opgaat, zijn er ook eigenlijk twee bewijzen nodig.
  ⇒ Als D verbonden is, dan is er voor K ≥ 5 volgens stelling 1 altijd een  Vd+ 3 zonder nullen.
Blijft over de gevallen  K = 3 en K = 4.
Maar er is maar één K = 3 verbonden toernooi, en ook maar één K = 4 verbonden toernooi (op isomorfe gevallen na natuurlijk). Dat zijn de volgende twee:
       
   

       
    Van de eerste  heeft geen enkele Vn geen nullen meer.
Van de tweede heeft  V9  geen nullen meer  (ga dat zelf maar na; elk punt is in 9 stappen vanaf elk ander punt te bereiken)
Dus de stelling geldt voor K ≥ 4 
       
  ⇐ Makkie:  Als D niet verbonden is, dan zijn er knooppunten Ki en Kj te vinden  zodat Kj niet bereikbaar is vanaf Ki.  Dat betekent dat het element Vnij  van Vn  altijd gelijk is aan nul, immers dat element geeft het aantal
n-staps routes van Ki naar Kj aan, en die zijn er nooit.
(verder weten we de K = 3 en K = 4 gevallen hierboven al)
■      
       
Oké, allemaal best, maar wat heeft dit te maken met de winnaar van een toernooi?

Bekijk het volgende toernooi met 5 spelers, met de digraaf D die aangeeft wie van wie heeft gewonnen:
       

       
Als we alleen kijken hoeveel wedstrijden iedere speler heeft gewonnen en dat als score s gebruiken, dan krijgen we
s = (3, 3, 1, 2, 1).  Merk nog even op dat je s als kolom kunt krijgen door V met de kolom vectoren met allemaal enen te vermenigvuldigen.
       

       
Vanwege de scores zou ik voorlopig zeggen dat 1 en 2 gelijk bovenaan zijn geëindigd, 4 is op de derde plaats geëindigd en 3 en 5 zijn gedeeld laatste.

Je kunt natuurlijk als verfijning ook gaan kijken van WIE de teams hebben gewonnen.  Immers, als je van een hooggeplaatst team wint dan zou dat zwaarder mee moeten tellen dan als je van een laaggeplaatst team wint. Je zou kunnen tellen hoeveel een team INDIRECT  ("via-via") heeft gewonnen door te kijken hoeveel winstpartijen de teams die door ze verslagen zijn hebben.
Team 1 heeft bijvoorbeeld gewonnen van 3, 4, en 5, maar die hebben respectievelijk 1, 2 en 1 eigen winstpartijen, dus je zou kunnen zeggen dat team 1 indirect van  1 + 2 + 1 = 4 anderen heeft gewonnen.
Ik hoop dat je ziet dat we hier de tweestapsverbindingen aan het tellen zijn, en die geven we dan ook aan met s2 en berekenen we via V2: 
       

       
Je ziet dat team 2 de meeste indirecte overwinningen heeft gehaald.
We zouden nu door kunnen gaan door de driestapsverbindingen  s3 en de vierstaps  s4, enz. te berekenen.
Dat geeft de volgende rij scorevectoren:
       

       
Om iets duidelijker te maken wat er nou gebeurt vervang ik alle kentallen van de s-vectoren door hun relatieve grootte (dus percentage van het totaal). Dat geeft:
       

       
De interessante vraag is dan natuurlijk:  gaan die percentages naar een constante waarde toe? Dan zouden we dat als "DE" uitkomst van het toernooi kunnen gebruiken.
Het antwoord is "JA",  maar daar hebben we wel een stukje matrix-algebra voor nodig.

Perron en Frobenius ontdekten/bewezen (net na 1900) dat voor een matrix V met alleen maar positieve getallen geldt dat het gedrag van Vn  voor n naar oneindig wordt bepaald door de grootste eigenwaarde van V.  Ze noemden die eigenwaarde r  en toonden aan dat  (V/r)n  vermenigvuldigd met de kolomvector met enen dan convergeert naar een vector S, die een eigenvector van de matrix V is.

Hebben we zo'n matrix V met alleen maar positieve getallen?

Jazeker:  Dat zegt stelling 2  (Héhé, hebben we die tenminste niet voor niks afgeleid J)
 
Kortom:  er bestaat zo'n vector s¥,  en die kunnen we mooi als de uitkomst van het toernooi nemen.
Ik heb voor de grap met mijn GR nog even de 100-stapsverbindingen berekend  (dus via V100)  en dat gaf de vector s hiernaast.

We kunnen daaruit concluderen dat de toernooivolgorde is:   2 - 1 - 4 - 5 - 3
       
Maar ja,   niet alle toernooien zijn verbonden...
       
Als een toernooi niet verbonden is, dan krijg je niet zo'n matrix zonder nullen (immers elk punt is niet vanuit elk ander punt te bereiken) en dan is het dus ook onduidelijk of er wel zo'n scorevector s is waar de zaak naar toe loopt.

Gelukkig is de situatie in zo'n geval erg simpel....
Laten we de graaf splitsen in deelgrafen (D1, D2, ....) die elk apart wél verbonden zijn (ze kunnen zelfs uit één knooppunt bestaan).
Dan ziet dat er bijvoorbeeld zó uit:
       

       
Maar tussen die deelverzamelingen moeten ook verbindingslijnen lopen (het is immers een toernooi: iedereen heeft tegen iedereen gespeeld). En nou komt het:  de verbindingslijnen tussen twee van die gebieden kunnen maar één kant op zijn.  Ze gaan allemaal van het ene naar het andere gebied, nooit terug. Als dat immers wel zo was, dan waren al die knooppunten wél verbonden.  Dat zou er zó uit kunnen zien:
       

       
Een rode verbindingslijn tussen twee gebieden betekent dat ALLE verbindingslijnen van het ene naar het andere gebied die kant op lopen.
Maar dat betekent dat er een duidelijke hiërarchie in de gebieden aan te wijzen is. In het voorbeeld heeft alles van A gewonnen van C,  alles van A gewonnen van B, en alles van B gewonnen van C
De volgorde is daarom  A ⇒  B  ⇒  C

Dus we maken van de gebieden A, B en C apart de ranglijst op (zoals hierboven, en zetten die ranglijsten dan gewoon onder elkaar!!
       

© h.hofstede (h.hofstede@hogeland.nl)