¿Qué es un grafo? Recordemos que un grafo G es el par (V, A) que
representa una relación entre un conjunto de Vértices y otro de Aristas.
Representaremos cada elemento arista como un par de elementos de V.
Gráficamente representaremos los vértices por puntos y las aristas por líneas
que los unen. Un vértice puede tener 0 o más aristas, pero toda arista debe
unir exactamente 2 vértices. Las aplicaciones más importantes de los grafos son
las siguientes:
• Rutas entre ciudades.
• Determinar tiempos máximos y
mínimos en un proceso.
• Flujo y control en un programa
EJEMPLOS DE APLICACIONES DE GRÁFICAS
Los grafos son la
representación natural de las redes, en las que estamos cada vez más incluidos.
Los grafos son artefactos
matemáticos que permiten expresar de una forma visualmente muy sencilla y
efectiva las relaciones que se dan entre elementos de muy diversa índole. Un
grafo simple está formado por dos conjuntos:
• Un conjunto V de puntos
llamados vértices o nodos.
• Un conjunto de pares de
vértices que se llaman aristas o arcos y que indican qué nodos están
relacionados.
De una manera más informal
podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos,
denominados aristas o arcos. En un grafo simple entre dos nodos sólo hay un
arco. Si hay más de un arco hablamos de un multígrafo. Si los arcos se pueden
recorrer en una dirección concreta pero no en la contraria lo llamamos grafo
dirigido o dígrafo y los arcos son entonces aristas, si los arcos salen y
llegan al mismo punto formando un bucle el grafo resultante se llama
pseudografo.
A pesar de que un grafo parece
una estructura muy elemental, hay muchísimas propiedades de los grafos cuyo
estudio ha dado lugar a una completa teoría matemática. Fue Leonhard Euler
quien ideó los grafos como una manera muy potente y elegante de resolver el
problema de los puentes de Königsberg. Königsberg (hoy Kaliningrado en Rusia)
era en tiempos de Euler (siglo XVIII) una ciudad prusiana cruzada por siete
puentes. Durante la época se suscitó la cuestión no resuelta de si era posible
recorrer toda la ciudad cruzando cada uno de los puentes una y sólo una vez. Si
hacemos una representación esquemática de la ciudad vemos que los puentes unen
cuatro porciones de tierra.
La búsqueda por prueba y
error no conduce a ningún resultado. El problema de los puentes de Königsberg.
Esta ciudad esta recorrida por el río Pregel que crea dos islas. ¿Se puede
recorrer toda la ciudad pasando una sola vez por todos y cada uno de los 7
puentes que unen la parte insular de la ciudad con el resto? La solución de
Euler. El famoso matemático abstrajo los detalles de la forma de la ciudad y
sus puentes para quedarse con la conectividad, dando lugar a una de los
primeros grafos.
El orden de todos
los vértices es impar, lo que implica que es imposible recorrerlos pasando una
sola vez por cada uno. Euler realizó una abstracción del problema representando
mediante puntos las cuatro porciones de terreno y dibujando un arco entre cada
dos puntos por cada puente. Llamó orden de cada vértice al numero de arcos que
se reunían en el y se percató que el orden de cada vértice visitado en un recorrido
sin saltos ha de ser par (sale un enlace y entra otro) excepto para dos puntos
del grafo: aquellos donde se inicia y donde se acaba el recorrido, que han de
tener orden impar. Si el vértice donde se inicia y se acaba son el mismo
entonces todos los vértices han de ser de orden par. En el problema de
Königsberg el orden de todos los nodos es 3, esto es impar, por lo que quedó
claro que no existía solución para el problema. No había un camino que
recorriese todos los puentes pasando una sola vez por cada uno de ellos.
El interés de este
ejemplo es que además de dar lugar a una teoría matemática muy potente los
grafos se dibujan y resultan muy intuitivos, especialmente cuando los vértices
son pocos. Ejemplos de grafos que todos conocemos son los organigramas que
explicitan la estructura formal de la empresa, los árboles genealógicos o la
circuitería de los chips electrónicos. Se usan regularmente para resolver
problemas en la eficiencia del transporte, en sociología, electrónica y
electricidad, detección de fraude y en general en aquellos campos en los que la
conectividad es importante. De hecho vivimos en una sociedad interconectada en
la que, por definición, las redes (que son simplemente una forma de grafos
dirigidos en los que cada arco tiene un valor) forman cada vez más parte de
nuestra experiencia diaria. Internet es el arquetipo de la red y su
conectividad nos une a todos. Como anécdota, al parecer la captura de Saddam
Hussein se realizó en parte gracias a la labor de construcción del grafo de su
red de soporte, basada en las relaciones funcionales de Saddam con miembros de
su partido pero sobre todo de las relaciones tribales y familiares que le unen
a su ciudad natal de Tikrit.
Solución de
problemas por medio de gráficas. Gracias a las gráficas podemos resolver
fácilmente problemas que aparentemente son muy complicados. Resolver problemas
es la principal aplicación de las gráficas. A continuación mostraremos por
medio de un ejemplo como resolver un problema por medio de las gráficas.
Problema. ¿Es posible que en un departamento de 25 personas, clasificadas según
su desacuerdo, cada persona congenie con exactamente otras 5? Para enfrentar el
problema. ¿Dónde comenzar? Muchos problemas discretos se pueden resolver por
medio de una grafica. Determinación de una solución. Un elemento fundamental al
construir un modelo de gráfica es imaginar lo que esta debe ser: ¿Cuáles son
los vértices y cuales las aristas? En este problema, no tenemos muchas
opciones; tenemos personas y desacuerdos. Intentemos utilizar a las personas
como vértices. En un modelo de gráfica, es común que las aristas indiquen una
relación entre vértices. En este caso, la relación es “congeniar con”, de modo
que escribiremos una arista entre los vértices (personas) si ellas congenian.
Ahora supongamos que cada persona congenia con exactamente otras cinco. Por
ejemplo, en la figura que se muestra a continuación donde se muestra parte de
la gráfica, Tomás congenia con Samantha, Alexandra, Juan, Bertha, y Josefina, y
nadie más.
Esto implica que el grado de cada vértice es 5.
Ahora la situación se resume así: Tenemos 25 vértices. En este caso y cada
vértice tiene grado 5. Antes de continuar veamos si esto es posible. El
corolario dice que existe un número par de vértices de grado impar. Tenemos una
contradicción, pues existe un número impar de vértices de grado impar. Por lo
tanto, no es posible que en departamento de 25 personas clasificadas según sus
desacuerdos, cada persona congenie con exactamente otras cinco. Solución
formal. No es posible que en un departamento de 25 personas clasificadas según
sus desacuerdos, cada persona congenie con exactamente otras 5. Supongamos por
contradicción que esto es posible. Consideremos una gráfica donde los vértices
sean las personas y una arista conecte 2 vértices (personas) si las personas
congenian. Como cada vértice tiene grado impar, existe un número impar de
vértices de grado impar, lo cual es una contradicción. Resumen de técnicas para
resolver problemas.
No hay comentarios.:
Publicar un comentario