Problem zbioru wierzchołków rozrywających cykle
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 |
Problem zbioru wierzchołków rozrywających cykle (ang. feedback vertex set problem) – zagadnienie z teorii grafów, polegające na znalezieniu podgrafu X, w grafie G, takiego, że co najmniej k jego wierzchołków i krawędzi nie tworzy cyklu. Był jednym z pierwszych problemów, wobec których udowodniono NP-zupełność.
This article "Problem zbioru wierzchołków rozrywających cykle" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Problem zbioru wierzchołków rozrywających cykle.