Podgraf
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 edytuj
- ↑ a b Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 3. ISBN 0-387-95014-1.