Teoría de Grafos

🇲🇽 Notas de clase (UNAM)

🎲 Clase 1 y 2:

• Definición de gráfica, orden y tamaño.
• Grado de vértices.
• Grado máximo y mínimo de una gráfica.
• Isomorfismo de grafos.
• Tipos importantes de gráficas (Completas, bipartitas, ciclos, caminos, regulares y la gráfica de Petersen).
• Matriz de adyacencia e incidencia.
• Subgráficas, subgraficas inducida y generadora.
• Gráficas autocomplementarias.
• Caminos en gráficas (walk, trail, and path).

🎲 Clase 3:

• Conexidad y componentes conexas.
• Vértices de corte y puentes.
• Árboles.
• Definición de distancia, diámetro y cuello.

🎲 Clase 4:

• Operaciones en gráficas: Unión, producto cuadro, producto cruz, producto fuerte y producto lexicográfico.
• n-cubo.
• Bloques.

🎲 Clase 5:

• Gráfica de líneas.

🎲 Clase 6:

• Clanes (o clique) y gráfica de clanes.
• Bloque de una gráfica.
• Gráfica de bloques.
• Gráfica de bloques y cortes.

🎲 Clase 7:

• Homomorfiamo de gráficas (Tipo I y II)
• Isomorfismo y automorfismo de gráficas
• Grupo de automorfiamos de una gráfica
• Gráfica de Cayley

🎲 Clase 8 y 9:

• Recorridos en gráficas: Gráfica de Euler.
• El problema del cartero chino.

🎲 Clase 10:

• Recorridos en gráficas: Gráfica hamiltoniana
• Problema del movimiento del caballo (ajedrez)
• Teorema de Ore
• K-cerradura
• Gráfica hamiltonianamente conexa
• Problema del agente viajero

🎲 Clases 12 y 13:

• Planaridad (gráficas planas y gráficas aplanables)
• Gráfica dual
• Teorema de Euler (Fórmula de Euler)
• Gráfica plana máxima
• Menor de una gráfica
• Subdivisión de una gráfica

🎲 Clase 14:

• Gráficas homeomorfas
• Teorema de Kuratowski
• Gráfica de Heawood
• Gráfica 3-conexa

🎲 Clases 15 y 16:

• Encaje de 2-celdas
• Género de una superficie y género de una gráfica
• Género mínimo y género máximo
• Característica de Euler
• Número de cruce de una gráfica
• Número de cruce rectilineo de una gráfica

🎲 Clase 17 y 18:

• Coloración de gráficas
• Coloración propia
• Número crimático, acromático y pseudoacromático
• Coloración completa
• Clase cromática
• Teorema de Brooks
• Número de clan
• Gráfica de Grötzsch

🎲 Clase 19, 20 y 21:

• Teorema de los 5 colores
• Teorema de los 4 colores
• Teorema de Heawood
• Polinimio cromático
• Caracteristicas del polinomio cromático
• k-regiones coloreables
• Gráfica dual en una superficie
• Coloración de aristas
• Índice cromático
• Teorema de Vizing y grafos tipo I y II
• Cuello de una gráfica y Snacks
• Número cromático total
• Número de independencia

🎲 Clases 22 y 23

• Teoría extremal de gráfica
• Número de Turán
• Gráfica k-partita completa (casi regular)
• Teorema de Turán
• Número de Ramsey (Distintas versiones)
• Teorema de Chvátal
• Número de Ramsey bipartita

🎲 Clase 24 y 25

• Matching o apareamiento
• Apareamiento, vértices M-saturados y apareamientos perfectos y máximos
• Trayectorias M-alternantes
• Apareamiento M-aumentante
• Teorema de Berge
• Teorema de Hall, sistema de representantes y versión conjuntista del teorema de Hall
• Teorema de Tutte
• Teorema de Petersen
• Factor de una gráfica y factorización de una gráfica
• r-factor y r-factorización de una gráfica (1-factorización)
• Factorización hamiltoniana

🎲 Clase 26

• Grafos dirigidos
• Gráfica subyacente
• Conexidad
• Gráfica de condensación
• Extrado, ingrado, pozo y fuente
• Digráfica transitiva
• Matriz de adyacencia
• Orientación de gráficas
• Antotrayectorias y anticonexidad
• Torneos, marcadores y sucesión de marcadores

🎲 Clase 27 y 28

• Conexidad (k-conexidad)
• Conexidad líneal
• Conexidad local
• Teorema de Menger para vértices
• Teorema de Menger para aristas
• Flujos
• Ecuaciones de conservación
• Flujo máximo
• Corte de flujo y capacidad
• Teorema de Ford y Fulkenson
• Teorema de flujo-máximo-cortadura mínima