Introducción a la teoría de grafos y sus aplicaciones en matemáticas

INTRODUCCIÓN

JUSTIFICACIÓN DE LA ELECCIÓN DEL TEMA

El presente tema se caracteriza por ser coherente e innovador ya que parte del primer nivel de concreción curricular que son las bases legales que regulan nuestro sistema educativo, como la Ley Orgánica 3/2020 (LOMLOE), de 29 de diciembre, por la que se modifica la Ley Orgánica 2/2006, de 3 de mayo de educación (LOE), la Ley de Educación en Andalucía 17/2007 de 17 de diciembre (LEA), y fundamental e imprescindible la Orden del 30 de mayo de 2023. Las matemáticas, presentes en casi cualquier actividad humana, tienen un marcado carácter instrumental que las vincula con la mayoría de las áreas de conocimiento: las ciencias de la naturaleza, la ingeniería, la tecnología e incluso el arte o la música. En particular, Los grafos son modelos matemáticos de numerosas situaciones reales. De forma general, puede decirse que los grafos se utilizan para representar las relaciones existentes entre los elementos de un conjunto. Por lo tanto, podemos decir que los grafos son un artificio matemático que puede simplificar y resolver numerosas situaciones o problemas reales, desde los problemas relacionados con tráfico (aéreo, por carretera, de mercancías, etc.) o diseño de redes (de transporte, en sistemas eléctricos, etc.) hasta aplicaciones en ciencias tan dispares como la química, la genética, la informática, la bibliotecomanía o la arqueología.

RESEÑA HISTÓRICA

Leonhard Euler (s. XVIII) fue un matemático de gran talento que enriqueció las matemáticas, tal y como hace referencia en el libro de Carl B. Boyer: Historia de la matemática, en cada una de sus ramas. Uno de sus resultados más famosos fue su solución al problema de los "puentes de Königsberg". La ciudad de Königsberg estaba dividida en cuatro partes por el río Pregel, con siete puentes. Muchos habitantes de la época se plantearon el reto de encontrar una ruta por la ciudad que recorriera los siete puentes, cruzando cada uno de ellos una única vez y volviendo al punto de partida. Euler dio una demostración matemática de la imposibilidad de realizar dicho trayecto en las condiciones que se pretendían, y hoy en día, esa solución se considera como el origen de la teoría de grafos. A partir de entonces, muchos matemáticos han realizado contribuciones, entre los siglos XVIII y XIX se pueden citar a Cauchy, Vandermonde, Hamilton, Cayley y Kruskal. 1 4 6 5 2 3 7

CONCEPTOS FUNDAMENTALES DE LA TEORÍA DE GRAFOS

De forma informal, podríamos comenzar definiendo un grafo del siguiente modo: Un grafo es una colección de vértices y aristas que unen dichos vértices. Página 2 de 14De un modo más formal, definimos grafo del siguiente modo: Definición Un grafo es un par ordenado G = (V,A), donde V es un conjunto no vacío y a cuyos elementos se les llama vértices, y A es un conjunto de pares de elementos de V a cuyos elementos se les llama aristas. Definición Sea G = (V,A) un grafo. Entonces: 1) Si a = (u, v) es una arista del grafo G, entonces los vértices u y v se llaman los extremos de la arista a. 2) Si el vértice v E V es un extremo de la arista a E A, entonces se dice que v y a son incidentes. 3) Los vértices u, v E V se dicen adyacentes si existe una arista en el grafo G que une u y v. 4) Dos aristas se dicen incidentes si tiene un vértice en común. 5) Un punto del grafo que es extremo de alguna arista se llama nodo. En caso contrario, se llama vértice aislado. 6) Cuando en una arista coinciden los vértices, u = v, la arista se denomina lazo. Ejemplo: a1 v1 v2 v4 a2 v3 a3 v1 y v2 son vértices adyacentes a1 y a2 son aristas incidentes a3 es un lazo v4 es un vértice aislado Nota: Dado el grafo G = (V,A), se denota por V (G) al conjunto de vértices y por A(G) al conjunto de aristas de dicho grafo. Definición Sea G = (V,A) un grafo y v E V un vértice: a) Llamamos grado de v (grad (v)) al número de aristas que inciden en v. b) Un nodo se llama par si hay un numero par de aristas que lo tiene como extremo. De forma análoga se llamaría impar. En este cómputo, si la arista fuese un lazo entonces se cuenta dos veces. c) Se dice que v E V es terminal si gr(v) = 1. Además, un vértice aislado cumple que su grado es nulo. Teorema Si G = (V,A) es un grafo, entonces EvEv grad(v) = 2|A|. Demostración Según se considera cada arista a = (u, v) del grafo G, la arista suma 1 a grad(u) y a grad (v), luego suma 2 a la suma de todos los grados. Así, 2|A| es el total de grad (v), Vv E V. Teorema (Lema del apretón de manos) Página 3 de 14El número de vértices de grado impar de un grafo es par o cero.

TIPOS DE GRAFOS

Definición Un grafo simple es un grafo que verifica que para todo par de vértices existe a lo sumo una arista que los une. u v w Definición Un multigrafo o grafo general es un grafo con varias aristas entre dos vértices. u v w Definición Un pseudografo es un grafo en el cual aparecen lazos. u w v Definición Un grafo orientado, dirigido o dígrafo es un grafo donde a cada arista se le asigna un orden de sus extremos. El orden se indica en el dibujo con una flecha. Se llama origen al primer vértice de una arista y final al segundo. v1 v2 v3 V1 = {v2, 12, V3} A1 = {v102, 1203, V3V1} Definición Se llama grafo nulo a un grafo donde el conjunto de aristas es vacío. El grafo nulo de n vértices se designa por Nn· u N3 v w Definición Un grafo es regular si todos sus vértices tienen el mismo grado. Si dicho grado es k, entonces el grafo se llama k-regular. v1 v2 v2 v1 Ejemplo: grad(v1) # grad(v2) v8 v7 v5 v6 NO REGULAR DV4 v4 Página 4 de 14 V3 v3 3-REGULARDefinición Se denomina ciclo a todo grafo 2-regular. Los ciclos se representan por Cn, siendo n el número de vértices. Ejemplo: C4 C5

REPRESENTACIÓN DE GRAFOS

Un grafo se puede representar de diferentes formas:

1. Definiendo por enumeración los conjuntos V y A de vértices y aristas del grafo respectivamente. Esta forma es muy poco operativa. Ejemplo: ( V(G) = {a, b, c, d, e, f} A(G) = {ab, ae, bd, cd, ed}
2. Gráficamente, mediante un diagrama en el que aparezca un punto por cada vértice y una línea entre dos vértices adyacentes. Esta es la forma usual de representar un grafo. Ejemplo: e f a C b d
3. Por su matriz de incidencia: es una matriz que tiene tantas filas como vértices y tantas columnas como aristas, cuyos elementos dij vienen dados por: aij = 1 [1 si el vértice i y la arista j son incidentes 0 en caso contrario C 0 Ejemplo: d /1 1 0 1 e f a b 0 1 0 0 0 1 0 0 1 0 0 0 0 0 cd de 1 1
4. Por su matriz de adyacencia: es una matriz cuadrada que tiene tantas filas y columnas como vértices, cuyos elementos dij vienen dados por: aij = { : [1 si los vértices i y j son adyacentes 0 en caso contrario Página 5 de 14 0 0 1 0 ab ae bd 0 0 0 1 0b C f a 0 0 1 a 0 0 1 1 1 0 0 b 0 0 0 0 e 0 1 0 d 1 0 0 C 1 0 0 1 f 0 0

ISOMORFISMO DE GRAFOS

Definición Diremos que dos grafos G = (V,A) y G' = (V',A') son isomorfos si existe una aplicación biyectiva q: V -> V'. Es decir, la relación que relaciona biyectivamente pares de vértices de A con pares de vértices de A', de modo que los vértices conectados por aristas siguen estándolo. A la aplicación o se le denomina isomorfismo. Ejemplo: a b d 1 2 4 C G 3 Gʹ Teorema Sean G = (V,A) y G' = (V',A') dos grafos y « un isomorfismo entre G y G'. Si u E V, entonces: grad(u) = grad(p(u)). Observación Dos grafos con distinto número de vértices no pueden ser isomorfos. Y el recíproco no es cierto, es decir, grafos con igual número de vértices no tienen por qué ser isomorfos.

SUBGRAFOS

Definición Sea G = (V,A) un grafo. Un grafo G' = (V',A') se dice subgrafo de G si Ø # V'(G') ≤V(G) y A'(G') ≤ A(G). Observación Los subgrafos se obtienen eliminando algunas aristas y vértices del grafo original, de modo que, si eliminamos un vértice, hemos de eliminar todas las aristas que tienen tal vértice como extremo. Ejemplo: 1 2 3 4 G V (G) = {1,2,3,4} (1,2), (2,3), A(G) = (3,4), (4,1), (1,3), (2,4) 1 3 V(G) = {1,2,3} 2 A(G) = {(1,2), (2,3),) (3,1) G' (subgrafo de G) Definición 0 Ejemplo: d. e 0 10 0 1 0 0 0 0/ Página 6 de 14Sea G = (V,A) un grafo. Se denomina grafo complementario de G y se representa por G, al grafo que tiene el mismo conjunto de vértices y verifica que entre cada dos vértices existe una arista sí y sólo sí dicha arista no existe en G. Ejemplo: 1 2 1 2 3 4 3 4 G G

CAMINOS Y CICLOS. CONEXIÓN

Los grafos se usan con frecuencia para representar redes de transporte o de comunicación. En un grafo que representa una de estas redes es importante conocer la existencia de caminos que recorran todas las aristas o todos los vértices y que, en cierto modo, sean los más económicos. Definición Sea G = (V,A) un grafo. Entonces: a) Un camino en el grafo G es una sucesión en la que aparecen de forma alternada elementos de V y elementos de A de la forma vo, ao, 11, a1, 12, a2, ... , Un, an Con vi E V (i = 0, ... , n) y aj € A(j = 1, ... , n). A los vértices vo y vn se les llaman extremos del camino, o vértices inicial y final respectivamente. También se dice que el camino conecta vo con Un. La longitud del camino es el número de aristas que contiene dicho camino. El camino también puede expresarse mediante sus vértices de la siguiente manera: vo -> v1-> 12 -> ... > Vn-1 -> Un. b) Un camino se dice cerrado si sus extremos coinciden: v0 = Vn (pero sí pueden repetirse algún vértice). c) Un camino se dice simple si en la sucesión de vértices no hay ninguno repetido, por lo tanto, todas las aristas son distintas. d) Un ciclo es un camino cerrado donde los únicos vértices que se repiten son el primer y el último. e) Un circuito es un camino cerrado que no repite aristas (pero sí puede repetir vértices). Definición Un grafo G = (V,A) se dice conexo si para cada par de vértices u, v E V existe un camino cuyos extremos son u y v. Si un grafo no es conexo, se dice disconexo. Grafo conexo Grafo disconexo

GRAFOS EULERIANOS

Página 7 de 14

BIBLIOGRAFÍA

Página 1 de 141. INTRODUCCIÓN 1.1. JUSTIFICACIÓN DE LA ELECCIÓN DEL TEMA 1.2. RESEÑA HISTÓRICA 2. CONCEPTOS FUNDAMENTALES DE LA TEORÍA DE GRAFOS 2.1. TIPOS DE GRAFOS 2.2. REPRESENTACIÓN DE GRAFOS 2.3. ISOMORFISMO DE GRAFOS 2.4. SUBGRAFOS 3. CAMINOS Y CICLOS. CONEXIÓN 3.1. GRAFOS EULERIANOS 3.2. GRAFOS HAMILTONIANOS 4. GRAFOS COMPLETOS. GRAFOS BIPARTITOS COMPLETOS. GRAFOS PLANOS 5. ÁRBOLES. DIAGRAMAS EN ÁRBOL 5.1. ÁRBOLES ABARCADORES 5.2. ÁRBOLES CON RAÍZ 6. APLICACIONES DE LA TEORÍA DE GRAFOS 6.1. INGENIERÍAS 6.2. TEORÍA DE JUEGOS 6.3. VARIOS 7. CONCLUSIÓN 8. BIBLIOGRAFÍA