Estructura de Datos 09110998: Arbol

Arboles

Concepto:

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

Tipos:
Árboles Binarios
Árbol de búsqueda binario auto-balanceable
Árboles AVL
Árboles Rojo-Negro
Árbol AA
Árboles Multicamino
Árboles B (Arboles de búsqueda multicamino autobalanceados)
Árbol-B+
Árbol-B*

Las operaciones comunes en árboles son:

Enumerar todos los elementos.
Buscar un elemento.
Dado un nodo, listar los hijos (si los hay).
Borrar un elemento.
Eliminar un subárbol (algunas veces llamada podar).
Añadir un subárbol (algunas veces llamada injertar).
Encontrar la raíz de cualquier nodo.

Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son:

Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre.
Representar el árbol con un array donde cada elemento es un nodo y las relaciones padre-hijo vienen dadas por la posición del nodo en el array.

Recorridos:

Preorden
R - SI - SD

Postorden
SI - SD - R

Inorden
SI - R - SD

Mi Arbol Genealogico

Bosques:
En teoría de grafos, 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.

Un árbol es un grafo simple unidireccional G que satisface alguna de las siguientes condiciones equivalentes:

G es conexo y no tiene ciclos simples.
G no tiene ciclos simples y, si se añade alguna arista se forma un ciclo simple.
G es conexo y si se le quita alguna arista deja de ser conexo.
G es conexo y el grafo completo de 3 vértices $K 3$ no es un menor de G.
Dos vértices cualquiera de G están conectados por un único camino simple.

Si G tiene muchos vértices, n, entonces las definiciones anteriores son también equivalentes a cualquiera de las siguientes condiciones:

G es conexo y tiene n − 1 aristas.
G no tiene aristas simples y tiene n − 1 aristas.
La cantidad de hojas de un árbol siempre es mayor o igual a la mitad de la totalidad de los nodos.

En grafo unidireccional simple G recibe el nombre de bosque si no tiene ciclos simples.
Un árbol dirigido es un grafo dirigido que sería un árbol si no se consideraran las direcciones de las aristas. Algunos autores restringen la frase al caso en el que todos las aristas se dirigen a un vértice particular, o todas sus direcciones parten de un vértice particular.
Un árbol recibe el nombre de árbol con raíz si cada vértice ha sido designado raíz, en cuyo caso las aristas tienen una orientación natural hacia o desde la raíz. Los árboles con raíz, a menudo con estructuras adicionales como orden de los vecinos de cada vértice, son una estructura clave en informática; véase árbol (programación).
Un árbol etiquetado es un árbol en el que cada vértice tiene una única etiqueta. Los vértices de un árbol etiquetado de n vértices reciben normalmente las etiquetas {1,2, ..., n}.
Un árbol regular ( homogéneo) es un árbol en el que cada vértice tiene el mismo grado. Véase grafo regular.

Codigo:

package treenode;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;
import java.util.*;
public class SimpleTree
{
    public static void main(String[] args)
    {
        JFrame frame = new SimpleTreeFrame();
        frame.show();
    }
}
    class SimpleTreeFrame extends JFrame
    {
        DefaultMutableTreeNode root = new DefaultMutableTreeNode("Mundo");
        DefaultMutableTreeNode arge = new DefaultMutableTreeNode("Argentina");
        DefaultMutableTreeNode sant = new DefaultMutableTreeNode("Santa Fe");
        DefaultMutableTreeNode rafa = new DefaultMutableTreeNode("Rafaela");
        DefaultMutableTreeNode rosa = new DefaultMutableTreeNode("Rosario");
        DefaultMutableTreeNode safe = new DefaultMutableTreeNode("Santa Fe");
        DefaultMutableTreeNode vena = new DefaultMutableTreeNode("Venado Tuerto");
        DefaultMutableTreeNode vill = new DefaultMutableTreeNode("Villa Constitucion");
        DefaultMutableTreeNode cord = new DefaultMutableTreeNode("Cordoba");
        DefaultMutableTreeNode codo = new DefaultMutableTreeNode("Cordoba");
        DefaultMutableTreeNode cbro = new DefaultMutableTreeNode("Cura Brochero");
        DefaultMutableTreeNode rcua = new DefaultMutableTreeNode("Rio Cuarto");
        DefaultMutableTreeNode chac = new DefaultMutableTreeNode("Chaco");
        DefaultMutableTreeNode resi = new DefaultMutableTreeNode("Resistencia");
        DefaultMutableTreeNode vang = new DefaultMutableTreeNode("Villa Angela");
        DefaultMutableTreeNode chil = new DefaultMutableTreeNode("Chile");
        DefaultMutableTreeNode regi = new DefaultMutableTreeNode("Region Metropolitana");
        DefaultMutableTreeNode schi = new DefaultMutableTreeNode("Santiago de Chile");
        public SimpleTreeFrame()
        {
            setTitle("SimpleTree");
            setSize(300,200);
            addWindowListener(new WindowAdapter()
            {
                public void windowsClosing(WindowEvent e)
                {
                    System.exit(0);
                }
            }
            );
            root.add(arge);
            arge.add(sant);
            sant.add(rafa);
            sant.add(rosa);
            sant.add(safe);
            sant.add(vena);
            sant.add(vill);
            arge.add(cord);
            cord.add(codo);
            cord.add(cbro);
            cord.add(rcua);
            arge.add(chac);
            chac.add(resi);
            chac.add(vang);
            root.add(chil);
            chil.add(regi);
            regi.add(schi);
            JTree tree = new JTree(root);
            Container contentPane = getContentPane();
            contentPane.add(new JScrollPane(tree));
            Enumeration hijos = sant.children();
            while(hijos.hasMoreElements())
            {
                System.err.println("Hijos de Santa Fe: " + hijos.nextElement());
            }
            boolean hoja = vena.isLeaf();
            System.err.println("Es venado tuerto hoja: " + hoja);
            Enumeration breadth = root.breadthFirstEnumeration();
            while(breadth.hasMoreElements())
            {
                System.err.println("Breadth First: " + breadth.nextElement());
            }
            Enumeration depth = root.depthFirstEnumeration();
            while ( depth.hasMoreElements() )
            {
                System.err.println("Depth First : "+depth.nextElement());
            }
            Enumeration preorder = root.preorderEnumeration();
            while ( preorder.hasMoreElements() )
            {
                System.err.println("Pre Order : "+preorder.nextElement());
            }
            Enumeration postorder = root.postorderEnumeration();
            while ( postorder.hasMoreElements() )
            {
                System.err.println("Post Order : "+postorder.nextElement());
            }
        }
}

http://es.wikipedia.org/wiki/%C3%81rbol_(inform%C3%A1tica)#Tipos_de_.C3.A1rboles

http://es.wikipedia.org/wiki/%C3%81rbol_binario
http://es.wikipedia.org/wiki/%C3%81rbol_(teor%C3%ADa_de_grafos)

Videos:
---------------------------------------------------------------------

---------------------------------------------------------------------

---------------------------------------------------------------------

Grafos

Concepto:
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo.

Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.

Vertice:
Los vértices constituyen uno de los dos elementos que forman un grafo. Como ocurre con el resto de las ramas de las matemáticas, a la Teoría de Grafos no le interesa saber qué son los vértices.
Diferentes situaciones en las que pueden identificarse objetos y relaciones que satisfagan la definición de grafo pueden verse como grafos y así aplicar la Teoría de Grafos en ellos.

Arco:

Camino:
Un camino P en grafo G de longitud n desde un vertice Vo a Vn es la secuencia de n+ 1 vertices:
P = (Vo, V1, V2, ... Vn)
tal que (vi, Vi+1) E A (Arcos) para 0<=i <=n. La longitus del camino es el numero de arcos que lo forma.

Ejemplo:

P1 = (4,6,9,7) es un camino de longitus 3.

En algunos grafos se dan arcos desde un vertice a si mismo(V,V), el camino V - V se denomina bucle. No es frecuente encontrarse con grafos que tengan bucles.

Un caminoP=((Vo, V1, V2, ... Vn) es simple si todos los nodos que forman el camino son distintos, pudiendo ser iguales Vo,Vn (los extremos del camino). En el ejemplo anterior P1 es un camino simple.

Un ciclo es un camino simple cerrado, Vo = Vn de longitud >= 2, en definitiva compuesto al menos por 3 nodos.

Tipos:
Grafos simples

Un grafo es simple si hay sólo 1 arista que une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

Un grafo que no es simple se denomina Multigráfica o Gráfo múltiple.Grafos conexos

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

Grafos completos
Artículo principal: Grafo completo

Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.

El conjunto de los grafos completos es denominado usualmente

, siendo

el grafo completo de n vértices.

Un

, es decir, grafo completo de n vértices tiene exactamente

aristas.

La representación gráfica de los

como los vértices de un polígono regular da cuenta de su peculiar estructura.
Grafos bipartitosGrafo bipartito

Un grafo G es bipartito si puede expresarse como

(es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:
V1 y V2 son disjuntos y no vacíos.
Cada arista de A une un vértice de V1 con uno de V2.
No existen aristas uniendo dos elementos de V1; análogamente para V2.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.
Digrafo:

Dirigido:

No Dirigido:

Videos:

---------------------------------------------------------------------

---------------------------------------------------------------------

---------------------------------------------------------------------

Bibliografia:
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos#V.C3.A9rtice
http://es.wikipedia.org/wiki/Grafo_(estructura_de_datos)

Páginas

Arbol