Loading AI tools
Z Wikipedii, wolnej encyklopedii
Silnie spójna składowa (SSS) grafu skierowanego G to taki maksymalny podgraf H, a jednocześnie jego spójna składowa, taka, że pomiędzy każdymi dwoma jej wierzchołkami istnieje ścieżka.
Innymi słowy, w silnie spójnej składowej da się dojść z każdego jej wierzchołka do każdego innego.
Dla grafu nieskierowanego każda spójna składowa będzie silnie spójna.
Silnie spójne składowe mają zastosowanie przy de-cyklizacji grafu (usunięciu cykli) - graf silnie spójnych składowych(tzn. graf w którym wierzchołki odpowiadają silnie spójnym składowym, a krawędź istnieje pomiędzy wierzchołkami w.t.w. gdy w wejściowym grafie istniała między silnie spójnymi składowymi) jest acykliczny.
W obu przypadkach złożoność czasowa wynosi O(E), pamięciowa O(E+V)
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.