Teoría de Grafos

Elementos y características de los grafos.

Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices. Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc. La notación G = A (V, A) se utiliza comúnmente para identificar un grafo. Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.

Composición de un grafo.

Aristas :
Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.
• Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen 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 punto. 

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. 

Tipos de grafos.

Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.
Ejemplo:
G1 = (V1, A1)V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}G2 = (V2, A2)V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}G3 = (V3, A3)V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }
Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:

Hay también 6 tipos principales de grafos; simples, completos, bipartidos, planos, conexos y ponderados.
Grafo simple. Se dice que el grafo G = (V, E) es un grafo simple de grado n si todos sus vértices tienen grado n.
Grafo completo. Un grafo es completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices. Ejemplos
Grafo bipartido. Un grafo es bipartido si V=V1?V2 y cada arista de E une un vértice de V1 y otro de V2
-Grafo bipartido completo
.Un grafo es bipartido completo si V=V1?V2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,sal grafo bipartido completo donde V1 tiene r vértices y V2 tiene s vértices
Grafos planos. Un grafo plano es aquel que puede ser dibujado en el plano sin que ninguna arista se interseque.
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
Grafo ponderado. Un grafo es ponderado si presenta los pesos de cada arista y se puede determinar la longitud de una ruta, la cual es la suma de todos los pesos de las aristas.

Si lo que hay aquí no es claro puedes consultar: Conexión en grafos no dirigidos.

Representación de grafos

• 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 aijes el número de aristas que unen los vértices vi y vj. 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.
• Matriz de incidencia 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 ybij=0 en caso contrario. 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.

Representación Matemática de los grafos

En matemáticas y ciencias de la computación, la teoría de grafos, también llamada teoría de loas graficas estudia las propiedades de los grafos (también llamados graficas) Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de partes de vértices llamados aristas. 

Representación Computacional de los grafos

Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos, usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras mas sencillas y usadas se encuentran las listas y las matrices y aunque frecuentemente se usa una combinación de ambos. 

Algoritmos de recorrido y búsqueda

Algoritmos de recorrido y búsqueda: El camino más corto.

El problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima. Ahora bien, podemos emplear el algoritmo de Dijkstra para éstos casos, los pasos o procedimientos a seguir para éste algoritmo son los siguientes : Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.
1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi
4. Si la distancia desde x hasta va guardada en D es mayor que la distancia desde x hasta a, sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada.
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenándolos valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados. 

Algoritmos de recorrido y búsqueda: A lo ancho

La búsqueda en anchura es otro procedimiento para visitar sistemáticamente todos los vértices de un grafo. Es adecuado especialmente para resolver problemas de optimización, en los que se deba elegir la mejor solución entre varias posibles. Al igual que en la búsqueda en profundidad se comienza en un vértice v (la raíz) que es el primer vértice activo. En el siguiente paso se etiquetan como visitados todos los vecinos del vértice activo que no han sido etiquetados. Se continúa etiquetando todos los vecinos de los hijos de v (que no hayan sido visitados aún). En este proceso nunca se visita un vértice dos veces por lo que se construye un grafo sin ciclos, que será un árbol

Algoritmos de recorrido y búsqueda: En profundidad

En la búsqueda en profundidad se avanza de vértice en vértice, marcando cada vértice visitado. La búsqueda siempre avanza hacia un vértice no marcado, internándose “profundamente” en el grafo sin repetir ningún vértice. Cuando se alcanza un vértice cuyos vecinos han sido marcados, se retrocede al anterior vértice visitado y se avanza desde éste 

Arboles

En teoría de grafos, un árbol es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino. Un árbol a veces recibe el nombre de árbol libre. Definiciones Un árbol es un grafo simple unidireccional G que satisface alguna de las siguientes condiciones equivalentes:
• G es conexo y no tiene ciclos .
• G no tiene ciclos y, si se añade alguna arista se forma un ciclo.
• G es conexo y si se le quita alguna arista deja de ser conexo.
• G es conexo y el grafo completo de 3 vértices no es un menor de G.
• Dos vértices cual quiera de G están conectados por un único camino simple.
Si G tiene muchos vértices, n, entonces las definiciones anteriores son también equivalentes a cualquiera de las siguientes condiciones: • G es conexo y tiene n - 1 aristas.
• G es conexo y sin ciclos.
Cualesquiera 2 vértices están unidos por una única trayectoria

Componentes de un árbol

Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, de los cuales uno es conocido como raíz, además se crea una relación de parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc. Un árbol es una estructura que está compuesta por un dato y varios árboles. Dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente, es decir un nodo cualquiera puede ser considerado como la raíz de una árbol completo. En relación con otros nodos:
Nodo Padre: Nodo que contiene un puntero al nodo actual. En un árbol un nodo solo puede tener un nodo padre.. X es padre de Y sí y solo sí el nodo X apunta a Y, también se dice que X es antecesor de Y.
Nodo Hijo: Cualquiera de lo nodo apuntado por uno de lo nodo del árbol. Un nodo puede tener varios hijos. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.
Hermano: Dos nodos serán hermanos si son descendientes directos de un mismo nodo. En cuanto a la posición dentro del árbol:
Nodo Raíz: Es el único nodo del árbol que no tiene padre. Este es el nodo que usaremos para referirnos al árbol.
Nodo Hoja: Nodo que no tiene hijos. Se llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).
Nodo Interior: Es un nodo que no es raíz ni hoja.
Orden: Es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. Podríamos decir que nuestro árbol de ejemplo es de orden tres.
Grado: El número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto A como D tienen tres hijos, y no existen elementos con más de tres hijos
Nivel: Se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero, el de sus hijos uno y así sucesivamente. En el ejemplo, el nodo D tiene nivel 1, el nodo G tiene nivel 2 y el nodo N nivel 3.
Rama: Es el camino desde el nodo raíz a una hoja.
Altura: La altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas, el máximo número de nodos que hay que recorrer para llegar de la raíz a una de las hojas.
Peso: Es el número de nodos del árbol sin contar la raíz. 

Propiedades del árbol

Todo árbol es a su vez un grafo bipartito. Todo árbol con sólo un conjunto numerable de vértices es además un grafo plano. Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G. Dado n vértices etiquetados, hay n n-2 maneras diferentes de conectarlos para construir un grafo. El resultado se llama fórmula de Cayley. El número de árboles con n vértices de grado d1,d2,...,dn es: un coeficiente multinomial.
Contar el número de árboles no etiquetados es un problema complicado. De hecho, no se conoce ninguna fórmula para el número de árboles t(n) con n vértices (debe entederse aquí el número de árboles diferentes salvo isomorfismo de grafos). Los primeros valores de t(n) son 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, ... (sucesión A000055 en OEIS). Otter (1948) probó que Una fórmula más exacta para el comportamiento asintótico de t(n) implica que hay dos números a y ß (a ˜ 3 y ß ˜ 0.5) tales que: 

Clasificación de arboles

Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.
Tipos de árboles Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura). A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n. Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Arboles con peso

Dado un grafo conexo, un árbol recubierto mínimo de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc... , y se usa para asignar un peso total al árbol recubierto mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol expandido mínimo es un árbol recubridor que pesa menos o igual que otros árboles recubridores. Todo grafo tiene un bosque recubridor mínimo. En el caso de un empate, porque podría haber más de un árbol recubridor mínimo; en particular, si todos los pesos son iguales, todo árbol recubridor será mínimo. De todas formas, si cada arista tiene un peso distinto existirá sólo un árbol recubridor mínimo. La demostración de esto es trivial y se puede hacer por inducción. Esto ocurre en muchas situaciones de la realidad, como con la compañía de cable en el ejemplo anterior, donde es extraño que dos caminos tengan exactamente el mismo coste. Esto también se generaliza para los bosques recubridores. Si los pesos son positivos, el árbol recubridor mínimo es el subgrafo de menor costo posible conectando todos los vértices, ya que los subgrafos que contienen ciclos necesariamente tienen más peso total. 

Recorrido de un árbol

Árbol binario
• Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:
1. Visite la raíz
2. Atraviese el sub-árbol izquierdo
3. Atraviese el sub-árbol derecho
• Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
1. Atraviese el sub-árbol izquierdo
2. Visite la raíz
3. Atraviese el sub-árbol derecho
• Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
1. Atraviese el sub-árbol izquierdo
2. Atraviese el sub-árbol derecho
3. Visite la raíz
En general, la diferencia entre preorden, inorden y postorden es cuándo se recorre la raíz. En los tres, se recorre primero el sub-árbol izquierdo y luego el derecho.
• En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho
• En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho, y
• En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho.

Para más información puedes ver este video: Matemáticas Discretas: Árboles.

Redes teorema de flujo máximo teorema de flujo mínimo pareos y redes de Petri

Una Red de Transporte es una grafica dirigida, simple, con pesos y que debe cumplir las siguientes: Poseer una fuente o vértice fijo que no tiene aristas de entrada. Poseer un sumidero o vértice fijo que no tiene arista de salida El peso Cij de la arista dirigida de i a j llamado capacidad de “ij” es un numero no negativo.

Ejemplo de una red que parte de un punto a que es un Muelle y llega a un punto z que es una refinería.
Teorema de flujo máximo. Siendo G una red de trasporte, un flujo máximo es un flujo con valor máximo. En general, habrá varias flujos con el mismo valor máximo. La idea es sencilla: comenzar con cierto flujo inicial e incrementar de forma iterativa hasta que no pueda mejorarse más. El flujo resultante será el máximo. Para aumentar el valor de un flujo dado, debemos determinar un camino de la fuente al sumidero e incrementar el flujo a lo largo de ese camino.
Teorema del flujo mínimo.
En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedando partes disjuntas del conjunto de vértices, V1 y V2 que, situados en la red, dejan la fuente en una de ellas y al sumidero en la otra. Se llama capacidad de un corte a la suma: Capacidad (v,w) ; vV1, w?V2 V1es la parte que contiene a la fuente V2 es la parte que contiene al sumidero Sea F un flujo en G y sea (P, P) un corte en G. Entonces la capacidad de (p, p) es mayor o igual que el valor de F

Redes de Petri

Una red de Petri es un grafo orientado con dos tipos de nodos: lugares (representados mediante circunferencias) y transiciones (representadas por segmentos rectos verticales). Los lugares y las transiciones se unen mediante arcos o flechas.

Un arco une siempre lugares con transiciones y nunca dos lugares o dos transiciones. Una transición puede ser destino de varios lugares y un lugar puede ser el destino de varias transiciones. Una transición puede ser origen de varios lugares y un lugar puede ser origen de varias transiciones Los lugares pueden presentar marcas (una marca se representa mediante un punto en el interior del círculo).Cada lugar tiene asociada una acción o salida. Los lugares que contienen marcas se consideran lugares activos. Cuando un lugar está activo sus salidas están a uno. A las transiciones se les asocia eventos (funciones lógicas de las variables de entrada).Una transición se dice que está sensibilizada cuando todos su lugares origen están marcados. Cuando ocurre un evento asociado a una transición (la función lógica se hace uno), se dice que la transición está validada.

Aplicaciones de grafos y arboles

¿Qué es un grafo? Recordemos que un grafo G es el par (V, A) que representa una relación entre un conjunto de Vértices y otro de Aristas. Representaremos cada elemento arista como un par de elementos de V. Gráficamente representaremos los vértices por puntos y las aristas por líneas que los unen. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente 2 vértices. Las aplicaciones más importantes de los grafos son las siguientes: 

• Rutas entre ciudades. 

• Determinar tiempos máximos y mínimos en un proceso. 

• Flujo y control en un programa. 

Los grafos son la representación natural de las redes, en las que estamos cada vez más incluidos. Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos: 

• Un conjunto V de puntos llamados vértices o nodos.

• Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados. 

De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos. En un grafo simple entre dos nodos sólo hay un arco. Si hay más de un arco hablamos de un multígrafo. Si los arcos se pueden recorrer en una dirección concreta pero no en la contraria lo llamamos grafo dirigido o dígrafo y los arcos son entonces aristas, si los arcos salen y llegan al mismo punto formando un bucle el grafo resultante se llama pseudografo. A pesar de que un grafo parece una estructura muy elemental, hay muchísimas propiedades de los grafos cuyo estudio ha dado lugar a una completa teoría matemática. 

A continuación se presentan videos sobre la teoría de grafos para ampliar el conocimiento:

Parte 1:

Parte 2:

También se anexa un video para explicar el Ciclo Hamiltoniano que no se aborda en el blog:

Para concluir planteamos los siguientes problemas que son resueltos en el video que aparece más abajo:

Problema de la Asignación y su Relación con Teoría de Grafos.

Problema 01: Se tiene que elegir a cuatro miembros de la unidad de docentes de Matemáticas del FI para formar parte de las comisiones siguientes: Comisión de Proyectos, Comisión Docente, Comisión Permanente, Comisión de Planes de estudio. La mencionada unidad está formada por siete profesores, que mantienen su posibilidad para pertenecer a una u otra. ¿Cuál sería una posible asignación que respete las posibilidades del profesorado?

Problema 02: En el grupo PL1 de prácticas de laboratorio de la asignatura EMI2 se van a hacer prácticas por parejas, por lo que se solicita a los 16 alumnos que, previo acuerdo entre ellos, indiquen con quienes les gustaría formar pareja. ¿Será posible establecer 8 parejas para las prácticas que respeten las preferencias de los alumnos?

Resolución:

<<Entrada anterior                                                               Entrada siguiente>>
>Ir a la tabla de contenido<