*Grafos Eulerianos Existen todavía algunas familias de grafos que se derivan del concepto de grafos conexos. Este es el caso de los grafos eulerianos. Estas familias de grafos nos permiten resolver el famoso problema de los puentes de Königsberg: ¿cuándo es posible hacer un recorrido de una figura (en este caso de un grafo múltiple) sin pasar dos veces por la misma línea o por el mismo vértice? En la fig. 3.10 tenemos dos grafos G1 y G2; es posible recorrer uno de ellos sin repetir ninguna línea, pero el otro no. ¿Cuál es cuál? Es evidente que el grafo G1 no puede ser recorrido sin repetir alguna de sus líneas, mientras que el grafo G2 sí. *Recorridos sobre grafo Se parte de un nodo dado y se visitan los vértices del grafo de manera ordenada y sistemática, pasando de un vértice a otro a través de las aristas del grafo. Tipos de recorridos: ** Búsqueda primero en profundidad: Equivalente al recorrido en Equivalente al recorrido en preorden de un árbol. de un árbol. ** Búsqueda primero en anchura: Equivalente al recorrido de un árbol por niveles. *Problema de los puentes de Königsb El problema de los puentes de Königsberg es también llamado El problema de los siete puentes de Königsberg, es un célebre problema matemático, resuelto por Leonhard Euler en 1736 y cuya resolución dio origen a la teoría de grafos. Su nombre se debe a Königsberg, la ciudad de Prusia Oriental y luego de Alemania que desde 1945 se convertiría en la ciudad rusa de Kaliningrado. Análisis y solución del problema El problema, formulado originalmente de manera informal, consistía en responder a la siguiente pregunta: 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 sólo una vez cada uno, y regresando al mismo punto de partida? Repercusiones Esta abstracción del problema ideada por Euler dio pie a la primera noción de grafo, que es un tipo de estructura de datos utilizada ampliamente en matemática discreta y enciencias de la computación. A los puntos se les llama vértices y a las líneas aristas. Al número de aristas incidentes a un vértice se le llama el grado de dicho vértice. Específicamente, un diagrama como el de la abstracción del mapa de Königsberg representa un multigrafo no dirigido sin bucles. *Grafo etiquetado Un grafo etiquetado es la asignación de etiquetas, tradicionalmente representada mediante enteros, a las aristas o vértices, o ambos, de un grafo. Formalmente, dado un grafo G, un vértice etiquetado es una función que hace corresponde vértices de G a un conjunto de etiquetas. Un grafo con tal función definida es llamado grafo de vértices etiquetados. De la misma manera, una arista etiquetada es una función de asignación de aristas de G tal conjunto de «etiquetas». En este caso, Ges llamado como grafo de aristas etiquetadas. Cuando las etiquetas de las aristas pertenecen a un conjunto ordenado (i.e., los números reales), ésta puede ser llamada como grafo ponderado. Casos especiales ¨Etiquetado elegante Un grafo es denominado como elegante cuando sus vértices son etiquetados desde 0 a , el tamaño del grafo, y este etiquetado induce un etiquetado de aristas desde 1 a . Para cualquier arista e, los etiquetas de e son la diferencia positiva entre dos vértices incidentes con e. En otras palabras, si e es incidente con los vértices etiquetados k y j, e será etiquetado como . Así pues, un grafo  es elegante si y sólo si existe una inyección que induce una biyección de E a los enteros positivos hasta . ¨Etiquetado armonioso Un grafo armonioso es un grafo con k aristas que permiten una inyección de los vértices de G al grupo de enteros módulo k que induce una biyección entre las aristas de G y los enteros positivos hasta . Para cualquier arista e, los etiquetados de e son la suma de las etiquetas de dos vértices incidentes con e (mod q). ¨Coloración de grafos La coloración de grafos es un caso especial de grafos etiquetados, tales que los vértices adyacentes y las aristas coincidentes deben tener diferentes etiquetas. *Grafo Ponderado Un grafo ponderado es un grafo etiquetado con números reales
Please download to view
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
...

Problema de Los Puentes de Königsb

by ernestosantamaria

on

Report

Category:

Documents

Download: 0

Comment: 0

3

views

Comments

Description

Download Problema de Los Puentes de Königsb

Transcript

*Grafos Eulerianos Existen todavía algunas familias de grafos que se derivan del concepto de grafos conexos. Este es el caso de los grafos eulerianos. Estas familias de grafos nos permiten resolver el famoso problema de los puentes de Königsberg: ¿cuándo es posible hacer un recorrido de una figura (en este caso de un grafo múltiple) sin pasar dos veces por la misma línea o por el mismo vértice? En la fig. 3.10 tenemos dos grafos G1 y G2; es posible recorrer uno de ellos sin repetir ninguna línea, pero el otro no. ¿Cuál es cuál? Es evidente que el grafo G1 no puede ser recorrido sin repetir alguna de sus líneas, mientras que el grafo G2 sí. *Recorridos sobre grafo Se parte de un nodo dado y se visitan los vértices del grafo de manera ordenada y sistemática, pasando de un vértice a otro a través de las aristas del grafo. Tipos de recorridos: ** Búsqueda primero en profundidad: Equivalente al recorrido en Equivalente al recorrido en preorden de un árbol. de un árbol. ** Búsqueda primero en anchura: Equivalente al recorrido de un árbol por niveles. *Problema de los puentes de Königsb El problema de los puentes de Königsberg es también llamado El problema de los siete puentes de Königsberg, es un célebre problema matemático, resuelto por Leonhard Euler en 1736 y cuya resolución dio origen a la teoría de grafos. Su nombre se debe a Königsberg, la ciudad de Prusia Oriental y luego de Alemania que desde 1945 se convertiría en la ciudad rusa de Kaliningrado. Análisis y solución del problema El problema, formulado originalmente de manera informal, consistía en responder a la siguiente pregunta: 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 sólo una vez cada uno, y regresando al mismo punto de partida? Repercusiones Esta abstracción del problema ideada por Euler dio pie a la primera noción de grafo, que es un tipo de estructura de datos utilizada ampliamente en matemática discreta y enciencias de la computación. A los puntos se les llama vértices y a las líneas aristas. Al número de aristas incidentes a un vértice se le llama el grado de dicho vértice. Específicamente, un diagrama como el de la abstracción del mapa de Königsberg representa un multigrafo no dirigido sin bucles. *Grafo etiquetado Un grafo etiquetado es la asignación de etiquetas, tradicionalmente representada mediante enteros, a las aristas o vértices, o ambos, de un grafo. Formalmente, dado un grafo G, un vértice etiquetado es una función que hace corresponde vértices de G a un conjunto de etiquetas. Un grafo con tal función definida es llamado grafo de vértices etiquetados. De la misma manera, una arista etiquetada es una función de asignación de aristas de G tal conjunto de «etiquetas». En este caso, Ges llamado como grafo de aristas etiquetadas. Cuando las etiquetas de las aristas pertenecen a un conjunto ordenado (i.e., los números reales), ésta puede ser llamada como grafo ponderado. Casos especiales ¨Etiquetado elegante Un grafo es denominado como elegante cuando sus vértices son etiquetados desde 0 a , el tamaño del grafo, y este etiquetado induce un etiquetado de aristas desde 1 a . Para cualquier arista e, los etiquetas de e son la diferencia positiva entre dos vértices incidentes con e. En otras palabras, si e es incidente con los vértices etiquetados k y j, e será etiquetado como . Así pues, un grafo  es elegante si y sólo si existe una inyección que induce una biyección de E a los enteros positivos hasta . ¨Etiquetado armonioso Un grafo armonioso es un grafo con k aristas que permiten una inyección de los vértices de G al grupo de enteros módulo k que induce una biyección entre las aristas de G y los enteros positivos hasta . Para cualquier arista e, los etiquetados de e son la suma de las etiquetas de dos vértices incidentes con e (mod q). ¨Coloración de grafos La coloración de grafos es un caso especial de grafos etiquetados, tales que los vértices adyacentes y las aristas coincidentes deben tener diferentes etiquetas. *Grafo Ponderado Un grafo ponderado es un grafo etiquetado con números reales
Fly UP