De ce contează?
La un turneu de șah „fiecare cu fiecare", orice jucător joacă exact o partidă cu fiecare dintre ceilalți — fără remize, mereu un câștigător și un învins. Dacă tragi câte o săgeată de la învingător spre învins, obții o hartă a întregului turneu. Întrebarea cea mai naturală — „pot să-i așez pe toți într-un clasament în care fiecare l-a bătut, direct sau pe lanț, pe următorul?" — are mereu un răspuns „da". Acest tip de hartă se numește graf turneu.
Ce este
Un graf turneu este orientarea unui graf complet: pornești de la K_n,
în care toate perechile de noduri sunt legate, și dai un sens fiecărei
muchii. Rezultatul: între oricare două noduri u și v există exact un
arc — fie u→v, fie v→u, niciodată ambele și niciodată niciunul.
Numele vine direct din sport: fiecare nod e un jucător, fiecare arc e rezultatul
unei partide — u→v înseamnă „u l-a bătut pe v". Cum orice pereche joacă exact
o dată, fiecărei perechi îi corespunde fix un arc. De aici, două numere care nu
depind deloc de rezultate:
- numărul de arce este mereu
n·(n-1)/2— câte unul de pereche; - suma gradelor externe este tot
n·(n-1)/2— fiecare meci produce exact o victorie, deci adună exact 1 la totalul victoriilor. Gradul extern al unui nod e pur și simplu numărul lui de victorii.