Algoritmo de Malgrange

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 8 de julio de 2016; las comprobaciones requieren 5 ediciones .

El algoritmo de Malgrange es un método para dividir un gráfico en subgráficos fuertemente conectados .

Algoritmo

Sea dado un gráfico , donde es el conjunto de vértices en el que, , y es el conjunto de arcos descritos por la matriz de adyacencia , en la que . El algoritmo de partición es el siguiente: ${\ estilo de visualización G = (X, A)}$ $X=\{x{_{i}}\}$ $i={\overline {1,n))$ $A=\{a{_{i}}\}$ $i={\overline {1,m))$

Para un vértice arbitrario , encontramos cierres transitivos directos e inversos . $x{_{i}}\en X$ $T{^{+}}(x{_{i}})$ $T{^{-}}(x{_{i}})$
encontramos _ El conjunto de vértices de esta intersección constituye los vértices de un subgrafo máximo fuertemente conexo . $T{^{+}}(x{_{i}})\cap T{^{-}}(x{_{i}})$ $G{_{1}}=(X{_{1}},A{_{1}})$
Resta el subgrafo del grafo original : . $G{_{1))$ $G'=G\setminus G{_{1)),X'=X\setminus X{_{1}}$
El gráfico se toma como el gráfico original y mientras se repiten los pasos 1, 2, 3 del algoritmo. $GRAMO'$ $X'\neq \varnada$

Literatura

A. Kofman. Introducción a la combinatoria aplicada. - M. : Nauka, 1975. - S. 166. - 480 p.

Enlaces

Tamara Volchenskaya, Vladimir Knyazkov, Curso "Introducción a la teoría de grafos", Clase 7: "Métodos para dividir un gráfico en subgrafos máximos fuertemente conectados" // Intuit.ru , 2008

Algoritmos en grafos
Buscar focas	Algoritmo de Bron-Kerbosh Algoritmo de Kosarayu Algoritmo de Malgrange Algoritmo de Tarjan Algoritmo de Demucron Algoritmo aproximado para encontrar p-medianas El problema del camino más largo clasificación topológica Bisagra (teoría de grafos) Algoritmo de Karger (corte mínimo)
Maximización de flujo	algoritmo de Dinit Algoritmo Malhotra-Kumara-Maheshwari Algoritmo de empuje de preflujo Algoritmo de Ford-Fulkerson Algoritmo de Edmonds-Karp red de transporte
Pareo	Algoritmo de compresión de flores Algoritmo de Hopcroft-Karp algoritmo FKT
Gráficos de comunicación	Algoritmo Havel-Hakimi (secuencia gráfica) Distancia de edición de gráfico El problema de encontrar un subgrafo isomorfo
Otro	Algoritmo para árbol de articulación (recupera marginación) Algoritmo Cuthill-Mackey (reducción del ancho de la cinta) Compresión iterativa (idea de recursividad) Plantilla:Algoritmos de búsqueda en gráficos