Turnir (teorija grafov)
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 .

Poti in cikli 

Vsak turnir na končnem številu  točk vsebuje Hamiltonovo pot, kar pomeni, da je usmerjen na vseh  točkah. To se lahko preprosto pokaže z indukcijo na : predpostavimo, da izjava velja za , in upoštevajmo turnir  na  točkah. Izberimo točko  iz  in obravnavajmo usmerjeno pot  v . Naj je sedaj  največji, da bo za vsak  obstajala usmerjena povezava iz  v . Potem je:

  

želena usmerjena pot. Takšno razmišljanje da tudi algoritem za iskanje Hamiltonove poti. Znani so učinkovitejši algoritmi, ki zahtevajo pregledovanje le  točk..

To nakazuje, da ima krepko povezani turnir Hamiltonov cikel. Velja še naprej, da je vsak krepko povezani turnir točkovno pancikličen: za vsako točko v in za vsak k v območju od tri do števila točk v turnirju obstaja cikel dolžine k, ki vsebuje točko containing v. Če je turnir 4‑povezan, se lahko vsak par točk poveže s Hamiltonovo potjo.

Opombe in sklici

Viri 

 
 
 
 
 
 

Usmerjeni grafi
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 \ . Poti in cikli Vsak turnir na končnem številu točk vsebuje Hamiltonovo pot , kar pomeni , da je usmerjen na vseh točkah . To se lahko preprosto pokaže z indukcijo na \ : predpostavimo , da izjava velja za , in upoštevajmo turnir na točkah . Izberimo točko iz in obravnavajmo usmerjeno pot v \ . Naj je sedaj največji , da bo za vsak obstajala usmerjena povezava iz v \ . Potem je : želena usmerjena pot . Takšno razmišljanje da tudi algoritem za iskanje Hamiltonove poti . Znani so učinkovitejši algoritmi , ki zahtevajo pregledovanje le točk . . To nakazuje , da ima krepko povezani turnir Hamiltonov cikel . Velja še naprej , da je vsak krepko povezani turnir točkovno pancikličen : za vsako točko v in za vsak k v območju od tri do števila točk v turnirju obstaja cikel dolžine k , ki vsebuje točko containing v. Če je turnirpovezan , se lahko vsak par točk poveže s Hamiltonovo potjo . Opombe in sklici Viri Usmerjeni grafi