Teória grafov - História úprav

Defluo na 13:45, 7. september 2010

2010-09-07T13:45:30Z

Defluo na 13:27, 7. september 2010

2010-09-07T13:27:02Z

Defluo na 11:54, 28. január 2010

2010-01-28T11:54:01Z

Defluo na 11:51, 28. január 2010

2010-01-28T11:51:42Z

Defluo na 11:45, 28. január 2010

2010-01-28T11:45:30Z

Defluo: /* Rozhodovacie stromy */

2010-01-28T11:42:48Z

Rozhodovacie stromy

Defluo: /* Sieť toku */

2010-01-28T11:37:12Z

Sieť toku

Defluo na 11:33, 28. január 2010

2010-01-28T11:33:51Z

Defluo na 11:23, 28. január 2010

2010-01-28T11:23:35Z

Defluo na 11:12, 28. január 2010

2010-01-28T11:12:50Z

← Staršia verzia		Verzia zo dňa a času 13:45, 7. september 2010
Riadok 25:		Riadok 25:

	__TOC__		__TOC__
−
	=Teória grafov=		=Teória grafov=

@@ Riadok 43: / Riadok 43: @@
 K tomu, aby bol zadaný [http://en.wikipedia.org/wiki/Graph_(mathematics) graf] (označíme ho ''φ'') je treba, aby boli dané dve množiny: množina '''vrcholov''' ''V'' (predtým zmieňované body v grafe) a množina '''hrán''' ''H'' (zmienené čiary). Vo väčšine prípadov sú obe množiny konečné, avšak nie je to nutná podmienka existencie grafu.  Graf potom zapisujeme ako ''φ=VH'', prípadne ''φ=(V,H)''.
-Ku každej hrane musia patriť dva vrcholy, ktoré sú touto hranou spojené a nazývajú sa '''krajné vrcholy hrany'''. Hovoríme aj, že krajné vrcholy '''ležia''' na spoločnej hrane. Vrcholy sa nazývajú '''susednými''' ak existuje taká hrana, na ktorej oba vrcholy ležia. Môže však existovať aj vrchol, ktorý nepatrí k žiadnej hrane. V takomto prípade hovoríme o '''izolovanom vrchole'''. K tomu, aby z množín vrcholov a uzlov mohol vzniknúť graf je ďalej potrebné poznať pravidlo, na základe ktorého vieme určiť, ktoré dvojice vrcholov majú byť spojené hranou. Jednotlivé hrany môžu tiež určovať smer vzájomnej interakcie krajných vrcholov. Vtedy hovoríme o '''orientovanej hrane''' a označujeme ju šípkou. Graf, ktorý obsahuje len orientované hrany sa nazýva '''orientovaný graf'''. Ak sú v grafe orientované aj neorientované hrany, ide o '''zmiešaný graf'''. Krajné vrcholy pri orientovaných hranách sú potom nazvané '''počiatočný''' a '''koncový vrchol''' hrany. '''Slučku''' v grafe tvorí hrana, ktorej krajné vrcholy splývajú (sú tvorené jedným vrcholom). '''Priľahlé hrany''' sú také, ktoré majú aspoň jeden spoločný krajný vrchol. Dve navzájom rôzne hrany, ktoré majú rovnaké krajné vrcholy sa v neorientovanom grafe nazývajú '''rovnobežné'''. V orientovanom grafe potom takéto hrany rozlišujeme podľa orientácie na '''súhlasne rovnobežné''' a '''nesúhlasne rovnobežné'''. Neorientovaný graf je '''jednoduchý''' ak v ňom neexistujú žiadne rovnobežné hrany [26].
+Ku každej hrane musia patriť dva vrcholy, ktoré sú touto hranou spojené a nazývajú sa '''krajné vrcholy hrany'''. Hovoríme aj, že krajné vrcholy '''ležia''' na spoločnej hrane. Vrcholy sa nazývajú '''susednými''' ak existuje taká hrana, na ktorej oba vrcholy ležia. Môže však existovať aj vrchol, ktorý nepatrí k žiadnej hrane. V takomto prípade hovoríme o '''izolovanom vrchole'''. K tomu, aby z množín vrcholov a uzlov mohol vzniknúť graf je ďalej potrebné poznať pravidlo, na základe ktorého vieme určiť, ktoré dvojice vrcholov majú byť spojené hranou. Jednotlivé hrany môžu tiež určovať smer vzájomnej interakcie krajných vrcholov. Vtedy hovoríme o '''orientovanej hrane''' a označujeme ju šípkou. Graf, ktorý obsahuje len orientované hrany sa nazýva '''orientovaný graf'''. Ak sú v grafe orientované aj neorientované hrany, ide o '''zmiešaný graf'''. Krajné vrcholy pri orientovaných hranách sú potom nazvané '''počiatočný''' a '''koncový vrchol''' hrany. '''Slučku''' v grafe tvorí hrana, ktorej krajné vrcholy splývajú (sú tvorené jedným vrcholom). '''Priľahlé hrany''' sú také, ktoré majú aspoň jeden spoločný krajný vrchol. Dve navzájom rôzne hrany, ktoré majú rovnaké krajné vrcholy sa v neorientovanom grafe nazývajú '''rovnobežné'''. V orientovanom grafe potom takéto hrany rozlišujeme podľa orientácie na '''súhlasne rovnobežné''' a '''nesúhlasne rovnobežné'''. Neorientovaný graf je '''jednoduchý''' ak v ňom neexistujú žiadne rovnobežné hrany.<ref name="necas_jiri">Nečas, Jiří. Grafy a jejich použití. Praha : SNTL, 1978.</ref>
 ==Základné druhy grafových štruktúr==
@@ Riadok 54: / Riadok 54: @@
 '''Digraf''' (z angl. digraph = directed graph, v prekl. orientovaný graf) neobsahuje neorientované hrany, slučky a násobné hrany (rôzne orientované rovnobežné hrany obsahovať môže). '''Multidigraf''' neobsahuje neorientované hrany a slučky. '''Pseudodigraf''' neobsahuje len neorientované hrany.
-'''Migraf''' (z angl. mixed graph, v prekl. zmiešaný graf) neobsahuje násobné hrany a slučky. '''Multimigraf''' neobsahuje slučky. '''Pseudomigraf''' môže obsahovať všetky druhy hrán  [27].
+'''Migraf''' (z angl. mixed graph, v prekl. zmiešaný graf) neobsahuje násobné hrany a slučky. '''Multimigraf''' neobsahuje slučky. '''Pseudomigraf''' môže obsahovať všetky druhy hrán.<ref name="plesnik_jan">Plesník, Ján. Grafové algoritmy. Bratislava : VEDA, 1983.</ref>
 Každý z týchto typov grafových štruktúr môže mať k prvkom svojej štruktúry priradenú určitú hodnotu (váhu), ktorá reprezentuje výhodnosť prechodu daným prvkom. Takýto graf potom nazývame '''ohodnotený''' alebo '''vážený graf'''. Rozoznávame '''hranovo ohodnotený graf''' a '''vrcholovo ohodnotený graf'''. Ohodnotené hrany môžu napr. reprezentovať vzdialenosti medzi miestami, ktoré predstavujú jednotlivé vrcholy. Ohodnotené môžu byť hrany aj vrcholy zároveň a to aj viacerými hodnotami, kde každá hodnota predstavuje inú veličinu (napr. vzdialenosť, čas, cenu, atď). Pomocou takto ohodnotených grafov sa dá reprezentovať a riešiť množstvo praktických problémov, z ktorých najvýznamnejšie sú rozpísané v nasledujúcej kapitole.
@@ Riadok 74: / Riadok 74: @@
 ===Farbenie grafov===
-Farbenie grafov je špeciálnym prípadom označovania prvkov grafov. Rozlišujú sa tri druhy farbenia grafov. Pri '''farbení vrcholov''' sa vrcholy značia takou farbou, aby žiadne dva vrcholy spojené spoločnou hranou nemali rovnakú farbu. Pri '''farbení hrán''' nesmú mať rovnakú farbu zase hrany, ktoré spájajú rovnaký vrchol. Poslednou možnosťou je '''farbenie plôch''', ktorých hranice sú v planárnom grafe určené hranami. [http://sk.wikipedia.org/wiki/Plan%C3%A1rny_graf Planárny (rovinný) graf] je taký, kde sa nepretínajú žiadne hrany. Oba problémy farbenia hrán a plôch môžu byť prevedené na farbenie vrcholov [13].
+Farbenie grafov je špeciálnym prípadom označovania prvkov grafov. Rozlišujú sa tri druhy farbenia grafov. Pri '''farbení vrcholov''' sa vrcholy značia takou farbou, aby žiadne dva vrcholy spojené spoločnou hranou nemali rovnakú farbu. Pri '''farbení hrán''' nesmú mať rovnakú farbu zase hrany, ktoré spájajú rovnaký vrchol. Poslednou možnosťou je '''farbenie plôch''', ktorých hranice sú v planárnom grafe určené hranami. [http://sk.wikipedia.org/wiki/Plan%C3%A1rny_graf Planárny (rovinný) graf] je taký, kde sa nepretínajú žiadne hrany. Oba problémy farbenia hrán a plôch môžu byť prevedené na farbenie vrcholov.<ref name="graph_coloring">Graph coloring. Wikipedia. [Online] 2008. [Dátum: 2. 1 2009.] http://en.wikipedia.org/wiki/Graph_coloring.</ref>
 Problémy s farbením grafov sa vyskytli v 19. storočí pri vyfarbovaní štátov na mapách. Bolo treba určiť minimálny potrebný počet farieb, ktoré zabezpečia, že žiadne dva susediace štáty nebudú rovnakej farby. Populárnou aplikáciou farbenia grafov je napr. hra sudoku.
@@ Riadok 96: / Riadok 96: @@
 ===Sieť toku===
-[http://en.wikipedia.org/wiki/Flow_network Sieť toku] je orientovaný graf, v ktorom každá hrana má svoju '''kapacitu''' a do každej hrany prúdi '''tok'''. Množstvo toku danou hranou nesmie prekročiť jej kapacitu. Pre každý vrchol, okrem zdroja toku a odvodu toku, musí platiť, že množstvo “pritekajúceho“ toku do vrcholu je rovné množstvu “odtekajúceho“ toku z vrcholu [14].
+[http://en.wikipedia.org/wiki/Flow_network Sieť toku] je orientovaný graf, v ktorom každá hrana má svoju '''kapacitu''' a do každej hrany prúdi '''tok'''. Množstvo toku danou hranou nesmie prekročiť jej kapacitu. Pre každý vrchol, okrem zdroja toku a odvodu toku, musí platiť, že množstvo “pritekajúceho“ toku do vrcholu je rovné množstvu “odtekajúceho“ toku z vrcholu.<ref name="flow_network">Flow network. Wikipedia. [Online] 2009. [Dátum: 2. 1 2009.] http://en.wikipedia.org/wiki/Network_flow.</ref>
 	Tento druh grafov sa využíva na modelovanie premávky v dopravnom systéme, tekutín v potrubí, prúdu v elektrických sieťach a iných praktických aplikáciách.
@@ Riadok 107: / Riadok 107: @@
 Cieľom rozhodovacích stromov je rozdeliť alebo charakterizovať určité objekty do podkategórií podľa určitých vlastností. Prvý uzol by mal obsahovať najvšeobecnejšiu charakteristiku skúmaných objektov, v ďalších by sa postupne mali vlastnosti objektu postupne viac a viac upresňovať až pokiaľ sa nedôjde k poslednému vrcholu. Vtedy je už objekt daný na vstupe pomerne presne charakterizovaný (za predpokladu správnych podmienok v jednotlivých vrcholoch). Príkladom použitia rozhodovacích stromov môžu byť aj [[Aplikácie teórie grafov a teórie hier v rozhodovacích problémoch_3#Herné stromy | herné stromy]].

← Staršia verzia		Verzia zo dňa a času 11:54, 28. január 2010
Riadok 93:		Riadok 93:

	Vyhľadávanie optimálneho sledu v grafoch súvisí s mnohými praktickými problémami od hľadania vhodnej cesty pre kropiace auto, určovanie trasy doručovania pošty až po určovanie trasy v GPS navigáciách alebo v robotike.		Vyhľadávanie optimálneho sledu v grafoch súvisí s mnohými praktickými problémami od hľadania vhodnej cesty pre kropiace auto, určovanie trasy doručovania pošty až po určovanie trasy v GPS navigáciách alebo v robotike.
−

	===Sieť toku===		===Sieť toku===

← Staršia verzia		Verzia zo dňa a času 11:51, 28. január 2010
Riadok 107:		Riadok 107:
	Obrázok 10 znázorňuje interpretáciu riešenia problému obchodného cestujúceho pomocou rozhodovacieho stromu. V každom vrchole stromu sa obchodný cestujúci rozhoduje, ktorým mestom sa môže ďalej vydať. Jednotlivé hrany sú ohodnotené vzdialenosťou, ktorú musí prejsť. V danom prípade má úloha dve riešenia, kde cesta obchodného cestujúceho bude mať dĺžku 32.		Obrázok 10 znázorňuje interpretáciu riešenia problému obchodného cestujúceho pomocou rozhodovacieho stromu. V každom vrchole stromu sa obchodný cestujúci rozhoduje, ktorým mestom sa môže ďalej vydať. Jednotlivé hrany sú ohodnotené vzdialenosťou, ktorú musí prejsť. V danom prípade má úloha dve riešenia, kde cesta obchodného cestujúceho bude mať dĺžku 32.

−	Cieľom rozhodovacích stromov je rozdeliť alebo charakterizovať určité objekty do podkategórií podľa určitých vlastností. Prvý uzol by mal obsahovať najvšeobecnejšiu charakteristiku skúmaných objektov, v ďalších by sa postupne mali vlastnosti objektu postupne viac a viac upresňovať až pokiaľ sa nedôjde k poslednému vrcholu. Vtedy je už objekt daný na vstupe pomerne presne charakterizovaný (za predpokladu správnych podmienok v jednotlivých vrcholoch). Príkladom použitia rozhodovacích stromov môžu byť aj herné stromy.	+	Cieľom rozhodovacích stromov je rozdeliť alebo charakterizovať určité objekty do podkategórií podľa určitých vlastností. Prvý uzol by mal obsahovať najvšeobecnejšiu charakteristiku skúmaných objektov, v ďalších by sa postupne mali vlastnosti objektu postupne viac a viac upresňovať až pokiaľ sa nedôjde k poslednému vrcholu. Vtedy je už objekt daný na vstupe pomerne presne charakterizovaný (za predpokladu správnych podmienok v jednotlivých vrcholoch). Príkladom použitia rozhodovacích stromov môžu byť aj [[Aplikácie teórie grafov a teórie hier v rozhodovacích problémoch_3#Herné stromy \| herné stromy]].

@@ Riadok 101: / Riadok 101: @@
 ===Rozhodovacie stromy===
 [http://en.wikipedia.org/wiki/Decision_tree Rozhodovací strom] je druhom orientovaného grafu, ktorý neobsahuje žiadne kružnice. V počiatočnom vrchole takéhoto grafu nekončí žiadna hrana a v ostatných vrcholoch končí vždy práve jedna hrana. Každý vrchol, okrem posledných - '''listových vrcholo'''v, predstavuje určitú '''rozhodovaciu situáciu'''. Po rozhodnutí vo vrchole vedie postup cez hranu, ktorá zodpovedá danému rozhodnutiu v počiatočnom vrchole. Takto sa pokračuje až do koncového vrcholu, ktorý reprezentuje výsledný stav ovplyvnený rozhodnutiami v jednotlivých vrcholoch rozhodovacieho stromu.
 Obrázok 10 znázorňuje interpretáciu riešenia problému obchodného cestujúceho pomocou rozhodovacieho stromu. V každom vrchole stromu sa obchodný cestujúci rozhoduje, ktorým mestom sa môže ďalej vydať. Jednotlivé hrany sú ohodnotené vzdialenosťou, ktorú musí prejsť. V danom prípade má úloha dve riešenia, kde cesta obchodného cestujúceho bude mať dĺžku 32.
-Cieľom rozhodovacích stromov je rozdeliť alebo charakterizovať určité objekty do podkategórií podľa určitých vlastností. Prvý uzol by mal obsahovať najvšeobecnejšiu charakteristiku skúmaných objektov, v ďalších by sa postupne mali vlastnosti objektu postupne viac a viac upresňovať až pokiaľ sa nedôjde k poslednému vrcholu. Vtedy je už objekt daný na vstupe pomerne presne charakterizovaný (za predpokladu správnych podmienok v jednotlivých vrcholoch). Príkladom použitia rozhodovacích stromov môžu byť aj herné stromy, ktoré sú presnejšie opísané v nasledujúcej kapitole.
+Cieľom rozhodovacích stromov je rozdeliť alebo charakterizovať určité objekty do podkategórií podľa určitých vlastností. Prvý uzol by mal obsahovať najvšeobecnejšiu charakteristiku skúmaných objektov, v ďalších by sa postupne mali vlastnosti objektu postupne viac a viac upresňovať až pokiaľ sa nedôjde k poslednému vrcholu. Vtedy je už objekt daný na vstupe pomerne presne charakterizovaný (za predpokladu správnych podmienok v jednotlivých vrcholoch). Príkladom použitia rozhodovacích stromov môžu byť aj herné stromy.

← Staršia verzia		Verzia zo dňa a času 11:42, 28. január 2010
Riadok 101:		Riadok 101:

	===Rozhodovacie stromy===		===Rozhodovacie stromy===
		+	[http://en.wikipedia.org/wiki/Decision_tree Rozhodovací strom] je druhom orientovaného grafu, ktorý neobsahuje žiadne kružnice. V počiatočnom vrchole takéhoto grafu nekončí žiadna hrana a v ostatných vrcholoch končí vždy práve jedna hrana. Každý vrchol, okrem posledných - '''listových vrcholo'''v, predstavuje určitú '''rozhodovaciu situáciu'''. Po rozhodnutí vo vrchole vedie postup cez hranu, ktorá zodpovedá danému rozhodnutiu v počiatočnom vrchole. Takto sa pokračuje až do koncového vrcholu, ktorý reprezentuje výsledný stav ovplyvnený rozhodnutiami v jednotlivých vrcholoch rozhodovacieho stromu.
		+
		+	Obrázok 10 znázorňuje interpretáciu riešenia problému obchodného cestujúceho pomocou rozhodovacieho stromu. V každom vrchole stromu sa obchodný cestujúci rozhoduje, ktorým mestom sa môže ďalej vydať. Jednotlivé hrany sú ohodnotené vzdialenosťou, ktorú musí prejsť. V danom prípade má úloha dve riešenia, kde cesta obchodného cestujúceho bude mať dĺžku 32.
		+
		+	Cieľom rozhodovacích stromov je rozdeliť alebo charakterizovať určité objekty do podkategórií podľa určitých vlastností. Prvý uzol by mal obsahovať najvšeobecnejšiu charakteristiku skúmaných objektov, v ďalších by sa postupne mali vlastnosti objektu postupne viac a viac upresňovať až pokiaľ sa nedôjde k poslednému vrcholu. Vtedy je už objekt daný na vstupe pomerne presne charakterizovaný (za predpokladu správnych podmienok v jednotlivých vrcholoch). Príkladom použitia rozhodovacích stromov môžu byť aj herné stromy, ktoré sú presnejšie opísané v nasledujúcej kapitole.

← Staršia verzia		Verzia zo dňa a času 11:37, 28. január 2010
Riadok 96:		Riadok 96:

	===Sieť toku===		===Sieť toku===
		+
		+	[http://en.wikipedia.org/wiki/Flow_network Sieť toku] je orientovaný graf, v ktorom každá hrana má svoju '''kapacitu''' a do každej hrany prúdi '''tok'''. Množstvo toku danou hranou nesmie prekročiť jej kapacitu. Pre každý vrchol, okrem zdroja toku a odvodu toku, musí platiť, že množstvo “pritekajúceho“ toku do vrcholu je rovné množstvu “odtekajúceho“ toku z vrcholu [14].
		+	Tento druh grafov sa využíva na modelovanie premávky v dopravnom systéme, tekutín v potrubí, prúdu v elektrických sieťach a iných praktických aplikáciách.
		+
	===Rozhodovacie stromy===		===Rozhodovacie stromy===

@@ Riadok 81: / Riadok 81: @@
 {| align="right"
-| valign="top" | [[Súbor:Atgathvrp-obr8-kaliningradske_mosty.png | thumb | 150px | '''Obr. 8 – Kaliningradské mosty''']]
+| valign="top" | [[Súbor:Atgathvrp-obr8-kaliningradske_mosty.png | thumb | 160px | '''Obr. 8 – Kaliningradské mosty''']]
 | valign="top" | [[Súbor:Atgathvrp-obr9-kaliningradske_mosty_v_grafe.png‎ | thumb | 130px | '''Obr. 9 – Kaliningradské mosty v grafe''']]
 |}
 Úlohy s hľadaním určitej cesty v grafoch sú pravdepodobne najstaršími úlohami v teórii grafov vôbec a aj dodnes najviac problémov riešených pomocou grafov súvisí s hľadaním určitej optimálnej cesty. Ako príklad možno uviesť problém [http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg Kaliningradských mostov], ktorý vyriešil [http://en.wikipedia.org/wiki/Euler Euler].
 Cez Kaliningrad tečie rieka Pregoľa (vtedajšia Pregel), ktorá vytvára dva ostrovy a tým rozdeľuje mesto na štyri časti. Jednotlivé časti boli pospájané siedmimi mostami ako je to znázornené na obr. 11. Úloha hlavolamu spočívala v navrhnutí cesty, ktorá by viedla cez všetky mosty, ale po každom moste sa smie prejsť len raz. Euler dokázal, že riešenie takúto cestu nájsť nie je možné. Hneď na začiatku si uvedomil, že trasa akou sa prechádza po danej časti mesta je irelevantná a záleží len na tom v akom poradí sa počas cesty bude prechádzať cez jednotlivé mosty. Štyri časti mesta teda znázornil len jednoduchými bodmi, ktoré potom poprepájal čiarami predstavujúcimi mosty ako je to ukázané na obr. 9. Tým sa aj zároveň ukazuje, že interpretácia problémov pomocou grafov nezávisí od mnohých vlastností skutočných objektov. V tomto prípade sa napr. neberie do úvahy vzdialenosť mostov, tvar prejdenej trasy, tvar rieky, ani tvar častí mesta.
 ===Sieť toku===
 ===Rozhodovacie stromy===