![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/8/89/4-tournament.svg/langsl-640px-4-tournament.svg.png&w=640&q=50)
Turnir (teorija grafov)
From Wikipedia, the free encyclopedia
Turnír je v teoriji grafov usmerjeni graf (digraf) tvorjen z določitvijo smeri vsake povezave v neusmerjenem polnem grafu. To pomeni, da je usmerjeni graf, v katerem je vsak par njegovih točk povezan z eno usmerjeno povezavo.
Mnogo pomembnih značilnosti turnirjev je prvi raziskoval Landau med modeliranjem relacije nadvlade pri jati kokoši. Trenutne uporabe turnirjev med drugim vključujejo raziskovanje teorije glasovanja in teorije družbene izbire. Ime turnir izhaja iz takšne predstavitve grafov kot izida krožnega sistema v katerem vsak igralec igra z drugim igralcem točno enkrat, in v katerem ni žrebanja. V usmerjenem grafu turnirja točke odgovarjajo igralcem. Povezava med vsakim parom igralcev je usmerjena od zmagovalca k poražencu. Če igralec premaga igralca
, potem rečemo, da
prevladuje nad
.