Malgrangeův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 8. července 2016; kontroly vyžadují 5 úprav .

Malgrangeův algoritmus je metoda pro rozdělení grafu do silně propojených podgrafů .

Algoritmus

Nechť je dán graf , kde je množina vrcholů, ve kterých, , a je množina oblouků popsaných maticí sousednosti , ve které . Algoritmus rozdělení je následující: $G=(X,A)$ $X=\{x{_{i}}\}$ $i={\overline {1,n))$ $A=\{a{_{i}}\}$ $i={\overline {1,m))$

Pro libovolný vrchol najdeme přímé a inverzní tranzitivní uzávěry . $x{_{i}}\in X$ $T{^{+}}(x{_{i}})$ $T{^{-}}(x{_{i}})$
najdeme . Množina vrcholů tohoto průsečíku tvoří vrcholy maximálního silně spojeného podgrafu . $T{^{+}}(x{_{i}})\cap T{^{-}}(x{_{i}})$ $G{_{1}}=(X{_{1}},A{_{1}})$
Odečtěte podgraf od původního grafu : . $G{_{1))$ $G'=G\setminus G{_{1)),X'=X\setminus X{_{1}}$
Graf se bere jako původní graf a kroky 1, 2, 3 algoritmu se opakují. $G'$ $X'\neq \varnothing$

Literatura

A. Kofman. Úvod do aplikované kombinatoriky. - M. : Nauka, 1975. - S. 166. - 480 s.

Odkazy

Tamara Volchenskaya, Vladimir Knyazkov, Kurz "Úvod do teorie grafů", Přednáška 7: "Metody pro rozdělení grafu na maximální silně propojené podgrafy" // Intuit.ru , 2008

Algoritmy na grafech
Hledejte tuleně	Bron-Kerboshův algoritmus Kosarayuův algoritmus Malgrangeův algoritmus Tarjanův algoritmus Demucronův algoritmus Přibližný algoritmus pro nalezení p-mediánů Problém nejdelší cesty Topologické řazení Pant (teorie grafů) Kargerův algoritmus (minimální řez)
Maximalizace toku	Dinitův algoritmus Algoritmus Malhotra-Kumara-Maheshwari Preflow Push Algorithm Ford-Fulkersonův algoritmus Edmonds-Karpův algoritmus dopravní síť
Vhodný	Algoritmus komprese květin Hopcroft-Karpův algoritmus Algoritmus FKT
Komunikační grafy	Havel-Hakimi algoritmus (grafická sekvence) Vzdálenost editace grafu Problém hledání izomorfního podgrafu
jiný	Algoritmus pro artikulační strom (načte marginalizaci) Algoritmus Cuthill-Mackey (zmenšení šířky pásky) Iterativní komprese (myšlenka rekurze) Šablona: Vyhledávací algoritmy v grafech