A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
V teórii grafov sa termínom cesta v grafe G = (V, E) označuje postupnosť , pre ktorú platí (poprípade pre orientované grafy) a naviac . Je to teda postupnosť vrcholov, pre ktorú platí, že v grafe existuje hrana z daného vrcholu do jeho následníka. Žiadne dva vrcholy (a teda ani hrany) sa neopakujú.
Posledná podmienka odlišuje cestu od dvoch podobných pojmov:
- ťah je postupnosť, v ktorej sa môžu opakovať vrcholy, ale nie hrany
- sled je postupnosť, v ktorej sa môžu opakovať aj hrany
Vlastnosti
- dĺžka cesty je počet jej hrán alebo vrcholov (pre rôzne účely sa definuje rôzne)
- ak je graf G = (V, E) vážený s ohodnotením , potom váha (cena, …) cesty P v grafe G je
- ak povolíme , už nejde o cestu, ale o kružnicu
Disjunktné cesty
Cesty a sú
- vrcholovo disjunktné, pokiaľ
- hranovo disjunktné, pokiaľ
Kružnica
Kružnicou nazývame uzavrenú cestu. Teda cestu, ktorá začína a končí v rovnakom vrchole.
Pozri aj
Tento článok je čiastočný alebo úplný preklad článku Cesta (graf) na českej Wikipédii.
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Česko-Slovensko
1736
1926
Algoritmus
Binárny strom (teória grafov)
Cesta (teória grafov)
Chromatické číslo
Chromatický index
Cyklomatické číslo grafu
Diskrétna matematika
Eulerovský ťah
Excentricita (teória grafov)
Faktor grafu
Farbenie grafu
Farbenie vrcholov
Grafová postupnosť
Graf (matematika)
Hamiltonovská kružnica
Hamiltonovský graf
Informatika
Izomorfizmus grafov
Kaliningrad
Komplement grafu
Komponent grafu
Kostra grafu
Kružnica (teória grafov)
Leonhard Euler
Matematika
Minimálna kostra grafu
Most (teória grafov)
Neorientovaný graf
Neplanárny graf
Nezávislá množina
Ohodnotený graf
Oreho veta
Orientované stromy
Orientovaný graf
Otakar Borůvka
Petersenov graf
Podgraf
Pravidelný graf
Priesečníkové číslo (teória grafov)
Problém obchodného cestujúceho
Problém siedmich mostov
Rovinný graf
Súvislý graf
Sled (teória grafov)
Slovensko
Spektrálna teória grafov
Strom (teória grafov)
Teória grafov
Teória grafov – grafová postupnosť
Topologická teória grafov
Vrchol (teória grafov)
Vzdialenosť (teória grafov)
Wikipédia:Výhonok
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk