Arboles y Grafos

Ver más

Unidad 1. Habilidades Directivas y su Conceptualización.

por Roberto Gaxiola

donacion de organos

por karen vanessa clavijo rodriguez

CLASIFICACIÓN DE LOS SISTEMAS DE INFORMACIÓN A NIVEL EMPRESARIAL

por Gabriela González

diferencias del software libre y comercial

por arturo cabañas

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'.