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
Neplanárny graf alebo nerovinný graf je graf, ktorý nie je rovinný graf.
Pre neplanárny graf možno nakresliť diagram grafu len tak, že niektoré hrany sa krížia v nekoncových bodoch.
Miery neplanárnosti grafu
Pre každý graf G možno určiť nesledujúce miery neplanárnosti grafu
- priesečníkové číslo grafu
- hrúbku grafu
- jemnosť grafu
- rod grafu
Priesečníkové číslo grafu
Priesečníkové číslo grafu G je minimálny počet dvojíc hrán, ktoré sa krížia (pretínajú) pri ľubovoľnom nakreslení diagramu grafu G.
Hrúbka grafu
Hrúbka grafu G je minimálny počet jeho planárnych podgrafov zjednotením ktorých dostávame graf G.
Jemnosť grafu
Jemnosť grafu G je maximálny počet hranovo disjunktných neplanárnych podgrafov grafu G
Tieto miery sú kombinatorické miery neplanárnosti grafov. Existuje ešte jedna miera, ktorá má čisto geometrickú interpretáciu.
Rod grafu
Rod grafu je minimálny počet premostení, ktoré treba pridať ku guli, aby sa na jej povrchu dal nakresliť diagram príslušného grafu bez pretínania sa hrán. Planárne grafy majú rod 0, rod 1 majú grafy, ktorých diagramy môžeme nakresliť na anuloid (“pneumatiku”).
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