Niech G będzie niepustym grafem prostym. Graf, który można przedstawić na płaszczyźnie w taki sposób, że żadne dwie krawędzie nie przecinają się nazywamy grafem płaskim, natomiast graf nazywamy planarnym, gdy jest on izomorficzny do grafu płaskiego. Jeśli dodatkowo wszystkie jego wierzchołki leżą na obszarze zewnętrznym, graf nazywamy zewnętrznie planarnym. Indeksem krawędziowym grafu G nazywamy najmniejsze k takie, że k-ty iterowany graf krawędziowy grafu G jest nieplanarny. Analogicznie definiujemy indeks krawędziowo-blokowy, zewnętrznie-krawędziowy i zewnętrznie-krawędziowo-blokowy. W artykule charakteryzujemy wszystkie grafy pod względem wartości powyższych indeksów.
Autorzy
Informacje dodatkowe
- Kategoria
- Publikacja monograficzna
- Typ
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku o zasięgu krajowym
- Język
- polski
- Rok wydania
- 2009
Źródło danych: MOSTWiedzy.pl - publikacja "Planarność i zewnętrzna planarność grafów" link otwiera się w nowej karcie
