Coloreado de grafos

Coloreado de Grafos Elmer Mosher

Figure 1: Figura 1

Capítulo 1. Generalidades sobre grafos. 1.1. Introducción. El estudio de grafos está ligado habitualmente a la topología, aunque durante los últimos años ha adquirido carta de independencia y se ha convertido en una valiosa herramienta matemática en campos tan dispares como la investigación operativa, la lingüística, la química, la física,la genética y la teoría de redes [W1]. Un grafo es sencillamente un conjunto de puntos, los vértices, algunos de los cuales están ligados entre ellos por medio de líneas, las aristas. La naturaleza geométrica de estos arcos no tiene importancia, sólo cuenta la manera en la que los vértices están conectados. El problema de los siete puentes de Könisberg (véase la Fig. 1) se considera como elprimer problema de teoría de grafos: en 1700, los habitantes de Könisberg, se preguntaban si era posible recorrer esta ciudad pasando una vez y sólo una por cada uno de los puentes sobre el río Pregel, y volviendo al punto de partida. En aquella época, Könisberg tenía siete puentes, uniendo las cuatro partes de la ciudad separadas por las aguas, y dispuestas de determinada manera. En 1736, Euler probóque la respuesta a esta pregunta era negativa, usando un grafo (véase la Fig. 2): se dibujan sobre una hoja de papel cuatro vértices que simbolizan las cuatro partes separadas de la ciudad, después se trazan entre estos vértices las aristas, simbolizando los puentes. El Teorema de Euler se enuncia en el lenguaje de teoría de grafos del siguiente 1

Coloreado de Grafos Elmer Mosher

Figure 2:Figura 2

modo: “Existe un circuito (camino cerrado) euleriano (que pasa por cada arista exactamente una vez) en un grafo si y sólo si el grafo es conexo (existe un camino ligando cada par de vértices) y cada vértice tiene grado (número de aristas que llegan al él) par” . Es bastante fácil comprender ahora la razón por la que el problema de los siete puentes de Könisberg no tiene solución: unpaseante que llega a uno de los cuatro barrios de la ciudad debe forzosamente irse y tomando un puente diferente. En el grafo, ésto se traduce por el hecho de que cada vértice debe estar asociado a un número par de aristas. Pero, la con…guración de los puentes de Könisberg no veri…ca esta condición, probada por Euler como necesaria y su…ciente. En 1847, G. Kirchho¤ (1824-1887) analizó un tipoespecial de grafo llamado árbol. Kirchho¤ utilizó este concepto en ciertas aplicaciones de redes eléctricas, al formular su extensión de las leyes de Ohm para ‡ ujos eléctricos. Diez años después, A. Cayley (1821-1895) desarrolló el mismo tipo de grafos para contar los distintos isómeros de hidrocarburos saturados Cn H2n+2 , n 2 Z + . [Gr] Un concepto importante dentro de la teoría de grafos es la delciclo hamiltoniano, llamado así en honor de W. Hamilton (1805-1865), quien en 1859 usó la idea para formular un acertijo que usa las aristas de un dodecaedro regular. La solución para este problema no es difícil de encontrar, pero en el mundo de la investigación matemática se siguen buscando las condiciones necesarias y su…cientes para caracterizar los grafos no dirigidos (posteriormenteaclararemos este concepto) que poseen un camino o ciclo hamiltoniano. [Gr] Otro de los famosos y sorprendentes problemas relacionados con la teoría de grafos es el Teorema de los Cuatro Colores: F. Guthrie (1831-1899) plantea en 1852 la siguiente conjetura: “para colorear cualquier mapa geopolítico plano

2

Coloreado de Grafos Elmer Mosher

A

B C D

(suponiendo cada país formado por un únicotrozo), de tal modo que dos países con frontera común sean de distinto color, basta (como máximo) con cuatro colores” La relación de esta conjetura con la Teoría de Grafos es que si elegimos . un punto en cada país representado y se traza una línea uniendo dos puntos cada vez que correspondan a dos países adyacentes, se obtiene un grafo. El problema del Coloreado de Grafos consiste en atribuir un...