Teoria De Grafos

Capítulo 3

TEORÍA DE GRAFOS
1. 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, deja de funcionar, queremos saber si la red queda conexa, es decir, si todas las estaciones que siguen funcionandopueden 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 anodos, 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 susaristas, y GP su función de aristas. Generalmente pensamos en un grafo como un dibujo:

pero es difícil hacer algoritmos sobre dibujos. Si ponemos nombres a los nodos y a las aristas así:

este dibujo corresponde al grafo G en donde GN = {1, 2, 3, 4}, GA = {a, b, c, d, e}, P (a) = {1, 2}, P (b) = {2, 3}, P (c) = {1, 4}, P (d) = {1, 3}, P (e) = {3}. Claro que la representación formal es medioengorrosa, pero lo que importa ahora es el concepto, y buscamos estructuras de datos más limpias después. Una arista a con P (a) = {p}, como la arista e del ejemplo, se llama rulo. Los rulos son irrelevantes en las aplicaciones que consideramos aquí pero los teoremas que consideramos son válidos si se permiten rulos o no, así que no queremos prohibirlos. Es más amigable decir “el nodo p está conectado ala arista a” que decir, aúnque más compactamente, “p ∈ P (a)”; por eso elegimos el primero muchas veces.
39

40

3. TEORÍA DE GRAFOS

Un nodo que no es conectado a ninguna arista se llama nodo aislado. No interesan mucho nodos aislados; la única atención que los damos es prohibirlos donde molestan. 2. Caminos y conectividad

Una noción fundamental es la de un camino. Un camino empiezaen algún nodo, y sigue por aristas visitando varios nodos. Formalmente: Definición 3.2. Un camino en un grafo G = (N, A, P ) es una sucesión (posiblemente vacía) a = a1 . . . an de aristas tal que existe una sucesión p = p0 . . . pn de nodos tal que para cada ai , P (ai ) = {pi−1 , pi }. La sucesión p se llama un recorrido del camino a. Se dice que a empieza en p0 y termina en pn . Claro que nocualquier sucesión de aristas es un camino, porque puede ser que no exista recorrido. Por ejemplo, en el grafo anterior la sucesión c, b no es un camino. La sucesión a, b sí es, y su recorrido es 1, 2, 3. La sucesión a, a tiene dos recorridos: 1, 2, 1 y 2, 1, 2. La sucesión de a solo tiene dos recorridos, 1, 2 y 2, 1. Para cualquier nodo p, la sucesión de sólo p es recorrido del camino vacío. Dado uncamino y un nodo p, hay a lo sumo un recorrido de ese camino que empieza con p. Algunos autores prohiben que un camino repita aristas (pero dejan que sus recorridos repitan nodos). Para algunas aplicaciones nuestras más adelante conviene hablar de caminos que repiten aristas. Definición 3.3. Los nodos p, q de un grafo son conexos, o p es conexo con q, si hay un camino que empieza en p y terminaen q. Nótese que la relación de conexos es de equivalencia. El camino vacío conecta cualquier nodo consigo mismo (si ya estoy en p, entonces para llegar a p no hago nada). Definición 3.4. Un grafo es conexo si cualquier par de sus nodos son conexos. El primer algoritmo que vamos a ver va a decidir si dos puntos dados son conexos. Empezamos con una descripción informal. Supongamos que los...