Teoria de grafos

Algoritmos y Recorridos sobre Grafos

1. Grafos
Se dice que un grafo es un conjunto de vértices (también llamados nodos) unidos por ligas denominadas aristas. Sea e = {p, q} una arista, entonces se tiene que: • El vértice p y el vértice q son llamados vértices finales de la arista e • Los vértices p y q son llamados vértices adyacentes. • Se dice que la arista e es incidente al vértice p (ytambién al vértice q). • Si p y q son el mismo vértice entonces la arista e es denominada un lazo. Cuando dos aristas conectan al mismo par de nodos, se dice que éstas son aristas paralelas. Un grafo simple es aquel que no cuenta con lazos o aristas paralelas. Un grafo en el que existen lazos o aristas paralelas es denominado multigrafo. Dos aristas que incidan sobre un mismo vértice son llamadasaristas adyacentes. Un grafo pesado es aquel al que se le ha asignado un número no negativo a cada una de sus aristas. El grado de un vértice es el número de aristas que inciden en él. Si un grafo tiene una arista para cada par de vértices distintos, entonces éste es llamado un grafo completo. Si los nodos finales de una arista forman un par ordenado entonces se dice que ésta es una arista dirigida.Sea e = {p, q} una arista dirigida, entonces: • El vértice p es llamado vértice inicial y el vértice q es llamado vértice final de e. • La arista e es incidente únicamente al vértice final q. Si todas las aristas de un grafo son aristas dirigidas, entonces éste es llamado grafo dirigido o digrafo. Si todas las aristas de un grafo no son aristas dirigidas (sus vértices forman pares no ordenados),el grafo es llamado grafo no dirigido. Un grafo mixto se compone de aristas dirigidas y aristas no dirigidas. El complemento F de un grafo G, es el grafo cuyos vértices son los vértices de G, pero tal que dos vértices son adyacentes en F sí y sólo si éstos no son adyacentes en G. Una caminata es una secuencia de vértices en la cual cualesquiera dos vértices consecutivos son adyacentes en el grafo.Una ruta es una caminata en la cual todos los vértices son distintos. Una ruta en un grafo dirigido es llamada una ruta dirigida. Un circuito, o ciclo, es una caminata en la cual su primer y último vértices son el mismo. Un grafo es acíclico si y sólo si éste no cuenta con circuitos. Se dice que un grafo es conectado si existe una caminata entre cualesquiera par de sus nodos. Si en un grafoexiste un par de nodos u y v tales que no existe una caminata que permita llegar de u a v entonces el grafo es llamado desconectado. Un grafo fuertemente conectado es un grafo dirigido en el cual existe una caminata dirigida que permite conectar cualesquiera par de nodos.

Dr. Ricardo Pérez-Aguila, agosto 2008

1

Algoritmos y Recorridos sobre Grafos

Un subgrafo de un grafo G consiste de unsubjunto de nodos y aristas de G. Un componente de G es un subgrafo máximo conectado de G. Un subgrafo que contiene a todos los vértices de G es llamado un subgrafo de expansión (spanning subgraph) de G. Un árbol es un grafo conectado acíclico. Un bosque es un grafo acíclico (nótese que un bosque puede ser o no un grafo conectado mientras que un árbol es estrictamente un grafo conectado). Un árbolde expansión (spanning tree) de un grafo G es un árbol que es un subgrafo de expansión de G. Un bosque de expansión (spanning forrest) es un bosque que es un subgrafo de expansión de G.

1.1 Permutación Aleatoria de n Elementos
Se producirá una permutación aleatoria del conjunto de enteros {1, 2, 3, …, n} al generar una secuencia de intercambios aleatorios. Considérese, por ejemplo, lageneración de una permutación aleatoria de los enteros en el conjunto {1, 2, 3, 4, 5}, n = 5. Supóngase que los elementos permutados serán guardados en un arreglo de enteros perm. Una primer etapa considerará la inicialización del arreglo perm como perm[i] = i, i = 1, 2…, n. Por lo tanto en un principio se tendrá: • perm[1] = 1 • perm[2] = 2 • perm[3] = 3 • perm[4] = 4 • perm[5] = 5 La segunda etapa...