Ejercicios resueltos de conceptos básicos y representaciones

Para un grafo no dirigido con 5 vértices, la matriz es $5 \times 5$ simétrica:

$$M = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}$$

donde las filas/columnas corresponden a A, B, C, D, E respectivamente.

• $\deg(A) = 2$ (conectado a B, C)
• $\deg(B) = 2$ (conectado a A, D)
• $\deg(C) = 2$ (conectado a A, D)
• $\deg(D) = 3$ (conectado a B, C, E)
• $\deg(E) = 1$ (conectado a D)

$\sum_{v \in V} \deg(v) = 2 + 2 + 2 + 3 + 1 = 10 = 2|E| = 2 \times 5$ $\checkmark$

Para $K_n$: $|V| = n$, $|E| = \frac{n(n-1)}{2}$

Matriz de adyacencia:

• Espacio: $O(n^2)$
• Verificar adyacencia: $O(1)$
• Encontrar vecinos: $O(n)$

Lista de adyacencia:

• Espacio: $O(n + n(n-1)) = O(n^2)$
• Verificar adyacencia: $O(n)$
• Encontrar vecinos: $O(n)$

Para un árbol: $|V| = n$, $|E| = n-1$

Matriz de adyacencia:

• Espacio: $O(n^2)$
• Verificar adyacencia: $O(1)$
• Encontrar vecinos: $O(n)$

Lista de adyacencia:

• Espacio: $O(n + 2(n-1)) = O(n)$
• Verificar adyacencia: $O(\deg(v))$ promedio $O(1)$
• Encontrar vecinos: $O(\deg(v))$ promedio $O(1)$

• Para grafos densos ($K_n$): Ambas representaciones usan $O(n^2)$ espacio, matriz es mejor para consultas
• Para grafos dispersos (árboles): Lista de adyacencia es significativamente más eficiente en espacio: $O(n)$ vs $O(n^2)$

Con 4 vértices etiquetados, el número máximo de aristas es $\binom{4}{2} = 6$.

Cada arista puede estar presente o ausente, por lo tanto hay $2^6 = 64$ grafos diferentes.

• 0 aristas: $\binom{6}{0} = 1$ grafo (4 vértices aislados)
• 1 arista: $\binom{6}{1} = 6$ grafos
• 2 aristas: $\binom{6}{2} = 15$ grafos
• 3 aristas: $\binom{6}{3} = 20$ grafos
• 4 aristas: $\binom{6}{4} = 15$ grafos
• 5 aristas: $\binom{6}{5} = 6$ grafos
• 6 aristas: $\binom{6}{6} = 1$ grafo ($K_4$ completo)

• 0 aristas: $\chi(G) = 1$ (todos los vértices mismo color)
• 1 arista: $\chi(G) = 2$ (los dos vértices conectados necesitan colores diferentes)
• 2 aristas:
• Si las aristas no comparten vértice: $\chi(G) = 2$
• Si comparten un vértice: $\chi(G) = 2$
• 3 aristas:
• Si forman un triángulo: $\chi(G) = 3$
• Si forman un camino: $\chi(G) = 2$
• 4, 5, 6 aristas: Depende de la estructura, pero máximo $\chi(K_4) = 4$

• $K_4$ (grafo completo): $\chi(K_4) = 4$
• Ciclo $C_4$: $\chi(C_4) = 2$ (grafo bipartito)
• Árbol con 4 vértices: $\chi(T) = 2$

En un grafo simple $G$ con $n$ vértices:

• Cada vértice puede tener grado entre $0$ y $n-1$ (inclusive)
• Hay $n$ posibles valores de grado: $\{0, 1, 2, \ldots, n-1\}$
• Tenemos $n$ vértices para asignar a $n$ posibles grados

Observación clave: no pueden existir a la vez un vértice de grado $0$ y otro de grado $n-1$ (este último estaría conectado con el primero).

Caso 1: Si existe un vértice de grado $0$ (aislado):

• Ningún vértice tiene grado $n-1$, así que los $n$ grados están en $\{0, 1, \ldots, n-2\}$
• Hay $n$ vértices y solo $n-1$ valores posibles

Caso 2: Si no existe ningún vértice de grado $0$:

• Los $n$ grados están en $\{1, 2, \ldots, n-1\}$
• De nuevo hay $n$ vértices y solo $n-1$ valores posibles

En ambos casos, por el principio del palomar, al menos dos vértices tienen el mismo grado (para $n \geq 2$).

Grados posibles: $\{0, 1, 2, 3, 4, 5\}$

Estructuras especiales:

• Grafo completo $K_6:$ Todos los vértices tienen grado $5$
• Grafo vacío: Todos los vértices tienen grado $0$
• Estrella: Un vértice grado $5$, cinco vértices grado $1$
• Ciclo $C_6$ Todos los vértices tienen grado $2$

Consideremos un grafo con secuencia de grados $(5, 4, 3, 2, 1, 0)$:

• El vértice de grado $5$ está conectado a todos los demás
• Pero el vértice de grado $0$ no está conectado a nadie
• Contradicción: el vértice de grado $5$ no puede estar conectado al de grado $0$

La demostración confirma que siempre existe al menos un par de vértices con el mismo grado, lo que limita significativamente las estructuras posibles de grafos.