6.1.1 COMPONENTES DE UN GRAFO
6.1.2 TIPOS DE GRAFO
6.2 REPRESENTACIÓN DE LOS GRAFOS
6.2.1 MATEMÁTICA
6.2.2 COMPUTACIONAL
6.3 ALGORITMOS DE RECORRIDO Y BUSQUEDA
6.3.1 EL CAMINO MAS CORTO
6.3.2 A LO ANCHO
6.3.3 EN PROFUNDIDAD
6.4 ÁRBOLES
6.4.1 COMPONENTES
6.4.2 PROPIEDADES
6.4.3 CLASIFICACIÓN
6.4.4 ÁRBOLES CON PESO
6.4.5 RECORRIDO DE UN ÁRBOL
6.5 REDES
6.6 APLICACIONES DE GRAFOS Y ÁRBOLES
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. (Fuente)
6.1 ELEMENTOS Y CARACTERÍSTICAS DE LOS GRAFOS
Un grafo (G) es un diagrama que consta de un conjunto de vértices (V) y un conjunto de lados (L).
Considérese el siguiente grafo:
A partir de esta figura se definen los siguientes elementos:
Vértices (nodos)
Se indican por medio de un pequeño círculo y se les asigna un número o letra. En el grafo anterior los vértices son V= {a,b,c,d}.
Lados (ramas o aristas)
Son las líneas que unen un vértice con otro y se les asigna una letra, un numero o una combinación de ambos. En el grafo anterior los lados son: L= {1, 2, 3, 4, 5, 6}.
Lados paralelos
Son aquellas aristas que tienen relación con un mismo par de vértices. En el grafo anterior los lados paralelos son: P={2,3}.
Lazo
Es aquella arista que sale de un vértice y regresa al mismo vértice. En el grafo anterior se tiene el lazo: A= {6}
Valencia de un vértice
Es el numero de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son:
Valencia (a)=2
Valencia (b)=4
Valencia (c)=2
Valencia (d)=3
Hay que observar como en el caso del vértice del lazo solo se considera una vez, entrada o salida pero no ambos.
6.1.1 COMPONENTES 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.
6.1.2 TIPOS DE GRAFOS
GRAFOS SIMPLES
Son aquellos grafos que no tienen lazos ni lados paralelos.
GRAFO COMPLETO DE N VÉRTICES (kn)
Es el grafo en donde cada vértice está relacionado con todos los demás sin lazos ni lados paralelos. Se indica como kn en donde n es el número de vértices del grafo.
La valencia en cada uno de los vértices de los grafos completos es (n – 1), y el numero de lados esta dado por la expresión
Núm. De lados = n(n – 1)
2
en donde n es el numero de vértices del grafo.
COMPLEMENTO DE UN GRAFO (G‘)
Es el grafo que le falta al grafo G, de forma que entre ambos formas de grafo completo de n vértices. Este grafo no tiene lazos ni ramas paralelas.
GRAFO BIPARTIDO
es el grafo que esta compuesta por dos conjuntos de vértices, A ={a1,a2, a3…, an} y B = {b1,b2,…, bm} en donde los elementos del conjunto B, pero entre los vértices de un mismo conjunto no existe arista que los una.
Una forma muy sencilla de saber si un grafo es bipartido es aplicar el hecho de que nunca tiene un ciclo de longitud impar, además de que debe cumplir con la característica mencionada anteriormente.
GRAFO BIPARTIDO COMPLETO (Kn, m)
Es el grafo que esta compuesto por dos conjuntos de vértices, uno de ellos A ={a1,a2, a3…, an} Y otro B= {b1,b2,…, bm), y en el cada vértice de A esta unido con todo los vértices de B, pero entre los vértices de un mismo conjunto no existe arista que los una. El grafo bipartido completo se indica como kn, m.
6.2 REPRESENTACIÓN DE LOS 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.6.2.1 MATEMÁTICA
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.
6.2.2 COMPUTACIONAL
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.
6.3 AlGORITMOS DE RECORRIDO Y BUSQUEDA
6.3.1 EL CAMINO MAS 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.
6.3.2 EN 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 árbol6.3.3 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
6.4 ÁRBOLES
Definición. Sea A un grafo. A recibe el nombre de árbol sí y sólo si:
Los árboles son una clase de grafos. Un claro ejemplo de un árbol es el siguiente:
Consideremos cuatro parejas de chismosos {a, A, b, B, c, C, d, D} donde a, b, c y d son los esposos y A, B, C y D son sus esposas respectivamente. Supongamos que a llama a su esposa para contarle algún chisme, entonces ella llama a las otras señoras para difundir el chisme, y cada una de ellas a su vez llama a su esposo para comunicárselo. El siguiente grafo muestra la propagación del chisme:
Un árbol es un grafo no dirigido conexo que no contiene circuitos, es decir que no existen dos o más paseos sobre un par de vértices.
Un conjunto de árboles disjuntos es llamado bosque. Un vértice de grado 1 en un árbol se llama hoja o un nodo terminal, y un vértice de grado mayor que 1 recibe el nombre de rama o nodo interno. Por ejemplo, son hojas: b, c, d y los vértices a, A, B, C, D son nodos rama.
Las propiedades de los árboles son:
• Existe un único paseo entre dos vértices cualesquiera de un árbol.
• El número de vértices es mayor en uno al número de aristas de un árbol.
• Un árbol con dos o más vértices tiene al menos dos hojas.
Un árbol T (libre) es una gráfica simple que satisface lo siguiente; si v y w son vértices en T, existe una trayectoria simple única de v a w. Se muestra un ejemplo:
Un árbol con raíz es un árbol en el que un vértice específico se designa como raíz, se presenta un ejemplo:
Como la trayectoria simple de la raíz a cualquier vértice dado es única, cada vértice está en un nivel determinado de manera única. Así, el nivel de la raíz es el nivel 0, los vértices que están debajo de la raíz están en el nivel 1, y así sucesivamente. Por lo tanto podemos decir que: el nivel de un vértice v es la longitud de la trayectoria simple de la raíz a v.
La altura de un árbol con raíz es el número máximo de nivel que ocurre.
Ejemplo:
Tomando como referencia el gráfico del árbol con raíz determine el nivel del vértice a, b, g y determine también la altura del árbol.
Para el vértice a su nivel es 0
Para el vértice b su nivel es 1
Para el vértice g su nivel es 2
La altura del árbol es de 2.
Ejercicio:
Construya dos árboles libres uno de 7 vértices y el otro de 5 vértices, luego determine cuantas aristas tiene cada árbol. (FUENTE)
6.4.1 COMPONENTES
Componentes (raíz, hoja, padre, hijo, descendientes, ancestros)
Las siguientes son las características y propiedades más importantes de los árboles en general:
a) Todo árbol que no es vacío, tiene un único nodo raíz.
b) Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. en
este caso es común utilizar la expresión X es hijo de Y.
c) Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. en es caso es
común utilizar la expresión X es padre de Y.
d) Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre),
son hermanos.
e) Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.
f) Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.
g) Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el
máximo grado de todos los nodos del árbol, es decir, el grado más alto entre todos los nodos.
h) Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por
definición la raíz tiene nivel 1.
i) Altura del árbol es el máximo número de niveles de todos los nodos del árbol.
6.4.2. PROPIEDADES DEL ÁRBOL
Entre las propiedades más importantes de los árboles está la presencia de un paseo entre cualquiera de dos vértices del árbol; segundo, que el número de vértices no es menor al número de aristas del árbol y que un árbol con más de dos vértices tiene por lo menos dos hojas.
Un ejemplo claro de los árboles en la vida cotidiana son los árboles genealógicos. Para este caso, los vértices representan a los miembros de la familia y los arcos representan la relación de parentesco. Conforme los conocimientos adquiridos con anterioridad, el árbol no deja de ser un grafo, pero es del tipo no dirigido.
6.4.3. CLASIFICACIÓN DE ÁRBOLES
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.
6.4.4. ÁRBOLES 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.
6.4.5. 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
6.5 REDES
Teorema de flujo máximo y mínimo.
Definición: Existe un flujo que viaja desde un único lugar de origen hacia un único lugar de destino a través de arcos que conectan nodos intermediarios. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al destino la mayor cantidad posible de flujo.
Usos del Algoritmo de flujo máximo y mínimo: Este algoritmo se utiliza para reducir los embotellamientos entre ciertos puntos de partida y destino en una red.
Por ejemplo:
1. Sistema de Vías Públicas.
2. Transporte de petróleo desde la refinería hasta diversos centros de almacenamiento.
3. Distribución de energía eléctrica a través de una red de alumbrado público
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.
Su mecanismo básico, si bien, la representación de grandes sistemas es costosa.
Para facilitar su uso en diferentes campos de aplicación, el modelo original se ha extendido en dos aspectos:
1. Introducción de modificaciones estructurales para incrementar la potencia o la comodidad de modelado o para facilitar la solución de los problemas de análisis.
2. Definición de redes de Petri temporizadas que se pueden utilizar para analizar cuantitativamente las prestaciones del sistema modelado.
Definiciones básicas:
· Una plaza p es entrada de una transición t si existe un arco desde p a t.
· Una plaza p es salida de una transición t si existe un arco desde t a p.
6.6 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.
Excelente pagina super recomendable y muy completa, encontre casi todos los temas que buscaba solo me faltaron 3
ResponderEliminarGrafos es un tema que no suele enseñarse en las universidades a pesar de su importancia dentro de las Matemáticas Discretas, por lo que su difusión es muy importante. muy buens esta página.
ResponderEliminarThe Best Casinos Near Harrah's Philadelphia Casino and Spa
ResponderEliminarHarrah's 나주 출장샵 Philadelphia Casino and Spa is owned and operated by the 상주 출장샵 Eastern Band 구미 출장샵 of the 보령 출장안마 Cherokee Indians and operated by 오산 출장마사지 Caesars.