Zbiór dominujący
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 |
W teorii grafów zbiorem dominującym grafu G = (V,E) nazywamy taki podzbiór V' zbioru wierzchołków V, że każdy wierzchołek, który nie należy do V' ma w tym zbiorze co najmniej jednego sąsiada (jest połączony krawędzią z przynajmniej jednym wierzchołkiem z V'. Zwyczajowo przez γ(G) oznaczamy liczbę wierzchołków w najmniejszym zbiorze dominującym grafu G.
Zobacz też: pokrycie wierzchołkowe, zbiór niezależny, skojarzenie
