Logica

Introducción a la teoría de grafo
La teoría de grafos se aplica en campos tan diversos como las ciencias sociales, lingüística, ciencias
físicas, ingeniería de computación, etc., dado que ellos tratan en muchos problemas con objetos discretos
y relaciones binarias, es decir estructuras finitas.
La teoría de grafos desempeña también un papel importante en varios campos de las ciencias de laconmutación, tales como la teoría de la conmutación y diseño de la lógica, inteligencia artificial,
lenguajes formales, gráficos por computadora, sistemas opertativos, escrituras de compiladores y
organización y recuperación de la información.
Recordemos, en particular, la definición de grafo no dirigido: un grafo no dirigido es un par ordenado
(V,E) donde V es un conjunto de elementos y E esuna relación binaria definida en V.
Ej.:
Si V = {a, b, c, d} y E = {(a, b ), (a, c ), (a, d ), (b, c ), (b, d ), (d, d ), (d, a )}
Puede representarse geométricamente por medio de puntos y líneas entre los puntos. Esto es:

a•

•d

•b

•c

Otras afirmaciones:
•
•

Decimos que u es adyacente a v si y solo si existe una arista (u,v) ε a E.
Decimos que una arista (u,v) incide en losvértices u y v.

• Llamamos Valencia de un vértice u al número de lados que inciden en él, simbólicamente δ(u).
• Dos lados que inciden en los mismos vértices se llaman paralelos.
• Los lados del tipo (u,u) se llaman lazos o rulos.
• Un camino de un vértice u a otro vértice v es la sucesión de lados distintos del tipo:
(u,x1) (x1, x2) (x2, x3)……… (xn-1,v) el cual también se puede expresar dela siguiente forma:
(u, x1, x2, , x3 ……… ,v) Ej.: (a, b, d, a, c, b).
• La longitud de un camino es la cantidad de lados que pertenecen a dicho camino.
• Un circuito es un camino que comienza y termina en un mismo vértice Ej.: (a, b, c).
• Un grafo es Conexo si existe un camino entre cualquier par de vértices.
Ejemplo de aplicaciones:
Ejemplo 1: Una de las aplicaciones más frecuentes de losgrafos es la se tiene cuando planea uno sus
vacaciones. Si viajamos por carreteras, se utilizan unos mapas de carreteras que representan la red viaria
disponible para el viaje. Un mapa de carreteras es un grafo en el cual los nodos son los pueblos y ciudades
de alguna comarca, y las aristas representan las carreteras que unen estos pueblos y ciudades.
Ejemplo 2: Modelado de redes decomputadoras. Una red de computadoras consta de elementos tales
como computadores y líneas de comunicación. Cada nodo del grafo es un dispositivo, tal como un
computador o un Terminal, y cada arista o enlace denota un medio de comunicación tal como una línea
telefónica o un cable de red.
Los grafos son importantes para modelar estas redes con respecto a su fiabilidad y su eficiencia.
Caso de estudio1:

En 1859 el matemático irlandés Sir William Hamilton diseñó un juego que vendió a un fabricante de
juguetes de Dublín.
El juego estaba formado por un dodecaedro regular de madera con las 20 esquinas (vértices) etiquetado
con los nombres de ciudades importantes. El objetivo del juego era hallar un circuito entre las aristas del
sólido de modo que cada ciudad estuviera en el cicloexactamente una vez.
Una de las posibles formas de
jugar consistía en lo ya indicado
de intentar rellenar con unas
pequeñas piezas troncocónicas
todas las oquedades del tablero,
respectivamente etiquetadas por
letras
del
alfabeto,
que
corresponderían a las iniciales
de determinadas ciudades del
mundo, siguiendo las líneas
marcadas en el mismo y sin
poder saltar por encima de
alguna oquedadpreviamente
cubierta por una de estas piezas

El siguiente gráfico representa a este sólido .El juego tiene varias soluciones. Una es la que se
muestra con color rojo.

Este juego dio lugar a la siguiente definición.
Definición: Si G = (V,E) es un grafo conexo, se dice que G tiene circuito de Hamilton si existe un
circuito que pase por todos los vértices exactamente una vez.
Ejemplos...