Algoritmul Malgrange

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 8 iulie 2016; verificările necesită 5 modificări .

Algoritmul Malgrange este o metodă de partiţionare a unui graf în subgrafe puternic conectate .

Algoritm

Să fie dat un grafic , unde este mulțimea de vârfuri în care, , și este mulțimea de arce descrise de matricea de adiacență , în care . Algoritmul de partiţionare este următorul: $G=(X,A)$ $X=\{x{_{i}}\}$ $i={\overline {1,n)}$ $A=\{a{_{i}}\}$ $i={\overline {1,m))$

Pentru un vârf arbitrar găsim închideri tranzitive directe și inverse . $x{_{i}}\in X$ $T{^{+}}(x{_{i}})$ $T{^{-}}(x{_{i}})$
Găsim . Mulțimea nodurilor acestei intersecții constituie vârfurile unui subgraf maximal puternic conectat . $T{^{+}}(x{_{i}})\cap T{^{-}}(x{_{i}})$ $G{_{1}}=(X{_{1}},A{_{1}})$
Scădeți subgraful din graficul original : . $G{_{1))$ $G'=G\setminus G{_{1)),X'=X\setminus X{_{1}}$
Graficul este luat ca grafic original și în timp ce pașii 1, 2, 3 ai algoritmului se repetă. $G'$ $X'\neq \varnothing$

Literatură

A. Kofman. Introducere în combinatorică aplicată. - M. : Nauka, 1975. - S. 166. - 480 p.

Link -uri

Tamara Volchenskaya, Vladimir Knyazkov, Curs „Introducere în teoria graficelor”, Cursul 7: „Metode pentru împărțirea unui graf în subgrafe maxime puternic conectate” // Intuit.ru , 2008

Algoritmi pe grafice
Căutați sigilii	Algoritmul Bron-Kerbosh Algoritmul lui Kosarayu Algoritmul Malgrange algoritmul lui Tarjan algoritmul lui Demucron Algoritm aproximativ pentru găsirea p-medianelor Problema drumului cel mai lung Sortare topologică Balama (teoria grafurilor) Algoritmul lui Karger (tăiere minimă)
Maximizarea fluxului	Algoritmul lui Dinit Algoritmul Malhotra-Kumara-Maheshwari Algoritmul de preflux Push Algoritmul Ford-Fulkerson Algoritmul Edmonds-Karp reteaua de transport
Potrivire	Algoritm de compresie a florilor Algoritmul Hopcroft-Karp Algoritmul FKT
Grafice de comunicare	Algoritmul Havel-Hakimi (secvență grafică) Distanța de editare a graficului Problema găsirii unui subgraf izomorf
Alte	Algoritm pentru arborele de articulare (recuperează marginalizarea) Algoritmul Cuthill-Mackey (reducerea lățimii benzii) Compresie iterativă (idee de recursivitate) Șablon:Algoritmi de căutare pe grafice