Mam do rozwiązania teoretyczne zad. z Algorytmów.
Ile punktów artykulacji może minimalnie istnieć w drzewie T składającym się z n wierzchołków? odp. uzasadnij
czy odp może brzmieć 0? bo punkt artykulacji to wierzchołek, którego usunięcie rozspójnia graf
na pyt ile maksymalnie- odpowiedziałam, ale minimalnie.... nie mam pojęcia
wiem kiedy wierzchołek jest puntem artykulacji a kiedy nie jest...
Proszę o pomoc
maksymalnie: n-2
minimalnie: fllor(n/2)
Minimalnie nie będzie przypadkiem 1? Np jest jeden wierzchołek połączony ze wszystkimi innymi, a reszta między sobą nie jest w ogóle połączona. To będzie drzewo gdzie ten dobrze połączony wierzchołek jest korzeniem, a reszta wierzchołków jest liśćmi. Wtedy usunięcie korzenia rozspójnia graf, ale usunięcie dowolnego liścia nie.
proszę o uzasadnienie, dlaczego akurat tyle punktów
Która odp jest poprawna?
1 - logicznie brzmi poprawnie, a to z podłogą nie wiem skąd się wzięło...