¿Hay algún teorema que relacione el número de coincidencias perfectas en un gráfico no bipartito con su permanente?

Answer 1

Los gráficos no bipartitos no tienen matrices de biadjacencia.

Todos los gráficos tienen matrices de adyacencia. La matriz de adyacencia de un gráfico bipartito es especial porque puede dividirse en cuatro cuadrantes con los dos cuadrantes a lo largo de la diagonal principal llenos de ceros. El cuadrante superior derecho es una submatriz, que llamamos matriz de biadjacencia. El cuadrante inferior izquierdo es su transposición. Podemos construir la matriz de adyacencia completa solo a partir de la matriz de biadjacencia, de modo que toda la información sobre el gráfico bipartito está contenida dentro de la matriz de biadjacencia.

Un gráfico m, n-bipartito tendrá una matriz de biadjacencia mXn. Cada una de las m filas yn columnas corresponderá a un vértice. A diferencia de la matriz de adyacencia completa, cada vértice está representado por una fila o una columna, no por ambas.

Ahora pregúntese “¿por qué el permanente de una matriz de biadjacencia de un gráfico bipartito es igual al número de coincidencias perfectas en un gráfico bipartito?”

El permanente de una matriz 0-1 es solo la cantidad de formas de seleccionar un subconjunto de los 1 de modo que cada fila y columna contenga solo un elemento individual del subconjunto. En una matriz de biadjacencia, cada uno de estos subconjuntos representa una coincidencia perfecta. Cada ‘1’ representa una arista, lo que significa que cada vértice (fila y columna) tiene una y solo una arista.

Ahora, ¿qué representaría el permanente de una matriz de adyacencia completa?
Bueno, ¿qué representaría un solo subconjunto de 1 que cubra cada fila y columna exactamente una vez? La respuesta a la segunda pregunta sería qué contaría el permanente. Suponiendo que estamos tratando con gráficos simples, de modo que ningún vértice pueda tener un borde en sí mismo, cada ‘1’ en el gráfico de adyacencia tendría un número de fila diferente de su número de columna. Por ejemplo, supongamos que hay un ‘1’ en la fila 3 col 5. Entonces todavía no hemos cubierto la fila 5, por lo que necesitamos otro ‘1’, digamos en la fila 5, col 4. Observe que los dos bordes que tenemos acaba de representarse en el vértice 5, porque la fila 5 y la columna 5 representan el vértice 5. Si completamos la cobertura de filas y columnas, encontraremos que hemos generado un conjunto de ciclos que cubren todos los vértices.

Entonces, eso es lo que cuenta el permanente de la matriz de adyacencia completa: varias formas de cubrir los vértices de un gráfico con uno o más ciclos, de modo que cada vértice pertenezca a un solo ciclo. Eso es muy diferente a contar combinaciones perfectas.

Quizás esté pensando, ¿qué hay de crear una submatriz de la matriz de adyacencia para gráficos no bipartitos similar a la matriz de biadjacencia para gráficos bipartitos? Eso no funcionará porque no puede dividir los vértices de un gráfico no bipartito en dos conjuntos, de modo que cada conjunto no tenga bordes. Si representa el vértice A con una fila y sin columna, y el vértice B con una fila y sin columna, entonces, ¿cómo representa un borde de A a B? No puedes Es por eso que solo los gráficos bipartitos pueden tener matrices de biadjacencia.