|
Každý neorientovaný graf možno previesť na orientovaný graf, s tým istým počtom vrcholov a dvojnásobným počtom hrán.
'''Sled''' v grafe F je postupnosť, v ktorej sa striedajú vrcholy a hrany v0, v1, v2, ... vn.
uzavretý - je taký sled, v ktorom je prvý vrchol zhodný s posledným a podobne
otvorený - je taký ťah, v ktorom je prvý vrchol zhodný s posledným
triviálny - je sled, ktorý obsahuje len jediný vrchol a žiadnu hranu
netriviálny
orientovaný - je ľubovoľná striedavá postupnosť vrcholov a hrán v G tvare
neorientovaný - postupnosť vrcholov a hrán v0, e1, v1, e2,…eK, vK, , kým každá hrana je spojuje vrcholy vi-1a vi
'''Ťah''' je sled, v ktorom sú všetky hrany navzájom rôzne (vrcholy sa môžu opakovať).
'''Cesta''' je sled, v ktorom sú všetky vrcholy navzájom rôzne (=> aj všetky hrany).
'''Cyklus''' je netriviálny uzavretý ťah, v ktorom sú všetky vrcholy okrem prvého a posledného rôzne.
Dĺžka sledu, ťahu, cesty či cyklu je daná počtom hrán.
Definícia súvislosti grafu:
a) súvislý - ak pre každé dva vrcholy u, v existuje cesta z u do v (ak sa viem z každého vrcholu dostať do každého)
b) nesúvislý - ak pre každé dva vrcholy u, v neexistuje cesta z u do v (ak sa neviem dostať z každého vrcholu do každého)
c) silne súvislý - ak z každého vrcholu existuje cesta do každého
d) slabo súvislý – ak by bez orientácie bol súvislý (napr. z 1 sa nedostanem do 4, 5)
Príklad:
Dvaja hráči striedavo ťahajú figúrkou umiestnenou na hracej doske tvaru štvorca, ktorá
je rozdelená na 8 × 8 políčok. Hráč, ktorý je na ťahu, ťahá figúrkou F vždy o jedno pole, a to alebo nadol, alebo vľavo, alebo šikmo vľavo nadol (pokiaľ by tým nevyšiel z hracej dosky). Pôvodne je figúrka F v pravom hornom rohu, cieľom hráčov je dostať ju do ľavého dolného rohu. Vyhráva ten, komu sa to podarí. Kto vyhrá pri obojstranne bezchybnej hre a ako treba „bezchybne hrať“?
Riešenie:
Uvažujeme orientovaný graf, ktorého vrcholmi budú všetky možné pozície tejto hry v našom prípade je pozícia jednoznačne určená polohou figúrky na hracej doske. Vrcholy U, V spojíme orientovanou hranou vychádzajúcou z vrcholu U práve vtedy, keď hráč, ktorý je na ťahu, môže jediným svojím ťahom prejsť z pozície U do pozície V . Dôležitou vlastnosťou tohto orientovaného grafu je, že je acyklický, t. j. neexistuje v ňom trať začínajúca a končiaca v tom istom vrchole. Táto podmienka je ekvivalentná s tým, že hra nutne končí po konečnom počte ťahov. V grafe teda existuje vrchol, z ktorého nevychádza žiadna hrana.
Teraz postupne ohodnotíme vrcholy nášho grafu prívlastkom „vyhrávajúci“ alebo „prehrávajúci“ nasledovne:
Najprv ohodnotíme všetky vrcholy nultého rádu – v našom prípade vrchol A1 – ako prehrávajúci alebo vyhrávajúci podľa toho, či hráč, ktorý je na ťahu (a nemôže ťahať) podľa pravidiel hry vyhral alebo prehral. V našom prípade A1 je prehrávajúci vrchol, lebo keď je figúrka na A1 a sme na ťahu, to znamená, že súper ju tam dostal a vyhral. Ak máme už ohodnotené všetky vrcholy nultého až n- tého rádu, tak vrcholy rádu n + 1 ohodnotíme takto: Vrchol je vyhrávajúci práve vtedy, keď existuje
hrana, ktorá vychádza z neho do prehrávajúceho vrcholu (ak takáto hrana neexistuje, nazveme ho prehrávajúci).
=== Ďalšie typy grafov ===
| 