lOMoARcPSD|20021759
MATEMATICAS
DISCRETAS
REPORTE DE GRAFOS Y ARBOLES
INSTITUTO TECNOLOGICO DE CUAUTLA
RUIZ RIVERA SANTIAGO NO. 22680274
INGENIERIA EN SISTEMAS COMPUTACIONALES
DOCENTE: IRIS CITLALI CAMPOS ROMERO
FECHA DE ENTREGA: 6 de diciembre de 2022
Dirección de correo electrónico:
[email protected] 1
lOMoARcPSD|20021759
Tabla de contenido
Elementos, características y componentes de los grafos.....................................................3
Representación de los grafos...................................................................................................8
Matemática...................................................................................................................................9
Computacional..........................................................................................................................10
Algoritmos de recorrido y búsqueda......................................................................................12
El camino más corto.................................................................................................................14
A lo ancho..................................................................................................................................14
RECORRIDO DE UN ARBOL.............................................................................................................................................20
TEOREMA DE FLUJO MáXIMO........................................................................................................................................21
TEOREMA DEL FLUJO MíNIMO........................................................................................................................................22
PAREOS Y REDES DE PETRI.......................................................................................................................................22
CONCLUSIONES.......................................................................................................................23
BIBLIOGRAFIAS........................................................................................................................24
2
lOMoARcPSD|20021759
Elementos, características y componentes de los grafos
Definición de grafo
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.
Elementos y componentes de los grafos
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.
Son los puntos o nodos con los que está 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
una arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice
3
lOMoARcPSD|20021759
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.
Caminos
Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no
vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso
•x e y se llaman los extremos del camino
•El número de aristas del camino se llama la longitud del camino.
•Si los vértices no se repiten el camino se dice propio o simple.
• Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
•Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino
cerrado.
•Llamaremos ciclo a un circuito simple
•Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo
vértice es accesible respecto a si mismo
4
lOMoARcPSD|20021759
Características
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.
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.
Grafos completos:
Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es
decir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los
grafos completos es denominado usualmente, siendo el grafo completo de n vértices, es
decir, un grafo completo de vértices tiene exactamente
aristas. La representación gráfica de los como los vértices de un polígono regular da cuenta
de su peculiar estructura.
Grafos bipartitos:
5
lOMoARcPSD|20021759
Un grafo G es bipartito si puede expresarse como (es decir, sus vértices son la unión de
dos grupos de vértices), bajo las siguientes condiciones: • y son disjuntos y no vacíos. •
Cada arista de A une un vértice de V1 con uno de V2. No existen aristas uniendo dos
elementos de V1, análogamente para V2. Bajo estas condiciones, el grafo se considera
bipartito, y puede describirse informalmente como el grafo que une o relaciona dos
conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios en los que
debe unirse un elemento de la columna A con un elemento de la columna B.
Tipos de grafo: grafo simple o simplemente grafo:
Es aquel que acepta una sola 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.
Es la definición estándar de un grafo.
Multigrafo 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.
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.
6
lOMoARcPSD|20021759
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. Ejemplos:
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
Grafos planos:
Un grafo plano es aquel que puede ser
dibujado en el plano sin que ninguna
arista se intersecte.
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
7
lOMoARcPSD|20021759
hacia b. Ejemplos:
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.
Representación de los grafos
Matriz de adyacencia
La matriz de adyacencia de un grafo es simétrica. Si un vértice es aislado entonces la
correspondiente fila (columna) está 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
está compuesta sólo por ceros.
Matriz de incidencia
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.
Matemática
En matemáticas y ciencias de la computación, la teoría de grafos, también llamada teoría de
las gráficas estudia las propiedades de los grafos (también llamados gráficas) 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.
8
lOMoARcPSD|20021759
Por medio de la teoría de los grafos podemos resolver diversos problemas, como la síntesis
para circuitos secuenciales, contadores, o sistemas de apertura. Se utiliza en diferentes
áreas por ejemplo, en las áreas de Sistemas y Computación, en áreas de ingeniería.
También por medio de ellas podemos responder preguntas tales como, ¿Qué tarea debo
hacer primero?, ¿Qué tiempo es más corto?, ¿Cuál
9
lOMoARcPSD|20021759
es el más barato?, y así podemos obtener caminos óptimos para las soluciones aplicando
diversos algoritmos como puede ser el algoritmo de Floyd.
Un grafo G es un par (V,E) donde:
V ={v1,…,vn} es un conjunto de vértices E =
{e1,…,em} es un conjunto de aristas, Con
cada ek Î {vi, vj}, con vi, vj Î V, vi ≠ vj
Los vértices se representan como puntos y las aristas como líneas entre vértices Ejemplo:
G = (V,E)
V = {a,b,c,d }
E = {{a,b}, {b,c}, {a,c}, {a,d}, {d,b}
} Proponer otro recorrido:
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 más sencillas y usadas se encuentran las listas y las matrices y aunque
frecuentemente se usa una combinación de ambos.
10
lOMoARcPSD|20021759
Representación mediante matrices:
La forma más fácil de guardar datos en nodos es mediante la utilización de un vector que
indique los nodos, de manera que aristas entre los nodos se puedan ver como relaciones
entre los índices.
Sintaxis:
Tipo_de_variable[ ][ ]… [ ] Nombre_del_array= new
Tipo_de_variable[dimensión1][dimensión2]…[dimensiónN];
Arreglos Unidimensionales:
Es un arreglo que solo posee una dimensión, está formado por un conjunto de elementos
del mismo tipo de datos que almacenan bajo un nombre y se diferencia por la posición de
cada uno en el arreglo que inicia desde el 0.Estos pueden ser de 1 hasta n veces, donde n
es un número de elementos del arreglo.
Sintaxis:
TipoDato nombre []=new TipoDato [Total de elementos];
11
lOMoARcPSD|20021759
Algoritmos de recorrido y búsqueda
Existen algunas maneras útiles en las cuales se pueden ordenar sistemáticamente los nodos
de un árbol. Los más importantes son: pre orden, post-orden y en-orden.
Pre orden: (raíz, izquierdo, derecho).
Para recorrer un árbol binario no vacío en pre orden, 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
12
lOMoARcPSD|20021759
3. Visite la raíz
Se llama recorrido de un árbol al proceso que permite accede una vez a cada uno de los
elementos de un árbol para examinar el conjunto completo. Primero se ven los algoritmos
para construir el árbol, para la expresión dada en sufijo, prefijo o posfijo y también se
presentan algoritmos para reconocer si una expresión está correcta cuando está dada en
prefijo o posfijo.
Los ordenamientos más importantes son llamados: prefijo, sufijo y posfijo.
Recorrido en PREFIJO:
1. Visitar la raíz
2. Recorrer el subárbol izquierdo en prefijo
3. Recorrer el subárbol derecho en prefijo
· Recorrido SUFIJO:
1. Recorrer el subárbol izquierdo en sufijo
2. Visitar la raíz
3. Recorrer el subárbol derecho en sufijo
· Recorrido en POSFIJO:
1. Recorrer el subárbol izquierdo en postfijo
2. Recorrer el subárbol derecho en postfijo
3. Visitar la raíz
13
lOMoARcPSD|20021759
El camino más corto
En la Teoría de Grafos, uno de los problemas más conocido es el del camino más corto.
El problema 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.
Por ejemplo:
En el grafo siguiente, Luisa y Pedro tienen que encontrar el camino más corto (en el
sentido de menos “pesado”) entre los vértices a y e.
La solución es el camino a, b, c, e.
A lo ancho
En ciencias de la computación, A *es un
algoritmo informático que se utiliza amplia
mente 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.
14
lOMoARcPSD|20021759
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.
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.
ARBOLES
COMPONENTES Y PROPIEDADES
Desde el punto de vista conceptual, un árbol es un objeto que comienza con una raíz y se
extiende en varias ramificaciones o líneas, cada una de las cuales puede extenderse en
ramificaciones hasta terminar, finalmente en una hoja.
Los árboles representan las estructuras no-lineales y dinámicas de datos más
importantes en computación. Dinámicas, puesto que la estructura árbol puede cambiar
durante la ejecución de un programa. NO lineales, puesto que a cada elemento del árbol
pueden seguirle varios elementos.
15
lOMoARcPSD|20021759
Para comprender mejor que es un árbol comenzaremos explicando cómo está
estructurado.
Nodos: Se le llama Nodo a cada elemento que contiene un Á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 Padre: Se utiliza este término para llamar a todos aquellos nodos que tiene al
menos un hijo.
Nodo Hijo: Nodo Hijo: Cualquiera de lo nodo apuntado por uno de los nodos 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.
Nodo Hermano: Los nodos hermanos son aquellos nodos que comparte a un mismo
padre en común dentro de la estructura.
Nodo Hoja: Nodo que no tiene hijos. Se llama hoja o terminal a aquellos nodos que
no tienen ramificaciones (hijos).
Nodo Rama: Estos son todos aquellos nodos que no son la raíz y que además tiene
al menos un hijo.
Rama: Es el camino desde el nodo raíz a una hoja.
CLASIFICACION POR ALTURA Y NUMERO DE NODOS
Altura: Le llamamos Altura al número máximo de niveles de un Árbol.
La altura es calculada mediante recursividad tomando el nivel más grande de los
dos sub-árboles de forma recursiva de la siguiente manera:
16
lOMoARcPSD|20021759
altura = Max(altura(hijo1), altura(hijo2), altura(hijoN)) + 1
Árbol binario.
En ciencias de la computación, un árbol binario es una estructura de datos en la cual
cada nodo y un hijo derecho. No pueden tener más de dos hijos (de ahí el ijo tiene
como referencia a null, es decir que no almacena ningún o un nodo externo. En el caso
contrario el hijo es llamado un nodo árboles binarios son los árboles binarios de
búsqueda, los montículos fman. A veces un árbol binario perfecto es denominado árbol
binario bol binario completo como un árbol binario lleno en el que todas las
profundidades
Árbol binario de búsqueda auto-balanceable.
En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o
equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el
número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo
momento, automáticamente. Esto es importante, ya que muchas operaciones en un
árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los
árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes
en situaciones normales, como cuando las claves son insertadas en orden. Mantener
baja la altura se consigue habitualmente realizando transformaciones en el árbol, como
la rotación de árboles, en momentos
clave.
Árbol multicamino
17
lOMoARcPSD|20021759
Los árboles multicamino o árboles multirrama son estructuras de datos de tipo árbol
usadas en computación. Un árbol multicamino posee un grado g mayor a dos,
donde cada nodo de información del árbol tiene un máximo de g hijos. Sea un árbol de
m-caminos A, es un árbol m- caminos si y sólo si: A está vacío
ARBOLES CON PESO
Conocemos como peso a el número de nodos que tiene un Árbol. Este factor es
importante porque nos da una idea del tamaño del árbol y el tamaño en memoria que
nos puede ocupar en tiempo de ejecución (Complejidad Espacial en análisis de
algoritmos.)
El peso se puede calcular mediante cualquier tipo de recorrido el cual valla contando
los nodos a medida que avanza sobre la estructura. El peso es un árbol es igual a la
suma del peso de los sub-árboles hijos + 1
peso = peso(hijo1) + peso(hijo2) + peso(hijoN)+ 1
18
lOMoARcPSD|20021759
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.
Árbol abarcador de menor peso. Vamos a considerar de nuevo el problema de la red de
conducción, pero ahora añadiremos un ingrediente nuevo. El estudio previo de
ingeniería nos informa de qué tramos es posible construir, pero, además, disponemos
de la información sobre el coste de cada uno de esos tramos. Queremos, claro, elegir
una red que conecte todas las ciudades con el menor coste posible. La información de
los costes se traduce en que cada arista lleva asociado un número. Lo que buscamos
es un árbol
19
lOMoARcPSD|20021759
abarcador del grafo, pero justo aquel (o aquellos) para el que la suma de los costes de
las aristas elegidas sea mínima.
Para modelar esta situación, necesitamos una generalización del concepto de grafo.
Un grafo con pesos (o grafo ponderado) será un grafo G en el que, además, cada arista
a tenga asociado lo que llamaremos su peso, p(a), un número real no negativo. La
matriz de vecindades de un grafo con pesos será simétrica, con ceros en la diagonal, y
sus entradas serán los pesos de las aristas (o 0 si no hay tales aristas).
RECORRIDO DE UN ARBOL
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: (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).
20
lOMoARcPSD|20021759
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 pre orden, 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 pre orden, 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.
REDES
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.
TEOREMA DE FLUJO MáXIMO.
21
lOMoARcPSD|20021759
Siendo G una red de transporte, un flujo máximo es un flujo con valor máximo. En
general, habrá varios 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.
PAREOS Y 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
22
lOMoARcPSD|20021759
CONCLUSIONES
Después del trabajo realizado llegue a la conclusión de que hay diferentes tipos de
grafos y que se pueden hacer de distintas formas así como la definición que trata
de ser una relación de aristas y vértices.
Se me facilita la práctica de los grafos ya que no se me hacen tan difíciles, los
grafos nos ayudaran el día de mañana en la carrera de sistemas computacionales.
En sistemas computacionales funcionan como nodos para la práctica de
algoritmos.
23
lOMoARcPSD|20021759
BIBLIOGRAFIAS
4.2 Tipos de grafos.. (s.f.). Recuperado 8 noviembre, 2019, de
http://cidecame.uaeh.edu.mx/lcc/mapa/PROYECTO/libro5/42_tipos_de_grafos.htm
l
6.1 Elementos y Características de los Grafos - Matemáticas Discretas. (s.f.).
Recuperado 8 noviembre, 2019, de https://sites.google.com/site/matedicreta/6-1-
elementos-y-caracteristicas-de-los-grafos
Cristofer, C. (2017, 29 noviembre). 5.1 ELEMENTOS, CARACTERÃSTICAS Y
COMPONENTES DE LOS GRAFOS. Recuperado 9 noviembre, 2019, de
https://conjuntos-y-relaciones.blogspot.com/2017/11/51-elementos-caracteristicas-
y_20.html
Elementos, características y componentes de los grafos. (2017a, 29 noviembre).
Recuperado 8 noviembre, 2019, de
http://tcsjmdiscretas.blogspot.com/2017/11/elementos-caracteristicas-y-
componentes.html
Elementos, características y componentes de los grafos. (2017b, 29 noviembre).
Recuperado 8 noviembre, 2019, de
http://tcsjmdiscretas.blogspot.com/2017/11/elementos-caracteristicas-y-
componentes.html
6.2.2 Representación Computacional de los grafos - Matemáticas Discretas, R. P.
(s.f.). 6.2.2 Representación Computacional de los grafos - Matemáticas Discretas.
Recuperado 8 noviembre, 2019, de
https://sites.google.com/site/matematicasmoralesgalindo/6-2-representacion-de-
los-grafos/6-2-2-representacion-computacional-de-los-grafos
24
