APLICACIONES DE GRAFOS

Objetivo:

Mostrar la aplicación de la teoría de grafos dentro de los márgenes de diseño en la vida real y los diferentes programas utilizados, ya sea en estructuras de comunicación, y dirigidos a la ejecución de programas.

1. Generalidades

Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en todas las áreas de Ingeniería. Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd. Para la administración de proyectos, utilizamos técnicas como PERT en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos. La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red.

LISTAS Y MATRICES

Lista de adyacencia

En esta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sóllo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vertices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta. 

Matriz de adyacencia

Se trata de una matriz cuadrada de n filas *n columnas (siendo n el número de vértices del grafo).

Para construir la matriz de adyacencia, cada elemento a ij vale {{1}} cuando haya una arista que una los vértices i y j En caso contrario el elemento a ij vale 0.

La matriz de adyacencia, por tanto, estará formada por ceros y unos.

Una lista de adyacencia invertida almacena para cada vértice la lista de adjuntos
desde otros vértices.

Con la estructura de puede calcular el grado de entrada de cualquier vértice
solamente contando el numero de nodos de la lista del vértice requerido.

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 (más formalmente fuertemente conexo) si todos sus vértices están conectados por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b. Es posible determinar si un grafo es fuertemente conexo coleccionando la información de los grados de sus vértices al tiempo que se acumulan las diferentes rutas que salen de un vértice o llegan a él. 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 conexos", 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.

Grafos Bipartitos Un grafo G es bipartito si puede expresarse como G = {V1 + V2, A} (es decir, la unión de dos grupos de vértices), bajo las siguientes condiciones: 

• V1 y V2 son distintos y tienen más de un elemento cada uno. 

• Una arista en 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. 

Cibergrafia :

http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0701_Tc1003_TODO_Grafos.pdf

GRAFOS ISOMORFOS

Se dirá que dos grafos G y G' son isomorfos entre sí, si: 

1. Existe una función biyectiva .
2. Si dos vértices vi, vj son adyacentes en V(G), es decir, viRvj, entonces las correspondientes imágenes de dichos vértices también son adyacentes pero en V(G'), dicho de otra forma,; y viceversa.

Ejemplo: En la siguiente figura, tenemos que G es isomorfo a G'.

Donde V(G) = {1,2,3,4} y V(G') = {A,B,C,D} y como debe cumplirse quef:V(G)  V(G') es una biyección, entonces f(1) = D, f(2) = B, f(3) = C, f(4) = A. Observar que 1R4 en G, entonces, D R A en G'.

Tenemos otra función que también define un isomorfismo entre G y G'.

f(1) = B, f(2) = D, f(3) = C y f(4) = A.

Observar, igualmente, que para este caso 1 R 4 en G, entonces, B R A en G'.

La relación de isomorfismo preserva las vecindades de cada vértice.

La relación de isomorfismo de dos grafos G y G' se denota de la siguiente manera, 

Corolario: Si , entonces:

/V(G) /= /V(G')/

/E(G) /= /E(G') /

Si tiene vi tiene "k" vértices vecinos vi1, vi2, vi3, ... , vik, entonces, f(vi) tiene los siguientes "k" vértices vecinos f(vi1), f(vi2), f(vi3), ... , f(vik).

vi y f(vi) tienen la misma valencia.

Cibergrafía:

http://teoriadegrafos.blogspot.com.co/2007/03/isomorfismo-de-grafos.html

GRAFOS EULERIANOS Y HAMILTONIANOS

Existen todavía algunas familias de grafos que se derivan del concepto de grafos conexos. Este es el caso de los grafos eulerianos y los grafos hamiltonianos. Estas familias de grafos nos permiten resolver el famoso problema de los puentes de Königsberg:

¿cuándo es posible hacer un recorrido de una figura (en este caso de un grafo múltiple) sin pasar dos veces por la misma línea o por el mismo vértice?

Tenemos dos grafos G1 y G2; es posible recorrer uno de ellos sin repetir ninguna línea, pero el otro no. ¿Cuál es cuál? Es evidente que el grafo G1 no puede ser recorrido sin repetir alguna de sus líneas, mientras que el grafo G2 sí.       

                           

Grafos Eulerianos

Recorrido cerrado

Cubre todas las líneas de un grafo, comenzando y terminando en un mismo vértice, recorriendo sin repetición y en forma continua todas las líneas de un grafo G cualquiera. Cuando tal recorrido existe, se denomina eulerianoy un grafo que se puede trazar mediante un recorrido euleriano se llamagrafo euleriano. En la fig. 3.11, G1 es obviamente un grafo euleriano; G2 no lo es, a pesar de que se puede trazar continuamente, ya que el recorrido comienza y termina en vértices distintos; finalmente, G3 no es un grafo euleriano, porque no se puede trazar continuamente.

                                

Diremos que un grafo G es la unión disjunta de ciclos, si podemos descomponer a G como la unión de ciclos que no tienen líneas en común, aunque se permite que tengan, al menos, un vértice en común.

En la figura el grafo se puede descomponer como la unión disjunta de los ciclos C = v1v2v3v4v5v6v1; C' = v1v7v5v1; C'' = v2v7v4v2; C''' = v3v8v9v3 y el recorrido euleriano para el grafo G viene dado por la secuencia de sus líneas 1, 2,..., 15.

OBSERVACION : Esta descomposición por lo general no es única. El grafo de la fig. 3.11 admite otra descomposición como unión disjunta de ciclos, por ejemplo, C = v1v2v7v1; C' = v3v4v2v3; C'' = v3v8v9v3; C''' = v7v4v5v7; C'''' = v5v1v6v5 .

Recíprocamente, supongamos que G es una unión disjunta de ciclos. Sea C un ciclo cualquiera en G. Si entonces G es un ciclo y por lo tanto euleriano. Si existe un ciclo C' en G que tiene un vértice v en común con C (por hipótesis). Si G es la unión de C y C', entonces, comenzando en v trazamos C y luego C', obteniendo así un recorrido euleriano de G. Si la unión de C y C' no es todo G, existe un ciclo C'' que tiene algún vértice v' en común con C o con C', digamos por ejemplo con C'. Si G es la unión de C, C' y C'', entonces comenzando en v trazamos C, luego trazamos C' hasta llegar a v' y luego trazamos C'' hasta completar C', luego regresamos a v como ilustra el diagrama de la fig. 3.13.

Así, obtenemos un recorrido euleriano de G. Si la unión de C, C' y C'' no es todo G, continuamos con este procedimiento hasta obtener un recorrido euleriano de G.

COROLARIO 2: Un grafo conexo es euleriano si y sólo si todos sus vértices tienen valencia par. (Este teorema rige también para multigrafos).

Demostración:

En un recorrido euleriano, cuando visitamos un vértice, necesitamos al menos dos líneas distintas adyacentes al vértice (una para llegar al vértice y otra para salir de él), incluyendo al vértice inicial, porque tenemos que regresar a él para concluir el recorrido. Esto significa, que cada vértice contribuye con un número par de líneas y, por lo tanto, su valencia es par.

Grafos Hamiltonianos

Definición: Un circuito o ciclo hamiltoniano es un ciclo simple que contiene todos los vértices de G. Un circuito hamiltoniano es una trayectoria que empieza y termina en el mismo vértice y pasa por cada vértice una sola vez. 

Ejemplos: ¿Cuál de los grafos siguientes admite un circuito hamiltoniano? 

Solución 

(a) No admite circuitos hamiltonianos. El razonamiento es el siguiente: Si se empieza en v1, v2, v3, v4 y si se está en los demás vértices, en el v5 se estará dos veces. Si se empieza en v5, para luego ir a los vértices v1 o v4 ó a v3 o v2 respectivamente, se tendrá que pasar de nuevo por v5 (puesto que se empezará en v5). Para completar el circuito, se debe regresar a v5, por lo que se pasa tres veces por él.

(b) Un ciclo hamiltoniano es: v1 e1 v2 e2 v3 e3 v4 e4 v1 Teorema. Sea G un grafo conexo con n vértices, donde n≥3. 

Si la suma de los grados de cada par de vértices no adyacentes es mayor o igual a n, entonces G tiene un circuito hamiltoniano. 

Cibergrafia:

http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0702_Tc1003_TODO_Euler_Hamilton.pdf

http://teoriadegrafos.blogspot.com.co/2007/03/grafos-eulerianos-y-hamiltonianos.html

CICLOS Y CIRCUITOS DE GRAFOS

Ciclo, es una cadena simple, cuyos dos vértices extremos, inicial y terminal, coinciden (no tiene en cuenta la orientación). Si queremos describir la orientación en un ciclo designamos como: u+ = {ui : ui orientada en el sentido del ciclo} u- = {ui : ui orientada en el sentido contrario al ciclo} 

Ciclo elemental, es un ciclo donde no se repite ningún vértice (salvo el primero que coincide con el último). Lo notamos uE = (u1,...,un). 

Propiedad 1: Todo ciclo uC es una suma de ciclos elementales sin aristas comunes. 

Propiedad 2: Un ciclo es elemental si y solo si es un ciclo minimal (es decir que no se pueden deducir otros ciclos por supresión de aristas).

Seudociclo, es una cadena donde los extremos coinciden pero que una misma arista puede figurar más de una vez (también consecutivamente). 

Cociclo del conjunto de vértices A, es el conjunto de aristas incidentes a A, del tipo I(A) no vacío y particionado en dos clases I+(A) y I-(A). 

Ciclo Euleriano es aquel que incluye todas las aristas del grafo una sola vez, conteniendo cada vértice por lo menos una vez. 

Cadena Euleriana, es aquella que recorre todas las aristas una sola vez ( = simple) tocando todos los vértices del grafo. 

Todo multigrafo que posee un ciclo Euleriano es conexo y todos sus vértices tienen grado par . 

A partir del siguiente ejemplo daremos una idea del mecanismo utilizado por Euler para demostrar que la conexidad y el grado par de todos los vértices de un multigrafo, son condiciones necesarias y suficientes para garantizar la existencia de un ciclo Euleriano. Tenemos este grafo que es conexo y sus vértices tienen grado par.

1) Primero se comienza por trazar un camino simple desde un vértice, p. ej a. Supongamos que recorremos a-d-j-n-o-k-l-h-f-e-b-a. Volvimos a a.

La propiedad del grado par, significa que siempre podemos abandonar cada vértice al que entramos, exepto a. Es decir que cualquier cadena que trazemos desde a debe volver a a, formando un ciclo.

2) Las restantes aristas del grafo inicial , conforman un grafo no conexo, pero todos sus vértices mantienen el grado par, ya que al retirar el ciclo encontrado, se redujo cada grado en una cantidad par . Cada subgrafo conexo posee un ciclo Euleriano: d-c-i-j-k-e-d y h-g-m-h

. 3) Estos dos ciclos pueden ser insertados en el ciclo encontrado en 2) en los vértices comunes d y h respectivamente, originando un ciclo Euleriano a-d-c-i-j-k-e-d-j-n-o-kl-h-g-m-h-f-e-b-a, en el grafo original.

Cibegrafía:

https://www.fing.edu.uy/inco/grupos/bioinf/bioinfo1/teorico/grafos.pdf

CLASIFICACIÓN DE LOS GRAFOS

Multigrafo: Es un grafo no orientado con múltiples aristas entre pares de nodos.

Grafo simple: Es un grafo sin bucles, sin múltiples aristas entre pares de vértices.

Grafo completo Para todo par de vértices de G, existe por lo menos una arista que los une. Por lo tanto, un grafo completo de n vértices es aquel que tiene sus n vértices mutuamente adyacentes. n-clique, es un grafo completo simple de n vértices. Se nota Kn.

Subgrafo de G = (X,U) engendrado por el conjunto A ⊂ X, es un grafo cuyos vértices pertenecen al conjunto A y cuyas aristas son aquellas de G que tienen las dos extremidades en A. 

Grafo parcial de G = (X,U) engendrado por V ⊂ U, es el grafo G' = (X,V) cuyos vértices son los mismos de G y cuyas aristas son las que conforman el conjunto V ⊂ U. 

Subgrafo parcial de G, es un subgrafo de un grafo parcial de G

Grafo bipartito: Es un grafo cuyo conjunto de vértices puede ser particionado en dos clases X1 y X2 de tal forma que dos vértices de la misma clase no sean jamás adyacentes. Se nota G = (X1,X2,U)

Grafo bipartito completo, es aquel en el que para todo elemento de X1 y todo elemento de X2 existe por lo menos un arco que los liga.

Un grafo simple bipartito completo con p elementos en X1 y q elementos en X2 se nota Kp,q.

Grafo Regular: es aquel en el que todos sus vértices tienen el mismo grado.

Grafo Ponderado G = (X, U, W) donde (X, U,) es un grafo y W es una función W: U → Z+ (Z+: enteros positivos) . Si u ∈ U, w(u) es llamado el peso de la arista u. Estos pesos corresponden, según la aplicación, a costos, capacidades u otras propiedades de las aristas o arcos. Cuando se desea asignar valores negativos o reales a los pesos de las aristas, se debe tener especial cuidado en la elección de los algoritmos ya que la correctitud de los mismos puede depender de la restricción a Z+.

Grafo Conexo: es aquel en el que para cada par de vértices de G, existe una cadena que los une. En grafos orientados se definen 2 conceptos:

1.  Débilmente conexo: si existe una cadena (sin tener en cuenta la orientación) que une cada par de nodos distintos. 
2.  Fuertemente conexo: si para cada par ordenado de nodos x e y, existe un camino que va de x a y. 

Una componente conexa de un grafo G, es un subgrafo de G engendrado por los vértices que pueden unirse a un vértice xi dado, mediante una cadena (puede ser todo el grafo G).

Cibergrafía:

https://www.fing.edu.uy/inco/grupos/bioinf/bioinfo1/teorico/grafos.pdf

REPRESENTACIÓN DE LOS GRAFOS

1. Representación de grafos por matriz de incidencia. Matriz de adyacencia. Definición 1.4.1. 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.

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.

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

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

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

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 de unos que aparecen en una determinada columna es igual al grado de entrada del correspondiente vértice.

Cibergrafía:

http://docencia.udea.edu.co/regionalizacion/teoriaderedes/informaci%F3n/C1_RepresentacionMatrices.pdf 

HISTORIA DE LA TEORIA DE GRAFOS

El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana,algunos ejemplos podrían ser los siguientes:un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama),grafos matem´ticos que representan las relaciones binarias,una red de carreteras,la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad. En cada caso,es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos(vértices)con líneas conectándolos (arcos). De aquí se podría deducir que un grafo es básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio,es decir,un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices.Por otro lado,y debido a su generalidad y a la gran diversidad de formas que pueden usarse,resulta complejo tratar con todas las ideas relacionadas con un grafo.

Para facilitar el estudio de este tipo de dato,a continuación se realizará un estudio de la teoría de grafos desde el punto de vista de las ciencias de la computación. Considerando que dicha teoría es compleja y amplia,aquí sólo se realizará una introducción a la misma,describiéndose el grafo como un tipo de dato y mostrándose los problemas típicos y los algoritmos que permiten solucionarlos usando un ordenador.

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos grandes bloques:

Grafos Dirigidos.

Grafos no Dirigidos(pueden ser considerados un caso particular de los anteriores).

Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido.Por el contrario,la red de carreteras de un país representa en general un grafo no dirigido,puesto que una misma carretera puede ser recorrida en ambos sentidos.No obstante,podemos dar unas definiciones generales para ambos tipos.

Cibergrafia

http://teoriagrafosgerson.blogspot.com.co/2008/08/historia-de-la-teoria-de-grafos.html

OBJETIVO:

El Objetivo de este blog, es dar a conocer la estructura manejada en los diferentes tipos de árboles, dentro de la programación estructurada y estructura de datos en C, viendo como desarrollan una secuencia de pasos lógicos para formar y administrar información o los distintos tipos en cuanto a manejo de archivos, establecer las propiedades de los grafos, sus funcionalidades, aplicaciones varias dentro de las estructuras de datos.


Estructura de Datos

Las estructuras de datos es una colección de datos  que se caracterizan por su organización y las operaciones que se definen en ellos; debido a su eficiencia, Las estructuras de datos son un medio para manejar grandes cantidades de datos de manera eficiente para usos tales como grandes bases de datos y servicios de indización de Internet.  Por tanto una estructura de datos se caracterizará por las relaciones entre los datos que la constituyen y las operaciones posibles en ella. Esto supone que mediante un conjunto de reglas, las relaciones y operaciones posibles como insertar nuevos elementos o eliminar los ya existentes, con lo anterior se define la estructura.

Las estructuras de datos se basan generalmente en la capacidad de un ordenador para recuperar y almacenar datos en memoria.

¿QUÉ ES UN GRAFO?

Teoría de grafos :
La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias de la Computación. Los grafos constituyen una herramienta básica para modelar fenómenos discretos y son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos. En matemáticas y ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados vértices (o nodos) conectados por líneas llamadas aristas (o arcos) que pueden tener orientación (dirección asignada). Típicamente, un grafo está diseñado por una serie de puntos (los vértices) conectados por líneas (las aristas).

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado como uno de los primeros resultados 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. 

Los grafos son, como veremos, un lenguaje, una notación, que permite representar relaciones binarias es decir, entre pares de objetos en un conjunto (recordemos la sección 3.5). De una manera informal, podríamos decir que un grafo es una colección de vértices y de aristas que unen estos vértices. Los vértices los dibujaremos como puntos del plano, y las aristas serán líneas que unen estos puntos. Vayamos con las definiciones formales: 

Definición Formal: Un grafo G es un conjunto no vacío V (de vértices) y un conjunto A (de aristas) extraído de la colección de subconjuntos de dos elementos de V. Una arista de G es, pues, un subconjunto {a, b}, con a, b ∈ V , a = b. 

En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un grafo más claro. 

Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy legibles. Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o un alcantarillado. 

Cibergrafía:

https://www.uam.es/personal_pdi/ciencias/gallardo/capitulo8a.pdf

http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0701_Tc1003_TODO_Grafos.pdf