# data[].attributes.body
La teoría de grafos es una rama de las matemáticas que estudia las relaciones entre objetos, modeladas mediante vértices (nodos) y aristas (conexiones). Esta teoría tiene gran importancia en ciencias como la informática, la ingeniería, la biología, la sociología y otras, debido a su capacidad para representar redes y estructuras complejas. Desde redes sociales hasta mapas de transporte o distribución de energía, los grafos permiten analizar, optimizar y resolver problemas reales de manera eficiente.

# data[].attributes.body
es una rama de las matemáticas que estudia las estructuras formadas por nodos (vértices) y las conexiones entre ellos (aristas). Esta teoría tiene aplicaciones fundamentales en campos como la informática, la ingeniería, la biología y las ciencias sociales. Su estudio permite modelar y resolver problemas relacionados con redes, rutas, conexiones y relaciones.

Un grafo es una pareja ordenada G = (V, E), donde V es un conjunto de vértices y E es un conjunto de aristas.
(Gross & Yellen, 2006)

# data[].attributes.body
Grafo simple: sin lazos ni múltiples aristas.

Multigrafo: permite múltiples aristas entre los mismos vértices.

Grafo dirigido (dígrafo): las aristas tienen una dirección.

Grafo ponderado: cada arista tiene un valor o peso.

Grafo completo: todos los nodos están conectados entre sí.

Grafo bipartito: los vértices se pueden dividir en dos conjuntos disjuntos, y todas las aristas conectan nodos de conjuntos distintos.

(Diestel, 2017)

# data[].attributes.body
Son los puntos o elementos fundamentales del grafo. Representan entidades como personas, estaciones, computadoras, etc.

Se denotan comúnmente con letras (A, B, C...).

El número de conexiones de un nodo se llama grado.

Los vértices representan los objetos del problema a modelar.
(Cormen et al., 2009)

# data[].attributes.body
Segmento o Camino

Un camino es una sucesión de aristas consecutivas que conectan un conjunto de vértices. Si no se repite ningún vértice, se llama camino simple.

Un camino de longitud k es una secuencia de k aristas que conectan k+1 vértices.
(Gross & Yellen, 2006)

# data[].attributes.body
Se refiere a un camino en el que no se repiten aristas ni vértices. Si una trayectoria inicia y termina en el mismo nodo, se llama ciclo o circuito.

Una trayectoria simple no repite vértices; un circuito sí, pero regresa al punto inicial.
(Diestel, 2017)

# data[].attributes.body
Un grafo es conexo si existe al menos un camino entre cada par de vértices. Si no es posible conectar ciertos nodos, se dice que es no conexo.

En grafos dirigidos se habla de fuertemente conexo si todos los nodos son alcanzables desde cualquier otro.

La conexidad es fundamental para estudiar la accesibilidad dentro de una red.
(Gross & Yellen, 2006)

# data[].attributes.body
Este teorema afirma que cualquier mapa plano puede ser coloreado con un máximo de cuatro colores, de modo que regiones adyacentes no compartan el mismo color. Es una aplicación importante de la teoría de grafos en la cartografía.

El teorema fue demostrado con ayuda de computadoras en 1976 por Appel y Haken.
(Appel & Haken, 1977)

# data[].attributes.attachment_link.readable_text
El teorema de los cuatro colores se enunció en forma de conjetura en 1852, pero tuvo que esperar hasta el año 1996 para ser admitido como válido por la práctica totalidad de la comunidad matemática.

El poema que abre este escrito es precisamente el que William Thomas Tutte dedicó a Wolfgang Haken -uno de los investigadores que dio una primera prueba del teorema en 1977, aunque tuvo que esperar hasta 1996 a ser ratificada por otros investigadores- tras más de cien años de fallidos intentos por probar su validez.

El teorema de los cuatro colores afirma que, para colorear un mapa geográfico plano sin que dos países colindantes tengan el mismo color, basta con cuatro tonos diferentes.

Se imponen las siguientes restricciones a los mapas aludidos en el teorema:

1. son siempre conexos -es decir, de una pieza- y cada una de sus regiones también es conexa;

2. dos territorios distintos de un mapa no pueden tocarse sólo en un punto, es decir, para ser colindantes deben compartir frontera en el sentido indicado en la figura 1.

Podría pensarse que un mapa con una gran cantidad regiones, poseyendo extrañas formas, y colindando de manera singular necesitaría mayor cantidad de colores que un mapa más sencillo. Pero, el teorema afirma que no es el caso.

Se trata de un problema topológico, ya que no es importante la forma de las regiones del mapa, sino la manera en la están colocadas las unas respecto a las otras.

¿Cómo empezó esta historia? El abogado y botánico Francis Guthrie observó que era capaz de colorear un mapa complicado de los cantones de Inglaterra con sólo cuatro colores, y conjeturó que debía suceder lo mismo con cualquier otro mapa geopolítico. En 1852, se lo comentó a su hermano Frederick y éste a su vez a Augustus de Morgan, su profesor.

Francis Guthrie observó, además, que tres colores no bastaban, mostrando lo que llamó el diagrama crítico (figura 2), que obviamente precisa de cuatro colores para no contradecir las condiciones de su conjetura -la parte blanca central es una región del mapa-.

Frederick Guthrie fue el primero en observar que el problema de los cuatro colores no se podía generalizar a dimensión 3: en efecto, según un ejemplo posterior de Heinrich Tietze, es posible construir un ejemplo de mapa tridimensional que precise tantos colores como se desee. Su propuesta consistía en tomar barras numeradas de 1 hasta n,ordenándolas como muestra la figura 3, y sobre ellas colocaba otras n barras numeradas de 1 hasta n, girándolas 45 grados. De este modo, Tietze conseguía un mapa tridimensional con n regiones (cada número correspondía a un 'país'), que obviamente necesitaba exactamente n colores para no contradecir las reglas de la conjetura...

Augustus de Morgan se interesó por la conjetura de Guthrie y la difundió entre sus colegas. El 23 de octubre de 1852 escribió a William Rowan Hamilton: "A student of mine [se refiere a Frederick Guthrie] [...] asked me today to give him a reason for a fact which I did not know was a fact - and do not yet. He says that if a figure be any how divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured - four colours may be wanted, but not more - the following is the case in which four colours are wanted. Query cannot a necessity for five or more be invented "

En ese momento Hamilton estaba trabajando en teoría de cuaterniones, y respondió cuatro días después a De Morgan, con sarcasmo: "I am not going to attemt your quaternion of colour very soon ".

Decepcionado, De Morgan se puso en contacto con otros matemáticos. En 1853, escribió a William Whewell, describiendo la conjetura como un axioma matemático.

El problema de los cuatro colores cruzó el Atlántico: Charles Sanders Peirce dio un seminario sobre la demostración, aunque nunca la escribió.

Tras la muerte de De Morgan en 1871, el problema de los cuatro colores pareció olvidarse; aunque Peirce seguía buscando su demostración, ninguno de los amigos británicos de De Morgan lo mencionaban.

Años más tarde, en junio de 1878, Arthur Cayley hizo la siguiente pregunta en un encuentro de la London Mathematical Society: " Has a solution been given of the statement that in colouring a map of a country, divided into counties, only four colours are required, so that no two adjacent counties should be painted in the same colour"? .

Realmente interesado por el problema, en 1879 publicó una nota corta sobre el tema en los Proceedings of the Royal Geographical Society. Admitía la dificultad del tema: " I have not succeeded in obtaining a general proof: and it is worth while to explain wherein the difficulty consists ".

Entre otros, en esa nota observaba que, a la hora de probar el teorema, podían imponerse condiciones más restrictivas sobre los mapas a colorear, en particular, bastaba con limitarse a mapas cúbicos, es decir, aquellos en los que hay exactamente tres regiones en cada punto de encuentro. En efecto, si en un mapa hay más de tres regiones en alguno de los puntos de encuentro (ver figura 5); sobre este punto puede pegarse un pequeño parche que produce un mapa cúbico. Si se puede colorear este mapa con cuatro colores, también se puede obtener un 4-coloreado del mapa original: basta con colapsar el parche en un punto.

Continuará en... El teorema de los cuatro colores (2): el error de Kempe y la clave de la prueba.
Referencias:
Marta Macho Stadler, Mapas, colores y números , Descubrir las matemáticas hoy: Sociedad, Ciencia, Tecnología y Matemáticas 2006 (2008) 41-68

Robin Wilson , Four colors suffice: how the map problem was solved, Princeton University Press, 2002.

Sobre la autora: Marta Macho Stadler es profesora de Topología en el Departamento de Matemáticas de la UPV/EHU, y colaboradora asidua en ZTFNews, el blog de la Facultad de Ciencia y Tecnología de esta universidad.

# data[].attributes.attachment_link.title
El teorema de los cuatro colores (1): una historia que comienza en 1852

# data[].attributes.attachment_link.description
Wolfgang Haken Smote the Kraken One! Two! Three! Four! Quoth he: "the monster is no more". (W.T. Tutte) El teorema de los cuatro colores se enunció en forma de conjetura en 1852, pero tuvo que esperar hasta el año 1996 para ser admitido como válido por la práctica totalidad de la comunidad matemática.

# data[].attributes.body
La teoría de grafos estudia las relaciones entre objetos conectados mediante nodos y aristas, siendo esencial para modelar redes y resolver problemas reales.
→ (Diestel, 2017) https://medium.com/@matematicasdiscretaslibro/cap%C3%ADtulo-11-teoria-de-grafos-3b00228dd81c

Los tipos de grafos permiten clasificar las estructuras según sus propiedades, como la dirección de las aristas o la presencia de pesos.
→ (Gross & Yellen, 2006) https://posgrados.inaoep.mx/archivos/PosCsComputacionales/Curso_Propedeutico/Matematicas_Discretas/Capitulo_4_Grafos.pdf

Los vértices representan entidades dentro del sistema, y el grado de un vértice indica su nivel de conexión.
→ (Cormen et al., 2009)

La noción de trayectoria y ciclo permite analizar rutas, recorridos y estructuras repetitivas en los grafos.
→ (Gross & Yellen, 2006)

El Teorema de los Cuatro Colores demuestra que cualquier mapa plano puede colorearse con solo cuatro colores sin que regiones adyacentes compartan el mismo.
→ (Appel & Haken, 1977)

La conexidad garantiza la existencia de caminos entre todos los nodos de una red.
→ (Diestel, 2017)

Referencias Bibliográficas

Appel, K., & Haken, W. (1977). Every planar map is four colorable. Illinois Journal of Mathematics, 21(3), 429–567. https://projecteuclid.org/euclid.ijm/1256049011

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.

Diestel, R. (2017). Graph theory (5th ed.). Springer. https://doi.org/10.1007/978-3-662-53622-3

Gross, J. L., & Yellen, J. (2006). Graph theory and its applications (2nd ed.). Chapman & Hall/CRC.

# data[].attributes.attachment_link.readable_text
Leonhard Euler fue el más grande matemático, filósofo y físico suizo. Nació el 15 de abril de 1707 en Basilea (Suiza).
Siendo un adolescente ingresó a la Universidad de Basilea, donde a los 17 años de edad, se graduó Doctor, provocando grandes aplausos con un discurso probatorio.
Trabajó todas las ramas conocidas de la matemática de su época y a todas les aportó algo. Resolvió el problema de los Puentes de Konigsberg que consistía en lo siguiente: dos islas en el río Pregel que cruza Königsberg se unen entre ellas y con tierra firme mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?

Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo terminando en el punto de partida sin repetir las líneas?

Euler demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par (condición necesaria para entrar y salir de cada punto regresando al punto de partida por caminos distintos en todo momento). En teoría de los grafos esta idea se corresponde con la posibilidad de encontrar un Ciclo Euleriano en un grafo.
Entre otras muchas de sus obras Introdujo los símbolos e (como la inicial de su nombre), la letra pi para dicho número (el honor a la letra inicial de Pitágoras), f(x) para las funciones, el sumatoria (∑) y el cálculo de i como la raíz cuadrada de -1. Argumentó que el infinito separaba los números positivos de los negativos de forma similar a como lo hace el cero. Definió las funciones logarítmicas y exponenciales. Elaboró e introdujo la integración doble. Descubrió el teorema de la composición de integrales elípticas. Amplió y perfeccionó la geometría plana y de sólidos. Fue el primero en considerar el seno y el coseno como funciones. Introdujo los factores integrantes en las ecuaciones diferenciales. Generalizó la congruencia de Fermat, introduciendo una expresión que Gauss denominó "indicador".
Considerado como el padre de la Teoría de Gráficas y como uno de los más grandes matemáticos de todos los tiempos.
Euler vivió casi durante los diecisiete últimos años de su vida en una ceguera total. Ni siquiera esta tragedia consiguió interrumpir sus investigaciones y publicaciones, que continuó al mismo e incluso a mayor ritmo hasta 1783.
En San Petersburgo el 18 de septiembre de 1783, en que, a la edad de setenta y seis años, murió de manera repentina mientras tomaba el té y jugaba con uno de sus nietos.
La teoría de gráficas o teoría de grafos es aplicada entre otras, en áreas tales como ciencias sociales, ciencias físicas, ingeniería de comunicación; pero, básicamente juega un papel importante en las ciencias de la computación, tales como inteligencia artificial, lenguajes formales, teoría de cambio y lógica de diseño, gráficos por computadora, sistemas operativos, compiladores, y organización y recuperación de información, en lo que respecta al modelado de problemas, indicando sus características de manera muy objetiva.
El concepto de grafo o gráfica es muy diferente a los trazos realizados en matemática sobre los ejes x e y.
Entre otras aplicaciones se utiliza para:
. Cartografía (coloreado de mapas)

. Modelado matemático

. Determinación de tiempos en el desarrollo de proyectos

. Urbanistas

. Programación de exámenes en una institución educativa

.Programación de horarios en una entidad cualquiera

. Programación de distribución de servicios públicos (recolección de basuras en una ciudad, red de acueducto, de alcantarillado y de gas)

. Diseño de boards o tarjetas plásticas para dispositivos electrónicos.  Redes de computadores
Los elementos de un grafo son los nodos o vértices y las aristas. Cada arista se forma por la unión de dos vértices. En decir, hay una relación entre las aristas y los nodos. Por ejemplo, si se usan grafos para la ejecución de un plan de actividades, los vértices se pueden asociar con las actividades y las aristas corresponderían al tiempo que tarda o a la probabilidad que se tiene para que se realice una actividad. En tal caso se trabaja en grafos dirigidos con peso.
Este capitulo pretende completar, de un modo organizado, los conceptos y términos sobre grafos que aparecen en este tema, los cuales inciden, fundamentalmente en el tratamiento algorítmico de los problemas planteados.

Sea V el conjunto no vacío de vértices o nodos y E el conjunto de lados o aristas (pares de vértices); se dice que G es un grafo, si G= (V, E) es una estructura de datos compuesta por esos dos conjuntos V y E que forman un conjunto de pares ordenados o desordenados de vértices o nodos. Los pares de vértices van entre paréntesis y los pares desordenados, pondrán entre llaves.

Un grafico dirigido G, también llamado "dígrafo o digrafo", consta de un conjunto V de vértices y un conjunto E de aristas tales que cada arista e E E se asocia con un par ordenado de vértices. Si existe una única arista e asociada con el par ordenado (v, w) de vértices, escribimos e = (v, w) lo cual denota una arista de v a w. En conclusión, se puede afirmar que un grafo dirigido es aquel que tiene uniones unidireccionales que suelen dibujarse con una flecha.

Un grafo dirigido es aquel que tiene todas sus aristas dirigidas; es decir, un dígrafo está asociado a un par ordenado (vea figura 9.1a). Por ejemplo, si w es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja ordenada (w,v), que es diferente de (v,w) ; es decir,

Los vértices de donde parten las aristas se denominan vértices salientes y los vértices a donde llegan las aristas se llaman vértices entrantes.

Un grafo no dirigido (vea figura 10.1b) consta de un conjunto de vértices y un conjunto E de aristas tal que cada arista e E E queda asociada a un par no ordenado de vértices. Si existe una única lista e asociada con los vértices v y w, escribimos e = {v,w} ó e = {w,v}. en este contexto, {v,w} denota una arista entre v y w en un grafo no dirigido y no un par ordenado. En conclusión un grafo no dirigido es aquel en el cual sus aristas son direccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A. Sus aristas son no dirigidas; es decir, un dígrafo está asociado a un par desordenado (vea figura 10.1d).

Ejemplo 11.1: si u es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja desordenada {w,v}, que es igual que escribir {v,w}; es decir, {w,v}={v,w}. En tal caso, w es vértice e partida o de llegada; igualmente sucede con v.

Es aquel grafo dirigido en el que sus aristas tienen una etiqueta (vea figura 10.1c). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso. Se usa en el modelado de problemas de la vida real; por ejemplo, al tiempo que se tardará en realizar una actividad determinada o la distancia que hay de un lugar a otro.

Es aquel grafo en el que algunas de sus aristas son dirigidas y otras son no dirigidas (vea figura 11.1d).

Según la figura 11.1c se podría interpretar por ejemplo, que para pasar de la actividad 1 a la 3 se tarda un tiempo p2; que pasar de actividad 3 a la 2 se tarda un tiempo p3 y, de la actividad 2 a la 1 se tardaría un tiempo p1. Un grafo no dirigido puede dibujarse con aristas dirigidas haciendo que cada lado les corresponda aristas invertidas.

Son aquellos que conforman un lado o arista. Todo lado conformado por dos vértices se dice que es incidente sobre esos vértices. Si un vértice no tiene otro adyacente se dice que es aislado.

Ejemplo 11.2: en G2 de la figura 11.2, son adyacentes los vértices 1 y 3. Así que la arista {1,3} incide sobre los vértices 1 y 3

En G1 de la figura 11.2: 1 es adyacente hacia 2 ó 2 es adyacente desde 1, donde la arista (1,2) incide sobre los vértices 1 y 2.

Ejemplo 11.3: en el grafo de la figura 11.2 la arista e1 incide sobre los vértices 1 y 2; igualmente, e7 incide sobre los vértices 5 y 6.

De cualquier manera, para dar algo de sentido a la terminología usada y también para desarrollar algunas ideas intuitivas, se representará un grafo por medio de un diagrama. Ese diagrama se llamará igualmente grafo.
1

Las definiciones y términos presentadas en este texto no están restringidos a aquellos grafos que pueden ser representados por medio de diagramas, aunque parezca ser el caso, ya que estos términos tengan una fuerte asociación con dicha representación. Debemos resaltar que una representación diagramática es posible únicamente en casos muy simples.

Los diagramas se pueden representar gráficamente cuando la cantidad de vértices no es grande. Para tal fin, puede utilizar los siguientes diagramas:

Los grafos G2, G3 y G4 son grafos no dirigidos; G1 es un grafo dirigido

Cuando un vértice se dirige a él mismo, se denomina "bucle". Si un grafo no tiene bucles o si a lo sumo existe una arista uniendo 2 vértices cualesquiera, se denomina "Grafo simple".

Cuando la cantidad de vértices es razonablemente grande se puede utilizar una representación para la computadora: matrices. Esta manera de representación permite hacer manipulaciones de un grafo utilizando las operaciones que ofrecen las matrices y en consecuencia determinar,por ejemplo, el grado de un grafo, el camino más corto para ir a un vértice, el número de caminos de longitud n, los ciclos, entre otros.
En vista del orden de los vértices que se requiere para hacer la representación matricial, se utilizarán dígrafos y la matriz cuadrada conocida como "matriz de adyacencia" que se denotará MA.

Ejemplo 11.5: dado el grafo G1 de la figura 11.4, donde V={1,2,3} conjunto de vértices ordenado. Su matriz de adyacencia es

La matriz de adyacencia siempre es simétrica (aij = aji). Cuando se trata de grafos con peso o ponderados en lugar de 1 el valor que tomará será el peso de la arista. Si el grafo es no dirigido hay que asegurarse que se marca con un 1 (o con el peso) tanto la entrada a[i] [j] como la entrada a[j] [i], puesto que se puede recorrer en ambos sentidos.
El algoritmo Implementado en lenguaje C es:

El grado entrante de un vértice es el número de aristas que llegan al vértice.

Ejemplo 11.6: el vértice 3 del grafo G3 de la figura 11.3, tiene grado entrante 4 y en el grafo G1 de la misma figura, el grado entrante del vértice 3 es 1.

El grado saliente de un vértice corresponde al número de aristas que salen del vértice.
Ejemplo 11.7: en G3 de la figura 11.3 el vértice 3 tiene grado saliente igual a 4. Ahora, en G1 de la figura 11.3 el vértice 1 tiene grado 2.

Figura 11.5: ejemplo 11.8

Se llama grado de un vértice v al número de aristas que lo tienen como extremo, (cada bucle lo cuenta dos veces). Se designa por d(v) y corresponde al número de aristas incidentes sobre el vértice v. Un vértice aislado tiene grado cero.
En los grafos dirigidos el grado total de un vértice es la suma del grado entrante más el grado saliente. En los grafos no dirigidos, el grado total de un vértice es igual al número de aristas que tiene el vértice. Por lo tanto, la suma de los grados de los vértices es igual al doble de las aristas del grafo. Compruébalo con varios ejemplos.
Ejemplo 11.8: de la figura 11.5, el vértice a tiene grado total igual a 3; vértice b, grado 3; vértice c, grado 2; vértice d, grado 1; vértice e, grado 1.

Isomorfismo significa "de igual forma". Dos grafos son isomorfos si existe correspondencia uno a uno entre los nodos de ambos grafos, y además conservan la adyacencia tanto entre los nodos como en la dirección de los lados.
Dos grafos G1 y G2, son isomorfos si existe una correspondencia uno a uno entre los vértices de los grafos, tal que todo par de vértices que son adyacentes en un grafo si y sólo si el correspondiente par de vértices son adyacentes en el otro grafo.
Es decir, sean G1 = (V1, E1) y G2 = (V2, E2) grafos simples. Se dice G1 y G2 son isomorfos (la misma forma), si hay una función biyectiva f de V1 a V2 con la propiedad de que a y b son adyacentes en G1 si y solo si f(a) y f (b) son adyacentes en G2, para todo a y b en V1. Tal función f es llamada un isomorfismo.
Ejemplo 11.9: de acuerdo con la definición de isomorfismo se podría decir que un par cualquiera de nodos que está unido por una arista debe tener los nodos correspondientes en el otro grafo también unidos por un eje, así mismo debe existir una correspondencia uno a uno entre los ejes. Por lo tanto, los grafos mostrados en la figura 11.6 (a) y (b) son isomorfos.

Solución:

Invariantes de grafos isomorfos. Los invariantes de dos grafos simples isomorfos son tener iguales: 1. El número de vértices; 2. El número de aristas; 3. La correspondencia entre los grados de los vértices. De tal manera ambos grafos, para alguna ordenación de vértices y lados, sus matrices de adyacencia son iguales.
A partir de sus invariantes (propiedad que los grafos simples deben cumplir) podremos mostrar cuando 2 grafos no son isomorfos o lo que es lo mismo, cuando 2 grafos no son iguales. De tal manera, si en alguna de esas cantidades difieren los grafos simples, se puede decir que no son isomorfos.
Ejemplo 11.10: determine si los grafos de la figura 11.7 son isomorfos, utilizando sus matrices de adyacencia.

Se dice que G es un grafo plano si puede representarse gráficamente sin la intersección de sus aristas. Es decir, un grafo es plano si puede dividirse en regiones no acotadas.
Ejemplo 11.10: el grafo de la figura 11.7a representa un grafo plano, porque puede graficarse sin que se crucen las aristas, como la figura 11.7b. Dichos grafos son iguales.

Sea G un grafo plano conexo con n vértices y e aristas, que se descompone en r regiones, entonces n-e+r=2.

Demostración por inducción sobre a
Si e=0, entonces n =1, r =1 y se cumple que n−e+r = 2
Supongamos que el resultado es cierto para todos los grafos planos y conexos con e-1 aristas, donde e>=1.
Sea G un grafo plano y conexo con e aristas. Si G no es árbol, entonces existe alguna arista e de un ciclo de G. Entonces, G-{e} es plano, conexo con n vértices, e-1 aristas y r-1 regiones.
La hipótesis de inducción asegura entonces que:
n- (e-1)+ (r-1)= 2 , es decir, n- e + r = 2

Corolario: Si G=(V,E) es un grafo plano con e aristas y n vértices: e ≤ 3n - 6

Ejemplo 11.12: los grafos de la figura 11.9 no representan grafos planos. Compruébelo

Dos grafos G1 y G2 son homeomorfos si pueden reducirse a gráficas isomorfas realizando varias reducciones en serie. La reducción en serie se da cuando en una gráfica G las aristas (v, v1) y (v, v2) están en serie, y al hacer reducción en serie desaparece v y solo queda v1, v2. Los grafos homeomorfos permiten afirmar cuándo una gráfica no es plana.

Por consiguiente, si ambos grafos G1 y G2 pueden obtenerse a partir de un mismo grafo por una sucesión de subdivisiones elementales de aristas o reducción en serie, se dice que los grafos son homeomorfos.

Grafo conexo. Es aquél grafo en que existe camino simple entre cualquier par de vértices. Es decir, desde cualquier vértice v tiene al menos un camino para llegar al vértice w. También llamado grafo conectado.

Ejemplo 11.13: en la figura 11.10a, el grafo es conexo, pues dados dos vértices cualesquiera v y w existe un camino de v a w.

Grafo disconexo. Un grafo G es disconexo, si dos o más de sus nodos no están conectados por caminos simples (figura 10.10b).
Grafo regular. Es un grafo G conexo (figura 11.11) cuyos vértices tienen el mismo grado.
Grafo completo. Un grafo G dirigido o no dirigido (simple) es completo si cada vértice es adyacente a los demás Wvértices del grafo. Es decir, entre cada par de nodos v y w existe una arista de v hacia w y de w hacia v (forzosamente tendrán que cumplirse ambas condiciones). Todo grafo completo es regular; pero no el recíproco; por ejemplo, el grafo de la figura 11.11.
Grafo fuertemente conexo. Es un grafo dirigido que tiene camino entre cualquier par de vértices; por ejemplo, el grafo de la figura 11.12. Generan la relación de equivalencia. Mínimo deberá tener 2 caminos de un vértice a otro.

Grafo Bipartito. Un grafo G=(V,E) es bipartito, si el conjunto de vértices V puede separarse en dos subconjuntos V1 y V2 disjuntos (V1 V2=) de modo que cada arista de E sea incidente con un vértice de V1 y con un vértice de V2; también puede decirse, cada vértice de V1 es adyacente con vértices de V2, pero no hay adyacencias entre los vértices de cada subconjunto.
La figura 11.13 presenta un grafo bipartito, donde V1 = (v1, v2, v3) y V2 = (v4, v5) son conjuntos disjuntos donde cada arista es incidente en un vértice de V1 y un vértice de V2; es decir, cada vértice de V1 es adyacente con cada vértice de V2. Observe

que un grafo es bipartito, si y solo si, no tiene ciclos con longitud impar.

Grafo no bipartito. Un grafo G= (V, E) es bipartito, si el conjunto de vértices V no se puede separar en dos o más subconjuntos. El grafo de la figura 11.14 no es bipartito porque no se puede separar en dos subconjuntos.

Grafo Bipartito Completo. El grafo bipartito completo con m y n vértices, denotada (Km, n), es la gráfica simple cuyo conjunto de vértices esta dividido en conjuntos V1 con m vértices y V2 con n vértices, de los cuales existe una arista entre cada par de vértices v1 y v2, donde v1 esta en V1 y v2 está en V2.
El grafo de la figura 11.15 es bipartito completo con dos y cuatro vértices (K2, 4) donde V1= {3,5} y V2= {1, 2, 4, 6}.

Corresponde a los vértices por los cuales hay que pasar para ir desde un vértice w hacia un vértice v. Es decir un camino entre dos vértices es una lista de vértices que están conectados por una arista del grafo.
Para que un camino o trayectoria exista es condición necesaria que las aristas sobre la trayectoria existan sobre el conjunto de aristas que definen el grafo.
Ejemplo 10.14: en la figura 10.16 el camino abdefgc es un camino que comienza en el vértice a y pasa por los vértices b, d, e, f, g y c.

Existe camino simple cuando todos sus vértices, excepto tal vez el primero y el último, son distintos.
Ejemplo 11.15: una trayectoria simple para ir desde el vértice b hasta el vértice g en el grafo de la figura 11.10, es: b-d-a-c-f-g.
En la figura 11.16 la trayectoria b-e-d-a-e-c-f-g no es simple, porque se pasa dos veces por el nodo e.

La longitud de una trayectoria corresponde al número de lados de la trayectoria para ir de un vértice a otro.
Ejemplo 11.16: según el grafo de la figura 11.17, para ir desde 3 hasta 1 el camino tiene longitud 2 (pasa por 2 aristas), pero de 1 hasta 3 tiene longitud 1 (sólo tiene 1 arista).

Un ciclo (también llamado circuito) es un camino simple de longitud mínimo 1 que empieza y termina en el mismo vértice; es decir, es una trayectoria simple en la cual el primero y el último vértices son el mismo.

Ejemplo 11.17: en el grafo de la figura 11.17, la trayectoria 1, 3, 2, 1 es un ciclo.
Ejemplo 11.18: en el grafo de la figura 11.16, la trayectoria a-d-b-e-f-g-c-a es un ciclo de longitud 7.

Sea G un grafo conexo. La distancia entre un par de vértices v y w es la longitud mínima de un camino entre esos vértices y se denota d(v, w). De acá se deduce:

Si un grafo es dirigido el máximo número de lados es n(n-1) y para grafos no dirigidos n(n-1)/2.
Ejemplo 10.19: 1. ¿cuál es el máximo número de aristas de un grafo que tiene n vértices, ilustre la respuesta con dos ejemplos.
El máximo número de aristas del grafo dirigido de la figura 11.18 es: ) 1n(n  con n = 4  aristas dirigidas= ) 14(4 -1)=12

2. ¿Cuál es el máximo número de aristas de un grafo bipartito con n vértices?; ilustre la respuesta con dos ejemplos.

Un punto de articulación de un grafo no dirigido G es un nodo v tal que cuando es eliminado de G (junto con las aristas incidentes en el) se divide un componente conexo del grafo en dos o más componentes conexos. El cálculo de los puntos de articulación se basa en un recorrido de profundidad.

Ejemplo 11.20: en la figura 11.21, los vértices a y c son puntos de articulación, pues si falla uno de estos, se pierde la comunicación entre otros nodos. Si este grafo representará una red de computadores, y si a o c no funcionaran esto causaría que ciertos computadores quedasen incomunicados.

Ejemplo 11.21: dibuje dos grafos con seis vértices que tengan exactamente a) dos puntos de articulación y b) cero puntos de articulación. Solución:

Dado un grafo simple G = (V, E) con n=|V| vértices {v1,. .. , vn} y m=|E| aristas {e1, ..., em}, su matriz de incidencia es la matriz B de orden nxm, B(G)=(bij), donde bij=1 si vi es incidente con ej y bij=0 en caso contrario.

Si la matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista incide exactamente en dos vértices, cada columna tiene exactamente dos unos. La cantidad de unos que aparece en cada fila es igual al grado del vértice correspondiente. Una fila compuesta sólo por ceros corresponde a un vértice aislado.

Camino de Euler. Se dice que un grafo G conexo tiene camino de Euleriano si su trayectoria incluye todas las aristas una y solo una vez.
Ciclo o circuito de Euler. Un grafo G conexo tiene al menos un ciclo Euler si se recorren todas las aristas del grafo G exactamente una vez, excepto la arista inicial y la final (que son las mismas). Es decir, un grafo G tiene un circuito de Euler, si puede pasar por todas las aristas sin repetir arista.
Teorema 11.1: Un grafo G tiene un ciclo de Euler, si y solo si G es un grafo conexo y cada vértice tiene grado par.
Teorema 11.2: Si G es un grafo conexo que tiene un par de vértices de grado impar, entonces no puede existir un ciclo de Euler en G, pero si, camino de Euler.
Camino de Hamilton. Es aquella trayectoria que contiene cada vértice que lo compone una y solo una vez.
Ciclo de Hamilton. Un ciclo de una gráfica G es Hamiltoniano, si cada vértice del grafo G conexo aparece exactamente una vez, excepto por el vértice inicial y final (que aparece dos veces).
Teorema 11.3 (también llamado teorema de ORE, que hace memoria a Oystein Ore en 1960). Un grafo conexo G de n vértices para n ≥3 tal que deg(u) + deg(v)≥ n siendo u y v cualquier par de vértices no adyacentes del grafo G, entonces contiene un ciclo Hamiltoniano.

Teorema 11.4: (también llamado teorema de DIRAC, que memoriza a Gabriel A. Dirac en 1952) Un grafo conexo G de n vértices con n ≥ 3 tal que todos los vértices de G tienen grado mayor o igual que n/2 contiene un ciclo Hamiltoniano. El Teorema de Dirac dice lo siguiente: Sea un grafo G, con sus vértices y aristas, conexo, con la cantidad total de vértices n mayor o igual a 3, dicho grafo debe cumplir todas estas características para poder continuar aplicando el Teorema. Por lo tanto, si el grado de cada uno de los vértices de este grafo es mayor o igual que la mitad del número total de vértices de G, entonces este grafo es Hamiltoniano.

Ejemplo 11.23: el grafo G3 de la figura 11.28 tiene ciclo Hamiltoniano
Ejercicio: Ilustre los teoremas 11.3, 11.4 y 11.5 con un ejemplo.

Problema 10.1: determine si los grafos G y H de la figura 10.29 son isomorfos.

Solución: Los grafos son isomorfos, pues un posible isomorfismo es: f (u1) = v1, f (u2) = v4, f (u3) = v3, f (u4) = v2

Problema 11.2: qué tipo de camino y de ciclo tiene el grafo de la figura 11.30?

El grafo de la figura 11.30 no tiene ciclo de Euler, pero si camino de Euler, porque tiene un solo par de nodos de grado impar; además tiene ciclo y camino de Hamilton, porque desde cualquier par de nodos no adyacentes, la suma de sus grados es mayor o igual que la mitad de cantidad de vértice.
Problema 11.3: determine, si los grafos G1 y G2 de las figuras 11.31, 11.32, 11.33 son isomorfos; cuál o cuáles tienen camino y/o ciclo de Euler o de Hamilton.
Solución:

Los grafos de la figura 11.31

. no son isomorfos, porque falla la invariante del grado de los vértices, así: hay 2 nodos de grado 4 en el grafo G1 y en el G2 solo hay un vértice con este grado; en el grafo G2 hay un vértice de grado 2; en cambio en el grafo G2 ninguno tiene ese grado.

. G1 tiene ciclo y camino de Hamilton, ya que se pueden recorrer todos los vértices, sin repetir vértice. Además tiene camino de Euler, porque tiene exactamente 2 vértices de grado impar y permite recorrer todas las aristas sin repetir arista, basta con partir desde un vértice de grado impar hasta el otro vértice de grado impar: parta de a y llegue e. Pero no tiene ciclo de Euler ya que todos sus nodos no son de grado par.

Los grafos de la figura 11.32 se tiene

.Los grafos G1 y G2 son isomorfos. Veamos un posible isomorfismo:

. G1 y G2 tienen ciclo de Hamilton (porque desde cualquier par de vértices no adyacentes la suma de sus grados es mayor o igual que la cantidad de vértices del grafo) y por ende camino de Hamilton; tiene además, camino de Euler (porque tiene exactamente un par de vértices de grado impar), pero no tienen ciclo de Euler (algunos vértices tienen gado impar).
Los grafos de la figura 10.33 se puede afirmar que

.Los grafos G1 y G2 son isomorfos porque tienen la misma cantidad de aristas y de vértices, con su respectivo grado.
. G1 y G2 tienen ciclo y camino de Hamilton, no tienen ni ciclo ni camino de Euler.

Problema 11.4: determine si el grafo de la figura 11.34 es plano. Si lo es, dibújelo de nuevo sin que se crucen sus aristas.

Dibuje un grafo de 7 vértices con:

Efectivamente, luego de analizar detenidamente la gráfica se observa que se puede trazar sin que se crucen las aristas, quedando el grafo (figura 11.35):

Ahora vamos a aplicar la fórmula para hace la verificación correspondiente.
Gráfica plana conexa con r = 7 regiones (A, B, C, D, E, F y cara externa), e = 10 aristas y v = 5 vértices; Por lo tanto, n - e + r =2; es decir, la grafica es plana.
Problema 11.4: para los grafos de las figuras 11.36 y 11.37, identifique las gráficas planas.

Las gráficas de las figuras 11.36 y 11.37 no son planas, porque siempre quedan 2 vértices que al conectarse se cruzan otras aristas.

Problema 11.5: dibuje un grafo que tenga las siguientes características; grafo plano conexo con 9 vértices y con grados 2, 2, 2, 3, 3, 3, 4, 4 y 5. En efecto, El grafo de la figura 10.38 tiene 14 aristas, 6 caras. En efecto, cumple con las condiciones de una gráfica plana (7caras-14aristas+9vertices=2).

G1:

A) es un grafo regular

B) es un grafo simple y conexo

C) es un grafo que tiene un camino de Euler

D) es un grafo bipartito

2. El grafo que cumple la siguiente condición dada en la tabla 1

A) Es Plano, con 8 regiones y fuertemente conexo

B) C) Es plano, con 8 regiones, pero no fuertemente conexo

C) Es plano, con 9 regiones y fuertemente conexo D)

D) Es plano, con 9 regiones, pero no fuertemente Conexo

a. 0 puntos de articulación

b. 1 punto de articulación

c. 2 puntos de articulación

d. 3 puntos de articulación e. 4 puntos de articulación

2. ¿El grafo de la figura 11.39 es bipartito?

3. Un grafo G es bipartito si y solo si todos sus ciclos tienen longitud par. En caso tal que la afirmación sea cierta ilústrelo con un ejemplo.

4. Un grafo conexo G que tenga exactamente dos vértices v y w de grado impar, tiene un camino entre v y w. En caso tal que la afirmación sea cierta ilústrelo con un ejemplo.

5. Si una gráfica G tiene más de dos vértices de grado impar, entonces ¿G no puede tener un camino de Euler?. Ilustre su afirmación con un ejemplo.

6. Si G es un grafo conexo que tiene exactamente dos vértices de grado impar, entonces tiene un camino Euler (basta con partir de vértice de grado impar para llegar al otro vértice de grado impar). Ilustre la afirmación con un ejemplo usando grafos de 5 y de 6 vértices.

9. Dibuje dos grafos que no sean Eulerianos.

11.1 Marque con X la respuesta correcta y en caso afirmativo complete el resto, teniendo en
cuenta el grafo 3, que representa la internet de una empresa donde cada nodo corresponde
a las oficinas de un departamento. Puede afirmarse según la figura 11.42
11.2 En el grafo 4, cada arista corresponde a las carreteras para ir de una ciudad a otra. Puede
afirmarse según la figura 11.43

13. Los dígrafos DG1 y DG2, DG3 y DG4, DG5 y DG6 representan grafos de la figura 11.45 que son
isomorfos? Dichos grafos son planos?. Compruebe sus respuestas llenado la
Tabla de la figura 11.46 con X según el grafo, siendo n: número de vértices y a: número de aristas,
r: número de regiones (en caso de ser plano)

17. Haga un programa que halle la matriz potencia (definida por el usuario).

# data[].attributes.attachment_link.description
Leonhard Euler fue el más grande matemático, filósofo y físico suizo. Nació el 15 de abril de 1707 en Basilea (Suiza). Siendo un adolescente ingresó a la Universidad de Basilea, donde a los 17 años de edad, se graduó Doctor, provocando grandes aplausos con un discurso probatorio.

# data[].attributes.headline
Cuadro: 10 Ejemplos de Usabilidad de la Teoría de Grafo

# data[].attributes.subject
Cuadro: 10 Ejemplos de Usabilidad de la Teoría de Grafo

# data[].attributes.body
La teoría de grafos no es solo un tema teórico, sino una herramienta poderosa con múltiples aplicaciones prácticas. Nos permite resolver problemas cotidianos y complejos relacionados con rutas, redes y estructuras interconectadas. Gracias a ella, es posible optimizar sistemas y procesos tanto a nivel local como global, impactando positivamente en distintas disciplinas.