Conceptos Clave: Árboles, Redes y Redes de Petri en Teoría de Grafos

Árboles

Definición

Un árbol es un grafo no dirigido conectado sin circuitos simples. Además, no contiene aristas múltiples, con la propiedad de que hay un único camino simple entre cada par de vértices.

Utilidad de los Árboles

Los árboles son útiles para organizar y relacionar datos en una base de datos y otras aplicaciones diversas. En matemáticas discretas se estudian los árboles libres, con raíz, de expansión y binarios.

Componentes

• Raíz
• Hoja
• Padre
• Hijo
• Descendientes
• Ancestros

Nodo: Definición

Es un elemento de información que reside en el árbol.

Línea (Arista): Definición

Es un par de nodos ordenados, y a la secuencia de líneas se le denomina ruta (path).

Propiedades del Árbol

• Tienen un nodo al que se le llama raíz del árbol.
• Todos los nodos, excepto la raíz, tienen una sola línea de entrada (el nodo raíz no tiene ninguna).
• Existe una ruta única del nodo raíz a todos los demás nodos del árbol.
• Si hay una ruta de 'a' a 'b', entonces a 'b' se le denomina "hijo" de 'a' y es el nodo raíz de un subárbol.

Número de Nodos

• Un árbol estrictamente binario con n hojas siempre contiene 2n-1 nodos.
• Un árbol binario de profundidad d es un árbol binario casi completo si cualquier nodo a un nivel menor que d-1 tiene 2 hijos (un árbol estrictamente binario casi completo con n hojas tiene 2n-1 nodos, como cualquier otro árbol estrictamente binario con n hojas).

Árboles con Peso: Definición

Un árbol con peso es un grafo donde cada arista tiene un número asociado o peso, normalmente al peso de una arista se le designa por w(e). La suma de los pesos de todas las aristas de un grafo con peso se llama peso del grafo.

Tipos de Recorrido de un Árbol

• Preorden (Raíz, Izquierda, Derecha)
• Inorden (Izquierda, Raíz, Derecha)
• Postorden (Izquierda, Derecha, Raíz)

Redes

Definición

Una red es un método o secuencia que ayuda a tomar decisiones acertadas, optimizando flujos en vías con mayor capacidad, creando nuevas o eliminando antiguas.

Flujo Máximo

Generalmente existen varios flujos con el mismo valor máximo. Para encontrar el flujo máximo, consideraremos un flujo inicial en cada arista igual a cero, después se determina un camino específico de la fuente al sumidero y se incrementa el flujo.

Flujo Mínimo y Cortes

En lo que respecta a las redes, un corte es un conjunto de aristas cuya eliminación divide el conjunto de vértices V en dos subconjuntos disjuntos, V1 y V2, de modo que la fuente está en V1 y el sumidero en V2. Se llama capacidad de un corte a la suma de las capacidades de las aristas que van de V1 a V2: Capacidad(V1, V2) = Σ capacidad(v, w) para v ∈ V1, w ∈ V2. V1 es el subconjunto que contiene la fuente, V2 es el subconjunto que contiene el sumidero. Sea f un flujo en G y sea (V1, V2) un corte. Entonces la capacidad de (V1, V2) es mayor o igual que el valor de f (Teorema de Flujo Máximo-Corte Mínimo).

Redes de Petri

Concepto

Las Redes de Petri clásicas se conciben como un grafo dirigido que posee dos tipos de nodos principales: los lugares, representados por círculos, y las transiciones, representadas por barras rectangulares. Entre los nodos se ubican los arcos dirigidos, los cuales se encargan de unir las transiciones con los lugares y viceversa.

Definición Formal

Formalmente, una Red de Petri se define como una quíntupla, PN = (P, T, F, W, M0), donde:

• P = {p1, p2, ..., pm} es un conjunto finito de lugares.
• T = {t1, t2, ..., tn} es un conjunto finito de transiciones.
• F ⊆ (P × T) ∪ (T × P) es un conjunto de arcos dirigidos.
• W: F → {1, 2, 3, ...} es una función de pesos de los arcos.
• M0: P → {1, 2, 3, ...} es el marcado inicial de la red.

Además, se cumple que P ∩ T = ∅ y P ∪ T ≠ ∅.