El documento define y describe los árboles, incluyendo sus propiedades como que son grafos conexos y acíclicos con un único camino entre cada par de vértices. También describe diferentes tipos de árboles como binarios, trinarios y cuaternarios, y cómo se pueden clasificar por altura y número de nodos. Además, explica los recorridos de árboles como en profundidad y en anchura, así como árboles con peso y redes de flujo y flujo máximo.
0 calificaciones0% encontró este documento útil (0 votos)
25 vistas5 páginas
El documento define y describe los árboles, incluyendo sus propiedades como que son grafos conexos y acíclicos con un único camino entre cada par de vértices. También describe diferentes tipos de árboles como binarios, trinarios y cuaternarios, y cómo se pueden clasificar por altura y número de nodos. Además, explica los recorridos de árboles como en profundidad y en anchura, así como árboles con peso y redes de flujo y flujo máximo.
El documento define y describe los árboles, incluyendo sus propiedades como que son grafos conexos y acíclicos con un único camino entre cada par de vértices. También describe diferentes tipos de árboles como binarios, trinarios y cuaternarios, y cómo se pueden clasificar por altura y número de nodos. Además, explica los recorridos de árboles como en profundidad y en anchura, así como árboles con peso y redes de flujo y flujo máximo.
El documento define y describe los árboles, incluyendo sus propiedades como que son grafos conexos y acíclicos con un único camino entre cada par de vértices. También describe diferentes tipos de árboles como binarios, trinarios y cuaternarios, y cómo se pueden clasificar por altura y número de nodos. Además, explica los recorridos de árboles como en profundidad y en anchura, así como árboles con peso y redes de flujo y flujo máximo.
Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
Descargar como docx, pdf o txt
Está en la página 1/ 5
ARBOLES
Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices. Sea G = (V, A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos. Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz. Ejemplo de árbol: Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices. Sea G = (V, A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos. Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz. Ejemplo de árbol: En la figura anterior G1 corresponde a lo que llamamos mediante la definición ÁRBOL, en el caso de G2, éste no corresponde debido a que contiene un ciclo. Podemos destacar que cuando un grafo G es un Árbol, se reemplaza G, por R. En la figura mostrada G1 es un subgrafo de G2, en el que G1 contiene los vértices de G2 y es árbol, además lo llamaremos “árbol abarcador”, por que proporciona conexión mini mal para el grafo y un esqueleto mínima que une los vértices.
COMPONENTES Y PROPIEDADES: Hay un tipo especial de grafo, denominado árbol, que se presenta en múltiples aplicaciones. En ciencias de la computación los árboles son particularmente útiles. Por ejemplo: se utilizan para organizar información de tal modo que sea posible efectuar eficientemente operaciones que atañan a esa información. Para construir algoritmos eficientes para localizar artículos en una lista. Para construir códigos eficientes para almacenar y transmitir datos. Para modelar procedimientos que son llevados a cabo al utilizar una secuencia de decisiones. Introduzcamos pues el concepto de árbol. Árbol Un árbol es un grafo T = (V, E) acíclico y conexo Dado que un árbol no puede tener ciclos, no podrá contener ni aristas múltiples ni bucles, por lo tanto, cualquier árbol debe ser un grafo simple.
Si T = (V, E) es un grafo de orden n, son equivalentes
1. T es un árbol.
2. Entre cualquier par de vértices de T existe un único camino.
3. T es conexo y toda arista de T es una arista puente.
4. T es acíclico y maximal respecto a esta propiedad.
5. T es conexo y tiene tamaño n -1.
6. T es acíclico y tiene tamaño n - 1.
CLASIFICACION POR ALTURA Y NUMEROS DE NODOS: La altura h de un árbol T es el máximo de las longitudes de los paseos en un árbol, y se denota como h(T). En el ejemplo podemos observar que la altura del árbol es 4, entones la podemos expresar como h(T)= 4, el cual es el máximo de longitudes de todos los paseos en Los árboles pueden ser binarios (cada nodo padre tiene uno o dos hijos máximo), trinarios (cada nodo padre tiene máximo tres hijos), cuartenarios (cada nodo padre tiene como máximo 4 hijos), etc.
¿ ARBOLES CON PESO: El peso de un árbol en un nodo dado es el número de nodos en el árbol sin contarse el mismo. El peso de un nodo en un árbol es la longitud del camino más largo del nodo a una hoja. El peso de un árbol es el peso de la raíz. Un árbol con peso es un grafo donde cada lado tiene un número asociado o peso. Normalmente, al peso de un lado e se le designa por w(e). La suma de todos los pesos de todos los lados de un grafo con peso se llama el peso del grafo Peso total del grafo = 19
RECORRIDO DE UN ARBOL: Se puede hacer un recorrido de un árbol en profundidad o en anchura. Los recorridos en anchura son por niveles, se realiza horizontalmente desde la raíz a todos los hijos antes de pasar a la descendencia de alguno de los hijos. El coste de recorrer el ABB es O(n), ya que se necesitan visitar todos los vértices. El recorrido en profundidad lleva al camino desde la raíz hacia el descendiente más lejano del primer hijo y luego continúa con el siguiente hijo. Como recorridos en profundidad tenemos inorden, preorden y postorden. Una propiedad de los ABB es que al hacer un recorrido en Ejemplo árbol binario de búsqueda Resultado de hacer el recorrido en: Inorden = [6, 9, 13, 14, 15, 17, 20, 26, 64, 72]. Preorden = [15, 9, 6, 14, 13, 20, 17, 64, 26, 72]. Postorden =[6, 13, 14, 9, 17, 26, 72, 64, 20, 15]. 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 MAXIMO:
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.
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.
TEOREMA DE FLUJO MINIMO:
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 PEDRI: 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.
