Podgraf

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

Podgraf danego grafu G to graf powstały przez usunięcie z grafu G pewnej liczby wierzchołków lub krawędzi (z tym zastrzeżeniem, że usuwając pewien wierzchołek usuwamy wszystkie do niego przyległe krawędzie)^[1].

W szczególności każdy graf jest swoim podgrafem.

Podgrafem indukowanym wierzchołkowo danego grafu G nazywamy graf powstały przez usunięcie z grafu G pewnej liczby wierzchołków oraz wszystkich wychodzących z nich i wchodzących do nich krawędzi. Inaczej mówiąc jest to graf, którego zbiór wierzchołków jest zawarty (jest podzbiorem) w zbiorze wierzchołków grafu G, a zbiór krawędzi składa się ze wszystkich krawędzi grafu G, których końce należą do zbioru wierzchołków nowo powstałego grafu. Zbiór wierzchołków tego podgrafu nie może być pusty^[1].

Podgrafem indukowanym krawędziowo danego grafu G nazywamy graf powstały z grafu G, którego zbiór krawędzi jest zawarty (jest podzbiorem) w zbiorze krawędzi grafu G, a zbiór wierzchołków stanowią końce krawędzi.

Przypisy

Zobacz też

• teoria grafów