Matemáticas Generales - Capítulo 5: GRAFOS - 1º Bachillerato PDF

Matemáticas Generales. 1º Bachillerato. Capítulo 5: GRAFOS www.apuntesmareaverde.org.es Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández Ilustraciones: Autor. Textos Marea Verde / Wikipedia 128...

Matemáticas Generales. 1º Bachillerato. Capítulo 5: GRAFOS www.apuntesmareaverde.org.es Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández Ilustraciones: Autor. Textos Marea Verde / Wikipedia 128 Capítulo 5: Grafos 1. GRAFOS 1.1. APLICACIÓN COTIDIANA DE LA TEORÍA DE GRAFOS 1.2. DEFINICIÓN FORMAL 1.3. MATRICES Y GRAFOS 2. TIPOS DE GRAFOS 2.1. GRAFOS DIRIGIDOS (DIGRAFOS) 2.1.1. TIPOS DE RELACIONES EN UN GRAFO DIRIGIDO 2.2. GRAFO PLANO 2.3. GRAFOS PONDERADOS 2.3.1. COSTE O PESO DEL CAMINO 2.4. ÁRBOLES 3. LA FÓRMULA DE EULER 4. GRAFOS EULERIANOS Y HAMILTONIANOS 4.1. GRAFOS EULERIANOS. EL PROBLEMA DE LOS SIETE PUENTES DE KÖNIGSBERG 4.2. GRAFOS HAMILTONIANOS 4.3. RELACIÓN ENTRE GRAFOS EULERIANOS Y HAMILTONIANOS 5. COLORACIÓN DE GRAFOS. ETIQUETADO DE GRAFOS 5.1. COLORACIÓN DE VÉRTICES Resumen Nos adentramos en la Teoría de Grafos, estudiando sus características principales y más relevantes, los tipos de grafos existentes y sus características más notables, aplicaciones prácticas en la vida cotidiana con ejemplos de problemas que nos podemos encontrar en el día a día, aprendiendo a interpretar las relaciones entre sus vértices y extrapolando la Teoría de Grafos a problemas cotidianos, donde el alumnado aprenderá a obtener, interpretar y discutir resultados. Asimismo, se estudiará la coloración como técnica de etiquetado en grafos. Todo ello acompañado de ilustraciones, tablas, resúmenes y ejercicios resueltos que facilitarán la comprensión y aprendizaje de estos nuevos conceptos. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 129 Capítulo 5: Grafos 1. GRAFOS 1.1. Aplicación cotidiana de la Teoría de Grafos Los grafos resultan de gran utilidad a la hora de afrontar problemas cotidianos, pues nos permiten organizar la información que disponemos en tablas de forma esquemática. Por ejemplo: Vamos a considerar la siguiente situación: Existen 4 pueblos situados en algún lugar de la geografía española. Dichos pueblos permanecen comunicados entre sí por una red de carreteras, algunas de un solo sentido, y otras de doble sentido, tal y como se recoge en la siguiente tabla: Pueblo 1 Pueblo 2 Pueblo 3 Pueblo 4 Pueblo 1 NO SÍ SÍ SÍ Pueblo 2 SÍ NO NO NO Pueblo 3 SÍ SÍ NO SÍ Pueblo 4 NO NO SÍ NO Donde hemos escrito «SÍ» si existe carretera directa que comunique dichos pueblos, y «NO» en caso contrario. Vemos que la información recopilada en la tabla la podemos representar de la siguiente forma: Pueblo 1 Pueblo 2 Pueblo 4 Pueblo 3 Este esquema recibe el nombre de grafo, y resulta muy conveniente porque nos permite visualizar la misma información que queda recopilada en la tabla pero de forma más sencilla, y nos resulta más conveniente a la hora de extraer conclusiones. En la vida cotidiana hacemos uso de los grafos sin darnos cuenta; por ejemplo en las redes sociales. ¿Nunca has mirado entre tus seguidores de Instagram quién te seguía de vuelta o quién seguía a tus amigos o dejaba de seguir a otro usuario? Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 130 Capítulo 5: Grafos Por ejemplo: Imagínate los siguientes usuarios de Instagram: @euler @gauss @faraday @m_curie @h_de_alejandria Has estado stalkeando sus perfiles y has descubierto que @euler solo sigue a @m_curie y a @gauss; @gauss sigue a @euler, a @faraday y a @h_de_alejandria; @faraday solo sigue a @h_de_alejandria; @m_curie sigue a todos y @h_de_alejandria solo sigue a @euler y a @m_curie. Visto así, parece algo complicado extraer conclusiones. Vamos a organizar los datos en una tabla. @euler @gauss @faraday @m_curie @h_de_alejandria @euler NO SÍ NO SÍ SÍ @gauss SÍ NO NO SÍ NO @faraday NO SÍ NO SÍ NO @m_curie SÍ NO NO NO SÍ @h_de_alejandria NO SÍ SÍ SÍ NO De esta forma, la información queda más organizada; sin embargo, podemos ir más allá y representarlo mediante un grafo: @euler @gauss @h_de_alejandria @faraday @m_curie Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 131 Capítulo 5: Grafos Los grafos nos permiten, como puedes ver, estudiar la relación entre distintos elementos, en el primer ejemplo eran pueblos que se conectaban mediante una red de carreteras; y en este segundo ejemplo, nos muestra la relación que tienen cinco usuarios de Instagram. Sin embargo, las aplicaciones de la Teoría de Grafos son muchísimas: conocer la localización óptima donde se pueden construir infraestructuras públicas, conocer el camino óptimo que puede seguir un camión de reparto entre distintas ciudades para reducir el gasto de combustible, organización del tráfico aéreo, organizando los vuelos de diferentes compañías entre las distintas ciudades, etc. Sus numerosas aplicaciones y su simplicidad a la hora de mostrar relaciones entre distintos elementos convierten a los grafos en uno de los objetos más estudiados y admirados en Matemáticas. Vamos a darle un poco de formalidad a lo que acabamos de descubrir, ¿te atreves? Matemáticas discretas. Teoría de Grafos https://www.youtube.com/watch?v=PdA1Jz6iEWQ 1.2. Definición formal En Matemáticas y Ciencias de la computación se llama grafo al conjunto de vértices o nodos unidos por aristas o arcos que representan una relación entre los elementos de un conjunto. Notación: Dado un grafo G V , E  , llamamos V al conjunto de vértices o nodos y E al conjunto de pares no ordenados de vértices, o, simplemente, al conjunto de aristas. Nótese que V   , aunque sí se puede dar el caso de que E sea el conjunto vacío (si no existen conexiones entre los elementos sometidos a estudio; se llama grafo vacío). Así por ejemplo, si volvemos al problema inicial sobre los cuatro pueblos que se encontraban conectados entre sí por diferentes carreteras, podemos distinguir en el grafo que hicimos los siguientes elementos: VÉRTICE (o nodo) Pueblo 1 ARISTA (o arco) Pueblo 2 Pueblo 4 Pueblo 3 Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 132 Capítulo 5: Grafos Luego el conjunto de vértices de este grafo estará formado por el conjunto de todos los pueblos: V  Pueblo1,Pueblo 2, Pueblo3, Pueblo4 Y al conjunto de aristas o arcos lo escribiremos así: E Pueblo1,Pueblo2 , Pueblo1,Pueblo3 , Pueblo2,Pueblo1 , Pueblo2,Pueblo3 , Pueblo3,Pueblo4 , Pueblo4,Pueblo1 , Pueblo4,Pueblo3 (conjunto formado por pares no ordenados de vértices) Importante: Si un vértice no recibe o emite ninguna arista o arco, lo llamamos vértice aislado. Ejemplo: Dado el siguiente grafo, escribe su conjunto de nodos y aristas. Comenzamos detectando en el grafo cuáles son los vértices y cuáles son las aristas. En nuestro ejemplo, tenemos 5 vértices o nodos, los cuales están representados por los círculos azules, acompañados de las letras mayúsculas A, B, C, D, E para diferenciarlos. Por tanto: V  A,B,C,D,E Pasemos ahora a las aristas. Observamos, gracias al grafo, que tenemos 5 aristas, que son las que unen los vértices  A,D ,  A,C ,  B, D ,  B,C  y  C, E . Luego: E   A, D  ,  A, C  ,  B, D  ,  B, C  ,  C, E  Diferencia entre arista y arco Dados los vértices v1 y v2 , representamos la relación existente entre ellos a través de una arista o un arco. De esta forma, diferenciamos entre arista y arco argumentando que un arco es una arista orientada. Abundaremos en la orientación de las aristas en el punto 2, cuando estudiemos el grafo orientado. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 133 Capítulo 5: Grafos 2. TIPOS DE GRAFOS 2.1. Grafos dirigidos (digrafo) Un grafo dirigido es aquel que tiene en consideración la dirección de la relación existente entre los vértices o nodos. Ejemplo: El metro de una determinada ciudad tiene una línea de sentido único desde la estación E1 hasta la estación E2. Desde dicha estación salen dos líneas de sentido único, también: una hacia la estación E1 y otra hasta la estación E3, que conecta únicamente con la estación E4, de sentido único. La E4 conecta con todas las anteriores también en sentido único. Como se ha fijado un sentido único, una línea que conecte dos estaciones no “servirá” igual a un pasajero que quiera ir de la E1 hasta la E4, por ejemplo, y viceversa (a no ser que exista otra línea que una ambas estaciones y con sentido contrario). O sea, importa la dirección en la cual se relacionan los nodos (o las estaciones, en nuestro ejemplo), por ello, deberemos dar la orientación adecuada a las aristas que unen cada nodo, con el objetivo de representar correctamente la relación entre los vértices unidos. Si representamos el grafo correspondiente al enunciado, obtendremos la siguiente figura. Observación: Que haya aristas con doble sentido indica que entre ambas estaciones hay dos líneas diferentes y cada una circula en una dirección. Como vemos, damos la dirección asignada por el enunciado a cada arista, en función del sentido de la línea. A partir de este ejemplo, podemos llegar a una conclusión muy importante: En un grafo dirigido, se debe tener en cuenta la dirección de la relación entre los nodos, por lo que dada un arco que une los vértices v1 y v2 , diremos, de forma general que  v1 , v2    v2 , v1  , puesto que  v1 , v2  indica que v1 conecta con v2 en el sentido v1 8 v2 , mientras que  v2 , v1  indica la misma conexión pero en sentido opuesto: v2 8 v1. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 134 Capítulo 5: Grafos 2.1.1. Tipos de relaciones en un grafo dirigido ARCO Relación que indica dirección. Entre dos vértices puede existir más de un arco. Como su nombre indica, es el camino o ruta que debemos seguir para llegar de un vértice origen a un vértice extremo. Al camino lo representamos por la letra griega  , y entre paréntesis escribimos los vértices por los que pasamos:   vi , v j ,... Luego, dado un camino que tiene como inicio al vértice v0 y final al vértice v f , escribiremos:   v0 , v f     v0 , vi , v j ,..., v f   Camino elemental: Es aquel camino que no pasa más de una vez por un CAMINO mismo vértice.  Camino compuesto: Es aquel camino que pasa más de una vez por un mismo vértice.  Ciclo (o circuito): Es aquel camino que vuelve a su punto de origen. Cualquier punto de un ciclo puede ser punto de salida (y a su vez de llegada).  Diferenciamos entre ciclos (o circuitos) elementales, si solo pasa una vez por un mismo vértice, o ciclos (o circuitos) compuestos, en caso contrario. BUCLE Es la conexión de un vértice consigo mismo. Grado de un nodo en un grafo dirigido  Grado de recepción un vértice o nodo: Llamamos grado de recepción de un vértice o nodo y denotamos por Gr  vi  , donde vi es el vértice de interés, al número de arcos que recibe vi.  Grado de emisión de un vértice o nodo: Llamamos grado de emisión de un vértice o nodo y denotamos por GrE  vi  , donde vi es el vértice de interés, al número de arcos que emite vi. Los vértices cuyo grado de emisión es mayor que 1 se llaman ramificaciones: si GrE  vi   1 8 vi es una ramificación. Por ejemplo, Supongamos que hemos realizado una fotografía a un vértice de un determinado grafo, obteniendo la siguiente imagen: Como podemos observar, a dicho vértice llegan dos arcos, y el mismo vértice emite otros dos arcos. Por lo tanto, escribiremos: Gr  vi   2 y GrE  vi   2. Si no lo tienes claro, puedes observar la imagen de al lado y notarás como los arcos verdes son los que recibe el vértice y los azules son los que emite. Importante: Aquel grafo cuyos vértices tengan el mismo grado se denomina grafo regular. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 135 Capítulo 5: Grafos Actividad resuelta El calendario de los aficionados al fútbol marca una fecha importante pasado mañana: el clásico. Un equipo de la Policía Nacional se encarga de velar por la seguridad de los aficionados, por lo que decide restringir el tráfico en las calles cercanas al perímetro de seguridad montado alrededor del Bernabéu, tal y como se muestra en el siguiente grafo. Contesta a las siguientes preguntas: a) ¿De qué tipo de grafo se trata? Justifica tu respuesta. b) Escribe un camino elemental y otro camino 3 1 compuesto. c) Escribe un circuito elemental. 2 4 a) Se trata de un grafo dirigido, pues los vértices están unidos por arcos (aristas orientadas). Podemos decir también, que la Policía, al limitar el tráfico de algunas calles a un solo sentido está logrando hacer que la dirección importe, pues una persona que quiera pasar por una calle en la que solo está permitida la conducción en un sentido, no podrá pasar, por lo que la dirección en este ejemplo sí importa. b) Un camino elemental puede ser  1,4   1,2,3,4 Un camino compuesto puede ser   4,3    4, 2,1, 2,3 , porque pasa dos veces por el vértice 2. c) Un circuito elemental puede ser   4, 2,3, 4  , porque regresa al vértice inicial habiendo pasado por cada vértice una única vez. El maravilloso mundo del mundo de la teoría de grafos. Este vídeo es una reducida re‐ copilación de la infinidad de aplicaciones y problemas que abarca la mara‐ villosa Teoría de Grafos. En particular, se tratan ejemplos relacionados con establecer caminos en un grafo para resolver retos clásicos como el Pro‐ blema del viajante. Para no excederme en tiempo, he dejado fuera pro‐ blemas que considero de gran interés ‐coloración de grafos, caminos eulerianos, algoritmos de reso‐ lución‐ de modo que, si tienes interés en que desarrolle estos temas, no olvides suscribirte y comen‐ tar qué aspectos debería incluir en una potencial segunda parte. Ojalá me anime a ello. Actividades propuestas 1. Inventa un grafo dirigido cualquiera con las siguientes características. a) Presenta un total de cinco vértices. b) Un vértice tiene grado de emisión 2 y grado de recepción 1. c) Un vértice presenta un bucle. d) Hay un vértice aislado. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 136 Capítulo 5: Grafos 2. Indica el grado de emisión y recepción de cada vértice en los siguientes grafos. a) b) c) d) 3. Sara trabaja como escritora para un periódico digital y todas las mañanas se levanta, desayuna, se viste y se dirige a la Estación de metro de Fibonacci en su ciudad. Cuando llega a la estación le entregan un folleto como este. El señor que le hace entrega del folleto le dice a Sara que para llegar a su trabajo debe llegar a la Estación de Emmy Noether. a) ¿Qué representa el folleto? b) ¿Puede Sara ir directamente a su trabajo o necesita parar primero en otra estación? c) Escribe un ejemplo de un circuito elemental. d) ¿Cuál es el trayecto con menos paradas que puede seguir Sara? e) Halla el grado de emisión y recepción de cada estación. ¿Qué significado tiene? Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 137 Capítulo 5: Grafos 2.2. Grafo plano Denominamos grafo plano a aquel grafo cuyas aristas solo se cortan en los puntos que representan a los vértices. Por ejemplo: Observa este grafo. ¿Observas como hay dos aristas que se cortan? Fíjate cómo podemos rediseñar este grafo y convertirlo en un grafo plano, de forma que sus aristas no se intersequen: Si un grafo que aparentemente no es plano logramos representarlo en un plano de forma que ninguna arista se cruce, entonces diremos que el grafo en cuestión sí es plano. Ejemplos de grafos no planos son: k3,3 Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 138 Capítulo 5: Grafos Teorema de Kuratowski: Un grafo es plano sí y sólo sí no contiene a ningún grafo homeomorfo (que pueda obtenerse a partir de subdivisiones elementales de aristas) al k3,3 o al k5. Teorema de Whitney: Un grafo no es plano sí y sólo sí al eliminar una arista, uniendo sus vértices, de dicho grafo obtenemos k3,3 o k5. Un ejemplo muy extendido es el famoso Grafo de Petersen: A partir de su representación es muy fácil darse cuenta de que no se trata de un grafo plano, pues hay varios puntos donde las aristas se cortan unas con otras. Sin embargo, si queremos argumentar nuestra postura usando el Teorema de Whitney, podemos decir que si de este grafo eliminamos las aristas marcadas en rojo, uniendo los vértices, obtendremos k5 , tal y como se muestra en esta otra imagen: 2.3. Grafo ponderado Actividad resuelta Queremos hacer un viaje por la geografía española visitando las ciudades de Málaga, Madrid, Barcelona, Valencia, Sevilla, Alicante y Asturias. Hemos consultado en Google Maps la longitud, en km, de cada trayecto, y lo hemos recopilado en la siguiente tabla: Málaga Madrid Barcelona Valencia Sevilla Alicante Asturias Málaga 0 529 996 618 206 472 974 Madrid 529 0 626 360 530 424 446 Barcelona 996 626 0 349 994 527 889 Valencia 618 360 349 0 656 170 804 Sevilla 206 530 994 656 0 595 779 Alicante 472 424 527 170 595 0 871 Asturias 974 446 889 804 779 871 0 Visto así en la tabla, no resulta efectivo a la hora de planificar el viaje, por lo que decidimos Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 139 Capítulo 5: Grafos esquematizarlo, hacer un grafo. Como vemos, el grafo, en este caso, no solo no aporta ninguna información sino que estamos perdiendo información, ¿no hicimos la tabla con la finalidad de conocer la longitud de cada trayecto?, ¿dónde está reflejada esa longitud en el grafo? Con el fin de no perder esta información, debemos colocar la longitud de cada trayecto en cada arista, como se ha hecho en el siguiente otro grafo: A este tipo de grafo, donde las aristas están acompañadas de un valor numérico que recibe el nombre de peso o coste se le llama grafo ponderado. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 140 Capítulo 5: Grafos Denominamos grafo ponderado a aquel grafo cuyas aristas se encuentran acompañadas de un valor p  vi , v j  que llamamos peso o coste. El grafo ponderado resulta muy útil a la hora de estudiar problemas cotidianos como el que se ha plan‐ teado aquí. 2.3.1. Coste o peso del camino Fíjate que si por ejemplo queremos hacer un viaje en el que queremos pasar solo y exclusivamente por Málaga, Alicante y Valencia, partiendo desde Madrid, para calcular el total de kilómetros que haremos en nuestro viaje, sin contar la vuelta a Madrid, basta con sumar los pesos de las aristas por donde pasamos (ahora le daremos formalidad a este concepto). En el ejemplo que hemos puesto deberemos sumar los 529 km que separan Madrid de Málaga, los 472 km que recorreremos hasta llegar a Alicante y los 170 km que separan Alicante de Valencia: Total de km efectuados  529  472  170  1 171 km Considérese un camino   vk , vn    vk ,..., vn  , se define por coste o peso del camino n 1   vk , vn    vk ,..., vn  a  p v , v   p v , v   p v ik i i 1 k k 1 k 1 , vk  2     p  vn 1 , vn . Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 141 Capítulo 5: Grafos Actividad resuelta La clase de 2º de Bachillerato está organizando el viaje de fin de curso. Tras votar entre los destinos candidatos, ha salido Nueva York como vencedor. Los alumnos barajan ahora dos compañías diferentes de vuelo, buscando aquella que resulte más barata. Consultando las páginas webs de ambas compañías, extraen la siguiente información:  La primera compañía no dispone de vuelo directo. Hay dos opciones: salen a las 8:00 de la mañana desde el aeropuerto Internacional de Valencia, llegan a las 9:05 al aeropuerto de Barcelona (El‐Prat), donde cogen otro vuelo hasta Nueva York, llegando a las 18:05. La segunda opción es salir desde Valencia a las 9:00 de la mañana hasta el aeropuerto de Barajas (Madrid), donde llegarían a las 10:00. De ahí cogen otro vuelo hasta Nueva York, llegando a las 18:10. Esta compañía cobra 52.5 € por cada hora volando.  La segunda compañía tampoco dispone de vuelo directo. Hay dos opciones, también: salen a las 7:00 de la mañana desde el aeropuerto de Valencia hasta el aeropuerto de París (Francia), llegando a las 11:00 de la mañana. Cogen otro vuelo hasta llegar a Nueva York, donde llegarían a las 19:15. Como segunda opción, pueden salir a las 9:15 de la mañana desde Valencia hasta Barcelona, llegando a las 10:05. Desde Barcelona cogen un vuelo directo a Nueva York, llegando a las 19:30. Esta compañía cobra 50 € por cada hora de vuelo. a) Elabora un grafo que recoja las rutas que ofertan ambas compañías. b) ¿Qué ruta es la más barata en cada compañía? ¿Cuál es la que deben elegir los alumnos de 2º de Bachillerato? c) Calcula el precio de cada ruta. a) Comenzamos elaborando cada grafo. Recordemos que la primera compañía ofertaba dos posibilidades. La primera de ellas la podemos separar en dos tramos: Valencia – Barcelona y Barcelona – Nueva York. Como al final nos preguntan por el precio (¿Qué ruta es la más barata en cada compañía? ¿Cuál es la que deben elegir los alumnos de 2º de Bachillerato?), y este viene dado en función de las horas de vuelo, vamos a incluir esta información en nuestro grafo. El tramo Valencia – Barcelona tiene una duración de 65 minutos; el tramo Barcelona – Nueva York tiene una duración de 540 minutos. La segunda posibilidad la dividimos en los tramos Valencia – Madrid y Madrid – Nueva York. La duración de estos tramos es 60 minutos y 490 minutos, respectivamente. La segunda compañía ofrece también dos posibilidades: la primera la podemos dividir en los tramos Valencia – París y París – Nueva York, con una duración respectiva de 240 minutos y 495 minutos. La segunda posibilidad la dividimos en los tramos Valencia – Barcelona, de duración 50 minutos y Barcelona – Nueva York, con una duración de 565 minutos. Trasladamos esta información a los grafos: Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 142 Capítulo 5: Grafos Compañía 1 Compañía 2 b) Puede que directamente pensemos en sumar los minutos de vuelo en cada camino que podamos formar con el inicio en Valencia y final en Nueva York, pero esto no tiene sentido, puesto que las rutas marcadas por la compañía son fijas, luego elegida una ruta, no podemos modificar su trayectoria. Una vez razonado esto, vamos a estudiar el precio de cada una de las rutas que oferta cada compañía.  Compañía 1 3 o Ruta 1:   2, 4    2,3, 4  8 p      p  i, i  1  p  2,3  p  3, 4   65  540  605 i2 2 o Ruta 2:  1, 4   1, 2, 4  8 p      p  vi , vi 1   p 1, 2   p  2, 4   60  490  550 i 1 Fíjate en la diferencia en cómo usamos la notación sigma en cada caso. En el primero, como los vértices están dados como números naturales consecutivos, se puede escribir como  p  i, i  1 En la segunda, en cambio, escribiremos  p  v , v  , donde i i 1 vi se refiere al vértice que ocupa la posición i dentro del camino, y vi 1 a su consecutivo. Por tanto, el precio lo podemos recoger en la siguiente tabla: Minutos de vuelo Horas de vuelo Precio/h Total (Coste del camino) COMPAÑÍA 1 Ruta 1 605 10.08333…h 529.375 € 52.5 € Ruta 2 550 9.1666…h 481.25 € Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 143 Capítulo 5: Grafos De la compañía 1, resulta más barata la ruta 2, con un precio total de 481.25 €. En realidad, sabiendo que la ruta dos es más rápida, ya podríamos haber deducido que ésta sería la más barata; sin embargo, como nos piden el precio en el apartado c), podemos calcularlo ya.  Compañía 2 3 o Ruta 1:  1, 4   1,3, 4  8 p      p  vi , vi 1   p 1,3  p  3, 4   240  495  735 i 1 2 o Ruta 2:  1, 4   1, 2, 4  8 p      p  vi , vi 1   p 1, 2   p  2, 4   50  565  615 i 1 Ya sabemos que resultará más barata la compañía 2. Sin embargo, como nos preguntan también por los precios, vamos a armar una tabla como la anterior. Minutos de vuelo Horas de vuelo Precio/h Total (Coste del camino) COMPAÑÍA 2 Ruta 1 735 12.25 h 612.5 € 50 € Ruta 2 615 9.1666…h 512.5 € c) Total COMPAÑÍA 1 Ruta 1 529.375 € Ruta 2 481.25 € COMPAÑÍA 2 Ruta 1 612.5 € Ruta 2 512.5 € Los alumnos de 2º de Bachillerato deben elegir a la compañía 1, y dentro de la misma, deben escoger la ruta 2. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 144 Capítulo 5: Grafos Actividades propuestas 4. Inés quiere hacer el siguiente viaje con su familia: Málaga – Sevilla – Madrid – Valencia – Málaga. a) Elabora el grafo que represente dicho viaje. Puedes ayudarte de un grafo anterior. b) Escribe la matriz de adyacencia del grafo representado. c) Calcula el coste del camino asociado al viaje que quiere realizar Inés. ¿Qué significa dicho coste? d) Si la cantidad de combustible gastado por el coche de la familia de Inés viene dictaminado por la función f(x) = 0.102 x, donde f  x  son el total de litros consumidos, y x el total de kilómetros recorridos, determina la cantidad de combustible que se ha gastado durante el viaje. 5. El siguiente grafo muestra la red de carreteras que existe entre dos grandes ciudades y el precio que se debe abonar en un determinado peaje para poder tomar dicha carretera. Halla el precio de todos los posibles caminos que se pueden seguir para llegar desde la ciudad A hasta la ciudad B. ¿Cuál de ellos resulta el más económico? 6. Una empresa de repartos debe efectuar la entrega de un determinado pedido. Si el camión de reparto se encuentra en el punto C y el destino es el punto D. Escribe todas las posibles rutas que puede seguir el repartidor para llegar al destino. a) Escribe la matriz de adyacencia de dicho grafo. b) Si la empresa hace un descuento de 0.5 € al importe total por cada hora de retraso en la entrega, y justo en el instante en el cual el repartidor se encuentra en el punto C ya lleva un retraso de media hora, ¿qué descuento se aplicará al producto si el repartidor opta por coger la ruta más rápida? ¿Y si coge la ruta más lenta? 7. Sabiendo que el gasto medio de combustible, en litros, de un determinado coche viene dictaminado por la función f(x) = 0.093 x, donde x son los kilómetros recorridos, elabora un grafo ponderado como este, en el que recojas los litros de combustible que pierde dicho coche al recorrer las diferentes distancias (en kilómetros) entre las ciudades consideradas en el grafo. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 145 Capítulo 5: Grafos 2.4. Árboles Llamamos árbol a aquel grafo que es acíclico y además, cada par de vértices del árbol debe estar conectado por exactamente un camino. Grafo conexo: Un grafo conexo si cada par de vértices está conectado por al menos un camino. Grafo acíclico: Es aquel grafo que no contiene ciclos.  En un árbol, al añadir una nueva arista, se forma un ciclo. Fíjate en los siguientes ejemplos para comprenderlo mejor. Ejemplos: Fíjate como este grafo es un árbol, puesto que es conexo (todos sus vértices están conectados por un camino) y, además, es acíclico (no contiene ciclos). Por el contrario, nota como este otro grafo no es un árbol, porque pese a que todos sus vértices estén conectados por un camino, el grafo presenta un ciclo. Sí se trata de un árbol. No está tan “claro” como el anterior, pero observa como no existe ningún ciclo, tomes el camino que tomes, nunca vuelves al punto de partida. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 146 Capítulo 5: Grafos Actividad propuesta 8. Discute qué grafos se corresponden con árboles. a) b) c) d) e) f) Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 147 Capítulo 5: Grafos 1.3. MATRICES Y GRAFOS 1.3.1. Definición de matriz Las matrices son una de las herramientas más usadas dentro de las Matemáticas y están asociadas a un conjunto de datos numéricos ordenados. Se utilizan, por ejemplo, en computación gráfica, para resol‐ ver sistemas de ecuaciones lineales, en procesos estocásticos… Encontramos las matrices en muchas ciencias: Sociología, Economía, Demografía, Física, Biología, etc. La idea intuitiva de matriz es muy sencilla, pudiéndose definir una matriz como un tabla de números ordenados, números que pueden provenir de experimentos, encuestas, análisis económicos, etc. Por tanto: Se llama matriz de orden m × n a un conjunto de números reales dispuestos en m filas y en n columnas, de la forma:  a11 a12  a1n    a a 22  a2n  A   21        a  a mn   m1 am2 Si el número de filas es igual al número de columnas (m = n) se habla de una matriz cuadrada. Actividad resuelta Ya hemos visto tablas de números, como: Málaga Madrid Barcelona Valencia Sevilla Alicante Asturias Málaga 0 529 996 618 206 472 974 Madrid 529 0 626 360 530 424 446 Barcelona 996 626 0 349 994 527 889 Valencia 618 360 349 0 656 170 804 Sevilla 206 994 656 0 595 779 530 Alicante 472 424 527 170 595 0 871 Asturias 974 446 889 804 779 871 0 Que se podría escribir como la matriz (eliminando muchas de las filas y columnas para verlo mejor): 0 529 996 𝐴 𝑎 529 0 626 996 626 0 Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 148 Capítulo 5: Grafos Ahora es una matriz de 3 filas y 3 columnas, por lo que decimos que su dimensión es 3x3. Por tanto es una matriz cuadrada de orden 3. El elemento a23 es el que ocupa la fila 2 y columna 3, luego es a23 = 626. Observa que es una matriz simétrica. Tomamos como eje de simetría la diagonal, y comprueba que; aij = aji. En nuestro caso: a23 = 626 = a32; a12 = 529 = a21; a13 = 996 = a31. 1.3.2. Matrices y grafos Las matrices y los grafos comparten una muy estrecha relación, siendo las matrices una de las herra‐ mientas más útiles dentro de la Teoría de Grafos. Gracias a ellas podemos establecer de forma numéri‐ ca y ordenada las conexiones entre los distintos vértices de un grafo, y además, su manejo nos permite resolver problemas cotidianos muy interesantes. Actividad resuelta En un país A, existen tres aeropuertos internacionales (A 1 , A 2 y A 3 ); en otro país B existen cuatro (B 1 , B 2 , B 3 y B 4 ); y en un tercer país C existen dos (C 1 y C 2 ). Desde el aeropuerto A 1 salen vuelos con destino a B 1 , B 2 , C 1 y dos vuelos con destino a B 4. Desde el aeropuerto A 2 salen vuelos con destino a B 2 , B 3 y dos vuelos con destino a B 4. Desde el aeropuerto A 3 sólo sale un vuelo con destino a B 3. Desde cada aeropuerto del país B, salen dos vuelos a cada uno de los aeropuertos del país C. Haz un grafo que exprese la situación. El esquema de los vuelos es: B1 B2 A1 A2 B3 A3 B4 C1 C2 Expresa mediante matrices: a) Los vuelos del país A al B. b) Los vuelos del país B al C. c) Los vuelos de A a C, sin transbordo Vamos a buscar las matrices del grafo: a) Representamos los vuelos desde A (filas) hasta B (columnas) Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 149 Capítulo 5: Grafos 1 1 0 2   X1   0 1 1 2  0 0 1 0   Es una matriz de dimensión 3x4. Tiene 3 filas y 4 columnas. b) Representamos los vuelos desde B (filas) hasta C (columnas) 2 2   2 2 X2   2 2   2 2   c) Representamos los vuelos directos desde A (filas) hasta C (columnas): 1 0   X 3  0 0 0 0   Es una matriz de dimensión 3x2, con 3 filas y 2 columnas. Ninguna de ellas es cuadrada ni simétrica. 1.3.3. La matriz de adyacencia La matriz de adyacencia asociada a un grafo es una matriz que nos ofrece información acerca de las relaciones entre los distintos vértices del grafo. Su construcción es relativamente sencilla, y la vamos a visualizar a través de los siguientes ejemplos. Actividad resuelta Dado el siguiente grafo, escribe su matriz de adyacencia.  ¿Cuál será la dimensión de nuestra matriz? Debe ser una matriz cuadrada de dimensión 5x5, ya que tenemos 5 vértices. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 150 Capítulo 5: Grafos  ¿Qué tipo de grafo es? Como es un grafo no dirigido, nuestra matriz de adyacencia será, por lo general (no siempre), una ma‐ triz cuadrada booleana (sus elementos solo pueden ser los dígitos 0 y 1). Escribiremos el dígito 1 en la posición aij si los vértices i y j son adyacentes. Por ser un grafo no dirigido, se trata de una matriz simétrica, donde aij  a ji. En caso de que dos vértices sean adyacentes por dos o más aristas, el dígito que ocupa la posición referente a esos vértices será el número de aristas que los conectan.  Buscamos los dígitos correspondientes a cada elemento Para conocer el dígito correspondiente a cada elemento nos preguntamos, por cada elemento: Para el a11 : ¿Existe alguna arista que conecte el vértice 1 con el vértice 1, en este sentido? La respuesta es no, por lo que escribimos el dígito 0. Para el a14 : ¿Existe alguna arista que conecte el vértice 1 con el vértice 4, en este sentido? La respuesta es sí. Hay 1 arista que satisface esta conexión. Por lo tanto, a14  1. Como A sólo está relacionado con C y con D, ponemos un 1 en la primera fila, tercera columna, y en la primera fila, cuarta columna. Y ponemos un 0 en el resto de las posiciones de la primera fila: 0 0 1 1 0 ⎛ ⎞ 𝐴 ⎜ ⎟ ⎝ ⎠ Como B está relacionado con C y con D, ponemos un 1 en la segunda fila, tercera columna, y en la se‐ gunda fila, cuarta columna. Y 0 en el resto de la segunda fila: 0 0 1 1 0 ⎛0 0 1 1 0⎞ 𝐴 ⎜ ⎟. ⎝ ⎠ Escribimos los elementos simétricos a los ya obtenidos: 0 0 1 1 0 ⎛ 0 0 1 1 0⎞ 𝐴 ⎜1 1 ⎟. 1 1 ⎝0 0 ⎠ Y así con cada vértice. 𝟎 𝟎 𝟏 𝟏 𝟎 ⎛𝟎 𝟎 𝟏 𝟏 𝟎⎞ 𝑨 ⎜𝟏 𝟏 𝟎 𝟎 𝟏 ⎟. 𝟏 𝟏 𝟎 𝟎 𝟎 ⎝𝟎 𝟎 𝟏 𝟎 𝟎⎠ Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 151 Capítulo 5: Grafos Actividad resuelta Escribe la matriz de adyacencia del siguiente grafo: Pueblo 1 Pueblo 2 Pueblo 4 Pueblo 3 ¿Cuál será la dimensión de nuestra matriz? Debe ser una matriz cuadrada de orden 4, ya que tenemos 4 pueblos. ¿Qué tipo de grafo es? Como es un grafo dirigido, debemos tener en cuenta el sentido de la relación. Hacemos notar que la existencia de una relación en el sentido i j no implica una relación en el sentido opuesto. Por lo que, por lo general, una matriz de adyacencia asociada a un grafo dirigido no será simétrica. La matriz de adyacencia es: 0 1 1 0 𝐴 1 0 1 0 1 0 0 1 1 0 1 0 Observa que, en efecto, no es simétrica. Actividad resuelta En mi ciudad se están celebrando algunas fiestas locales. Para ello, el Ayuntamiento ha reservado tres de los seis parques de la ciudad para la celebración de dichas fiestas. Todos los parques de la ciudad están conectados entre sí a través de una red de caminos. Los parques reservados están representados en rojo. Podemos apoyarnos de una matriz de adyacencia para conocer las conexiones entre los diferentes par‐ ques. Vamos a construir la matriz de adyacencia siguiendo los siguientes pasos. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 152 Capítulo 5: Grafos  ¿Cuál será la dimensión de nuestra matriz? Como hay 6 parques (que son justamente los 6 vértices del grafo) vamos a construir una matriz cuadrada de orden 6. Por tanto, llamando A a nuestra matriz de adyacencia, tenemos: 1 2 3 4 5 6 1    2  3  A   4  5    6   Recomendación: a la hora de construir la matriz de adyacencia resulta útil escribir en cada fila y columna el nombre de cada vértice, en nuestro caso, como los hemos enumerado del 1 al 6, es‐ cribimos los números del 1 al 6.  ¿Qué tipo de grafo es? Ya hemos visto que: A) Si es un grafo no dirigido, nuestra matriz de adyacencia será, por lo general (no siempre), una matriz cuadrada booleana (sus elementos solo pueden ser los dígitos 0 y 1). Escribiremos el dígito 1 en la posición aij si los vértices i y j son adyacentes. Por ser un grafo no dirigido, se trata de una matriz simétrica, donde aij  a ji. En caso de que dos vértices sean adyacentes por dos o más aristas, el dígito que ocupa la posición referente a esos vértices será el número de aristas que los conectan. B) Si es un grafo dirigido, debemos tener en cuenta el sentido de la relación. Hacemos notar que la existencia de una relación en el sentido i j no implica una relación en el sentido opuesto. Por lo que, por lo general, una matriz de adyacencia asociada a un grafo dirigido no será simétrica. En nuestro caso, se trata de un grafo dirigido. Construimos su matriz de adyacencia: 1 2 3 4 5 6 1  a11 a12 a13 a14 a15 a16    2  a21 a22 a23 a24 a25 a26  3 a a32 a33 a34 a35 a36  A   31  4  a41 a42 a43 a44 a45 a46  5  a51 a52 a53 a54 a55 a56    6  a61 a62 a63 a64 a65 a66  Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 153 Capítulo 5: Grafos Actividades propuestas 9. Completa la matriz de adyacencia del grafo: 1.3.4. Operaciones con matrices Suma de matrices Dadas dos matrices A y B de dimensión m  n , se define la suma de matrices  A  B  como aquella matriz cuyos elementos son la suma de los elementos que ocupan la misma posición: 𝑪 𝑨 𝑩 ⇒ 𝒄𝒊𝒋 𝒂𝒊𝒋 𝒃𝒊𝒋 a a12 a13  b b12 b13   a  b11 a12  b12 a13  b13  A   11  B   11  C  A  B   11   a 21 a 22 a 23   b21 b22 b23   a 21  b21 a 22  b22 a 23  b23  Ejemplo: 1 2 4  2 1 3  3 1 7       A  1 3 2 B    2 3 4 A  B   3 6 6  0 2 1    3 1 5  3  3 6      Producto de matrices Sean las matrices A y B de dimensiones m  n y n  p (es decir, el número de columnas de la matriz A es igual al número de filas de la matriz B). Se define el producto 𝐴 ∙ 𝐵, y en ese orden, como una matriz C de dimensiones m  p cuyos elementos son de la forma: 𝐴 𝑎 →𝐶 𝐴 𝐵 𝑎 𝑏 𝑐 𝑐 𝑎 𝑏 𝐵 𝑏𝑖𝑗 Es decir, el elemento c11 se obtiene multiplicando escalarmente los elementos de la primera fila de la matriz A por los elementos de la primera columna de la matriz B, y así sucesivamente. Para que dos matrices puedan multiplicarse debe verificarse que el número de filas de la primera coin‐ cida con el número de columnas de la segunda. Ejemplo: Veamos un producto de matrices desarrollado paso a paso de dos matrices cuadradas de dimensión 3: 1 2 3 2 1 0 𝐴 4 5 6 ; 𝐵 3 2 1 → 1 0 0 4 1 0 Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 154 Capítulo 5: Grafos 1∙2 2∙3 3∙4 1∙1 2∙2 3∙1 1∙0 2∙1 3∙0 20 8 2 →𝐴∙𝐵 4∙2 5∙3 6∙4 4∙1 5∙2 6∙1 4∙0 5∙1 6∙0 47 20 5 1∙2 0∙3 0∙4 1∙1 0∙2 0∙1 1∙0 0∙1 0∙0 2 1 0 El producto de matrices no es conmutativo Actividad resuelta Seguimos con la actividad anterior. Queremos saber ahora los vuelos posibles de A a C, con o sin trasbordo. Ya conoceos los vuelos directos: 1 0   X 3  0 0 0 0   Los vuelos con trasbordo los podemos obtener multiplicando las matrices X1 por X2. Sumando con los vuelos directos obtenemos:  2 2  1 1 0 2    1 0  2  2  0  4 2  2  0  4  1 0  8 8   1 0  9 8     2 2             X1  X 2  X 3   0 1 1 2      0 0    0  2  2  4 0  2  2  4    0 0   8 8    0 0   8 8   0 0 1 0   2 2  0 0  2 2     2  0 0  2 2    2 2      0 0  2   Actividad resuelta El grafo siguiente nos indica las relaciones de dominio entre cuatro personas: B A D C Escribimos su matriz de adyacencia: 0 1 0 1   0 0 1 1 0 0 0 0   0 0 0 0   Observamos, de nuevo, que está formada por 0 y 1, y que, como el grafo es dirigido, no es simétrica. Nos indica que A domina a B y a D, y que B domina a C y a D. Multiplicamos dicha matriz de adyacencia por sí misma, e interpretamos el resultado: Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 155 Capítulo 5: Grafos 0 1 0 1 0 1 0 1 0 0 1 1       0 0 1 1 0 0 1 1 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 0       0 0 0 0   0 0 0 0   0 0 0 0   Observamos que ahora A domina a C y D, solicitando ayuda a B, al que domina. A es el dominante. Actividad resuelta El grafo siguiente nos indica las personas que están conectadas por WhatsApp. B A C Escribimos su matriz de adyacencia: 0 1 1   1 0 0 1 0 0   Observamos, de nuevo, que está formada por 0 y 1, y que, como el grafo es NO dirigido, es una matriz simétrica. Nos indica que A está conectado por WhatsApp con B y C. Multiplicamos dicha matriz de adyacencia por sí misma, e interpretamos el resultado:  0 1 1  0 1 1  2 0 0       1 0 0  1 0 0   0 1 1 1 0 0 1 0 0  0 1 1       Ahora un WhatsApp de A podría llegar a esa misma persona A por dos caminos distintos (a través de B y de C), pero sólo sus propios WhatsApp. A la persona B le llegarían sus propios WhatsApp, y los de C. A la persona C le llegarían sus propios WhatsApp, y los de B. Actividades propuestas 10. Multiplica por sí misma la matriz de adyacencia del grafo adjunto, e interpreta el resultado: Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 156 Capítulo 5: Grafos 3. LA FÓRMULA DE EULER Teorema En un poliedro convexo, se cumple que el número de caras de dicho poliedro, C más el número de vértices, V , menos el número de aristas, A es siempre igual a 2 , es decir: C V  A  2 Este teorema ya lo has visto en Geometría de cursos anteriores. Vamos a demostrar este teorema de una forma muy sencilla. Por simplicidad, lo demostraremos para un cubo, aunque este razonamiento es extrapolable a cualquier otro poliedro convexo. Antes de comenzar con la demostración, debemos tener muy claro qué es un poliedro convexo. Un poliedro convexo es aquel para el cual dado cualquier par de puntos del mismo, el segmento que los une queda contenido dentro del poliedro. Poliedro convexo Ahora que ya sabemos lo que es un poliedro convexo, procedemos con la demostración Demostración Vamos a considerar, como hemos especificado anteriormente, al cubo, por una cuestión de simplicidad. Considerado el cubo, vamos a sustraer una de sus caras y vamos a proyectarlo sobre un plano, tal y como se observa en la siguiente imagen. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 157 Capítulo 5: Grafos A continuación, vamos a realizar las siguientes triangulaciones: Realizamos una serie de transformaciones y observamos cómo estas afectan al número de C  V  A. La primera transformación es fruto de la triangulación que ya hemos realizado. De esta forma, si nos fijamos en una sola cara (en el resto ocurre lo mismo), podemos ver cómo hemos añadido una nueva arista (en azul discontinua) y dividido una cara en dos, que es lo mismo que añadir una nueva cara. De esta forma, como la arista que añadimos resta a la cara que sumamos, el número C  V  A no se ve alterado. Continuamos realizando una segunda transformación. Vamos a eliminar aquellas caras que tengan una arista exterior (aquellas caras marcadas en verde): De esta forma, podemos notar como al eliminar dicha cara estamos eliminando a su vez una arista. Por lo tanto, C  V  A no ha sufrido ninguna alteración. Vamos a realizar la última transformación. Ahora vamos a eliminar aquellas caras que tengan dos aristas externas (las señaladas en azul en la siguiente imagen). Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 158 Capítulo 5: Grafos De esta forma, fíjate que estamos eliminando un total de 4 caras, 6 aristas y dos vértices, de forma que el número C  V  A sigue igual, sin alteraciones, puesto que observa cómo caras y vértices suman y aristas restan:  4  2    6   0. Por tanto, observa la figura que nos queda: Que tiene dos caras, cuatro vértices y 5 aristas. Pero… ¡Recuerda que al principio de la demostración extraíamos una cara! Esa cara tenía 4 vértices y 4 aristas; de forma que C  V  A   2  1    4  4    5  4   3  8  9  2 Quedando demostrado que C  V  A  2. Extrapolación del Teorema de Euler a grafos planos En un grafo plano, se verifica el Teorema de Euler (o Fórmula de Euler, según el autor); verificándose que en un grafo plano y conexo, el número de caras, más el de vértices, menos el número de aristas es siempre 2 : CV  E 2 Actividades propuestas 11. De un determinado poliedro convexo sabemos que su número de caras es 10 y su número de aristas es 16. Calcula el número de vértices de dicho poliedro. 12. Sabiendo que el número de caras de un determinado poliedro convexo es 6 y el número de aristas del mismo es 12, ¿cuál es el número de vértices de dicho poliedro? ¿de qué poliedro se trata? Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 159 Capítulo 5: Grafos 4. GRAFOS EULERIANOS Y HAMILTONIANOS 4.1. Grafos eulerianos. El problema de los siete puentes de Königsberg. Euler es considerado como el precursor de la Teoría de Grafos, debido a sus numerosas aportaciones a esta teoría. Una de las más importantes fue ofrecer solución a un problema contextualizado en la Prusia del siglo XVIII, cuando Euler tenía 34 años. Durante la estancia de Euler en Königsberg, se propagó el conocido como problema de los siete puentes de Königsberg, que se popularizó en modo de juego entre las mentes matemáticas de la época. Podemos resumir el problema a través del siguiente enunciado: Dado el mapa de Königsberg, con el río Pregel dividiendo el plano en cuatro regiones distintas, que están unidas a través de los siete puentes, ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo solo una vez cada uno, y regresando al mismo punto de partida? Fue Euler en 1763 quien ofreció solución a dicho problema, con la publicación de «Solutio problematis ad geometriam situs pertinentis». Para dar solución, Euler se basó en el siguiente planteamiento: Donde consideró el grafo de la última figura, en el que los vértices representan las diferentes regiones que separan los puentes (aristas): 2 2 1 4 1 4 3 3 En su solución, Euler argumentó que, para cualquier camino que consideremos, se deberá cumplir que el vértice intermedio de dicho camino debe estar conectado a dos aristas (si llegamos por medio de una determinada arista a un vértice concreto, la única forma de salir de dicho vértice es a través de una arista diferente), siendo el punto de inicio (y de final, claro) los únicos que puedan tener un número impar de aristas. Sin embargo, es fácil notar que esto no ocurre en nuestro grafo, cuyos vértices tienen todos grado impar (3 de ellos tienen grado 3 y uno de ellos, el restante, tiene grado 5). Luego… sería imposible encontrar un camino que satisfaga las condiciones planteadas en el problema. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 160 Capítulo 5: Grafos Ciclo euleriano: Recibe el nombre de ciclo euleriano (nombrado así en honor a Leonhard Euler), aquel ciclo o circuito que recorre todas las aristas una única vez del grafo y regresa al punto inicial. Un ciclo como éste era el que se pretendía buscar en el problema de los siete puentes de Königsberg. Sea un grafo no dirigido y conexo, se verifica que:  Si tiene como máximo dos vértices impares, y el resto tienen grado par, el grafo tomado en consideración contiene un camino euleriano.  Si el grado de cada vértice es par, el grafo tomado en consideración contiene un ciclo euleriano (y por tanto es un grafo euleriano). Dado un grafo dirigido conexo, decimos que es euleriano si el grado interno de sus vértices es igual al grado externo. Definimos como grafo euleriano al grafo que contiene un ciclo euleriano. 4.2. Grafos hamiltonianos Grafo hamiltoniano: Es aquel grafo que contiene un circuito hamiltoniano. Recibe dicho nombre en honor al matemático, físico y astrónomo irlandés William R. Hamilton. Llamamos circuito hamiltoniano al ciclo simple (solo pasa una vez por cada vértice) que recorre todos los vértices del grafo. Ejemplo: Fíjate como el siguiente grafo, G , contiene un ciclo hamiltoniano, que se ha señalado en rojo en la figura de al lado.  1, 2,3,5,1 8 Por tanto, podemos afirmar que el grafo G es un grafo hamiltoniano. Existe el Teorema de Dirac para conocer si un grafo es hamiltoniano o no. Es un teorema que no vamos a estudiar a fondo, pero si vamos a enunciar. Debe utilizarse con mucho cuidado y siempre en un grafo conexo. Teorema de Dirac Sea GV, E un grafo conexo formado por V vértices y E aristas, decimos que G es hamiltoniano sí V y sólo sí se verifica que Gr  v  , vV (para todo v perteneciente a V , o sea, para cada vértice). 2 Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 161 Capítulo 5: Grafos 4.3. Relación entre grafos eulerianos y hamiltonianos Como te has podido dar cuenta, los grafos eulerianos y hamiltonianos parecen estar muy relacionados; sin embargo, la relación entre eulerianos y hamiltonianos dependerá del grafo estudiado, no todos los grafos eulerianos son hamiltonianos, ni al revés. Actividades propuestas 13. Como ejercicio te proponemos completar la siguiente tabla, incluyendo en cada casilla un ejemplo de un grafo que cumpla con cada condición, para que compruebes por tu propia cuenta como no existe ninguna relación aparente. EULERIANO NO EULERIANO HAMILTONIANO NO HAMILTONIANO Actividades resueltas Un cartero ha repartido las cartas que llevaba en su saca desde la central de correos, O, a los domicilios A, B, C, D y E, que se comunican por la siguiente red de calles. El recorrido que ha seguido el cartero es el que está descrito en el grafo adjunto. a) ¿Existe algún circuito que pueda seguir el cartero para entregar todas las cartas pasando una única vez por una misma calle? Argumenta tu respuesta. b) ¿Es hamiltoniano el grafo descrito por la trayectoria que sigue el cartero? Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 162 Capítulo 5: Grafos A: Red de calles entre la central de Correos, O, B: Recorrido que sigue el cartero y las viviendas A,B,C,D,E Los números de cada arco indican el orden Solución: Nos preguntan por la existencia de un circuito formado por todas las calles de forma que solo pasemos una vez por cada una de ellas. Que sea un circuito implica que debamos finalizar en la central de Co‐ rreos, por la propia definición de circuito. Vemos que lo que nos piden en realidad es determinar la existencia de un circuito euleriano en el grafo A. Como podemos ver, el grafo tiene un total de seis vértices: todos ellos con un grado par, excepto los vértices A y E, que tienen un grado impar. Sin embargo, como son exactamente dos los vértices de gra‐ do impar, podemos determinar que sí existe un ciclo euleriano, en este caso: En nuestro caso, el cartero podría seguir el camino   O, A, B, C, D, E, O o también el camino 2  O, E, D,C, B, A, O. b) Sí, debido a la existencia del circuito   O, A, B, C, D, E, O , pues recorre todos los vértices del grafo regresando al vértice de inicio. Actividades propuestas 14. Dibuja un grafo euleriano y hamiltoniano. Indica el grado de cada vértice. 15. ¿Puede un grafo contener un ciclo hamiltoniano y no ser conexo al mismo tiempo? ¿Y puede no ser conexo pero contener un camino hamiltoniano? 16. Clasifica los siguientes grafos en eulerianos y hamiltonianos, planos y no planos, dirigidos o no dirigidos y en conexos o no conexos. 1 2 3 4 Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 163 Capítulo 5: Grafos 5. COLORACIÓN DE GRAFOS. ETIQUETADO DE GRAFOS. La coloración de grafos es una técnica de etiquetado que se lleva estudiando desde principios del año 1970. En coloración de grafos se define a S como un conjunto de números naturales asociados a una etiqueta que llamamos “color”. A S se le suele llamar paleta de colores. 5.1. Coloración de vértices De esta forma, al considerarse el grafo G y la paleta de colores S , llamamos coloración en vértices de G con (colores de; paleta de colores de) S a la correspondencia que asigna a cada vértice de G un color de S , por la cual vértices adyacentes no pueden recibir el mismo color. Formalmente, a la coloración de G con S la escribiremos como c :V  S. Denotamos por c  v , con v V al valor que asocia un color a v. Una coloración en la que intervienen k colores se lee k ‐coloración de vértices de G. Por lo que un grafo que presente una k ‐coloración de vértices de G se entenderá por k ‐coloreable. Sea  G el número mínimo de colores necesarios para colear G ; a este valor se le llama número cromático. En Teoría de Grafos, y más concretamente en coloración de grafos se buscan procedimientos eficientes, económicos y sistemáticos; en nuestro caso, con la finalidad de colorear nuestro grafo siguiendo un método eficaz y que nos asegure usar el mínimo número de colores. Para lograrlo, existen diferentes formas o métodos. Vamos a estudiar en nuestro caso, el método de coloración austero. Método de coloración austero (greedy algorithm, en inglés) Para colorear un grafo GV, E , tal que V v1, v2, v3,... por el método austero, utilizando la paleta de colores S  1,2,3,... seguiremos los siguientes pasos. Este es el paso más importante, pues por lo general, a ordenaciones distintas obtenemos PASO 1 coloraciones distintas. En este paso ordenaremos los vértices del grafo. Se pueden seguir diferentes criterios para lograr dicha ordenación. PASO 2 Asignamos el primer color de la paleta al primer vértice. O sea: c v1  1. Para colorear el siguiente vértice, v2 nos debemos fijar en si es vecino de v1 o no. En caso PASO 3 afirmativo asignamos el siguiente color, 2 , en caso contrario continuamos coloreando con el primer color. Para colorear el tercer vértice, comprobaremos si es o no vecino de v1 y/o de v2 , y no PASO 4 podremos utilizar los colores que hayamos usado con sus vecinos. … Para colorear vk tachamos en la paleta de colores aquellos utilizados por sus vecinos, y PASO K usamos el primero disponible luego de excluir el resto. Bachillerato General. Matemáticas Generales. Capítulo 5: Grafos Autor: Javier Zambrana Aguilar Revisora: Raquel Hernández www.apuntesmareaverde.org.es Ilustraciones: Autor. Marea Verde / Wikipedia 164 Capítulo 5: Grafos Por ejemplo: Vamos a colorear el siguiente grafo, que une las capitales de las provincias de Andalucía. Ordenamos los vértices por grado decreciente: VÉRTICE Huelva Cádiz Málaga Sevilla Córdoba Granada Jaén Almería GRADO 2 3 4 4 4 4 2 1 Aquellos vértices con igual grado serán ordenados por orden alfabético, como sigue: Córdoba, Granada, Málaga, Sevilla, Cádiz, Huelva, Jaén, Almería Para asignar los colores, vamos a armar la siguiente tabla: VÉRTICE Córdoba Granada Málaga Sevilla Cádiz Huelva Jaén Almería COLOR 1 2 3 2 1 3 3 1 Le asignamos el Observamos que primer color Granada es vecina de por ser el pri‐ Córdoba, por lo que mer vértice por automáticamente, en Observamos que colorear. nuestra paleta se Málaga es vecina elimina el color 1, tanto de Córdoba coloreándose el como de Granada segundo vértice del (las dos anterio‐ siguiente color dis‐ res), por lo que los ponible, o sea, el 2. colores 1 y 2 (usa‐