Podgraf w grafie
Podgraf danego grafu G można zdefiniować jako graf, który powstaje poprzez usunięcie pewnej liczby wierzchołków lub krawędzi. Należy przy tym pamiętać, że usunięcie wierzchołka pociąga za sobą usunięcie wszystkich krawędzi do niego przylegających. Warto zaznaczyć, że każdy graf może być uznany za swój własny podgraf.
Rodzaje podgrafów
Wyróżniamy dwa główne typy podgrafów:
- Podgraf indukowany wierzchołkowo: Powstaje z grafu G poprzez usunięcie pewnej liczby wierzchołków oraz wszystkich krawędzi, które do nich prowadzą lub od nich wychodzą. Zbiór wierzchołków tego podgrafu musi być niepusty.
- Podgraf indukowany krawędziowo: Jest to graf, w którym zbiór krawędzi jest podzbiorem krawędzi grafu G, a zbiór wierzchołków składa się z końców tych krawędzi.
Podsumowanie
Podgrafy pozwalają na analizę struktur grafów poprzez usuwanie wierzchołków i krawędzi, co może pomóc w lepszym zrozumieniu właściwości grafu G oraz jego relacji wewnętrznych.
