Capitulo 5: Teoria de Grafos

Historia de Teoría de Grafos

El trabajo de Leonhard 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. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Archivo:6n-graf.svg

Un grafo con 6 vértices y 7 aristas.

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.

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

Imagen que muestra representaciones de los distintos

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.

Definición:

Sea G=(V, A). G’=(V’,A’) se dice subgrafo de G si:

1- V’ incluido V

2- A’ incluido A

3- (V’,A’) es un grafo

  • Si G’=(V’,A’) es subgrafo de G, para todo v € G se cumple gr (G’,v)≤ gr (G, v)

G2 es un subgrafo de G.

Ciclos y caminos hamiltonianos

Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega).

Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas).

Se habla también de camino hamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada. Por ejemplo, un caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano. Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro.

Características de grafos

Grafos simples

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

Un grafo que no es simple se denomina Multigráfica o Gráfo múltiple.

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.

Grafos completos

Un grafo 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  , es decir, grafo completo de n vértices tiene exactamente aristas.

Grafos bipartitos

Un grafo G es bipartito si puede expresarse como G = \{V_1 \cup V_2, A\} (es decir, sus vértices son 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.

Lazos o bucles

Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Grafo no dirigido

Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V,E) donde:

* V\neq\emptyset

* E\subseteq \{x\in\mathcal P(V): |x|=2\} es un conjunto de pares no ordenados de elementos de V\,.

Un par no ordenado es un conjunto de la forma {a,b}, de manera que {a,b} = {b,a}. Para los grafos, estos conjuntos pertenecen al conjunto potencia de V de cardinalidad 2, el cual se denota por \mathcal P(V).

Grafo dirigido

Un grafo dirigido o digrafo es un grafo G = (V,E) donde:

* V\neq\emptyset

* E \subseteq \{(a,b) \in V \times V: a \neq b \}\, es un conjunto de pares ordenados de elementos de V\,.

Dada una arista (a,b), a es su nodo inicial y b su nodo final.

Por definición, los grafos dirigidos no contienen bucles.

Un grafo mixto es aquel que se define con la capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son casos particulares de este.

Conectividad en grafos

A diferencia de los conceptos anteriores, que afectaban a vértices del grafo, la conectividad es una
propiedad del grafo en su conjunto. Un grafo orientado puede ser conexo o fuertemente conexo. Un
grafo orientado sólo puede ser conexo. Más concretamente, tenemos:
Diremos que un grafo es conexo si existe al menos un ciclo entre toda pareja de vértices. El concepto
es aplicable tanto a grafos orientados como para no orientados: obsérvese que se ha definido ciclo
tanto para grafos orientados como para no orientados.
Diremos que un grafo orientado es fuertemente conexo si existe al menos un camino entre toda pareja
de vértices. Todo grafo orientado fuertemente conexo será también conexo.

Leave a Reply

Please leave these two fields as-is:

Protected by Invisible Defender. Showed 403 to 6 bad guys.