En teoría de grafos , el criterio de planaridad de Mac Lane es una caracterización de los grafos planos en términos de sus espacios de ciclo , llamado así en honor a Saunders Mac Lane , quien lo publicó en 1937. Afirma que un grafo finito no dirigido es plano si y sólo si el espacio de ciclo de el gráfico (tomado módulo 2) tiene una base de ciclo en la que cada borde del gráfico participa como máximo en dos vectores de base.
Para cualquier ciclo c en un gráfico G , se puede formar un vector m -dimensional 0-1 que tenga un 1 en las posiciones de coordenadas correspondientes a los bordes en c y un 0 en las posiciones de coordenadas restantes. El espacio de ciclo C ( G ) de la gráfica es el espacio vectorial formado por todas las posibles combinaciones lineales de vectores formados de esta manera. En la caracterización de Mac Lane, C ( G ) es un espacio vectorial sobre el campo finito GF(2) con dos elementos; es decir, en este espacio vectorial, los vectores se suman en coordenadas módulo dos. Una base 2 de G es una base de C ( G ) con la propiedad de que, para cada arista e en G , como máximo dos vectores de base tienen coordenadas distintas de cero en la posición correspondiente a e . Luego, dicho más formalmente, la caracterización de Mac Lane es que las gráficas planas son exactamente las gráficas que tienen una base 2.
Una dirección de la caracterización establece que todo gráfico plano tiene una base 2. Tal base se puede encontrar como la colección de límites de las caras acotadas de una incrustación plana del gráfico G dado .
Si una arista es un puente de G , aparece dos veces en el límite de una sola cara y, por lo tanto, tiene una coordenada cero en el vector correspondiente. Así, las únicas aristas que tienen coordenadas distintas de cero son las que separan dos caras diferentes; estos bordes aparecen una vez (si una de las caras es ilimitada) o dos veces en la colección de límites de caras limitadas. Queda por demostrar que estos ciclos forman una base. Una forma de demostrar esto es por inducción. Como caso base, G es un árbol, entonces no tiene caras acotadas y C ( G ) es de dimensión cero y tiene una base vacía. De lo contrario, eliminar una arista de la cara ilimitada de G reduce en uno tanto la dimensión del espacio del ciclo como el número de caras limitadas y se sigue la inducción.
Alternativamente, es posible utilizar la fórmula de Euler para mostrar que el número de ciclos en esta colección es igual al rango del circuito de G , que es la dimensión del espacio de ciclos. Cada subconjunto de ciclos no vacío tiene una suma vectorial que representa el límite de la unión de las caras acotadas en el subconjunto, que no puede estar vacío (la unión incluye al menos una cara acotada y excluye la cara no acotada, por lo que debe haber algunas aristas que separen a ellos). Por lo tanto, no existe un subconjunto de ciclos cuyos vectores sumen cero, lo que significa que todos los ciclos son linealmente independientes . Como conjunto linealmente independiente del mismo tamaño que la dimensión del espacio, esta colección de ciclos debe formar una base.
O'Neil (1973) proporcionó el siguiente argumento simple para la otra dirección de la caracterización, basado en el teorema de Wagner que caracteriza los grafos planos por menores prohibidos . Como observa O'Neill, la propiedad de tener una base 2 se conserva en los gráficos menores : si uno contrae una arista, se puede realizar la misma contracción en los vectores de base, si se elimina una arista que tiene una coordenada distinta de cero en una sola vector base, entonces ese vector puede eliminarse de la base, y si se elimina un borde que tiene una coordenada distinta de cero en dos vectores base, entonces esos dos vectores pueden reemplazarse por su suma (módulo dos). Además, si C ( G ) es una base cíclica para cualquier gráfico, entonces debe cubrir algunas aristas exactamente una vez, porque de lo contrario su suma sería cero (imposible para una base), por lo que C ( G ) puede aumentarse en una base más. ciclo que consiste en estos bordes cubiertos individualmente, preservando la propiedad de que cada borde se cubra como máximo dos veces. Sin embargo, el gráfico completo K 5 no tiene bases 2: C ( G ) es de seis dimensiones, cada vector no trivial en C ( G ) tiene coordenadas distintas de cero para al menos tres aristas, por lo que cualquier base aumentada tendría al menos 21 puntos distintos de cero. , superando los 20 distintos de cero que se permitirían si cada uno de los diez bordes fuera distinto de cero en como máximo dos vectores de base. Por un razonamiento similar, el gráfico bipartito completo K 3,3 no tiene base 2: C ( G ) es de cuatro dimensiones, y cada vector no trivial en C ( G ) tiene coordenadas distintas de cero para al menos cuatro aristas, por lo que cualquier base aumentada tener al menos 20 distintos de cero, superando los 18 distintos de cero que se permitirían si cada uno de los nueve bordes fuera distinto de cero en como máximo dos vectores de base. Dado que la propiedad de tener una base 2 es menor cerrada y no es cierta para los dos gráficos no planos mínimos menores K 5 y K 3,3 , tampoco es cierta para ningún otro gráfico no plano.
Lefschetz (1965) proporcionó otra prueba, basada en topología algebraica . Utiliza una formulación ligeramente diferente del criterio de planaridad, según la cual un gráfico es plano si y sólo si tiene un conjunto de ciclos (no necesariamente simples) que cubren cada arista exactamente dos veces, de modo que la única relación no trivial entre estos ciclos en C ( G ) es que su suma sea cero. Si este es el caso, entonces dejar fuera cualquiera de los ciclos produce una base que satisface la formulación del criterio de Mac Lane. Si un gráfico plano está incrustado en una esfera, sus ciclos de caras satisfacen claramente la propiedad de Lefschetz. Por el contrario, como muestra Lefschetz, siempre que un gráfico G tiene un conjunto de ciclos con esta propiedad, necesariamente forman los ciclos faciales de una incrustación del gráfico en la esfera.
Ja'Ja' y Simon (1982) utilizaron el criterio de planaridad de Mac Lane como parte de un algoritmo paralelo para probar la planaridad del gráfico y encontrar incrustaciones planas. Su algoritmo divide el gráfico en componentes triconectados , después de lo cual hay una incrustación plana única (hasta la elección de la cara exterior) y se puede suponer que los ciclos en base 2 son todos los ciclos periféricos del gráfico. Ja'Ja' y Simon comienzan con una base de ciclo fundamental del gráfico (una base de ciclo generada a partir de un árbol de expansión formando un ciclo para cada combinación posible de una ruta en el árbol y un borde fuera del árbol) y la transforman en una 2-base de ciclos periféricos. Estos ciclos forman las caras de una incrustación plana del gráfico dado.
El criterio de planaridad de Mac Lane permite contar fácilmente el número de ciclos de caras acotados en un gráfico plano, como el rango de circuito del gráfico. Esta propiedad se utiliza para definir el coeficiente de mallado del gráfico, una variante normalizada del número de ciclos de caras acotadas que se calcula dividiendo el rango del circuito por 2 n − 5 , el número máximo posible de caras acotadas de un gráfico plano con el mismo conjunto de vértices (Buhl et al. 2004).