Podgraf
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Podgraf danego grafu G to graf powstały przez usunięcie z grafu G pewnej liczby wierzchołków lub krawędzi.
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.
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.
