2 - Tipos de grafos

Este capítulo resume las variantes más habituales de grafos y cómo impactan en su modelado en C. Conocer la clasificación ayuda a elegir la representación (matriz o lista de adyacencia) y los algoritmos apropiados.

2.1 Grafo no dirigido

Las aristas no tienen orientación; la conexión entre u y v es bidireccional. En matrices de adyacencia esto se refleja con simetría (matriz[u][v] == matriz[v][u]).

• Modela relaciones mutuas: amistad, enlaces físicos, interconexiones de hardware.
• Las operaciones de grado cuentan cada arista una sola vez.

2.2 Grafo dirigido (digraph)

Las aristas tienen sentido de origen y destino. Se usan para dependencias o flujos unidireccionales.

• Las matrices dejan de ser simétricas y se habla de grado de entrada y grado de salida.
• Permiten detectar ciclos orientados y aplicar ordenamiento topológico.

2.3 Grafos ponderados

Cada arista almacena un peso (distancia, costo, capacidad). Los pesos pueden ser enteros, flotantes o incluso valores simbólicos que luego se interpretan.

• En matrices se guarda el valor del peso en vez de 0/1.
• Relevante para algoritmos de caminos mínimos y flujos.

2.4 Grafos no ponderados

Las aristas solo indican presencia o ausencia de conexión. Se modelan con booleanos (0/1) o listas simples de vecinos.

• Simples de almacenar y recorrer.
• Comunes en problemas de conectividad y componentes.

2.5 Grafos simples y multigrafos

Un grafo simple no tiene lazos (aristas que empiezan y terminan en el mismo vértice) ni aristas paralelas repetidas.

• Fácil de representar con matrices o listas sin contar duplicados.

Un multigrafo permite varias aristas entre los mismos vértices y lazos.

• En listas se suelen almacenar todas las instancias; en matrices puede representarse con conteos o listas de pesos.
• Se emplean en modelado de rutas con varias alternativas equivalentes.

2.6 Grafos completos

Cada par de vértices está conectado por una arista. En un grafo no dirigido con n vértices hay n(n-1)/2 aristas.

• Su densidad es máxima; en matrices de adyacencia casi todos los valores son 1 o un peso.
• Sirven como casos extremos para analizar complejidad de algoritmos.

2.7 Grafos bipartitos

Dividen los vértices en dos conjuntos disjuntos U y V de modo que todas las aristas conectan un vértice de U con uno de V. No hay aristas dentro del mismo conjunto.

• Se usan en problemas de emparejamiento, asignación y recomendación.
• Se pueden reconocer verificando que no existan ciclos de longitud impar.

2.8 Grafos dispersos y densos

La densidad mide cuántas aristas existen respecto del máximo posible. Un grafo denso tiene muchas aristas y se beneficia de matrices de adyacencia; uno disperso tiene pocas aristas y suele representarse mejor con listas.

• Elegir la estructura adecuada evita desperdicio de memoria y acelera las operaciones de recorrido.
• La clasificación influye en la elección de algoritmos (por ejemplo, Dijkstra con montículo para grafos dispersos).