title: Algoritmo de Cuthill-McKee
text: # 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.
  
  