Zbiór niezależny w grafie
– zbiór wierzchołków
pomiędzy którymi nie ma żadnej krawędzi. Innymi słowy każda krawędź w
jest incydentna z co najwyżej jednym wierzchołkiem w tym zbiorze.
Problem największego zbioru niezależnego polegający na znalezieniu w danym grafie zbioru niezależnego o maksymalnej liczbie wierzchołków, jest znanym problemem NP-trudnym.
Problem ten nie powinien być mylony z maksymalnym zbiorem niezależnym w sensie inkluzji. Zbiór taki jest maksymalny gdy dodanie do niego jakiegokolwiek elementu sprawia, że przestaje być niezależny. Znalezienie takiego zbioru wierzchołków jest proste i może być wykonane za pomocą algorytmu zachłannego.
Zobacz też
Najważniejsze pojęcia |
|
---|
Wybrane klasy grafów |
|
---|
Algorytmy grafowe |
|
---|
problemy grafowe |
|
---|
Inne zagadnienia |
|
---|