Algoritmo de Cuthill-Mackey

El Cuthill -McKee es un algoritmo de reducción de ancho de cinta para matrices simétricas El nombre de los desarrolladores - Elizabeth Cuthill y James McKee.

Reverse Cuthill-McKee ( RCM , reverse Cuthill-McKee ) es el mismo algoritmo con numeración de índice inversa.

Algoritmo

La matriz simétrica original se trata como la matriz de adyacencia del gráfico . El algoritmo Cuthill-McKee renumera los vértices del gráfico de tal forma que, como resultado de la correspondiente permutación de las columnas y filas de la matriz original, se reduce el ancho de su cinta . $n\veces n$ $(V,E)$

El algoritmo crea un conjunto ordenado de vértices que representan la nueva enumeración de vértices. Para un gráfico conectado , el algoritmo se ve así: $R$

seleccione un vértice periférico (o vértice pseudo-periférico ) para el valor inicial de la tupla ; $v$ ${\ estilo de visualización R: = (v)}$
para , mientras se cumpla la condición , realice los pasos 3-5: ${\ estilo de visualización i = 1,2,...}$ ${\ estilo de visualización | R | < n}$
construye un conjunto de adyacencia para , donde es el -ésimo componente de , y excluye los vértices que ya están contenidos en , es decir: ; ${\ estilo de visualización \ nombre del operador {Adj} (R_ {i})}$ $Rhode Island$ $Rhode Island$ $i$ $R$ $R$ $A_{i}:=\operatorname {Adj} (R_{i})\setminus R$
ordenar en orden ascendente de grados de vértice ; $Ai}$
añadir a la tupla de resultados . $Ai}$ $R$

En otras palabras, el algoritmo enumera los vértices en una búsqueda en anchura , en la que los vértices adyacentes se recorren en orden creciente de sus potencias .

Para un gráfico desconectado, el algoritmo se puede aplicar por separado a cada componente conectado [1] .

La complejidad computacional del tiempo del algoritmo RCM siempre que se utilice la ordenación por inserción para ordenar , , donde es el grado máximo de un vértice, es el número de aristas del gráfico [2] . ${\ estilo de visualización O (m | E |)}$ $metro$ ${\ estilo de visualización | E |}$

Elección del vértice inicial

Para obtener buenos resultados, necesitas encontrar el vértice periférico del gráfico . Esta tarea es generalmente bastante difícil, por lo que, en lugar de ella, suelen buscar un vértice pseudoperiférico utilizando alguna de las modificaciones del algoritmo heurístico de Gibbs et al. $(V,E)$

Para describir el algoritmo, se introduce el concepto de una estructura de nivel raíz . Para un vértice dado , la estructura de nivel arraigada será una partición del conjunto de vértices : $v$ $v$ $\mathcal{L}$ $V$

{\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots,L_{l(v)}(v)\},

donde los subconjuntos se definen de la siguiente manera: ${\ Displaystyle L_ {i} (v)}$

L_{0}(v)=\{v\},

L_{1}(v)=\nombre del operador {Adj} (L_{0}(v))

L_{i}(v)=\operatorname {Adj} (L_{i-1}(v))-L_{i-2}(v),\qquad i=2,3,\dots,l (v).

Algoritmo para encontrar un vértice pseudoperiférico [3] :

seleccione un vértice arbitrario de ; $r$ $V$
construye una estructura de niveles para la raíz : ; $r$ ${\mathcal {L}}(r)=\{L_{0}(r),L_{1}(r),\dots,L_{l(r)}(r)\}$
seleccione el vértice con el grado mínimo de ; $v$ ${\ Displaystyle L_ {l (r)} (r)}$
construye una estructura de niveles para la raíz : ; $v$ ${\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots,L_{l(v)}(v)\}$
si , entonces asigne y vaya al paso 3; ${\ estilo de visualización l (v)> l (r)}$ ${\ estilo de visualización r: = v}$
el vértice es el vértice pseudoperiférico deseado. $v$

Notas

↑ George, Liu, 1984 , págs. 65-66.
↑ George, Liu, 1984 , pág. 68.
↑ George, Liu, 1984 , págs. 70-72.

Literatura

E. Cuthill y J. McKee. Reduciendo el ancho de banda de matrices simétricas dispersas en Proc. 24 Nat. Conf. ACM , páginas 157-172, 1969.
George A., Liu J. Solución informática de grandes sistemas definidos positivos dispersos. — M .: Mir, 1984. — 333 p.

Enlaces

Documentación del algoritmo Cuthill-McKee para las bibliotecas Boost C++ .
Explicación detallada del algoritmo Cuthill-McKee .
Explicación detallada del algoritmo Cuthill-McKee (ruso) (enlace inaccesible) .
Implementación del algoritmo Cuthill-McKee en Python (enlace no disponible) .