Teoria de grafos

UNIDAD 6. TEORÍA DE GRAFOS


6.1 Elementos y Características de los 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 modelizar fenómenos discretos y son fundamentales para la compresión de las estructuras de datos y el análisis del algoritmo.

Definición: Un grafo G =(N, A) consta de un conjunto de nodos N y un conjunto de aristas A, en donde a cada arista es un par no ordenado de nodos (vértices o puntos). Una arista en general se representa por { a, b }. A las aristas también se le llaman segmentos. Una forma de representar grafos es mediante círculos para los nodos, conectados por líneas para las aristas.

Ejemplo 1:

El Grafo G que consta de los nodosN y segmentos S
se denota como: G(N,S) donde:
N = {n1, n2, n3, n4, n5, n6, n7, n8}
A = {{n1, n2}, {n1, n5}, {n3, n4}, {n4, n7}, {n2, n6}, {n6, n2}}



zx


Notación: Una arista es un conjunto, pero puede haber dos aristas que conecte los mismos nodos, por lo que se le puede anteponer un nombre, por ejemplo la arista 1 puede nombrarse como a1= {n2, n6}, la arista 2 como a2= {n2, n6},estas dos aristas unen los nodos n2 y n6. También puede ser que en una arista importe el orden de los nodos por lo que podemos en este caso utilizar la notación de par ordenado (n1, n2) cambiando las llaves por paréntesis y orientando el sentido de la arista.

La terminología que manejaremos regularmente para el uso de grafos es el siguiente:

• CAMINO. Es una secuencia alternada devértices y segmentos de la forma V1,S1,V2,S2,V3,S3,V4. Secuencia de vértices V1,V2,V3,V4 o secuencia de segmentos S1,S2,S3. Para la siguiente figura un camino puede representarse como: 6,4,5,1,2 otro ejemplo es 3,2,5,4,6 El siguiente NO es un camino válido: 6,5,3,1 pues no hay un segmento entre los nodos 6 y 5, ni entre 5 y 3, ni entre 3 y 1..

[pic]

• LONGITUD DE CAMINO. Es elnúmero de segmentos en ese camino. Para el camino 6,4,5,1,2 la longitud es 4 pues hay 4 segmentos.


• SENDERO. Es un camino en el cual todos los segmentos son diferentes. El camino 6,4,5,1,2 es un sendero. El camino 6,4,5,2,5,1 no lo es pues un mismo segmento es recorrido 2 veces.


• TRAYECTORIA. Es un camino en el cual todos los nodos son diferentes; así toda trayectoria debe serun sendero. El camino 6,4,5,1,2 es una trayectoria, el camino 6,4,5,2,3,4 no lo es pues se repite el nodo 4.


• CAMINO SIMPLE. Es cuando todos sus vértices, excepto tal vez el primero y el último, son distintos.

• CICLO SIMPLE. Es un camino simple de longitud por lo menos de uno, que empieza y termina en el mismo vértice. El camino 4,5,2,3,4 es un ciclo.



Tipos de GrafosUn Grafo Dirigido (también llamado Digrafo) es un grafo con una direcci[on asignada a cada segmento.
Le llamamos arcos a los segmentos dirigidos y se escriben como un par ordenado de vértices (v, w) donde V es el vértice inicial y W es el vértice terminal del arco. Un arco se expresa como: V(W y se representa de la siguiente manera:
[pic]
Los vértices de un grafo pueden usarse pararepresentar objetos. Los arcos se utilizan para representar relaciones entre objetos.

Las aplicaciones más importantes de los grafos dirigidos son las siguientes:

• Rutas entre ciudades.
• Determinar tiempos máximos y mínimos en un proceso flujo y control en un proceso.
• Flujo y control en un programa.

En los diagramas, las aristas dirigidas se muestran mediante flecha que tambiénmuestran las direcciones.

En las figuras (b), (e) y (g) se presenta gráficas dirigidas. Aquéllas dadas en c y f son no dirigidas, mientras que la dada en d es mixta.

La gráfica dada en la figura a se podría considerar como dirigida y no dirigida. Nótese que la arista x1, x2 y x3 en la figura (e) están asociadas con los pares ordenados (1,2), (2,3) y (3,1) respectivamente, mientras que...