TEORÍA DE GRAFOS

TEORÍA DE GRAFOS

En una red de comunicación, no es necesario que toda estación pueda comunicarse directamente con otra, puesto que las estaciones pueden actuar de posta para un mensaje entre otras dos estaciones. Si una estación, o una línea de datos, dejan de funcionar, queremos saber si la red queda conexa, es decir, si todas las estaciones que siguen funcionando pueden comunicarse entre sí. Para preguntas como ésta, no nos interesa la ubicación física de las estaciones, sino sólo su conectividad, y es así que surge la noción matemática de grafo, que es simplemente unos nodos con algunas conexiones que se llaman aristas. Una arista puede conectar dos nodos, o, como en algunas aplicaciones, un nodo consigo mismo. Una arista está anclada en sus dos extremos a nodos, o posiblemente al mismo nodo en los dos extremos. Formalmente:

Definición 3.1. Un grafo es (N, A, P) donde N es un conjunto de nodos, A es un conjunto de aristas, y P es una función de las aristas tal que cada P(a) = {p, q} donde p, q son nodos (posiblemente con p = q, así que podemos decir que P(a) es un conjunto de 1 o 2 elementos). Cuando G es un grafo, GN denota sus nodos, GA sus aristas, y GP su función de aristas. (1)

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 modernizar fenómenos discretos y son fundamentales para la compresión de las estructuras de datos y el análisis del algoritmo.

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

CAMINO. Es una secuencia alternada de vé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.

LONGITUD DE CAMINO. Es el número de segmentos en ese camino.

SENDERO. Es un camino en el cual todos los segmentos son diferentes.

TRAYECTORIA. Es un camino en el cual todos los nodos son diferentes; así toda trayectoria debe ser un sendero.

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.

...