TEORÍA DE GRAFOS Y ÁRBOLES
Teoría de grafos
- Los grafos son estructuras discretas que aparecen ubicuamente en cada disciplina donde se requiere modelar algo.
- En general los grafos son mapas conceptuales que ayudan a representar el conocimiento.
- Los grafos tiene muchas aplicaciones en problemas de ingeniería, computación, biología, física, urbanismo, comunicaciones, economía, redes sociales, entre muchas otras.
Propiedades de los Grafos
- Adyacencia. Dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
- Incidencia. Una arista es incidente a un vértice si ésta lo une a otro.
- Ponderación. Corresponde a una función que asocia a cada arista un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo.
- Etiquetado. Distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.
¿Qué es un grafo?
- Un grafo G consiste en un conjunto no vacío de vértices o nodos V y un conjunto de arcos o aristas E ⇒ G = (V,E).
- Grafo del griego grafos: dibujo, imagen. Cada e є E tiene un par (v1 ,v2 ) є V x V asociado; es decir, e conecta v1 con v2 .
- El grado de un vértice o nodo v є V es igual al número de arcos o aristas que lo tienen como extremo.
Vértices (Nodos). Elementos (objetos) que forman un grafo.
Cada uno lleva asociada un grado característico según la
situación, que se corresponde con la cantidad de arcos o
aristas que confluyen en dicho vértice.
Arcos o Aristas. Relaciones entre los elementos que forman
el grafo. Existen los siguientes tipos:
- Ramas. Arco o arista que unen un vértice con otro.
- Paralelas (múltiples). Arcos o aristas conjuntas si el vértice inicial y final son el mismo.
- Cíclicas (lazo, bucle). Arco o arista que el vértice inicial y final es el mismo.
Grafo dirigido
Un grafo dirigido o digrafo es un tipo de grafo en el cual las aristas tienen un sentido definido, a diferencia del grafo no dirigido, en el cual las aristas son relaciones simétricas y no apuntan en ningún sentido.
Al igual que en el grafo generalizado, el grafo dirigido está definido por un par de conjuntos
, donde:
, un conjunto no vacío de objetos simples llamados vértices o nodos.A veces un digrafo es denominado digrafo simple para distinguirlo del caso general del multigrafo dirigido, donde los arcos constituyen un multiconjunto, en lugar de un conjunto. En este caso, puede haber más de un arco que una dos vértices en la misma dirección, distinguiéndose entre sí por su identidad, por su tipo (por ejemplo un tipo de arco representa relaciones de amistad mientras que el otro tipo representa mensajes enviados recientemente entre los nodos), o por un atributo como por ejemplo su importancia o peso.
A menudo también se considera que un digrafo simple es aquél en el que no están permitidos los bucles. Un bucle es un arco que une un vértice consigo mismo.
Árboles
Desde el punto de vista conceptual, un árbol es un objeto que comienza con una raíz y se extiende en varias ramificaciones o líneas, cada una de las cuales puede extenderse en ramificaciones hasta terminar, finalmente en una hoja. Los árboles representan las estructuras no-lineales y dinámicas de datos más importantes en computación. Dinámicas, puesto que a cada elemento del árbol pueden seguirle varios elementos.
Propiedades de 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.
- Gráficamente puede representarse una estructura árbol de diferentes maneras y todas ellas equivalentes;
Árbol mediante grafo ⇧
Características de un árbol
- NODO indica un elemento, o ítem, de información.
- Todo árbol que no es vacío, tiene un único nodo raíz.
- Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. X es hijo de Y.
- Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. X es padre de Y.
- Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.
- Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.
- Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.
- Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol.
- Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición, la raíz tiene nivel 1.
- Altura del árbol es el máximo número de niveles de todos los nodos del árbol.
Árbol binario
Un árbol ordenado es aquel en el cual la distribución de las ramas sigue cierto orden. Los árboles ordenados de grado 2 son de especial interés puesto que representan una de las estructuras de datos más importante en computación, conocida como árboles binarios. En un árbol binario cada nodo puede tener como máximo dos subárboles; y siempre es necesario distinguir entre el subárbol izquierdo y el subárbol derecho.
Aplicacionesde arboles binarios
- Árboles binarios de búsqueda.
- Representación de una expresión algebraica.
- Árbol Genealógico.
Árboles binarios distintos
Dos árboles binarios son distintos cuando sus estructuras son diferentes. Ejemplo:
Árboles binarios similares
Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos difiere entre sí:
Árboles binarios equivalentes
Los árboles binarios equivalentes se definen como aquellos que son similares y además los nodos contienen la misma información:
Árboles binarios completos
Se define un árbol binario completo como un árbol en el que todos sus nodos, excepto los de último nivel, tienen dos hijos; el subárbol izquierdo y el subárbol derecho:
Recorridos en árboles binarios
Una de las operaciones más importantes a realizar en un árbol binario es el recorrido de los mismos. Recorrer significa visitar los nodos del árbol en forma sistemática; de tal manera que todos los nodos del mismo sean visitados una sola vez. Existen tres formas diferentes de efectuar el recorrido y todas ellas de naturaleza recursiva, éstas son:
Recorrido en preorden:
- Visitar la raíz
- Recorrer el subárbol izquierdo
- Recorrer el subárbol derecho
Recorrido en inorden:
- Recorrer el subárbol izquierdo
- Visitar la raíz
- Recorrer el subárbol derecho
Recorrido en postorden:
- Recorrer el subárbol izquierdo
- Recorrer el subárbol derecho
- Visitar la raíz
Árbol binario de busqueda
El árbol binario de búsqueda es una estructura sobre la cual se pueden realizar eficientemente las operaciones de búsqueda, inserción y eliminación. Formalmente se define un árbol binario de búsqueda de la siguiente manera: “Para todo nodo T del árbol debe cumplirse que todos los valores de los nodos del subárbol izquierdo de T deben ser menores o iguales al valor del nodo T. De forma similar, todos los valores de los nodos el subárbol derecho de T deben ser mayores o iguales al valor del nodo T”.
Ejemplos de Grafos y árboles en la vida cotidiana
- Emisor radiofusión
- El problema de los puentes de Königsberg
- Calles para conectar librerias
- Reino animal
- Posibles punntos de llegada entre ciudades
PÁGINAS CONSULATADAS
http://www.kramirez.net/Discretas/Material/Presentaciones/Grafos.pdf
https://www.slideshare.net/AlexisChavez1/rboles-y-grafos
