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
Graf je abstraktný matematický objekt daný a teória grafov a sú obvykle abstrakciou reálnych problémov či štruktúr. Typickým príkladom je modelovanie cestnej siete ako grafu, kde vrcholy sú mestá a hrany zastupujú cesty.
- Poznámka: V slovenskej literatúre sa množina hrán zvykne označovať aj symbolom H. Vo svetovej literatúre sa obvykle označuje E z anglického edge.
Definície
Neorientovaný graf
Graf alebo neorientovaný graf G je usporiadaná dvojica G = (V, E), kde:
- V je neprázdna konečná množina vrcholov grafu,
- E je množina neusporiadaných dvojíc typu {u, v}, kde u ≠ v, nazývaných hrany grafu.
Príklad neorientovaného grafu:
- V = {1, 2, 3, 4}
E = {{1, 2}, {1, 3}, {2, 3}, {3, 4}}
Orientovaný graf
Orientovaný graf alebo digraf G je usporiadaná dvojica G = (V, E), kde:
- V je neprázdna konečná množina vrcholov grafu,
- E je množina usporiadaných dvojíc typu (u, v), kde u ≠ v, nazývaných orientované hrany grafu.
Príklad digrafu:
- V = {1, 2, 3, 4}
E = {(1, 2), (1, 3), (3, 2), (3, 4), (4, 3)}
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.
Ďalšie typy grafov
Ak sú v grafe povolené aj orientované, aj neorientované hrany, takýto graf sa nazýva migraf. Pripustením viacerých „rovnakých“ hrán (u, v) (resp. {u, v}) získavame multidigraf (resp. multigraf). Ak v grafe existujú aj orientované, aj neorientované hrany a navyše niektoré z nich majú rovnaký aj začiatočny, aj koncový bod, nazývame tento graf multimigrafom. Graf, ktorý obsahuje aj slučky sa zvykne nazývať pseudograf (resp. pseudodigraf a pseudomigraf).
Diagram grafu
Diagram grafu je jeho grafickým znázornením a každý graf ma nekonečné množstvo diagramov. Jednoduchšie grafy je možné zobraziť do roviny (kde sa hrany pretínajú iba vo vrcholoch), takéto diagramy sa nazývajú rovinné. Vrcholy sa väčšinou zobrazujú ako krúžky či bodky a hrany ako čiary.
Vlastnosti grafov
- Triviálny graf je taký, ktorého množina vrcholov V pozostáva iba z jedného vrcholu a jeho množina hrán E je prázdna.
- Graf sa nazýva rovinným, ak k nemu existuje rovinný diagram.
- Hranová množina E úplneho grafu (resp. digrafu) obsahuje všetky kombinácie {u, v} (resp. (u, v)), také že u, v ∈ V a u ≠ v. Teda každé dva vrcholy sú spojené hranou.
- Pravidelným grafom stupňa k nazveme graf, v ktorom má každý vrchol v z V stupeň k.
- Graf sa nazýva bipartitný, ak jeho množinu vrcholov možno rozdeliť na dve disjunktné množiny V1, V2, pre ktoré platí, že žiadne dva vrcholy z tej istej časti nie sú susedné.
- Grafy G = (V, E) a G0 = (V0, E0) sú komplementárne, ak pre ne platí, že V = V0 a pre každé dva rôzne vrcholy u, v platí {u, v} ∈ E práve vtedy ak {u, v} ∉ E0. Graf G1 = (V, E ∪ E0) je teda úplným grafom. Graf G0 je komplement grafu G.
- Ak konkrétna aplikácia vyžaduje aby mali hrany priradenú určitú hodnotu (cenu alebo všeobecnejšie váhu), takýto graf obohatíme o funkciu w, ktorá zobrazuje množinu hrán do množiny reálnych čísel (E → R). Tento graf G = (V, E, w) nazývame hranovo-ohodnotený. Niekedy sa vyžaduje viac ohodnotení hrán a to vedie k použitiu viacerých funkcií.
Podgrafy
Graf G0 = (V0, E0) je podgrafom grafu G = (V, E), ak platí V0 ⊆ V a E0 ⊆ E. Potom môžeme písať G0 ⊆ G.
Faktorový podgraf grafu G je taký podgraf G0 = (V0, E0), v ktorom platí V0 = V.
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.
Binárny strom (teória grafov)
Cesta (teória grafov)
Chromatické číslo
Chromatický index
Cyklomatické číslo grafu
Eulerovský ťah
Excentricita (teória grafov)
Faktor grafu
Farbenie grafu
Farbenie vrcholov
Grafová postupnosť
Graf (matematika)
Hamiltonovská kružnica
Hamiltonovský graf
Hrana (teória grafov)
Komplement grafu
Komponent grafu
Kostra grafu
Kružnica (teória grafov)
Minimálna kostra grafu
Most (teória grafov)
Neplanárny graf
Nezávislá množina
Ohodnotený graf
Oreho veta
Orientované stromy
Párny graf
Petersenov graf
Podgraf
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)
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)
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