UNIDAD 5 REPRESENTACION, ALGORITMO DE GRAFO

 BLOG UNIDAD 5 REPRESENTACION, ALGORITMOS DE GRAFO 

Los gráfos son estructuras matemáticas que se utilizan para modelar relaciones y conexiones entre objetos. son lo mas importante en las matemáticas discretas debido que a su amplia aplicación en áreas como algoritmos o redes eh inteligencia artificial. 

 ¿Qué es un Grafo?

Un grafo$\mathrm{<span\; style="vertical-align:\; inherit;"> se\; define\; como\; un\; par\; ordenado:</span>}$

$$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">GRAMO</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">V</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">mi</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>$$G = (V, E),

Dónde:

• $\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">V</span></span>}$V : Conjunto devérticeso nodos ($\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid </span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">V</span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">norte</span></span>}$|V| = n ).
• $\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">mi</span></span>}$mi : Conjunto dearistaso conexiones entre pares de vértices ($\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid </span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">mi</span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid </span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">metro</span></span>}$|E| = m ).

Los grafos pueden ser:

1. Dirigidos: Los aristas tienen dirección (ej. un gráfico que representa seguidores en redes sociales).
2. No dirigidos: Las aristas no tienen dirección (ej. una red de carreteras).

 Tipos de Representación de Gráficos

Matriz de Adyacencia

Es una matriz cuadrada de tamaño$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">norte</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\times </span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">norte</span></span>}$n \veces n , donde$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">norte</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid </span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">V</span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid </span></span>}$n = |V| . Cada elemento$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">a</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">[</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">i</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">]</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">[</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">yo</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">]</span></span>$a[i][j] indica si existe una arista entre el vértice$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">i</span></span>}$i y el vértice$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">yo</span></span>}$yo ..

Ventajas:

• Fácil de implementar.
• Permite verificar si hay una conexión entre dos nodos en el tiempo$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">Oh</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)</span></span>$O(1) .

Desventajas:

• Consume mucho espacio ($\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">Oh</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(</span></span>{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">norte</span></span>}}^{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">2</span></span>}}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)</span></span>$O(n^2)), incluso para gráficos dispersos.

Ejemplo:
Para un grafo con$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">V</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\{</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">A</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">do</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\}</span></span>$V = \{A, B, C\} y$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">mi</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\{</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">A</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">do</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\}</span></span>$E = \{(A, B), (B, C)\} :

$$\text{<span style="vertical-align: inherit;"><span style="vertical-align: inherit;">Matriz de adyacencia:</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">[</span></span>\begin{array}{ccc}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">0</span></span>}& \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span>}& \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">0</span></span>}\\ \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span>}& \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">0</span></span>}& \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span>}\\ \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">0</span></span>}& \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span>}& \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">0</span></span>}\end{array}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">]</span></span>$$\text{Matriz de adyacencia:} \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}

---

Lista de Adyacencia

Es una lista donde cada vértice tiene asociada una lista de los vértices con los que están conectados.

Definición: 

• $\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">Cada\; vértice</span> tiene\; una\; lista\; de\; vértices\; adyacentes\; (sus\; vecinos).</span>}$

Ventajas:

• Eficiente en términos de espacio ($\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">Oh</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">norte</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">+</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">metro</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)</span></span>$O(n+m) ).
• Mejores párrafos dispersos.

Desventajas:

• Verificar si hay una conexión entre dos nodos puede tomar$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">Oh</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">d</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)</span></span>$Sobredosis) , donde$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">d</span></span>}$d es el grado del vértice.

Ejemplo:
Para el mismo grafo con$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">V</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\{</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">A</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">do</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\}</span></span>$V = \{A, B, C\} y$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">mi</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\{</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">A</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">do</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\}</span></span>$E = \{(A, B), (B, C)\} :

$$\text{<span style="vertical-align: inherit;"><span style="vertical-align: inherit;">Lista de adyacencia:</span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">A</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">:</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B</span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">:</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">A</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">do</span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">do</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">:</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B</span></span>}$$\text{Lista de adyacencia:} A: B B: A, C C: B

---

Matriz de incidencia

Es una matriz de tamaño $\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">norte</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\times </span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">metro</span></span>}$n \veces m , donde$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">norte</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid </span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">V</span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid </span></span>}$n = |V| y$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">metro</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid </span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">mi</span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid </span></span>}$m = |E| . Cada columna representa una arista y cada fila un vértice.

Definición:

• Si el vértice$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">i</span></span>}$i conectado a la arista$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">yo</span></span>}$yo , el valor es$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span>}$1 .
• En los gráficos dirigidos:$<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">-</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span>}$-1 para el vértice de inicio,$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span>}$1 para el vértice de destino.

Ventajas:

• Útil para ciertas operaciones algebraicas en teoría de gráficos.

Desventajas:

• Menos intuitivas y eficientes para operaciones básicas.

Ejemplo:
Para$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">V</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\{</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">A</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">do</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\}</span></span>$V = \{A, B, C\} y$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">mi</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\{</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">A</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,</span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">do</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)</span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\}</span></span>$E = \{(A, B), (B, C)\} :

$$\text{<span style="vertical-align: inherit;"><span style="vertical-align: inherit;">Matriz de incidencia:</span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">[</span></span>\begin{array}{cc}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span>}& \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">0</span></span>}\\ \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span>}& \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span>}\\ \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">0</span></span>}& \mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span>}\end{array}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">]</span></span>$$\text{Matriz de incidencia:} \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix}

---

 Represento una elección 

La elección entre matriz de adyacencia, lista de adyacencia o matriz de incidencia depende de:

1. Densidad del grafo: Si$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">metro</span></span>}$metro (número de aristas) es mucho menor que${\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">norte</span></span>}}^{\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">2</span></span>}}$n^2 , una lista de adyacencia suele ser más eficiente.
2. Operaciones frecuentes:
   • Para verificar conexiones rápidamente: Matriz de adyacencia.
   • Para recorrer aristas de un vértice: Lista de adyacencia.
3. Espacio disponible: Las listas son más compactas para gráficos dispersos.

   terminado y gracias paola erika cabrera rojas