TEORÍA DE GRAFOS

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) o gráfica es el principal objeto de estudio de la teoría de grafos.

Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.

6.1 ELEMETOS Y CARACTERÍSTICAS DE LOS GRAFOS

El trabajo de Leonard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología.

En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos.

En 1852 Francis Guthrie planteó el problema de los cuatro colores que plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges  en inglés) que pueden ser orientados o no.

Definición de grafo

Un grafo G (x, E) consta de un conjunto de elementos “x”, denominados nodos o vértices, y un listado de parejas de vértices E que expresa las relaciones entre dichos elementos.

Si no se considera el orden de los vértices en cada pareja, dichos pares se denominan aristas, y decimos que el grafo es no orientado.Si se consideran las relaciones, el par de aristas se llama arco y el grafo es orientado. Un grafo no orientado puede

siempre convertirse en orientado, expresando la doble relación entre los vértices.

Nodo

El nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a otros  

Aristas 

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

Aristas Adyacentes: Se dice que dos aristas son adyacentes si coinciden en el mismo vértice.

Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial 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 puntos.

Vértices: Son los puntos o nodos con los que esta conformado un grafo.

Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

Vértice Aislado: Es un vértice de grado cero.

Vértice Terminal: Es un vértice de grado 1

Camino

Cuando no termina en un mismo punto

CARACTERIZACIÓN DE GRAFOS

Grafos Simples

Un grafo es simple si a lo más sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es el único que une dos vértices específicos.

Un grafo que no es simple se denomina complejo.

Grafos Conexos

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

Un grafo es fuertemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

GRAFOS COMPLETOS

Un grafo simple es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.

El conjunto de los grafos completos es denominado usualmente, siendo el grafo completo de n vértices.Un Kn, es decir, grafo completo de n vértices tiene exactamente aristas.

La representación gráfica de los Kn como los vértices de un polígono regular da cuenta

de su peculiar estructura.

GRAFOS BIPARTITOS Un grafo G es bipartito si puede expresarse como (es decir, la unión de dos grupos de vértices), bajo las siguientes condiciones:

  * V1 y V2 son disjuntos y no vacíos.

  * Cada arista de A une un vértice de V1 con uno de V2.

  * No existen aristas uniendo dos elementos de V1; análogamente para V2.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.

GRAFOS PONDERADOS

En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así un grafo valuado.

Formalmente, es un grafo con una función v: A → R+.

Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la valuación será la distancia entre ellas.

Y, de momento, no se conocen métodos generales para hallar un ciclo de valuación mínima, pero sí para los caminos desde a hasta b, sin más condición.

6.1.1 COMPONENTES DE UN GRAFO (VERTICES,ARISTAS, LAZOS, VALENCIA)

Vértice (teoría de grafos)

En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto de vértices y un conjunto de aristas (pares no ordenados de vértices), mientras que un grafo dirigido está compuesto por un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En este contexto, los vértices son tratados como objetos indivisibles y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el grafo; por ejemplo, una red semántica es un grafo en donde los vértices representan conceptos o clases de objetos.

Los dos vértices que conforman una arista se llaman puntos finales y esa arista se dice que es incidente a los vértices. Un vértice w es adyacente a otro vértice v si el grafo contiene una arista (v,w) que los une. La vecindad de un vértice v es un grafo inducido del grafo, formado por todos los vértices adyacentes a v.

Vértices y grados

El grado de un vértice en un grafo es el número de aristas incidentes a él. Un vértice aislado es un vértice con grado cero; esto es, un vértice que no es punto final de ninguna arista. Un vértice hoja es un vértice con grafo uno. En un grafo dirigido, se puede distinguir entre grado de salida (”outdegree”, número de aristas que salen del vértice) y grado de entrada (”indegree”, número de aristas que llegan al vértice); un vértice fuente es un vértice con grado de entrada cero, mientras que un vértice hundido es un vértice con grado de salida cero.

Conexiones de vértices

Un vértice de corte es un vértice que al removerlo desconecta al grafo restante. Un conjunto independiente es un conjunto de vértices tal que ninguno es adyacente a otro, y una cobertura de vértices es un conjunto de vértices que incluye los puntos finales de cada arista en un grafo.

Arista (teoría de grafos)

En teoría de grafos las aristas, junto con los vértices, forman los elementos principales con los que trabaja esta disciplina, siendo consideradas las aristas las uniones entre nodos o vértices (véase la primera figura). Usualmente las aristas denotan relaciones entre los vértices (vecindad, herencia, orden, etc.) y, como ejemplo, se usan para delimitar regiones en un plano a partir de una nube de puntos (que serían los nodos).Aristas dirigidas y no dirigidas

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus direcciones únicas.

El conjunto de aristas será ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a, b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos orientados.

Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).

En el grafo anterior se ha utilizado una arista que tiene sus dos extremos idénticos: es un lazo (o bucle), y aparece también una arista bidireccional, y corresponde a dos aristas orientadas.

Aquí V = { a, b, c, d, e }, y A = { (a, c), (d, a), (d, e), (a, e), (b, e), (c, a), (c, c), (d, b) }.

Se considera la característica de “grado” (positivo o negativo) de un vértice v (y se indica como (v)), como la cantidad de aristas que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas incidentes a este vértice. Por ejemplo, el grado positivo (salidas) de d es 3, mientras que el grado negativo (llegadas) de d es 0.Según la terminología seguida en algunos problemas clásicos de Investigación

Operativa (p.ej.: el Problema del flujo máximo), a un vértice del que sólo salen aristas se le denomina fuente (en el ejemplo anterior, el vértice d); tiene grado negativo 0. Por el contrario, a aquellos en los que sólo entran aristas se les denomina pozo o sumidero (en el caso anterior, el vértice e); tiene grado positivo 0.

Subgrafo

Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo

de G es H o es isomorfo a H (dependiendo de las necesidades de la situación).

El subgrafo inducido de G es un subgrafo G’ de G tal que contiene todas las aristas adyacentes al subconjunto de vértices de G.

VERTICES

En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto de vértices y un conjunto de aristas (pares no ordenados de vértices), mientras que un grafo dirigido está compuesto por un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En este contexto, los vértices son tratados como objetos indivisibles y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el grafo; por ejemplo, una red semántica es un grafo en donde los vértices representan conceptos o clases de objetos.

Los dos vértices que conforman una arista se llaman puntos finales ("endpoints", en inglés), y esa arista se dice que es incidente a los vértices. Un vértice w es adyacente a otro vértice v si el grafo contiene una arista (v,w) que los une. La vecindad de un vértice v es un grafo inducido del grafo, formado por todos los vértices adyacentes a v.

Vértices y grados

El grado de un vértice en un grafo es el número de aristas incidentes a él. Un vértice aislado es un vértice con grado cero; esto es, un vértice que no es punto final de ninguna arista. Un vértice hoja es un vértice con grado uno. En un grafo dirigido, se puede distinguir entre grado de salida ("outdegree", número de aristas que salen del vértice) y grado de entrada ("indegree", número de aristas que llegan al vértice); un vértice fuente es un vértice con grado de entrada cero, mientras que un vértice hundido es un vértice con grado de salida cero.

Conexiones de vértices

Un vértice de corte es un vértice que al removerlo desconecta al grafo restante. Un conjunto independiente es un conjunto de vértices tal que ninguno es adyacente a otro, y una cobertura de vértices es un conjunto de vértices que incluye los puntos finales de cada arista en un grafo.

Vértices etiquetados

En el contexto de enumeración e isomorfismo de grafos, es importante distinguir entre

vértices etiquetados y vértices no etiquetados. Los vértices etiquetados son aquellos que están asociados con información extra mediante etiquetas, que los hace distinguibles entre sí; dos grafos son isomorfos sólo si existe una correspondencia entre sus pares de vértices con igual etiqueta. Un vértice no etiquetado es uno que puede ser sustituido por cualquier otro vértice basado sólo en sus adyacencias en el grafo, y no en información adicional a éste.

Vecindad de un vértice

La vecindad de un vértice x, denotado como esta dado por todos los vértices adyacentes a x.

6.1.2 TIPOS DE GRAFOS (SIMPLES, COMPLETOS, DIPARTIDOS, PLANOS, CONEXOS, PONDERADOS)

GRAFOS SIMPLES

Un grafo simple G = (V,E) consta de un conjunto no vacío deVértices V, y E, un conjunto de parejas no ordenadas de elementos distintos de V llamadas aristas.

Figura: ejemplo de un grafo simple

E = {{ Jamundí, Cali}, {Yumbo, Cali}, {Yumbo, Palmira}, . . .}

GRAFOS COMPLETOS

En teoría de grafos, un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.

Un grafo completo de n vértices tiene n(n − 1) / 2 aristas, y se nota Kn. Es un grafo regular con todos sus vértices de grado n − 1. Ningún grafo completo tiene lazos y está conectado totalmente, por ende, la única forma de hacer disconexo el grafo con una eliminación de vértices es aplicarla a todos.

El teorema de Kuratowski dice que un grafo planar no puede contener K5 (ó el grafo bipartito completo K3,3) y todo Kn incluye a Kn − 1, entonces ningún grafo completo Kn con es planar.

Ejemplos:

Los grafos completos de 1 a 12 vértices son los siguientes:

  * K1:0  * K2:1  * K3:3  * K4:6  * K5:10  * K6:15  * K7:21  * K8:28  * K9:36  * K10:45  * K11:55  * K12:66

GRAFOS DIPARTIDOS

Un Grafo bipartito se denomina en Teoría de grafos a un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen vértices de un conjunto con vértices de otro:  *   *   * no existe ninguna arista e = x1,x2 ni e = y1,y2

Siendo V el conjunto que contiene todos los vértices del grafo.

Los grafos bipartitos suelen representarse

1 2 3 4 5

Denunciar

|

gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.

Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U de azul y los vértices deV de verde obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.

Un grafo bipartito suele con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si los dos subconjuntos tiene la misma cantidad de elementos, decimos que el grafo bipartito G es balanceado.

Ejemplos

  * Todo grafo sin ciclos con cantidad de nodos impar es bipartito. Como consecuencia de esto:

      * Todo árbol es bipartito.      * Los grafos cíclicos con un número par de vértices son bipartitos.      * Todo grafo planar donde todas las caras tienen un número par de aristas es bipartito.

GRAFOS PLANOS

Definición y ejemplos

En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se interseque (una definición más formal puede ser que este grafo pueda ser "embebido" en un plano). Un grafo no es plano si no puede ser dibujado sobre un plano sin que sus aristas se intersequen. Los grafos K5 y el K3,3 son los grafos no planos minimales,

lo cual nos permitirán caracterizar el resto de los grafos no planos.

Teorema de Kuratowski

El matemático polaco Kazimierz Kuratowski encontró una caracterización de los grafos planos, conocida como el teorema de Kuratowski:

Un grafo es plano si y solo si no contiene un subgrafo que es una subdivisión elemental de K5 (el grafo completo de 5 vértices) o K3,3 (el grafo bipartito completo de 6 vértices).

Una subdivisión elemental de un grafo resulta de insertar vértices en las aristas (por ejemplo, cambiando •——• por •—•—•). Una formulación equivalente a este teorema es:

Un grafo es plano sí y solo sí no contiene ningún subgrafo homeomorfo a K5 ó K3,3.

Otros criterios para determinar si un grafo es plano

En la práctica, es difícil usar el teorema de Kuratowski para decidir rápidamente si un grafo es plano. Sin embargo, existe un algoritmo rápido para este problema: dado un grafo de n vértices y e el número de aristas, es posible determinar en tiempo O(n) (lineal) si el grafo es plano o no, utilizando los dos teoremas siguientes:

Teorema 1. Si n ≥ 3 entonces e ≤ 3n - 6

Teorema 2. Si n > 3 y no existen ciclos de longitud 3, entonces e ≤ 2n - 4

El grafo K3,3, por ejemplo, tiene 6 vértices, 9 aristas y ningún ciclo de longitud 3.

Por el teorema 2, no puede ser plano. Nótese que estos teoremas están construidos con una implicación unidireccional (si), y no bicondicional (si y solo si) y por tanto, solamente pueden ser usados para probar que el grafo no es plano, pero no que sea plano. Si ambos teoremas fallan, deben usarse otros métodos.

Fórmula de Euler

La fórmula de Euler enuncia que si un grafo conexo, plano es dibujado sobre un plano sin intersección de aristas, y siendo v el número de vértices, e el de aristas y f la cantidad de caras (regiones conectadas por aristas, incluyendo la región externa e infinita), entonces: v − e + f = 2,

Por ejemplo, la Característica de Euler es 2. De manera más ilustrativa, en los ejemplos anteriores, en el primer grafo plano tenemos: v=6, e=7 y f=3. Si el segundo grafo se redibuja sin las intersecciones de aristas, tenemos v=4, e=6 y f=4. La fórmula de Euler se puede probar de la siguiente manera: si el grafo no es un árbol, entonces se elimina una arista que completa un ciclo. Esto disminuye el valor de e y f en uno, dejando v − e + f constante. Repítase hasta llegar a un árbol.

Los árboles tienen v = e + 1 y f = 1, verificando la fórmula v - e + f = 2.

En un grafo simple, conexo y plano, cualquier región (posiblemente exceptuando la exterior) está conectada por al menos tres aristas y cada arista toca como muchas dos regiones. Usando la fórmula de Euler, se puede demostrar que estos grafos son escasos en el sentido que e ≤ 3v - 6 si v ≥ 3.

Se le dice plano máxima al grafo que es plano pero al agregarle cualquier arista dejase de serlo. Todas las regiones (incluso la externa) están conectadas por tres aristas, explicando la definición alternativa de triangular para este tipo de grafos.

Si un grafo triangular tiene v vértices con v > 2, entonces tiene exactamente 3v - 6 aristas y 2v - 4 regiones.

Nótese que la fórmula de Euler también es válida para poliedros simples. No es una casualidad: cada poliedro simple se puede ver como un grafo plano y conexo usando los vértices del poliedro como vértices del grafo, y las aristas del poliedro como aristas del grafo. Las caras o regiones del grafo plano resultante corresponden a las caras del poliedro. Por ejemplo, el segundo grafo plano del ejemplo corresponde a un tetraedro. Alternativamente, no todos los grafos planos y simples corresponden a un poliedro (los árboles, por ejemplo). Un teorema de Ernst Steinitz dice que los grafos planos formados a partir de poliedros convexos son precisamente los grafos planos simples y triangulares.

GRAFOS CONEXOS

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones

En teoría de grafos.

En teoría de grafos, un grafo G se dice conexo, si para cualquier par de vértices a y b en G, existe al menos una trayectoria (una sucesión de vértices adyacentes que no repita vértices) de a a b.

Definiciones Relacionadas

Un grafo dirigido tal que para cualesquiera dos vértices a y b existe un camino dirigido de ida y de regreso se dice grafo fuertemente conexo.Un conjunto de corte de vértices U en un grafo G, es un conjunto de vértices de G, tal que G-U no es conexo o trivial. Similarmente, un conjunto de corte de aristas F es un conjunto de aristas tal que G-F no es conexo.

Solución Computacional

El problema computacional de determinar si un grafo es conexo, puede ser resuelto con algunos algoritmos como el MFMC (max-flow, min-cut).

Algoritmo

Ejemplo de algoritmo iterativo implementado en C++ para determinar si un grafo es conexo utilizando búsqueda en profundidad, donde _n es la cantidad de vértices y _graph denota la matriz de adyacencia…

bool Graph::is_connected(){ if( _n <= 1 ) return true;

    vector<bool> visit(_n);    vector<bool>::iterator iter;

    for(iter=visit.begin();iter!= visit.end();iter++)        *iter=false;

    set<int> forvisit;    set<int>::iterator actual;

    forvisit.insert(0);    while( !forvisit.empty() )    {        actual = (forvisit.begin());             if( visit[*actual] == false )        {            for(int i=0;i<_n;i++)            {                if( _graph[*actual][i] == 1 && !visit[i])                    forvisit.insert(i);            }        }        visit[*actual]= true;        forvisit.erase(actual);    }

    bool result;    for(iter=visit.begin();iter!= visit.end();iter++)        result = result && *iter;    return result;}GRAFOS PONDERADOS

En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así un grafo valuado.

Formalmente, es un grafo con una función v: A → R+.

Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la valuación será la distancia entre ellas.

Y, de momento, no se conocen métodos generales para hallar un ciclo de valuación mínima, pero sí para los caminos desde a hasta b, sin más condición.

Entradas correspondientes a la etiqueta 'grafos ponderados'.

En esta clase hemos dado a toda prisa el último tema que nos va a entrar a examen.

  * Un grafo simple dirigido diremos que es grafo ponderado si tiene asociado una función W: A —> R llamada función de ponderación. La imagen de cada arco determinada por los vértices Vi y Vj la llamaremos peso del arco y lo denotaremos por Wij.

  * Sea G un grafo ponderado finito, llamaremos matriz de peso del grafo G a la siguiente matriz de orden nxn:

W=[Aij] / Aij = { Wij si (Vi, Vj) pertenecen a A;{ infinito si (Vi, Vj) no pertenecen a A;

  * En un grafo ponderado llamamos peso de un camino a la suma de los pesos de los arcos que lo forman.

  * En un grafo ponderado llamamos camino más corto entre dos vértices al camino de peso mínimo entre dichos vértices.

  * En un grafo ponderado llamamos camino más largo (o crítico) entre dos vértices al camino de peso máximo entre dichos vértices.

CAMINOS MÁS CORTOS

Suponemos que:

  * los pesos asociados a los arcos son todos no negativos.

  * el grafo es dirigido.

  * los vértices están numerados de 1 a n, de forma que Wij representa el peso del arco (i,j) y que el vértice 1 es el origen del camino. Además, Uj denotará el peso del camino más corto de 1 a j.

Teorema: Sea 1, …., k, ….., j un

camino más corto entre los vértices 1 y j de un grafo ponderado G. Entonces las secciones de este camino 1, ….., k, ….., j son los caminos más cortos entre los vértices respectivos.

Corolario: Supongamos que en un grafo ponderado tenemos un camino más corto entre los vértices 1 y j. Sea k el vértice inmediatamente anterior a j en este camino. Entonces la sección de este camino desde 1 a k es el camino más corto entre estos dos vértices. Además: Uj= Uk + Wkj

Ecuaciones de Bellman

U1 = 0Uj = min{Uk + Wkj}           j = 2, …., n        (siendo k diferente de j)

GRAFOS ACÍCLICOS. MÉTODO DEL CAMINO CRÍTICO

Teorema: Un grafo dirigido no tiene circuitos si y sólo si existe una numeración de los vértices para la que se cumple que si (i,j) es un arco del grafo entonces i < j.Con esta numeración, las ecuaciones de Bellman quedan así:

U1 = 0

Uj = min[Uk + Wkj}       j = 2, …. , n        (siendo k < j)

6.2       REPRESENTACIÓN DE LOS GRAFOS

Hay diversas formas de representar los grafos, y la más conveniente depende de la aplicación que tengamos en mente.

Una de las formas es listar los nodos que son adyacentes a cada nodo. Esto se denomina la lista de adyacencia del grafo.

Otra forma es representar la adyacencia por medio de una matriz, denominada la matriz de adyacencia.

Representación de grafos. Matriz de incidencia. Matriz de adyacencia.

Dado un grafo G = (V, E) con n vértices {v1, ..., vn} su matriz de adyacencia es la matriz de orden n×n, A(G)=(aij) donde aij es el número de aristas que unen los vértices vi y vj.

Ejemplo 1.4.2.

La matriz de adyacencia de un grafo es simétrica. Si un vértice es aislado entonces la correspondiente fila (columna) esta compuesta sólo por ceros. Si el grafo es simple entonces la matriz de adyacencia contiene solo ceros y unos (matriz binaria) y la diagonal esta compuesta sólo por ceros.

Dado un grafo simple G = (V, E) con n=|V| vértices {v1,..., vn} y m=|E| aristas {e1, ..., em}, su matriz de incidencia es la matriz de orden nxm, B(G)=(bij), donde bij=1 si vi es incidente con ej y bij=0 en caso contrario.

Ejemplo 1.4.4.

La matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El número de unos que aparece en cada fila es igual al grado del vértice correspondiente.

Una fila compuesta sólo por ceros corresponde a un vértice aislado.

Dado un grafo dirigido o dígrafo D = (V, E) con n vértices {v1, ..., vn} su matriz de adyacencia es la matriz de orden n×n, A(D)=(aij) donde aij es el número de arcos que tienen a vi como extremo inicial y a vj como extremo final.

Ejemplo 1.4.6.

La matriz de adyacencia de un dígrafo no es simétrica. Es una matriz binaria. El número de unos que aparecen en una fila es igual al grado de salida del correspondiente vértice y el número