domingo, 2 de agosto de 2015

arboles y grafos

En teoría de grafo, un árbol es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino. 
Un bosque es una unión disjunta de árboles, un árbol a veces recibe el nombre de árbol libre.
Es decir, si se cumple una de ellas otras también se cumplen. Para árboles finitos además se cumple que: Si un árbol G tiene un número finito de vertices, n, entonces tiene n − 1 aristas.
  • Un Grafo (o grafo no dirigido) es un conjunto V de vértices y un conjunto E de aristas tales que cada arista e ? E(queda asociada a un par no ordenado de vértices. Si existe una única arista e asociada con los vértices v y w, escribimos e = (v,w). En este contexto (v,w) denota una arista en un grafo no dirigido y no un par ordenado.
  • Un grafo dirigido (o digrafo) consta de un conjunto finito de vértices V y un conjunto de arcos E ? V × V (obsérvese que cada arco es un par ordenado de vértices).
  • Grafo conexo: un grafo G es conexo si dados cualesquiera dos vértices v y w en G, existe un camino de v a w.
  •  Camino: sean v0 y vn vértices de un grafo. Un camino de v0 a vn de longitud n es una sucesión alternante de n+1 vértices y n aristas que comienza con el vértice v0 y termina con el vértice vn.
  • Longitud del camino: es el número de aristas que contiene.
  • Ciclo: sean v y w vértices en un grafo G, un ciclo o circuito es un camino de longitud distinta de 0 de v a w, sin aristas repetidas.
  • Subgrafo: sea G (V, E) un grafo. (V", E") es un subgrafo de G si
  • a) V" ( V y E"( E.
  • b) Para cada arista e" ( E", si e" es incidente en v" y w", entonces v", w" ( V).
  •  Grafo con pesos (o poderado): es un grafo en el cual se le asignan valores a las aristas y la longitud del camino de un grafo con pesos es la suma de todos los pesos de las aristas en la ruta (camino).
Recorrido de un grafo

Recorrido en anchura:    El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.
Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente
 
Un árbol es un grafo simple no dirigido G que satisface:
  1. G es conexo y no tiene ciclos .
  2. G no tiene ciclos y, si se añade alguna arista se forma un ciclo.
  3. G es conexo y si se le quita alguna arista deja de ser conexo.
  4. G es conexo y el grafo completo de 3 vértices K_3 no es un menor de G.
  5. Dos vértices cualquiera de G están conectados por un único camino simple.
Un arbol es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino.

Partes de un arbol

Hijo: Es aquel nodo que siempre va a tener un nodo antecesor o padre, son aquellos que se encuentran en el mismo nivel 
  Padre: Es aquel que tiene hijos y también puede tener o no antecesores. 
  Hermano: Dos nodos son hermanos si son apuntados por el mismo nodo, es decir si tienen el mismo padre. 
 Raíz: Es el nodo principal de un árbol y no tiene antecesores.  
  Hoja o terminal: Son aquellos nodos que no tienen hijos o también los nodos finales de un árbol.
  Interior: Se dice que un nodo es interior si no es raíz ni hoja. 

 Nivel de un nodo: Se dice que el nivel de un nodo es el numero de arcos que deben ser recorridos, partiendo de la raíz para llegar hasta el.
Altura del árbol: Se dice que la altura de un árbol esel máximo de los niveles considerando todos sus nodos.  
Grado de un nodo: se dice que el grado de un nodo es el número de hijos que tiene dicho nodo.  
Grado del árbol: se dice que es el grado de un árbol es el máximo de los grados considerando todos sus nodos.

Tipos de arboles
 * Binario : Son arboles donde cada nodo solo puede apuntar a dos nodos.
* Binario de busqueda: Son arboles binarios ordenados.
* Arboles B: Arboles cuyos nodos pueden tener un numero multiple de hijos. 
Tree graph.svg


No hay comentarios:

Publicar un comentario