Malgrange algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2016. július 8-án felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A Malgrange algoritmus egy módszer a gráfok erősen kapcsolódó részgráfokra történő particionálására .

Algoritmus

Legyen adott egy gráf , ahol az a csúcshalmaz, amelyben, , és a szomszédsági mátrix által leírt ívek halmaza , amelyben . A particionálási algoritmus a következő: $G=(X,A)$ $X=\{x{_{i}}\}$ $i={\overline {1,n))$ $A=\{a{_{i}}\}$ $i={\overline {1,m))$

Egy tetszőleges csúcsra direkt és inverz tranzitív lezárásokat találunk . $x{_{i}}\in X$ $T{^{+}}(x{_{i}})$ $T{^{-}}(x{_{i}})$
találunk . Ennek a metszéspontnak a csúcskészlete alkotja egy maximálisan erősen összefüggő részgráf csúcsait . $T{^{+}}(x{_{i}})\cap T{^{-}}(x{_{i}})$ $G{_{1}}=(X{_{1}},A{_{1}})$
Vonja ki a részgráfot az eredeti gráfból : . $G{_{1))$ $G'=G\setminus G{_{1)),X'=X\setminus X{_{1}}$
A gráfot az eredeti gráfnak tekintjük, és az algoritmus 1., 2., 3. lépései megismétlődnek. $G'$ $X'\neq \varnothing$

Irodalom

A. Kofman. Bevezetés az alkalmazott kombinatorikába. - M. : Nauka, 1975. - S. 166. - 480 p.

Linkek

Tamara Volchenskaya, Vladimir Knyazkov, "Bevezetés a gráfelméletbe" kurzus, 7. előadás: "Módszerek egy gráf maximálisan erősen kapcsolódó részgráfokra particionálására" // Intuit.ru , 2008

Algoritmusok grafikonokon
Fókák keresése	Bron-Kerbosh algoritmus Kosarayu algoritmusa Malgrange algoritmus Tarján algoritmusa Demucron algoritmusa Hozzávetőleges algoritmus a p-mediánok meghatározásához A leghosszabb út problémája Topológiai rendezés Zsanér (gráfelmélet) Karger algoritmusa (minimális vágás)
Áramlás maximalizálása	Dinit algoritmusa Malhotra-Kumara-Maheshwari algoritmus Preflow Push Algorithm Ford-Fulkerson algoritmus Edmonds-Karp algoritmus közlekedési hálózat
Illesztés	Virágtömörítési algoritmus Hopcroft-Karp algoritmus FKT algoritmus
Kommunikációs grafikonok	Havel-Hakimi algoritmus (grafikus sorozat) Grafikon szerkesztési távolság Izomorf részgráf megtalálásának problémája
Egyéb	Algoritmus az artikulációs fa számára (lekéri a marginalizációt) Cuthill-Mackey algoritmus (szalagszélesség csökkentése) Iteratív tömörítés (rekurzió ötlete) Sablon: Keresési algoritmusok grafikonokon