Determinar el ciclo a partir de la matriz de adyacencia

Question

¿Existe una forma/algoritmo para determinar si hay un ciclo en un grafo si sólo tengo la matriz de adyacencia y no puedo visualizar el grafo?

Answer 1

Que los vértices de $G$ ser etiquetado $v_1,\ldots,v_n$ y la matriz de adyacencia de $G$ sea $A$ con fila/columna $i$ de $A$ corresponden a $v_i$ .

Si desea un enfoque puramente algebraico lineal (aunque no constructivo), considere $L=D-A$ , donde $D$ es la matriz diagonal con $(D)_{i,i}=\deg(v_i)$ . Esta matriz se denomina Laplaciano matriz de $G$ . Un hecho básico es que el número de veces que el cero aparece como un valor propio de $L$ es decir, $n-\text{rank}(L)$ es el número de componentes conectados de $G$ .

Reclamación : $G$ es acíclico si y sólo si $\text{trace}(L)=2\text{rank}(L).$

Equivalentemente, $G$ tiene un ciclo si y sólo si $$\text{trace}(L)\geq2(\text{rank}(L)+1).$$

Prueba : $G$ es acíclico si y sólo si es un bosque, es decir, $G$ tiene $c$ componentes y exactamente $n-c=\text{rank}(L)$ bordes. Por otro lado, por el Lema de Manipulación tenemos $|E(G)|=\frac{1}{2}\text{trace}(L)$ . El reclamo es el siguiente.