Teoría de grafos matriz de adyacencia

Question

¿Es posible que exista un grafo que cumpla estas condiciones?

Para un Grafo G, la matriz de adyacencia tiene todos los $1$'s en la primera fila y todos los $0$'s en la segunda fila.

Lo que pienso: Tal grafo no puede existir porque si hubiera $1$'s en la primera fila, significa que v1 está conectado con cada vértice en el grafo G. Sin embargo, al ser todas las $0$'s en la segunda fila indica que no hay ningún vértice conectado a v2, lo cual es una contradicción.

¿Estoy en lo correcto?

También otra pregunta, ¿en una matriz de adyacencia un bucle = 2 en la matriz?

Answer 1

Si estás tratando con un grafo no dirigido, la matriz de adyacencia es una matriz simétrica. Por lo tanto, $a_{12} = a_{21}$. Por lo tanto, la matriz de adyacencia no puede representar un grafo no dirigido.

Sin embargo, si estás hablando de la matriz de adyacencia para un grafo dirigido, entonces la segunda fila puede ser cero, si no hay aristas que emanen del segundo vértice (dependiendo de la convención que elijas).

Answer 2

También otra pregunta, ¿con una matriz de adyacencia un bucle = 2 en la matriz?

Este es un asunto de definición, y como tal, podemos elegir. Las posibilidades obvias son $1$ o $2$. Entonces, ¿cuál es mejor?

En este caso, hay una buena razón para escribir $1$ para un bucle en la matriz de adyacencia. Es decir, siempre que escribamos $1$ para bucles en la matriz de adyacencia, si $A=(A[i,j])$ es la matriz de adyacencia de un grafo, entonces $A^k[i,j]$ es el número de caminos de longitud $k$ de $i$ a $j$.

Sin embargo, para el grado del vértice, puede ser mejor contar un bucle como contribuyendo $2$, de lo contrario, el Lema de Estrechamiento de Manos no funcionaría (o, al menos, necesitaría ajustes).