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)
• ()

---

(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)(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)(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)(ejm)(ejm)(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)

---