Graf (matematika): Rozdiel medzi revíziami

Smazaný obsah Přidaný obsah
RibotBOT (diskusia | príspevky)
Riadok 28:
 
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ý
*otvorený
*triviálny
*netriviálny
*orientovaný
*neorientovaný
 
'''Ť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:
*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)
*nesúvislý - ak pre každé dva vrcholy u, v neexistuje cesta z u do v
(ak sa neviem z každého vrcholu dostať do každého)
*silne súvislý - ak z každého vrcholu existuje cesta do každého
*slabo súvislý - ak by bez orientácie bol súvislý
Toto je odkaz na obrázky a širší popis grafov [http://www.edi.fmph.uniba.sk/tmp/asset_cache/link/0000019445/pl08.pdf]
 
 
 
 
'''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.
 
=== Ďalšie typy grafov ===