GRAFOS
Matemáticas con puntos y rayas
En matemáticas y en ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos (conjunto de vértices o nodos unidos por aristas). Esta teoría sirve, por ejemplo: para analizar la estructura de internet o una red de carreteras, lo popular que puede ser un personaje determinado, la cantidad de amigos de una red social o cómo interactúan las partículas elementales.
INTRODUCCIÓN A LA TEORÍA DE GRAFOS
¿Qué es un grafo?
Un Grafo es un conjunto de puntos (llamados vértices) y segmentos o arcos (las aristas) que unen dichos puntos unos con otros.
Un grafo no es un gráfico, no se tienen en cuenta aspectos como la forma, la medida real o los ángulos. En un grafo la forma no es importante.
Se llama grado de un vértice, al número de aristas que inciden en dicho vértice.
Leonhard Euler
Este señor de la imagen es Leonhard Euler y está considerado el "padre" de la teoría de grafos, unos nuevos objetos matemáticos que te vamos a presentar. Euler, fue uno de los matemáticos más importantes del siglo XVIII y uno de los más grandes y más prolíficos de todos los tiempos. Aunque nació en Suiza, vivió la mayor parte de su vida en Alemania y en Rusia, y fue allí donde se encontró con el problema de los puentes de Könisberg. Presta atención...
subtítulo aquí
Los puentes de Könisberg
Königsberg (hoy en día Kaliningrado y pertenece a Rusia) está situada en las orillas y en las islas del río Pregel, que en el siglo XVIII estaba atravesado por 7 puentes. ¿Es posible planificar un paseo que cruce todos los puentes sin pasar por ninguno más de una vez? ¿El paseo puede comenzar y terminar en el mismo lugar.? Algunos de los habitantes de Königsberg opinaban que sí y otros que no.
¿Y tú qué crees?
¿Se pueden atravesar los 7 puentes pasando una sola vez por cada puente?
Volvamos al problema de los puentes
Lo primero que observó Euler es que la trayectoria que se escoge entre dos puentes
es irrelevante, lo único importante en la trayectoria es el orden en el cual se cruzan los puentes. Así que representó con puntos las cuatro zonas de la ciudad y a continuación, dibujó líneas entre las zonas, representando los puentes que las unían.
El problema de los puentes y los grafos.
Después del brillante planteamiento de Euler, el problema de los puentes se ha convertido en este: ¿Es posible recorrer este esquema, o mejor dicho este grafo, de forma que recorramos todos los vértices pasando una única vez por cada arista y saliendo y regresando del mismo vértice?
ProBLEMA
En Numerolandia hay nueve ciudades, con los nombres 1, 2, 3, 4, 5, 6, 7, 8 y 9. La única compañía aérea del país, FERMAT, establece una ruta aérea entre dos ciudades si y solamente si el número de dos dígitos formado por los nombres de las ciudades es divisible entre tres. Si visitas este extraño país, ¿Serás capaz de viajar, de alguna manera, de la ciudad 1 a la ciudad 9 por avión?
¿Qué es el ESPEJISMO DE LA MAYORÍA?
Algunas definiciones
Orden: Número de vértices del grafo
Tamaño: Número de aristas del grafo
Grafo Plano Un grafo es plano si se puede representar de forma que sus aristas no se crucen.
Grafo conexo Un grafo es conexo si cada par de vértices está unido por un camino.
Ciclo Es un camino cerrado en el que no se repite ninguna arista ni ningún vértice
Camino Sucesión de aristas consecutivas en la que el extremos de una es el origen de la siguiente.
Circuito Es un camino cerrado en el que no se repite ninguna arista.
Árbol Un árbol es un grafo en el que cualquier par de vértices está conectado por exactamente un camino.
Camino euleriano Es un camino que contiene todas las aristas apareciendo cada una de ellas exactamente una vez. Un ciclo que a su vez es un camino euleniano se denomina ciclo euleriano.
Camino hamiltoniano Es un camino que pasa por todos los vértices apareciendo cada uno de ellos exactamente una vez. Un ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano.
Grafos Eulerianos
Un grafo es euleriano si es conexo y el grado de todos sus vértices es par. En ese caso podemos encontrar un circuito euleriano, que recorre todas las aristas pasando por cada una de ellas una sola vez. Si el grafo es conexo y solo hay dos vértices de grado impar, el grafo es semieuleriano y habrá un camino euleriano, que recorre todas las aristas comenzando por uno de los vértices de grado impar y terminando en el otro.
El grafo de los puentes no es euleriano ni semieuleriano
Como todos los vértices tienen grado impar, el grafo no es euleriano y tampoco es semieuleriano. Eso significa que NO es posible recorrer este grafo pasando exactamente una única vez por cada arista. ¡Ni siquiera empezando y terminando en vértices diferentes!
¡¡¡ Tenemos un resultado importante !!!
Un grafo se puede dibujar de un solo trazo y sin trazar dos veces la misma arista cuando tiene dos o ningún vértice de grado impar. En caso contrario no se puede dibujar de esa forma. Si entre las condiciones está salir y llegar al mismo vértice, todos deben ser de grado par.
Algoritmo de Fleury
William Rowan Hamilton
Este otro señor de la imagen es Sir William Rowan Hamilton y fue un gran matemático, físico y astrónomo del siglo XIX. Fue un niño prodigio que a los trece años ya hablaba 12 idiomas y a los 22 era astrónomo real y profesor en el Trinity College en Irlanda. Hamilton es el creador del juego que veremos a continuación.
El Juego Icosiano o un viaje alrededor del mundo
Este juego estaba compuesto por un dodecaedro regular, de madera, provisto de un mango o asidero fijado en el centro de una de las caras del dodecaedro. En los vértices del poliedro se habían colocado clavos, mientras que las treinta aristas del dodecaedro estaban marcadas por trazos negros representando las rutas por las que el viajero podía pasar para ir de una población a otra. Para realizar el paseo y recordar las diversas poblaciones atravesadas, se tomaba una cuerda que se fijaba en el punto de partida y se iba enlazando en cada población, clavo, del recorrido.
El objetivo del juego era recorrer los veinte vértices del dodecaedro uno tras otro, una vez y solo una, y de tal forma que el vértice origen sea también el vértice destino.
El dodecaedro del Juego Icosiano se puede representar mediante un grafo plano
6. ¿Serías capaz de encontrar un camino que recorra todos los vértices del grafo pasando una única vez por cada uno y saliendo y regresando del mismo vértice?
COLORACIÓN DE GRAFOS
"Dado un grafo, ¿cuál es el número mínimo de colores que hay que utilizar para que pintando hábilmente cada vértice de un color, no haya dos vértices con el mismo color unidos por una arista?"
¿Por qué es importante este problema? ¿Qué tipo de aplicaciones tiene? Veamos qué es la coloración de grafos y algunos ejemplos de sus aplicaciones
Coloreando vértices.
Una coloración de un grafo es una asignación de colores a los vértices de forma que dos vértices unidos por una arista reciban colores distintos. Hay muchos problemas, como el reparto de tareas o la creación de horarios eficientes, en los que el coloreado de grafos es una herramienta poderosa. Fíjate en este ejemplo.
EL CURSO DE VERANO
En un campamento de verano para alumnado de BACHILLERATO hay nueve actividades para elegir, A1, ... , A9. La actividad A9 es obligatoria para todos. Sabemos, además, que hay alumnos/as que asistirán simultáneamente a las actividades A1 y A2, A3 y A4, A5 y A6, A7 y A8. ¿Podrías diseñar un horario que, utilizando el menor número de horas posible, permita a todos los alumnos asistir a las
actividades que desee?
Evidentemente, si diseñamos un horario con 9 horas, todo el alumnado podrá asistir a las actividades que escogió, pero intentemos encontrar un horario mejor.
EL CURSO DE VERANO
En primer lugar traducimos el problema a un grafo, en el que los vértices son las actividades, y estarán unidas por una arista si hay alumnado que las realice simultáneamente
Para garantizar que los alumnos que realizan varias actividades puedan asistir a todas, coloreamos con colores distintos todos los vértices que estén unidos por una arista.
Hemos necesitado tres colores. Por lo tanto podemos diseñar un horario con tres horas que permita a todos los alumnos asistir a las actividades que desea.
Encuentra el mínimo número de colores necesario para colorear estos grafos de forma que dos vértices adyacentes tengan distinto color. En cada grafo indica cuál es mayor de los grados de los vértices y compara este número con el número de colores que has necesitado. ¿Encuentras alguna relación?
Actividad: Rumbo a Madagascar
Vamos a trasladar a los animales del zoo de Central Park al mundo salvaje. Si los conoces, sabrás que son unos animales un tanto especiales con unas relaciones sociales bastante complicadas. Para su traslado en jaulas, que durará varios días, es necesario repartirlos en jaulas de forma que no tengamos que lamentar ninguna baja....
Observa las relaciones de incompatibilidad de la tabla. Según ésta, Alex no puede viajar en la misma jaula que Marty o Melman y los monos no pueden estar con Melman o Julien.
Queremos hacer el traslado usando el menor número de jaulas posible, para que nos salga más barato. ¿Cuál es el mínimo número de jaulas que necesitaremos, respetando las relaciones de incompatibilidad?
EN BUSCA DEL GRAFO PERDIDO, Clara Grima
+info
1
Raquel Méndez
Created on September 17, 2025
Start designing with a free template
Discover more than 1500 professional designs like these:
View
Witchcraft Presentation
View
Sketchbook Presentation
View
Vaporwave presentation
View
Animated Sketch Presentation
View
Pechakucha Presentation
View
Decades Presentation
View
Color and Shapes Presentation
Explore all templates
Transcript
GRAFOS
Matemáticas con puntos y rayas
En matemáticas y en ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos (conjunto de vértices o nodos unidos por aristas). Esta teoría sirve, por ejemplo: para analizar la estructura de internet o una red de carreteras, lo popular que puede ser un personaje determinado, la cantidad de amigos de una red social o cómo interactúan las partículas elementales.
INTRODUCCIÓN A LA TEORÍA DE GRAFOS
¿Qué es un grafo?
Un Grafo es un conjunto de puntos (llamados vértices) y segmentos o arcos (las aristas) que unen dichos puntos unos con otros. Un grafo no es un gráfico, no se tienen en cuenta aspectos como la forma, la medida real o los ángulos. En un grafo la forma no es importante. Se llama grado de un vértice, al número de aristas que inciden en dicho vértice.
Leonhard Euler
Este señor de la imagen es Leonhard Euler y está considerado el "padre" de la teoría de grafos, unos nuevos objetos matemáticos que te vamos a presentar. Euler, fue uno de los matemáticos más importantes del siglo XVIII y uno de los más grandes y más prolíficos de todos los tiempos. Aunque nació en Suiza, vivió la mayor parte de su vida en Alemania y en Rusia, y fue allí donde se encontró con el problema de los puentes de Könisberg. Presta atención...
subtítulo aquí
Los puentes de Könisberg
Königsberg (hoy en día Kaliningrado y pertenece a Rusia) está situada en las orillas y en las islas del río Pregel, que en el siglo XVIII estaba atravesado por 7 puentes. ¿Es posible planificar un paseo que cruce todos los puentes sin pasar por ninguno más de una vez? ¿El paseo puede comenzar y terminar en el mismo lugar.? Algunos de los habitantes de Königsberg opinaban que sí y otros que no.
¿Y tú qué crees?
¿Se pueden atravesar los 7 puentes pasando una sola vez por cada puente?
Volvamos al problema de los puentes
Lo primero que observó Euler es que la trayectoria que se escoge entre dos puentes es irrelevante, lo único importante en la trayectoria es el orden en el cual se cruzan los puentes. Así que representó con puntos las cuatro zonas de la ciudad y a continuación, dibujó líneas entre las zonas, representando los puentes que las unían.
El problema de los puentes y los grafos.
Después del brillante planteamiento de Euler, el problema de los puentes se ha convertido en este: ¿Es posible recorrer este esquema, o mejor dicho este grafo, de forma que recorramos todos los vértices pasando una única vez por cada arista y saliendo y regresando del mismo vértice?
ProBLEMA
En Numerolandia hay nueve ciudades, con los nombres 1, 2, 3, 4, 5, 6, 7, 8 y 9. La única compañía aérea del país, FERMAT, establece una ruta aérea entre dos ciudades si y solamente si el número de dos dígitos formado por los nombres de las ciudades es divisible entre tres. Si visitas este extraño país, ¿Serás capaz de viajar, de alguna manera, de la ciudad 1 a la ciudad 9 por avión?
¿Qué es el ESPEJISMO DE LA MAYORÍA?
Algunas definiciones
Orden: Número de vértices del grafo
Tamaño: Número de aristas del grafo
Grafo Plano Un grafo es plano si se puede representar de forma que sus aristas no se crucen.
Grafo conexo Un grafo es conexo si cada par de vértices está unido por un camino.
Ciclo Es un camino cerrado en el que no se repite ninguna arista ni ningún vértice
Camino Sucesión de aristas consecutivas en la que el extremos de una es el origen de la siguiente.
Circuito Es un camino cerrado en el que no se repite ninguna arista.
Árbol Un árbol es un grafo en el que cualquier par de vértices está conectado por exactamente un camino.
Camino euleriano Es un camino que contiene todas las aristas apareciendo cada una de ellas exactamente una vez. Un ciclo que a su vez es un camino euleniano se denomina ciclo euleriano.
Camino hamiltoniano Es un camino que pasa por todos los vértices apareciendo cada uno de ellos exactamente una vez. Un ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano.
Grafos Eulerianos
Un grafo es euleriano si es conexo y el grado de todos sus vértices es par. En ese caso podemos encontrar un circuito euleriano, que recorre todas las aristas pasando por cada una de ellas una sola vez. Si el grafo es conexo y solo hay dos vértices de grado impar, el grafo es semieuleriano y habrá un camino euleriano, que recorre todas las aristas comenzando por uno de los vértices de grado impar y terminando en el otro.
El grafo de los puentes no es euleriano ni semieuleriano
Como todos los vértices tienen grado impar, el grafo no es euleriano y tampoco es semieuleriano. Eso significa que NO es posible recorrer este grafo pasando exactamente una única vez por cada arista. ¡Ni siquiera empezando y terminando en vértices diferentes!
¡¡¡ Tenemos un resultado importante !!!
Un grafo se puede dibujar de un solo trazo y sin trazar dos veces la misma arista cuando tiene dos o ningún vértice de grado impar. En caso contrario no se puede dibujar de esa forma. Si entre las condiciones está salir y llegar al mismo vértice, todos deben ser de grado par.
Algoritmo de Fleury
William Rowan Hamilton
Este otro señor de la imagen es Sir William Rowan Hamilton y fue un gran matemático, físico y astrónomo del siglo XIX. Fue un niño prodigio que a los trece años ya hablaba 12 idiomas y a los 22 era astrónomo real y profesor en el Trinity College en Irlanda. Hamilton es el creador del juego que veremos a continuación.
El Juego Icosiano o un viaje alrededor del mundo
Este juego estaba compuesto por un dodecaedro regular, de madera, provisto de un mango o asidero fijado en el centro de una de las caras del dodecaedro. En los vértices del poliedro se habían colocado clavos, mientras que las treinta aristas del dodecaedro estaban marcadas por trazos negros representando las rutas por las que el viajero podía pasar para ir de una población a otra. Para realizar el paseo y recordar las diversas poblaciones atravesadas, se tomaba una cuerda que se fijaba en el punto de partida y se iba enlazando en cada población, clavo, del recorrido.
El objetivo del juego era recorrer los veinte vértices del dodecaedro uno tras otro, una vez y solo una, y de tal forma que el vértice origen sea también el vértice destino.
El dodecaedro del Juego Icosiano se puede representar mediante un grafo plano
6. ¿Serías capaz de encontrar un camino que recorra todos los vértices del grafo pasando una única vez por cada uno y saliendo y regresando del mismo vértice?
COLORACIÓN DE GRAFOS
"Dado un grafo, ¿cuál es el número mínimo de colores que hay que utilizar para que pintando hábilmente cada vértice de un color, no haya dos vértices con el mismo color unidos por una arista?"
¿Por qué es importante este problema? ¿Qué tipo de aplicaciones tiene? Veamos qué es la coloración de grafos y algunos ejemplos de sus aplicaciones
Coloreando vértices.
Una coloración de un grafo es una asignación de colores a los vértices de forma que dos vértices unidos por una arista reciban colores distintos. Hay muchos problemas, como el reparto de tareas o la creación de horarios eficientes, en los que el coloreado de grafos es una herramienta poderosa. Fíjate en este ejemplo.
EL CURSO DE VERANO
En un campamento de verano para alumnado de BACHILLERATO hay nueve actividades para elegir, A1, ... , A9. La actividad A9 es obligatoria para todos. Sabemos, además, que hay alumnos/as que asistirán simultáneamente a las actividades A1 y A2, A3 y A4, A5 y A6, A7 y A8. ¿Podrías diseñar un horario que, utilizando el menor número de horas posible, permita a todos los alumnos asistir a las actividades que desee?
Evidentemente, si diseñamos un horario con 9 horas, todo el alumnado podrá asistir a las actividades que escogió, pero intentemos encontrar un horario mejor.
EL CURSO DE VERANO
En primer lugar traducimos el problema a un grafo, en el que los vértices son las actividades, y estarán unidas por una arista si hay alumnado que las realice simultáneamente
Para garantizar que los alumnos que realizan varias actividades puedan asistir a todas, coloreamos con colores distintos todos los vértices que estén unidos por una arista.
Hemos necesitado tres colores. Por lo tanto podemos diseñar un horario con tres horas que permita a todos los alumnos asistir a las actividades que desea.
Encuentra el mínimo número de colores necesario para colorear estos grafos de forma que dos vértices adyacentes tengan distinto color. En cada grafo indica cuál es mayor de los grados de los vértices y compara este número con el número de colores que has necesitado. ¿Encuentras alguna relación?
Actividad: Rumbo a Madagascar
Vamos a trasladar a los animales del zoo de Central Park al mundo salvaje. Si los conoces, sabrás que son unos animales un tanto especiales con unas relaciones sociales bastante complicadas. Para su traslado en jaulas, que durará varios días, es necesario repartirlos en jaulas de forma que no tengamos que lamentar ninguna baja....
Observa las relaciones de incompatibilidad de la tabla. Según ésta, Alex no puede viajar en la misma jaula que Marty o Melman y los monos no pueden estar con Melman o Julien.
Queremos hacer el traslado usando el menor número de jaulas posible, para que nos salga más barato. ¿Cuál es el mínimo número de jaulas que necesitaremos, respetando las relaciones de incompatibilidad?
EN BUSCA DEL GRAFO PERDIDO, Clara Grima
+info