Rdzeń grafu
Z Wikipedii, wolnej encyklopedii
Rdzeń grafu to graf powstały przez kolejne usuwanie z grafu wierzchołków stopnia pierwszego, aż do momentu, gdy takich wierzchołków w grafie nie będzie. Przy tym zawsze wraz z wierzchołkiem v usuwamy krawędź, która ma v za swój wierzchołek.
Ten artykuł od 2016-06 wymaga zweryfikowania podanych informacji.
Z dowolnej acyklicznej komponenty grafu ostanie się w rdzeniu tylko jeden (dowolny) wierzchołek. Z pozostałych komponent do rdzenia wejdą te i tylko te wierzchołki i krawędzie, które należą do cykli.
Na każdym kroku istnieje na ogół wybór więcej niż jednego wierzchołka + krawędzi do usunięcia, ale ostateczny wynik, rdzeń, niemalże jest niezależny od tych wyborów (co wynika z ostatniej uwagi powyżej), a klasa izomorficzna rdzenia jest po prostu niezależna od wspomnianych wyborów, a zależy jedynie od klasy samego grafu. Przy tym dodatkowo mamy identycznościowe zanurzenie rdzenia w danym grafie.
Wikiwand in your browser!
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.
