Arboles y Grafos

Mais informações

Tipos de sistemas de información desde el punto de vista empresarial

por Paola Della Sera

OBJETIVOS DE LA CONTABILIDAD

por Rosa Helena Morantes Martinez

TEORÍAS DE GESTIÓN

por LUIS MEZA

INVERNADERO

por Valentina Gomez

Arboles y Grafos

Grafo. Abstracción matemática definida por la relación G= donde V es el conjunto de nodos o vértices y A es el conjunto de pares que definen los arcos o aristas que unen pares de vértices o lazos si unen a un vértice consigo mismo.

Venatas Y Desventajas

1. Se requiere un almacenamiento |v|*|v|. Es decir O(n2). 2. Solo al leer o examinar la matriz puede llevar un tiempo de O(n2).

1. Se puede determinar en un tiempo fijo y constante si un enlace(arco) pertenece o no al grafo. 2. Es fácil determinar si existe o no un arco o enlace, solo se debe posicionar en la matriz. 3. Es fácil determinar si existe un ciclo en el grafo, basta multiplicar la matriz por ella misma n veces hasta obtener la matriz nula(no hay ciclos) o bien una sucesión periódica de matrices(hay ciclo)

GRAFO DIRIGIDO: Un GRAFO DIRIGIDO G consiste de un conjunto V de vértices y un conjunto E al conjunto de aristas del grafo. GRAFO NO DIRIGIDO: Un Grafo no Dirigido se diferencia de un Grafo Dirigido debido a que cada arista en E es un par no ordenado de vértices.

Grafo orientado. [6] La definición de grafo orientado y la de grafo distan solo en un aspecto que en lugar de aristas, tiene arcos que se representan según los autores como (vi, vj) ó Matriz de adyacencia. [6] Dado un grafo G= de orden N al mismo se le asocia una matriz de adyacencia M cuadrada NxN donde cada fila y columna se asocia a un cada nodo específico y las celdas contienen la cantidad de aristas

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles. Esto son definiciones simples. Pero las características que implican no lo son tanto.

Ventajas Y Desventajas

v Sólo es recomendable para cuando el número de acciones es pequeño y no son posibles todas las combinaciones. v En la elección de un modelo, existe una cantidad muy limitada y dificulta para elegir el árbol óptimo. v Presenta inconvenientes cuando la cantidad de alternativas es grande y cuanto las decisiones no son racionales.

v Plantean el problema para que todas las opciones sean analizadas. v Permiten analizar totalmente las posibles consecuencias de tomar una decisión. v Proveen un esquema para cuantificar el costo de un resultado y la probabilidad de que suceda. v Ayuda a realizar las mejores decisiones sobre la base de la información existente y de las mejores suposiciones.

1. Leer val 2. Crear nodo 3. Hacer nodo.izq<-null, nodo.der<-null, nodo.info<-val 4. Si P.izq=null entonces P.izq<-nodo De lo contrario Hacer Q<-P.izq y ban<-1 4.1.Repetir mientras ban=1 4.1.1.Si val<=Q.info entonces 4.1.1.1.Si Q.izq=null entonces Q.izq<-nodo y ban <-0 De lo contrario Q<-Q.izq 4.1.1.2.{fin 4.1.1.1.} De lo contrario 4.1.1.3. Si Q.der=null entonces Q.der<-nodo y ban <-0 De lo contrario Q<-Q.der 4.1.1.4.{fin 4.1.1.3.} 4.1.2.{fin 4.1.1.} 4.2.{fin 4.1.} 5.{fin 4}

• Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'. • Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.