Yachakaj: Teoría de Grafos

 Grafos dirigidos y no dirigidos.
 Tipos de grafos simples: Camino simple, Ciclo, Completo, Bipartito (caracterización), Bipartito Completo y Rueda.
 Secuencia de grados de un grafo: Lema del apretón de manos, algoritmo Havel-Hakimi.
 Homomorfismo e isomorfismo de grafos.
---
 Grafo conexo.
 Distancia entre dos vértices, excentricidad de un vértice, radio, diámetro y centro de un grafo.
 Operaciones: Complemento de un grafo, eliminación de un vértice y una arista, subdivisión y contracción de una arista.
 Matriz de adyacencia, conteo de caminos de longitud k.
------
 Tipos de trayectorias: Recorrido y Circuito.
 Camino y Grafo Euleriano.
 Camino y Grafo Hamiltoniano: Teorema de Ore, Dirac y Bondy– Chvátal.
----
 Grafo de Ramanujan.
 Grafos fuertemente regulares (Grafo de Peterson)
 Algoritmo de Dijkstra
-----
Arboles:
 Definición y caracterización de un árbol.
 Isomorfismo de árboles
 Automorfismo de un árbol
 Codificación de un árbol
--------
 Árbol recubridor: Formula de Cayley
 Algoritmo de Kruskal
----
Graficando grafos en el plano:
 Grafo planar y planar maximal.
 Grafos homeomorfos
 Teorema de Kuratowski
 Género de un grafo
 Fórmula de Euler.
(poliedros)
----
 Grafo extraplanar.
 Teorema de Wagner
 Coloración de un vértice (número cromático).
 Teorema de Brooks
-------
 Polinomio cromático.
 Formula de eliminación y contracción de aristas.
----
 Coloración de aristas (número cromático)
 Teorema de Vizing, Ramsey, Turán y Schur

(grafos)

(def: grafo)(obs)
(representación de un grabo)(obs)

(grafos importantes)

(grafo completo K_n)
(ciclo C_n)
(ruta P_n)
(grafo bipartito K_(n,m))

(grafos isomorfos)

(def 2: isomorfos)(ejm)(ejm)

(subgrafos)

(def 3: subgrafo)
(def 4: subgrafo inducido)(ejm)
(camino de un grafo)(ejm de camino)
(ciclo de un grafo)(ejm de ciclo)

(conexidad)

(grafos conexos)
(camino)(ejm)
(componentes de un grafo)
(teorema 1)

(distancia de grafos)

(distancia)
(función distancia o métrica de un grafo)
(espacio métrico)

(matriz de adyacencia)

(def 1: matriz de adyacencia)(ejm)
(proposición 1)
(corolario 1)

(secuencia de grado (score) de un grafo)

(def 2: grafo de vértice)
(def 3: secuencia de grado)
(obs)(ejm)
(proposición 2)
(corolario 2: lema de handshake (apretón de manos) )
(teorema 1: teorema del score)

(grafos eurelianos; grafos eurelianos dirigidos; principio del Palomar)
(grafos eurelianos)

(introducción)
(def: recorrido cerrado eureliano)
(def: grafo eureliano)
(teorema 2: caracterización de grafos eurelianos)
(lema)

(grafos eurelianos dirigidos)

(def: aristas dirigidas)
(def: recorrido dirigido)
(consecuencias)
(proposición)
(proposición)

(grafo 2-conexo)

(def: k-vértice conexo)

(operaciones en grafos)

(eliminación de una arista)
(adición de una nueva arista)
(eliminación de un vértice)
(subdivisión de una arista)(ejm)

(caracterización de grafos 2-conexo)

(teorema)
(proposición)
(teorema)

(grafos libres de triángulos)

(grafos libres de triángulos)(casos particulares)
(teorema 1, 2)
(teorema)

(árboles)

(def 1: arboles)
(teorema 1: caracterización de árboles)
(def 2: vértice final)
(lema 1, 2)

(isomorfismo de árboles)

(def 3: árbol de raíz)
(def 4: árbol plantado)
(def 5: isomorfismo de árboles)
(def 6: isomorfismo de árboles con raíz)
(def 7: isomorfismo de árboles plantados)
(representación gráfica)(ejm 1)(ejm 2)(ejm)

(codificando los árboles)

(codificación de árboles plantados)
(decodificando códigos)
(codificando árboles con raíz)(¿qué significa A<B en el código anterior?)
(excentricidad de un vértice)
(centro de un grafo)
(proposición 1)
(código de un árbol)(ejm)(ejm)(ejm)(ejm)

(árbol de expansión de un grafo; noción del árbol de expansión mínima)
(árbol de expansión de un grafo)

(def: árbol de expansión de un grafo)(ejm)
(algoritmo: árbol de expansión)
(proposición)(ejm)

(el problema del árbol de expansión mínima)

(introducción)
(def: peso de una arista ; def: red o malla)(ejm)

(algoritmo de Kruskal)

(algoritmo de Kruskal)(ejm)
(proposición)
(el camino más corto)

(algoritmo Dijkstra)

(algoritmo Dijkstra)(ejm)

(grafos planares)

(def 1: arco)
(def 2: dibujo de un grafo)
(def 3: conjunto conexo)
(dibujo sobre otras superficies)

(superficie esférica)
(superficie del toro)
(superficie de la cinta del Mobius)
(esfera con dos asas)
(esfera con tres asas)
(botella de Klein)(obs)
(K_(3,3) y K_5 no son planares)
(K_5 sobre el toro)
(K_(3,3) sobre la banda de Mobius)

(proposición 1)
(def 4: género de un grafo planar)

(ciclos en grafos planares)

(def 5: curva de Jordan ; teorema 1: teorema de curva de Jordan)
(proposición 2)
(representación gráfica)(ejm 2)(caras y ciclos en grafos 2-conexos)
(proposición 3 ; teorema 2)

(fórmula de Euler)

(teorema 1)
(def 1: poliedro regular)
(poliedros regulares)
(proposición 1)
(proposición 2)
(proposición 3)

(coloración de mapas)

(def 2: coloración )(obs)
(propiedades)(ejm)
(def 3: grafo gradual)(ejm)
(teorema 2 ; proposición 4)
(números cromáticos conocidos)
(polinomio cromático)
(polinomios cromáticos de algunos grafos)(ejm: polinomio cromático del grafo lineal L_n)

(asdasd)

(sesión 7)

(grafos dirigidos y no dirigidos)

1. Identificar si un grafo es dirigido o no dirigido

(tipos de grafos simples:)
(camino simple)

2. Camino simple
3. Encontrar todos los caminos simples entre dos vértices

(ciclo)

4. Reconocer un ciclo

(grafos completos K_n)

5. Grafo completo K_n
6. Reconocer si un grafo es completo

(grafos bipartitos y caracterización)

7. Grafo bipartito
8. Caracterización fundamental de grafos bipartitos
9. Otro ejercicio de caracterización
10. Demostrar que un grafo NO es bipartito

(grafos bipartitos completos K_{m,n})

11. Grafo bipartito completo K_{m,n}
12. Reconstruir K_{m,n} a partir de grados

(grafos rueda W_n)

13. Grafo rueda W_n

(secuencia de grados)

14. Secuencia de grados

(lema del apretón de manos)

15. Lema del apretón de manos
16. Consecuencia: número de vértices de grado impar
17. Problema de aplicación del apretón de manos

(algoritmo Havel-Hakimi)

18. Havel-Hakimi: ¿una secuencia es gráfica?
19. Havel-Hakimi: ejemplo que SÍ es gráfico
20. Havel-Hakimi: ejemplo que NO es gráfico
21. Havel-Hakimi + apretón de manos

(homomorfismo de grafos)

22. Homomorfismo de grafos
23. Homomorfismo que NO es inyectivo

(isomorfismo de grafos)

24. Isomorfismo de grafos
25. Ejercicio clásico de isomorfismo
26. Encontrar el isomorfismo cuando los vértices están "desordenados"
27. ¿Cuándo dos grafos NO pueden ser isomorfos?
28. Problema de isomorfismo usando grados
29. Problema conceptual muy importante

(problemas combinados)

30. Problema combinado: grados + apretón de manos + tipo de grafo
31. Problema combinado de Havel-Hakimi
32. Ejercicio de verdadero/falso
33. Un contraejemplo importante
34. Problema de clasificación
35. Problema integrador tipo examen

(saber si o si)

(sesión 8)

(Grafo conexo)

1. Grafo conexo o no conexo

Ejemplo 1 — Determinar si un grafo es conexo

2. Grafo no conexo

Ejemplo 2

(Distancia entre dos vértices)

3. Distancia entre dos vértices

Ejemplo 3

4. ¡Cuidado! Distancia ≠ número de vértices
5. Distancias de todos los pares

(excentricidad de un vértice)

6. Excentricidad de un vértice

Ejemplo 4

7. Calcular todas las excentricidades

(radio, diámetro, centro)

8. Radio de un grafo
9. Diámetro de un grafo
10. Centro de un grafo

11. Ejercicio completo típico de examen
(matriz de adyacencia)

12. Matriz de adyacencia
13. Construir una matriz de adyacencia
14. Leer información de un grafo a partir de A

(conteo de caminos de longitud k)

15. Conteo de caminos de longitud 2
16. Ejemplo de A^2
17. Otro ejemplo: caminos de longitud 3
18. Ejercicio muy típico: "¿Cuántos caminos?"

()

19. Ejercicio inverso: te dan la matriz y debes reconstruir el grafo
20. Ejercicio combinado: matriz + distancias
21. Ejercicio combinado con A^2
22. Problema conceptual importante
23. Relación entre A^k y las distancias
24. Ejercicio de razonamiento

25. Problema de examen completo

(sesión 9)

(tipos de trayectoria: recorrido y circuito)
1. Identificar un recorrido
2. Distinguir recorrido de camino
3. Identificar un circuito
4. Ejercicio clásico: ¿es camino, circuito o ninguno?
(Eureliano)
5. Camino euleriano
6. Ejercicio Euler básico
7. Ejercicio: exactamente dos impares
8. Ejercicio donde NO existe camino euleriano
9. Ejercicio importante: 4 vértices impares
10. Problema tipo examen: encontrar el camino euleriano
(Hamiltoniano)
11. Ahora: Hamilton
12. Camino hamiltoniano vs circuito hamiltoniano
13. Ejercicio de identificación Hamilton
14. Ejercicio: camino Hamilton pero no circuito
15. Diferencia Euler vs Hamilton — ejercicio obligatorio
16. Un grafo puede ser Euleriano pero no Hamiltoniano
(Dirac)
17. Teorema de Dirac
18. Ejercicio de Dirac
19. Ejercicio donde Dirac NO permite concluir
(Oré)
20. Teorema de Ore
21. Ejercicio de Ore
22. Ejercicio típico de Ore
23. ¿Dirac u Ore?
24. Ejemplo donde Ore puede ser más útil
(Bondy-Chvátal)
25. Teorema de Bondy–Chvátal
26. Ejercicio de Bondy–Chvátal
27. Ejercicio de clausura paso a paso
28. Relación entre Dirac, Ore y Bondy–Chvátal
()

29. Problema tipo examen integrador
30. Otro problema integrador
31. Problema de verdadero/falso
32. Problema conceptual que debes saber explicar

33. Tabla de "qué hago en el examen"

(sesión 10)

PARTE I — GRAFOS DE RAMANUJAN
1. Ejercicio conceptual: ¿qué es un grafo de Ramanujan?
2. Ejemplo sencillo: C_5
3. Ejercicio de identificación4. Ejercicio donde NO es Ramanujan
PARTE II — GRAFOS FUERTEMENTE REGULARES
5. Definición que debes memorizar
6. Ejemplo fundamental: C_5
7. Ejercicio típico: ¿es fuertemente regular?
8. Ejemplo fundamental: grafo completo K_n
9. Ejemplo: K_{m,n}
10. Ejercicio usando la fórmula de conteo
PARTE III — COMPLEMENTO DE UN GRAFO
11. Definición
12. Ejemplo básico
13. Ejercicio de complemento usando grados
14. Complemento de un grafo regular
PARTE IV — ELIMINACIÓN DE UN VÉRTICE
15. ¿Qué significa eliminar un vértice?
16. Ejemplo
17. Ejercicio de conteo
PARTE V — ELIMINACIÓN DE UNA ARISTA
18. Definición
19. Ejemplo
20. Efecto sobre los grados
Ejemplo
PARTE VI — SUBDIVISIÓN DE UNA ARISTA
21. ¿Qué es subdividir una arista?
22. Ejemplo
23. Ejercicio de grados
PARTE VII — CONTRACCIÓN DE UNA ARISTA
24. ¿Qué significa contraer una arista?
25. Ejemplo sencillo
26. Diferencia FUNDAMENTAL: subdivisión vs contracción
PARTE VIII — PROBLEMA INTEGRADOR
27. Problema tipo examen
PARTE IX — PROBLEMAS QUE DEBERÍAS PODER RESOLVER SOLO
28. Ejercicio 1 — Complemento
29. Ejercicio 2 — Eliminación de vértice
30. Ejercicio 3 — Eliminación de arista
31. Ejercicio 4 — Subdivisión
32. Ejercicio 5 — Contracción
33. Ejercicio 6 — Fuertemente regular
34. Ejercicio 7 — No basta ser regular
35. Ejercicio 8 — Parámetros
36. Ejercicio 9 — Ramanujan
37. Ejercicio 10 — Ramanujan + interpretación

(sesión 11)

(definición y caracterización)

1. Reconocer si un grafo es árbol
2. Ejercicio clásico: demostrar que un grafo es árbol
3. Caracterización: camino único
4. Ejercicio inverso: camino único ⇒ árbol
5. Propiedad fundamental: eliminar una arista
6. Propiedad fundamental: agregar una arista

(isomorfismo)

7. Isomorfismo de árboles
8. Determinar si dos árboles son isomorfos
9. Ojo: misma secuencia de grados NO garantiza isomorfismo
10. Invariante de isomorfismo: número de hojas
11. Invariante: diámetro
12. Encontrar un isomorfismo

(automorfismo)

13. Automorfismo de un árbol
14. Automorfismos de un camino
15. Automorfismos de una estrella
16. Automorfismos: árbol con ramas iguales
17. Árbol con ramas diferentes

(codificación)

18. Codificación de un árbol: Prüfer
19. Obtener el código de Prüfer
20. Decodificar una secuencia de Prüfer
21. Relación entre Prüfer y grados ⭐

()

22. Problema combinado: Prüfer + grados
23. Problema combinado de examen
24. Problema de isomorfismo + Prüfer
25. Problema de automorfismos + grados
26. Ejercicio conceptual muy importante
27. Ejercicio de demostración típico

28. Resumen de lo que debes saber para el examen

(sesión 12)

(teoría)
(árbol recubridor)

1. Reconocer si un subgrafo es árbol recubridor
2. Encontrar un árbol recubridor de un grafo

(fórmula de Cayley)

3. Fórmula de Cayley: ejercicio directo
4. Cayley con 6, 7 y 10 vértices
5. Cayley: problema inverso
6. Cayley aplicado a árboles recubridores

(algoritmo de Kruskal)

7. Kruskal: ejercicio básico
8. Kruskal: ejercicio donde debes RECHAZAR una arista
9. Kruskal: problema de examen completo
10. ¿Por qué Kruskal funciona?

(algoritmo de Dijkstra)

11. Dijkstra: ejercicio básico
12. Dijkstra: reconstruir el camino mínimo
13. Dijkstra en formato de tabla
14. Dijkstra: identificar un error

()

15. Diferencia fundamental: Kruskal vs Dijkstra
16. Problema combinado — Kruskal vs Dijkstra
17. Pregunta teórica: ¿Kruskal siempre produce un árbol?
18. Pregunta teórica: ¿el MST es único?
19. Problema conceptual de Cayley + Kruskal
20. El problema que yo consideraría MÁS importante de la sesión

(lo que debes saber)

(sesión 13)
(sesión 14)
(sesión 15)
(sesión 16)
(sesión 17)
(sesión 18)

(grafos)

(def: grafo)

(obs)

(representación de un grabo)

(obs)

(grafos importantes)

(grafo completo K_n)

(ciclo C_n)

(ruta P_n)

(grafo bipartito K_(n,m))

(grafos isomorfos)

(def 2: isomorfos)

(ejm)

(subgrafos)

(def 3: subgrafo)

(def 4: subgrafo inducido)

(ejm)

(camino de un grafo)

(ejm de camino)

(ciclo de un grafo)

(ejm de ciclo)

(conexidad)

(grafos conexos)

(camino)

(ejm)

(componentes de un grafo)

(teorema 1)

(distancia de grafos)

(distancia)

(función distancia o métrica de un grafo)

(espacio métrico)

(matriz de adyacencia)

(def 1: matriz de adyacencia)

(ejm)

(proposición 1)

(corolario 1)

(score de un grafo)

(def 2: grafo de vértice; def 3: secuencia de grado)

(obs)

(ejm)

(proposición 2)

(corolario 2: lema de handshake)

(teorema 1: teorema del score)

(grafos eurelianos; grafos eurelianos dirigidos; principio del Palomar)

(introducción)

(def: recorrido cerrado eureliano; def: grafo eureliano)

(teorema 2: caracterización de grafos eurelianos)

(lema)

(grafos eurelianos dirigidos)(def: aristas dirigidas; def: recorrido dirigido)

(consecuencias)

(proposición)

(grafos 2-conexo; operaciones en grafo; grafos libres de triángulos)

(grafo 2-conexo)(def: k-vértice conexo)

(operaciones en grafos)

(ejm)

(teorema)

(proposición)

(teorema)

(grafos libres de triángulos)

(casos particuales)

(teorema 1, 2)

(teorema)

(árboles)

(def 1: arboles)

(teorema 1: caracterización de árboles)

(def 2: vértice final; lema 1, 2)

(isomorfismo de árboles)

(def 3: árbol de raíz ; def 4: árbol plantado)

(def 5: isomorfismo de árboles ; def 6: isomorfismo de árboles con raíz ; def 7: isomorfismo de árboles plantados)

(representación gráfica: ejm 1)

(ejm 2)

(ejm)

(codificando los árboles)

(codificación de árboles plantados)

(decodificando códigos)

(codificando árboles con raíz)

(¿qué significa A<B en el código anterior?)

(excentricidad de un vértice)

(centro de un grafo)

(proposición 1)

(código de un árbol)

(ejm)

(árbol de expansión de un grafo; noción del árbol de expansión mínima)

(def: árbol de expansión de un grafo)

(ejm)

(algoritmo: árbol de expansión)

(proposición)

(ejm)

(el problema del árbol de expansión mínima)(introducción)

(def: peso de una arista ; def: red o malla)

(ejm)

(algoritmo de Kruskal)

(ejm)

(proposición)

(el camino más corto)

(algoritmo Dijkstra)

(ejm)

(grafos planares)

(def 1: arco)

(def 2: dibujo de un grafo)

(def 3: conjunto conexo)

(dibujo sobre otras superficies)

(superficie esférica)

(superficie del toro)

(superficie de la cinta del Mobius)

(esfera con dos asas)

(esfera con tres asas)

(botella de Klein)

(obs)

(K_(3,3) y K_5 no son planares)

(K_5 sobre el toro)

(K_(3,3) sobre la banda de Mobius)

(proposición 1)

(def 4: género de un grafo planar)

(ciclos en grafos planares)

(def 5: curva de Jordan ; teorema 1: teorema de curva de Jordan)

(proposición 2)

(representación gráfica)(ejm 2)

(caras y ciclos en grafos 2-conexos)

(proposición 3 ; teorema 2)

(fórmula de Euler)

(teorema 1)

(def 1: poliedro regular)

(poliedros regulares)

(proposición 1)

(proposición 2)

(proposición 3)

(coloración de mapas)

(def 2: coloración )

(obs)

(propiedades)

(ejm)

(def 3: grafo gradual)

(ejm)

(teorema 2 ; proposición 4)

(números cromáticos conocidos)

(polinomio cromático)

(polinomios cromáticos de algunos grafos)

(ejm: polinomio cromático del grafo lineal L_n)

Yachakaj

Buscar este blog

domingo, 26 de abril de 2026

Teoría de Grafos

No hay comentarios.:

Publicar un comentario