Grafos y árboles

La teoría de grafos, también llamada teoría de gráficas, es una rama de las matemáticas y las ciencias de la computación que estudia las propiedades de los grafos.

¿QUE ES UN ÁRBOL?

En la ciencia de la computación definimos un árbol como un conjunto de nodos y líneas. Un nodo es un elemento de información que reside en el árbol. Una línea es un par de nodos ordenados, y a la secuencia de líneas se le denomina ruta.

Además, los árboles tienen las siguientes propiedades:

Tienen un nodo al que se le llama raíz del árbol.

Todos los nodos, excepto la raíz, tienen una sola línea de entrada (el nodo raíz no

tiene ninguna).

Existe una ruta única del nodo raíz a todos los demás nodos del árbol.

Si hay una ruta <a,b>, entonces a „b‟ se le denomina “hijo” de “a” y es el nodo raíz de un sub árbol

Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. Los arboles forman parte de los no dirigidos.

Sirven para organizar y relacionar datos en una base de datos, por ejemplo. Esto permite realizar operaciones de manera eficiente.

Un grafo dirigido (o digrafo) consta de un conjunto finito de vértices V y un conjunto de arcos E.

Un Grafo (o grafo no dirigido) es un conjunto V de vértices y un conjunto E de aristas tales que cada arista.

Longitud del camino: es el número de aristas que contiene.

Gráficamente puede representarse una estructura árbol de diferentes maneras y todas ellas
equivalentes

Ejemplo de árbol