Algoritmo de Cuthill-McKee
# Algoritmo de Cuthill-McKee

En el subcampo matemático de la teoría de matrices, el algoritmo de Cuthill-McKee es un algoritmo para reducir el ancho de banda de una matriz simétrica dispersa. El algoritmo invertido de Cuthill-McKee (RCM, por las siglas inglesas Reverse Cuthill-McKee) es el mismo algoritmo pero con los índices resultantes invertidos. En el ámbito práctico, emplear este último es generalmente una mejor solución.

## Algoritmo

Dada una matriz simétrica n×n, se visualiza como la matriz de adyacencia de un grafo. El algoritmo de Cuthill-McKee es entonces una renumeración de los vértices del grafo con el objetivo de reducir el ancho de banda de su matriz de adyacencia.

El algoritmo produce una n-tupla ordenada R de vértices, que es el nuevo orden de los vértices.

Primero, se elige un vértice periférico x y se realiza la asignación R := ({x}).

A continuación, para i = 1, 2, ... se iteran las próximas instrucciones mientras |R| < n

* Construir el conjunto de adyacencia $A_{i}$ de $R_{i}$ (siendo $R_{i}$ el i-ésimo componente de R) excluyendo aquellos vértices que ya estuvieran en R.

    $A_{i}:=\operatorname {Ady} (R_{i})\setminus R$
* Ordenar $A_{i}$ siguiendo una ordenación ascendente de los vértices.
* Añadir $A_{i}$ al conjunto resultado R.

En otras palabras, numerar los vértices de acuerdo a una particular búsqueda en anchura transversal, donde los vértices vecinos son visitados en orden de menor a mayor.

