LOS SIETE PUENTES DE LA ISLA KUEIPHOF
La isla Kueiphof en Koenigsberg (Pomerania) el río que la rodea se divide en dos brazos.
Sobre los brazos estaban construidos siete puentes y para los habitantes era
motivo de distracción descubrir un itinerario de manera que pudieran regresar al punto de partida, después de haber cruzado por los siete puentes pero pasando sólo una vez por cada uno de ellos.
Leonardo Euler estudió el asunto, representó las distintas zonas A, B, C y D por medio de puntos, mientras que los puentes estaban representados por líneas que
unían estos puntos. A la figura la llamó grafo, a los puntos los llamó vértices y a las líneas las denominó aristas.
Estudió si una figura lineal se podía dibujar
con un solo trazo, sin levantar el lápiz del papel y sin pasar dos veces por el mismo sitio.
Llegó a la siguiente conclusión:
1. Es imposible si hay más de dos vértices impares.
2. Es posible cuando:
a) Todos los vértices son pares y el punto de partida puede ser cualquiera.
b) Cuando no hay más de dos vértices impares y en este caso el comienzo del recorrido comienza en uno de ellos y termina en el otro.
(Impar es un vértice si de él parten un número impar de caminos).
A la isla A llegan 5 puentes; a la B llegan 3 puentes; a la orilla C llegan 3 puentes y a la orilla D llegan 3 puentes, por tanto, según las conclusiones
anteriores, el problema no tiene solución.
Ejemplos:
Estos dibujos pueden hacerse de un solo trazo:
Estos no pueden hacerse en las condiciones exigidas:
Este estudio de Euler dio origen a la teoría de los grafos, que se emplean en el estudio
de los circuitos eléctricos, en problemas
de transporte, programación con ordenador, etc.
Teoría de grafos
La Teoría de
Grafos juega un papel importante en la
fundamentación matemática de las Ciencias de la
Computación. Los grafos constituyen una herramienta básica para modelar fenómenos discretos y
son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos.
En matemáticas
y ciencias de la computación, la teoría de grafos estudia las
propiedades de los grafos, que son colecciones de objetos llamados vértices (o nodos) conectados por
líneas llamadas aristas (o
arcos) que
pueden tener orientación (dirección asignada). Típicamente, un grafo está diseñado por una serie de puntos (los vértices) conectados por líneas (las aristas).
El trabajo de Leonhard Euler, en 1736, sobre el
problema de los puentes de Königsberg es considerado como uno de los primeros resultados
de la teoría de grafos.
También se considera uno de los primeros resultados topológicos
en geometría
(que no depende de ninguna medida). Este ejemplo ilustra
la profunda relación entre la teoría de grafos y la topología.
En 1845 Gustav Kirchhoff publicó sus
leyes
de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos.
En 1852
Francis Guthrie planteó
el
problema de los cuatro colores que
plantea si es posible, utilizando solamente
cuatro colores, colorear
cualquier mapa de países de tal forma que dos países vecinos nunca tengan el
mismo color. Este problema, que no
fue resuelto
hasta un siglo después
por Kenneth
Appel y Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al
tratar de resolverlo, los matemáticos definieron
términos y conceptos teóricos fundamentales de los grafos.
Grafo
Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados
vértices, y A es un conjunto de pares de vértices, llamadas aristas.
En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas.
La posición de los vértices tampoco
importa,
y
se puede variar para obtener
un
grafo
más
claro.
Generalmente, se considera que colocar los vértices
en forma de polígono
regular da grafos muy legibles.
Prácticamente cualquier red puede ser modelada con un grafo: una red
de carreteras que conecta ciudades, una red eléctrica o un alcantarillado.
Aristas dirigidas y no dirigidas
En algunos casos es necesario asignar un sentido a las aristas,
por ejemplo, si se quiere representar la red de las calles de una ciudad con sus inevitables direcciones únicas. El
conjunto de aristas será ahora un subconjunto de todos los posibles
pares ordenados
de vértices, con (a,
b) ≠ (b, a). Los grafos que contienen
aristas dirigidas se denominan
grafos orientados, como el siguiente:
Las aristas no orientadas se consideran
bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).
Se considera la característica de "grado" (positivo o negativo) de un vértice,
como la cantidad de aristas
que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice
es simplemente la cantidad de
aristas que tocan este vértice. Por ejemplo, el grado positivo (salidas)
de d es 3, mientras que el grado negativo (llegadas) de b es 1.
Grafos isomorfos
Dos grafos tendrán la
misma “forma matemática” cuando la única diferencia entre ambos, en cuanto a su estructura, sea la representación gráfica de sus vértices y aristas.
Cuando las conexiones entre vértices tengan las mismas aristas, se
dice que son homorfos. [Hortalá, 270]
Ejemplo:
Subgrafo
Un grafo G1 es subgrafo de otro G si todos los vértices de G1 están en G pero no necesariamente todos los vértices de G están en G1. [Hortalá, 268]
Grafos Simples
Caracterización de Grafos
Un grafo es simple si a lo más sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es el único que une dos vértices específicos.
Un grafo que no es simple se denomina complejo.
Grafos Conexos
Un grafo es conexo (más formalmente fuertemente conexo)
si todos sus vértices están conectados por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.
Es posible determinar si un grafo es fuertemente conexo coleccionando la información de los grados de sus vértices al tiempo que se acumulan las diferentes rutas que salen de un vértice o llegan a él.
En términos matemáticos la propiedad de un grafo de ser fuertemente
conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una partición
de éstos en "componentes fuertemente
conexos", es decir, porciones del grafo, que son fuertemente conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas
demostraciones en teoría de grafos.
Grafos Completos
Un grafo simple es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.
El conjunto de los grafos completos es denominado usualmente, K siendo Kn el grafo completo de n vértices.
Un Kn, es decir, grafo completo de n vértices tiene exactamente
aristas.
La representación gráfica de los Kn como los vértices de un polígono regular da cuenta de su peculiar estructura.
Grafos Bipartitos
Un grafo G es bipartito si puede expresarse como G = {V1 + V2, A} (es decir, la unión de dos grupos de vértices), bajo las siguientes condiciones:
• V1 y V2 son distintos y tienen más de un elemento cada uno.
• Una arista en A une un vértice de V1 con uno de V2.
• No existen aristas
uniendo dos elementos de V1; análogamente para V2.
Bajo estas condiciones, el grafo se considera bipartito, y puede describirse
informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.
Ejemplos:
S1 b = 3
S 2 c = b + 2
S 3 a = 1
S 4 d = a * b + 5
S 5 e = d − 1
S 6 f = 7
S 7 e = c + d
S 8 g = b * f
Relación → se ejecuta primero
Ejemplo:
V = {a, b, c, d , e, f }
E = {a − c, a − b, a − e, a − d , a − f , c − b, e − d , e − f }
Ejemplo:
V = {a, b, c, d , e}
E = {(a, b), (a, d ), (b, c)}
V- Conjunto de Vertices
E- Conjunto de Aristas
G- Grafo
Donde V → E
→ G
Conjunto de vértices Conjunto de aristas Grafo
G = (V , E )
Grafo dirigido
Ejemplo 2: Ejemplo 2:
E : (a, b)
E : (a, b)
la arista es incidente
en los nodos a y b
a es el vértice origen
y b es el vértice terminal.
e vértice aislado
Ejemplo 2:
Grafo
dirigido.
Ejemplo 1: Grafo no dirigido.
⇒ Grafo: Cuando no se especifica se entiende
que es no dirigido
Definición: Sean x , y vértices (no necesariamente diferentes) de un grafo dirigido
G = (V , E ) un camino x - y en G es una sucesión alternada
finita
Camino
a-t: a-b-c-e-f
a-d-e-f
Camino cerrado: Cualquier camino x - y donde x = y ; esto es, inicia y termina en
el mismo nodo
a −
a
a − b − d − a
a − b − c − e − d − a
Camino abierto: Cuando
x ≠ y , inicia y termina en vértices diferentes
1. {a, b}, {b, d}, {d , c}, {c, e}, {e, d}, {d , b}
⇒ Camino:
a − b longitud = 6
se repiten vértices b y d
a ⎯⎯→ b ⎯⎯→ d ⎯⎯→ c ⎯⎯→ e ⎯⎯→ d ⎯⎯→ b
Se repite arista: {d , b} (2)
a ⎯⎯1→ b ⎯⎯2 → d ⎯⎯3 → c ⎯⎯4 → e ⎯⎯5 → d ⎯⎯2 → b
2. b ⎯⎯→ c ⎯⎯→ d ⎯⎯→ e ⎯⎯→ c ⎯⎯→ f
⇒ Camino:
b − f
longitud = 5
Se repiten vértice c
Arista no se repite
3. {f , c}, {c, e}, {e, d}, {d , a}:
⇒ Camino:
f − a
longitud = 4
No repite vértice
No repite arista
* Como no es dirigido
Camino a − b también camino b − a
Camino b − f
también camino
f − b
Camino
f −
a también camino a − f
4. {b, c}, {c, d}, {d , c}
Camino:
b − b cerrado:
x − x
b ⎯⎯→ c ⎯⎯→ d ⎯⎯→ b
Camino:
repite
arista
x − y
repite vértices
Camino cerrado: repite a y v:
x − x
Recorrido: no repite arista: (b − d )
b ⎯⎯→ c ⎯⎯→ d ⎯⎯→ e ⎯⎯→ c
f − a : f ⎯⎯→ c ⎯⎯→ e ⎯⎯→ d ⎯⎯→ a
Recorrido cerrado: b-b: x-x
Circuito = recorrido cerrado (no repite aristas y llega al mismo vértice) Ejemplo: {a, b}, {b, c}, {c, e}, {e, d}, {d, a}
a → b → c → e → d → a : camino a –a
recorrido a- a cerrado a – a longitud = 5
Camino simple:
no repite vértice:
no se repite vértice
f −
a : f ⎯⎯→ c ⎯⎯→ e ⎯⎯→ d ⎯⎯→ a
a ⎯⎯→ b ⎯⎯→ c ⎯⎯→ e : a − e
Camino simple cerrado: no repite vértices y lleva al mismo lado.
x − x
Ciclo: camino simple cerrado
|
Vértices repetidos
|
Aristas repetidas
|
x − y abierto
|
x − y cerrado
|
Nombre
|
|
X
|
X
|
X
|
-
|
Camino
|
|
X
|
X
|
-
|
X
|
Camino cerrado
|
|
X
|
-
|
X
|
-
|
Recorrido
|
|
X
|
-
|
-
|
X
|
Circuito
|
|
-
|
-
|
X
|
-
|
Camino
simple
|
|
-
|
-
|
-
|
X
|
Ciclo
|
No hay comentarios.:
Publicar un comentario