Unidad 6

TEORÍA DE GRAFOS 

La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos (también llamadas gráficas, que no se debe confundir con las gráficas que tienen una acepción muy amplia) estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados (edges en inglés) que pueden ser orientados o no. 

La teoría de grafos es una rama de las matemáticas discretas y aplicadas, y es una disciplina que unifica diversas áreas como combinatorias, álgebra, probabilidad, geometría de polígonos, aritmética y topología. 

6.1. ELEMENTOS Y CARACTERÍSTICAS DE LOS GRAFOS

Grafos simples 

Un grafo es simple si a lo más existe una arista uniendo 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 multígrafo. 

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. 

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

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, o número o una combinación de ambos. En el grafo anterior los lados

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 número 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 (d) el lazo solo se considera una vez, entrada o salida pero no ambos.

6.1.2. TIPOS DE GRAFOS

Tipos De Grafos 

Grafo simple, o simplemente grafo es aquel que acepta una sola arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo. 

Multígrafo, o pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido. 

Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha 

Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices. 

Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad. 

Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices. 

Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito. 

6.2. REPRESENTACIÓN DE LOS GRAFOS

Representación De Los Grafos 

Existen diferentes formas de representar un grafo (simple), además de la geométrica y muchos métodos para almacenarlos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. 

Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.

Estructura de lista 

Lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas. Lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra. Lista de grados - También llamada secuencia de grados o sucesión gráfica de un grafo no-dirigido es una secuencia de números, que corresponde a los grados de los vértices del grafo.

Estructuras matriciales 

Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño, donde es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento es 1, de lo contrario, es 0. Matriz de incidencia - El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (1 - conectado, 0 - no conectado) 

6.2.1. REPRESENTACIÓN MATEMÁTICA DE LOS GRAFOS

Representación Matemática De Los Grafos 

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. 

6.2.2. REPRESENTACIÓN COMPUTACIONAL DE LOS GRAFOS

Representación Comunicacional De Los Grafos 

Existen diferentes formas de representar un grafo (simple), además de la geométrica y muchos métodos para almacenarlos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria. Estructura de lista, lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas. Lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra. Lista de grados - También llamada secuencia de grados o sucesión gráfica de un grafo no-dirigido es una secuencia de números, que corresponde a los grados de los vértices del grafo. Estructuras matriciales Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño, donde es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento es 1, de lo contrario, es 0. Matriz de incidencia - El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (1 - conectado, 0 - no conectado) 

6.3. ALGORITMOS DE RECORRIDO Y BÚSQUEDA

Algoritmos De Recorrido Y Búsqueda 

En ciencias de la computación, A* es un algoritmo informático que se utiliza ampliamente en la búsqueda de caminos y el recorrido del grafo, el proceso de trazar un camino transitable de manera eficiente entre los puntos, llamados nodos. Destaca por su rendimiento y precisión, que goza de amplio uso. (Sin embargo, en los sistemas de los viajes de enrutamiento prácticos, generalmente superado por algoritmos que pueden pre-procesar la gráfica para lograr un mejor rendimiento.) 

Peter Hart , Nils Nilsson y Bertram Raphael del Instituto de Investigación de Stanford (ahora SRI International ) describieron por primera vez el algoritmo en 1968.Se trata de una extensión de la Edsger Dijkstra algoritmo de 1959 .A* consigue un mejor rendimiento tiempo usando heurística. 

Ejemplo 

Un ejemplo de una estrella (A *) algoritmo en acción donde los nodos son las ciudades conectadas con carreteras y h (x) es la distancia en línea recta al punto de destino: 

Clave: verde: inicio, el azul: objetivo, de color anaranjado: visited 

Nota: En este ejemplo se utiliza una coma como separador decimal

6.3.1. ALGORITMOS DE RECORRIDO Y BÚSQUEDA EL CAMINO MÁS CORTO

Algoritmos De Recorrido Y Búsqueda El Camino Más Corto 

En la teoría de grafos, el problema del camino más corto es el problema de encontrar un camino entre dos vértices (o nodos) en un gráfico de tal manera que la suma de los pesos de sus bordes constituyentes se reduce al mínimo. 

Esto es análogo al problema de encontrar el camino más corto entre dos intersecciones en un mapa de carreteras: vértices del gráfico corresponden a las intersecciones y los bordes corresponden a los segmentos de carretera, cada uno ponderado por la longitud de su segmento de carretera. 

Algoritmos 

Los algoritmos más importantes para la solución de este problema son: 

El algoritmo de Dijkstra resuelve las cortas de origen único problemas de ruta. Algoritmo de Bellman-Ford resuelve el problema de una sola fuente, si borde pesos pueden ser negativos. Un algoritmo de búsqueda * resuelve para el par de ruta más corta única utilizando la heurística para tratar de acelerar la búsqueda. Algoritmo de Floyd-Warshall resuelve todos los pares caminos más cortos. Algoritmo de Johnson resuelve todos los pares de trayectorias más cortas, y puede ser más rápido que Floyd-Warshall en grafos dispersos. Algoritmos adicionales y evaluaciones asociados se pueden encontrar en Cherkassky et al. 

6.3.2. ALGORITMOS DE RECORRIDO Y BÚSQUEDA A LO ANCHO

Algoritmo De Recorrido Y Búsqueda a Lo Ancho 

En ciencias de la computación, A * (pronunciado “Una estrella” (escuchar)) es un algoritmo informático que se utiliza ampliamente en la búsqueda de caminos y el recorrido del grafo, el proceso de trazar un camino transitable de manera eficiente entre los puntos, llamados nodos. Destaca por su rendimiento y precisión, que goza de amplio uso. (Sin embargo, en los sistemas de los viajes de enrutamiento prácticos, generalmente superado por algoritmos que pueden pre-procesar la gráfica para lograr un mejor rendimiento.) 

Peter Hart, Nils Nilsson y Bertram Raphael del Instituto de Investigación de Stanford (ahora SRI International) describieron por primera vez el algoritmo en 1968. Se trata de una extensión de la Edsger Dijkstra algoritmo de 1959. A * consigue un mejor rendimiento tiempo usando heurística. 

Ejemplo 

Un ejemplo de una estrella (A *) algoritmo en acción donde los nodos son las ciudades conectadas con carreteras y h (x) es la distancia en línea recta al punto de destino: 

Clave: verde: inicio, el azul: objetivo, de color anaranjado: visited 

Nota: En este ejemplo se utiliza una coma como separador decimal. 

Ilustración de la búsqueda A * para la búsqueda de ruta desde un nodo de inicio a un nodo objetivo en un robot de planificación de movimientos problema. 

Una búsqueda de * que utiliza una heurística que es de 5,0 (= ε) veces a la heurística consistente, y obtiene una ruta subóptima. 

6.3.3. ALGORITMOS DE RECORRIDO Y BÚSQUEDA EN PROFUNDIDAD

Algoritmos De Recorrido Y Búsqueda En Profundidad 

En ciencias de la computación, recorrido del grafo es el problema de visitar todos los nodos en un gráfico de una manera particular, actualización y / o control de sus valores a lo largo del camino, recorrido del árbol es un caso especial del recorrido del grafo. 

Una búsqueda en profundidad (DFS) es un algoritmo para recorrer un grafo finito. DFS visitas los nodos secundarios antes de visitar los nodos del mismo nivel, es decir, que atraviesa la profundidad de cualquier camino en particular antes de explorar su amplitud. Una pila (a menudo del programa pila de llamadas a través de recursión) se usa generalmente cuando la ejecución del algoritmo. 

El algoritmo comienza con un nodo “raíz” elegida, entonces iterativamente transiciones desde el nodo actual a una, el nodo no visitado adyacente, hasta que ya no puede encontrar un nodo inexplorado para la transición a partir de su ubicación actual. El algoritmo entonces retrocede a lo largo de los nodos visitados anteriormente, hasta que encuentra un nodo conectado a un territorio aún más desconocido. A continuación, se procederá por el nuevo camino como antes, dando marcha atrás cuando se encuentra con callejones sin salida, y termina cuando el algoritmo ha retrocedido más allá del nodo original “root” desde el primer paso. 

DFS es la base de muchos algoritmos de grafos conexos, incluyendo las clases topológicas y pruebas de planitud. 

6.4. ARBOLES

Arboles 

En las matemáticas, y más específicamente en la teoría de grafos, un árbol es un grafo no dirigido en el que cualquiera de los dos vértices están conectados por exactamente un camino simple. En otras palabras, cualquier conectado gráfico sin ciclos simples es un árbol. Un bosque es una unión de la desunión de los árboles. 

Los diferentes tipos de estructuras de datos conocidos como árboles en ciencias de la computación son equivalentes en grafos no dirigidos a los árboles en la teoría de grafos, aunque estas estructuras de datos son generalmente árboles arraigados , por lo tanto, de hecho, ser grafos dirigidos, y también pueden tener adicionales ordenamiento de las ramas. 

El término “árbol” fue acuñado en 1857 por el matemático británico Arthur Cayley. 

Un árbol etiquetado con 6 vértices y aristas 5 Vértices v Bordes V - 1 Número cromático 2 si v > 1 

Definiciones 

Un árbol es un no dirigido gráfico simple T que satisface cualquiera de las siguientes condiciones equivalentes: 

T está conectado y no tiene ciclos. T no tiene ciclos, y un ciclo simple se forma si cualquier borde se añade a T. T está conectado, pero no está conectado en su caso de un solo filo se retira de T. T está conectado y el 3-vértice grafo completo no es un menor de T. Cualquiera de los dos vértices en T pueden estar conectados por un único camino simple. Si T tiene un número finito de vértices, digamos n de ellos, entonces las afirmaciones anteriores son también equivalentes a cualquiera de las siguientes condiciones: 

T está conectada y tiene n - 1 aristas. T no tiene ciclos simples y tiene n - 1 aristas. 

6.4.1 COMPONENTES (RAIZ, HOJA, PADRE, HIJO, DESCENDIENTE, ANCESTRO)

Un árbol está divido en tres subconjuntos separados. 

El primer subconjunto contiene un único elemento llamado raíz del árbol. 

Los otros 2 subconjuntos son por si mismos árboles binarios y se les conoce como subárboles izquierdo y derecho del árbol original. Cada elemento de un árbol binario se denomina nodo. La ausencia de una ramificación indica un subárbol vacío. 

Si A es la raíz de un árbol binario y B es la raíz de su subárbol izquierdo o derecho, se dice que A es el padre de B y se dice que B es el hijo izquierdo o derecho de A. 

Un nodo que no tiene hijos se denomina hoja. El nodo n1 es un ancestro del nodo n2 (y n2 es un descendiente de n1) si n1 es el padre de n2 o el padre de algún ancestro de n2. 2 nodos son hermanos si son los hijos izquierdos y derecho del mismo padre. 

Si cada nodo que no es hoja es un árbol binario tiene subárboles izquierdo y derecho que no están vacíos, el elemento se clasifica como árbol estrictamente binario. 

Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos. 

Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica inherente de los mismos. Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro. 

6.4.2. PROPIEDADES 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 bosque es una unión disjunta de árboles. Un árbol a veces recibe el nombre de árbol libre. 

Un árbol es un grafo simple no dirigido G que satisface: 

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 K_3 no es un menor de G. Dos vértices cualesquiera de G están conectados por un único camino simple. 

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: 

Que 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 entenderse 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 α y β (α ≈ 3 y β ≈ 0.5) tales que: 

6.4.3 CLASIFICACIÓN ÁRBOL (ALTURA, NUMERO DE NODOS)

Altura 

La altura (o profundidad) de un árbol es el largo del mayor camino de la raíz a una hoja. 

Dado un camino < v0, v1, v2,..., vk > el largo de este camino es k. 

Por lo cual el largo de un camino es igual al número de arcos del camino. 

Número de Nodos

Nodo:

Es el término usado para referirse a un vértice de un árbol con raíz.

Un árbol estrictamente binario con n hojas siempre contiene 2n - 1 nodos. El nivel de un nodo en árbol binario se define del modo siguiente: la raíz del árbol tiene el nivel 0, el nivel de cualquier otro nodo en el árbol es uno más que el nivel de su padre.

Si un árbol binario contiene m nodos en el nivel I, contiene cuando mucho 2m nodos en el nivel I + 1. Dado que un árbol binario solo contiene un nodo en el nivel 0 (raíz), puede contener un máximo de 2I nodos en el nivel I. Un árbol binario completo de profundidad d es el árbol que contiene 2I nodos en el nivel I entre 0 y d. La cantidad total de nodos en un árbol binario completo de profundidad d, tn es igual a la suma de la cantidad de nodos en cada nivel entre 0 yd.

Un árbol binario de profundidad d es un árbol binario casi completo si: 

Cualquier nodo nd a un nivel menor que d - 1tiene 2 hijos. 

Para cualquier nodo nd en el árbol con un descendiente derecho en el nivel d, nd debe tener 1 hijo izquierdo y cada descendiente izquierdo de nd es una hoja en el nivel d o tiene 2 hijos. 

Los nodos de un árbol binario casi completo se enumeran para que se asigne a la raíz el No.1, se asigne a un hijo izquierdo 2 veces el número asignado a su padre y se asigne a un hijo derecho 1 más el doble del No. asignado a su padre. Un árbol estrictamente binario casi completo con n hojas tiene 2n - 1nodos, como cualquier otro árbol estrictamente binario con n hojas. Un árbol binario casi completo con n hojas que no es estrictamente binario tiene 2n nodos.

Solo hay un árbol binario casi completo con n nodos. Este árbol es estrictamente binario si y solo si n es impar.

6.4.4. ARBOLES CON PESO

Arboles Con Peso 

Un árbol binario de peso equilibrado es un árbol binario que se equilibra con base en el conocimiento de las probabilidades de la búsqueda de cada nodo individual. Dentro de cada sub-árbol, el nodo con el peso más alto aparece en la raíz. Esto puede resultar en un rendimiento más eficiente búsqueda. 

La construcción de tal árbol es similar a la de un Treap, pero los pesos de nodo se eligen al azar en este último. 

Ejemplo de peso árbol equilibrado 

6.4.5. RECORRIDO DE UN ÁRBOL PREORDEN INORDEN POSTORDEN

Recorrido De Un Árbol Pre orden Inorden Postorden 

En ciencias de la computación, el recorrido del árbol se refiere al proceso de la visita (el examen y / o actualización) de cada nodo de una estructura de datos de árbol, tal vez, de una manera sistemática. Estos recorridos están clasificados por el orden en el que se visitan los nodos. 

Hay tres tipos de recorrido en profundidad: pre-orden, en orden y después de la orden. Para un árbol binario, que se definen como operaciones recursivamente en cada nodo, comenzando con el nodo raíz sigue: 

Pre-orden: 

Visita la raíz. Recorrer el subárbol izquierdo. Recorrer el subárbol derecho. En orden (simétrica): 

Recorrer el subárbol izquierdo. Visita la raíz. Recorrer el subárbol derecho. Después de la orden: 

Recorrer el subárbol izquierdo. Recorrer el subárbol derecho. Visita la raíz. 

Ejemplo 

Árbol binario: 

Profundidad-primera 

Pre-orden de la secuencia de recorrido: C, B, A, D, C, E, G, I, H (raíz, izquierda, derecha) 

Dentro de la orden de la secuencia de recorrido: A, B, C, D, E, F, G, H, I (izquierda, raíz, a la derecha) 

Después de la orden de la secuencia de recorrido: A, C, E, D, B, H, I, G, F (izquierda, derecha, root) 

Primero en amplitud 

Nivel-orden de la secuencia de recorrido: F, B, G, A, D, I, C, E, H 

6.5 REDES TEOREMA DE FLUJO MÁXIMO TEOREMA DE FLUJO MINIMO PAREOS Y REDES DE PETRI)

Una Red de Transporte es una gráfica 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 número no negativo.

Flujo máximo 

Se puede considerar un grafo como una red de flujo. Donde un nodo fuente produce o introduce en la red cierta cantidad de algún tipo de material, y un nodo sumidero lo consume. Cada arco, por tanto, puede considerarse como un conducto que tiene cierta capacidad de flujo. 

Una red de flujo es un grafo dirigido G= (V, E) donde cada arco (u, v) perteneciente a E tiene una capacidad no negativa. Se distinguen dos nodos: la fuente o nodo s, y el sumidero o nodo t. Si existen múltiples fuentes y sumideros, el problema se puede simplificar añadiendo una fuente común y un sumidero común. 

Este algoritmo depende de tres conceptos principales: 

Un camino de aumento, es una trayectoria desde el nodo fuente s al nodo sumidero t que puede conducir más flujo. 

La capacidad residual es la capacidad adicional de flujo que un arco puede llevar cf. (u,v) = c(u,v) - f(u,v) 

Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a la capacidad del corte mínimo que separa a la fuente del destino. 

Ejemplo del Flujo Máximo.-

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 dirigido bipartito, con un estado inicial, llamado marcación inicial. Los dos componentes principales de la red de Petri son los sitios (también conocidos como estados) y las transiciones. Gráficamente, los sitios son dibujados como círculos y las transiciones como barras o rectángulos. Las aristas del grafo son conocidas como arcos. Estos tienen un peso específico, el cual es indicado por un número entero positivo, y van de sitio a transición y viceversa. Por simplicidad, el peso de los arcos no se indica cuando éste es igual a 1. Un arco que esté etiquetado con k puede ser interpretado como k arcos paralelos. 

6.6. APLICACIONES DE GRAFOS Y ARBOLES

Aplicaciones De Grafos y Arboles 

Un diagrama de árbol es una representación de una estructura de árbol, una forma de representar la naturaleza jerárquica de una estructura en una forma gráfica. 

En matemáticas y ciencias de la computación, teoría de grafos es el estudio de los gráficos, que son estructuras matemáticas utilizadas para modelar las relaciones entre pares de objetos. Un “gráfico” en este contexto se compone de “vértices “o” nodos “y líneas llamados bordes que los conectan. Un gráfico puede ser no dirigida , lo que significa que no hay distinción entre los dos vértices asociados con cada borde, o sus bordes puede ser dirigido desde un vértice a otro; ver gráfico (matemáticas) para las definiciones más detalladas y para otras variaciones en los tipos de gráfico que se considera comúnmente. Los gráficos son uno de los principales objetos de estudio en matemáticas discretas.