Unidad 1

TEORÍA DE GRAFOS

🧠 1. Idea central

Un grafo es una forma de representar relaciones.

👉 Piensa en:

Redes sociales (personas = vértices, relaciones = aristas)

Mapas (ciudades = vértices, carreteras = aristas)

Internet, circuitos, etc.

🔹 2. Conceptos fundamentales (base de TODO)

✔ Grafo

Un grafo es:

Vértices (nodos)

Aristas (conexiones)

✔ Tipos

No dirigido → relaciones mutuas

Dirigido → relaciones con dirección (flechas)

✔ Terminología clave

Adyacencia → dos vértices están conectados

Incidencia → relación vértice-arista

Grado → número de aristas que llegan a un vértice

Camino → secuencia de vértices conectados

Ciclo → camino que empieza y termina en el mismo vértice

👉 Esto es básico para TODO lo demás.

🔹 3. Representación de grafos

💡 Aquí pasas de dibujo → matemática/programación

✔ Matriz de adyacencia

Tabla NxN

1 si hay conexión, 0 si no

👉 Muy importante en exámenes

✔ Lista de adyacencia

Cada vértice tiene su lista de vecinos

Más eficiente en programación

✔ Matriz de incidencia

Relaciona vértices con aristas

🔹 4. Isomorfismo de grafos

💡 IDEA CLAVE: Dos grafos son iguales aunque estén dibujados distinto

👉 Se verifica con:

Mismos grados

Misma cantidad de aristas

Misma estructura

⚠ ERROR común: fijarse solo en la forma visual

🔹 5. Grafos planos

💡 Un grafo es plano si puedes dibujarlo sin que se crucen aristas

✔ Fórmula de Euler:

V - E + F = 2

👉 MUY IMPORTANTE (sale en examen)

✔ No planos famosos

K₅

K₃,₃

👉 Si aparece uno de estos → NO es plano

🔹 6. Ruta más corta (clave en informática)

✔ Algoritmo de Dijkstra

💡 Sirve para encontrar el camino más corto

Ejemplo:

GPS

Redes

✔ Idea:

Empiezas en un nodo

Vas actualizando distancias mínimas

Siempre eliges el más cercano

👉 Esto es MUY preguntado