GRAFOS
DEFINICION
es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
GRAFO NO DIRIGIDO
es un tipo de grafo en el cual las aristas representan relaciones simétricas y no tienen un sentido definido.
PAR ORDENADO
es una pareja de objetos matemáticos, en la que se distingue un elemento y otro. El par ordenado cuyo primer elemento es a y cuyo segundo elemento es b se denota como. Un par ordenado no es el conjunto que contiene a los elementos a y b, denotado por {a, b}.
VERTICE
es el punto donde se encuentran dos o más elementos unidimensionales.
NODO
es un punto de intersección, conexión o unión de varios elementos que confluyen en el mismo lugar.
GRAFO EULERIANO
Es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez.
GRAFO HAMILTONIANO
Es un camino, que visita todos los vértices del grafo una sola vez. Si además el primer y último vértice visitado coincide, el camino es un ciclo hamiltoniano.
ARBOLES EN MATEMATICAS
es un grafo no dirigido conectado con circuitos no simples; además, no contiene arcos múltiples, con la propiedad de que hay un único camino simple entre cada par de vértices
CONJUNTO DE VERTICES Y COMO SE EXPRESAN
Un grafo consiste de un conjunto finito de puntos llamados vértices y un conjunto finito de aristas, cada una de las cuales conecta dos vértices. Se dice que dos vértices son adyacentes, si están conectados por una arista.
Un grafo G=(V,E) es una pareja ordenada en la que V es un conjunto no vacío de vértices y E es un conjunto de aristas. Donde E consta de pares no ordenados de vértices, entonces se dice que x e y son adyacentes; y en el grafo se representa mediante una línea no orientada que una dichos vértices.
ELEMENTOS DE UN ARBOL
Altura: Es el máximo número de niveles de todos los nodos del árbol. Equivale al nivel más alto de los nodos más 1. También podemos hablar de altura de ramas, el máximo número de nodos que hay que recorrer para llegar de la raíz a una de las hojas.
Ancestros: los padres y los abuelos de un nodo hijo.
Descendientes: Hijos de los hijos.
Grado del Árbol: Es el máximo grado de todos los nodos del árbol.
Grado: El número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto A como D tienen tres hijos, y no existen elementos con más de tres hijos. También es el número de descendientes directos de un determinado nodo.
Hermano: Dos nodos serán hermanos si son descendientes directos de un mismo nodo. En cuanto a la posición dentro del árbol.
Longitud de Camino: Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.
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. Se define para cada elemento del árbol como la distancia a la raíz, medida en nodos
Nodo Hermano: Dos nodos serán hermanos si son descendientes directos de un mismo nodo.
Nodo Hijo: Cualquiera de lo nodo apuntado por uno de lo nodo del árbol. Un nodo puede tener varios hijos. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.
Nodo Hoja: Nodo que no tiene hijos. Se llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).
Nodo Interior: Es un nodo que no es raíz ni hoja.
Nodo Padre: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.
Nodo Raíz: Es el único nodo del árbol que no tiene padre es decir no es hijo de ningún elemento. Este es el nodo que usaremos para referirnos al árbol.
Nodo: Son los Vértices o elementos del Árbol.
Orden: Es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. Podríamos decir que nuestro árbol de ejemplo es de orden tres.
Peso: Es el número de nodos del árbol sin contar la raíz.
Rama: Es el camino desde el nodo raíz a una hoja.
RECORRIDOS DE UN ARBOL
Se puede hacer un recorrido de un árbol en profundidad o en anchura.
Los recorridos en anchura son por niveles, se realiza horizontalmente desde la raíz a todos los hijos antes de pasar a la descendencia de alguno de los hijos.
El coste de recorrer el ABB es O(n), ya que se necesitan visitar todos los vértices.
El recorrido en profundidad lleva al camino desde la raíz hacia el descendiente más lejano del primer hijo y luego continúa con el siguiente hijo. Como recorridos en profundidad tenemos inorden, preorden y postorden. Una propiedad de los ABB es que al hacer un recorrido en profundidad inorden obtenemos los elementos ordenados de forma ascendente.