Trabajos Del Tec

CAPÍTULO VTEORÍA DE GRAFOS Y SU APLICACIÓN
Para nadie es novedad observar en la vida cotidiana: carreteras, líneas telefónicas, líneas detelevisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas,automóviles, y tantas cosas mas; lo que no pensamos frecuentemente es que estos forman parte dealgo que en matemáticas se denomina como grafos.En este trabajo se tratarábrevemente de explicar lo que son los grafos, sus tipos, y algunasderivaciones de ellos, así como su representación gráfica y en algunos casos, su representación enalgún programa informático, así como en la memoria.
APLICACIÓN A PROBLEMAS DE VIDA REAL
La mayor parte de los problemas de la teoría de grafo pueden ser aplicados a:
1. Problemas de Existencia
•
El problema de los siete puentes deKönigsberg: Existe una trayectoria cerrada que cruce cadauno de los siete puentes exactamente una vez?
•
El problema del Caballo de Ajedrez: Existe una secuencia de los movimientos del caballo talque visite cada cuadrado de un tablero de ajedrez exactamente una vez y regresando a la posición de partida?
•
El problema de los Cuatro Colores: Puede colorearse todo mapa con cuatro colores de modoquelos países vecinos tengan colores diferentes?
2.
Problemas de Construcción
•
Determinar si un grafo dado es euleriano y construir un camino euleriano (algoritmo de Fleury).
3.
Problemas de Enumeración
•
Grafos etiquetados.
•
Digrafos etiquetados.

Teoría de grafos y su aplicación Pág. 56
•
Árboles etiquetados.
4.
Problemas de Optimización
•
Problema de encontrar el caminomínimo entre dos vértices en dígrafo pesado.
•
Problema del viajante de comercio
CONCEPTO GRAFOS
Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y Aes un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices. Losgrafosrepresentan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puederepresentar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas,circuitos eléctricos, etc.La notación
G = A (V, A)
se utiliza comúnmente para identificar un grafo. Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener elmismo grafo.En los grafos anteriores, los vértices son v
1
, v
2
, v
3
, v
4
mientras que los aristas son e
1
, e
2
, e
3
, e
4
, e
5
, e
6
,e
7
. Las aristas e2 y e7 se llaman aristas paralelas porque unen un mismo par de vértices. La arista e8se llama lazo o bucle porque une un vértice consigo mismo.
Aristas
Son las líneas con las que se unen las aristas de un grafo ycon la que se construyen tambiéncaminos. Si la arista carece de dirección se denota indistintamente
{a, b}
o
{b, a},
siendo a y b losvértices que une. Si
{a ,b}
es una arista, a los vértices a y b se les llama sus extremos.
•
Aristas Adyacentes:
Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
•
Aristas Paralelas:
Se dice que dos aristas son paralelas si vérticeinicial y el final son el mismo.
•
Aristas Cíclicas:
Arista que parte de un vértice para entrar en el mismo.
•
Cruce:
Son dos aristas que cruzan en un punto.

Teoría de grafos y su aplicación Pág. 57
Vértices
Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice alnúmero de aristas de las que es extremo. Se dice que un vértice es `par' o `impar'según lo sea sugrado.
•
Vértices Adyacentes:
si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista quelos une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V elvértice adyacente.
•
Vértice Aislado:
Es un vértice de grado cero.
•
Vértice Terminal:
Es un vértice de grado 1.
Ejemplo 1
Para el grafo siguiente:a.
Escribir el conjunto de...