Zbiór niezależny
Z Wikipedii
9 zaznaczonych na niebiesko wierzchołków tworzy (zaskakująco asymetrzyczny) maksymalny zbiór niezależny w tym grafie o 24 wierzchołkach.
W teorii grafów zbiór niezależny w grafie G=(V,E), to zbiór wierzchołków 
, pomiędzy którymi nie ma żadnej krawędzi. Innymi słowy każda krawędź w G jest incydentna z co najwyżej jednym wierzchołkiem w tym zbiorze.
Problem maksymalnego zbioru niezależnego polegający na znalezieniu w danym grafie zbioru niezależnego o maksymalnej liczbie wierzchołków, jest znanym problemem NP-zupełnym.
Problem maksymalnego zbioru nie powinien być mylony z maksymalnym zbiorem niezależnym w sensie teorii mnogości. 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
