Teoría de grafos

Introducción

Se a realizado este trabajo con el objetivo de que los alumnos conozcamos un panorama breve, pero a la vez abarcador, sobre varios temas de la teoría de grafos; que comprueben cómo una herramienta matemática modeliza problemas de la realidad con mayor evidencia para ellos en la práctica; que podamos notar cómo los grafos establecen un puente que vincula lo abstracto (el grafoteórico) y lo concreto (ejemplificación a través de situaciones problemáticas) a lo largo de todo el curso de este tema, dado que una gran mayoría de los estudiantes no encontramos en los contenidos de Matemática su aplicación a la realidad; que aprendamos el uso de algunos algoritmos y experimentemos las ventajas que éstos brindan, para una eficiente resolución de problemas.

Índice

Árboles(teoría de grafos)………………………………………………………………………………….4

Tipos de árboles………………………………………………………………………………………...….5

Operaciones de árboles……………………………………………………………………………….…..6

Grafos de Euler……………………………………………………………………………………………..7

Características………………………………………………………………………………………...……7

Grafos de Hamilton………………………………………………………………………………………...8

Conclusión…………………………………………………………………………………………….…….9Bibliografías……………………………………………………………………………………………..…10



Árboles

En ciencias de la informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo es padre de un nodo si existe un enlace desdehasta (en ese caso, también decimos que es hijo de ). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Formalmente, podemos definir un árbol de la siguiente forma:
• Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).
• Un nuevoárbol a partir de un nodo y árboles de raíces con elementos cada uno, puede construirse estableciendo una relación padre-hijo entre y cada una de las raíces de los árboles. El árbol resultante de nodos tiene como raíz el nodo , los nodos son los hijos de y el conjunto de nodos hoja está formado por la unión de los conjuntos hojas iniciales. A cada uno de los árboles se les denotaahora subárboles de la raíz.
Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a unahoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel (a distancia aristas de la raíz), se deben haber listado todos los de nivel . Otros recorridos típicos del árbol son preorden, postorden e inorden:
• El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugarla raíz y luego cada uno de los hijos en orden previo.
• El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar , luego la raíz y luego cada uno de los hijos en orden simétrico.
• El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno delos hijos en orden posterior y por último la raíz.
Finalmente, puede decirse que esta estructura es una representación del concepto de árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico (ver también teoría de grafos y Glosario en teoría de grafos).



Tipos de Árboles

Árbol binario
Es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un...