Zjisteni souvislosti grafu
Cau,
Je zadání zjistit jestli graf o nějakých n vrcholech je souvislý, a jsou vypsané jaké vrcholy jsou spojené s jakými. A pokud není souvislý tak kolik má komponent.
Zjistil jsem že to souvisí např. s vyledáváním do šířky, ale konkrétně nemůžu najít nikdě nějaký přesný návod jakým způsobem mám zjistovat jestli je souvislý nebo ne?
David H.
20. 01. 2016 00:26
3 odpovědi
Nejjednodušší typ algoritmu je tenhle.
Jsou i efektivnější algoritmy, ale to je asi zbytečné.
Pro graf daný množinou vrcholů V a množinou hran E:
(0) inicializace
X = V
Y = Ø
(1) nalezení souvislé komponenty neorientovaného grafu
vezmi s ∈ X:
-
X = X - { s}
-
Y = Y ∪ { s}
dokud X <> Ø a ∃ u v dalším kroku:
-
vezmi u ∈ X takové, že ∃ v ∈ Y: (u, v) ∈ E
-
X = X - { u}
-
Y = Y ∪ { u}
(2) Y obsahuje souvislou komponentu grafu
-
Y = Ø
-
opakuj krok (1)
Aha díky, a jmenuje se tento algoritmus nějak konkrétně? Případně jaké jsou ty další algoritmy prosím? Já to bohužel z tohoto zápisu, asi jen tak nepochopím.
Jmenuje se to algoritmus na zjištění souvislých komponent v neorientovaném grafu.
Když mi dáš celé zadání a v jakém ročníku, abych věděl, na jaké úrovni se spolu máme bavit, možná ti dokážu poradit.
Touhle oblastí se zabývá diskrétní matematika. Kapitoly z diskrétní matematiky od Matouška a Nešetřila sloužily jako učebnice na MFF UK, Matoušek mě tehdy učil, sežeň si ji, jestli chceš řešit takovéhle algoritmy.