Arboles Y Grafos

Índice

Contenido

Pág.

Introducción…………………………………………………………………………………4 Arboles Arboles Generales………………………………………………………………………....5 Terminologías básicas…………………………………………………………………..…5 Padre o raíz………………………………………………………………………………5 Arcos o ramas……………………………………………………………………………5 Hijos……………………………………………………………………………………..5 Grado de un nodo………………………………………………………………………..5 Nodosdescendientes…………………………………………………………………….5 Nodos ascendientes……………………………………………………………………..6 Hoja. …………………………………………………………………………………....6 Nivel. ………………………………………………………………….…………….….6 Altura o profundidad. …………………………………………………………………..6 Subárbol. ……………………………………………………………………………….6 Arboles Binarios. ………………………………………………………………………....6 Arboles binarios completos. ……………………………………………………………...6 Árbol binario de búsqueda. …………………………………………………………...….7 Arboles de expresiones.………………………………………………………………......7 Recorrido en arboles. …………………………………………………………………......7

Grafos Definición…………………………………………………………………………………………9 Terminologías básicas: Vértices. ………………………………………………………………………………...9 Conjunto de arcos. ………………………………………………………………....……9 Orden del grafo. ………………………………………………………………………...9 Nodos adyacentes. …………………………………………………………………….10 Grafo nulo. ………………………………………………………………………………10 Grafo dirigido.……………………………………………………………………….….10 Grafo no dirigido. ……………………………………………………………………….10 Grafo conectado y desconectado. ………………………………………………….……11 Grafo completo. ……………………………………………………………………...….11 Multígrafo. ……………………………………………………………………………....11 Representación secuencial de grafos (a través de matrices de adyacencias)…………….12 Representación enlazada de grafos (a través de listas enlazadas)……………………….12 Grafos ponderados (en arcos y vértices)…………………………………………………13 Grafo cíclico y acíclico…………………………………………………………….……13 Referencias…………………………………………………………………………………14

2

Introducción

Existen múltiples estructuras de datos, como pilas, colas, arboles, grafos, entre otras, de las cuales las últimas dos serán definidas en el material siguiente, así entonces:

Un árbol es una estructura de datos con gran importancia en la informática, son representaciones no lineales como son losarreglos de una o más dimensiones y las listas enlazadas, su uso es tradicional en la representación de formulas algebraicas, organización de objetos para optimizar la búsqueda de sus componentes y/o el árbol en sí mismo, inteligencia artificial. Resulta común en los variados sistemas operativos el

almacenamiento de sus archivos a través de esta herramienta. Su estructura base son los nodos,donde sólo uno carece de un padre, al cual se le denomina raíz, en los niveles siguientes en caso de existir se consideran hijos y si estos a su vez tienen hijos, en conjunto conforman un subárbol. Su nombre se debe a la similitud con los de la naturaleza donde todos los nodos excepto la raíz, se pueden observar como ramas.

Por su parte los grafos, se representan a través de TDA al igual que losarboles su estructura primordial son los nodos a los que se les define como vértices que están interconectados o no (según el tipo de grafo) mediante aristas (líneas sin sentido ni dirección) o arcos (líneas sin sentido ni dirección).

3

Arboles Arboles generales Intuitivamente, el concepto de árbol implica una estructura en la que los datos se organizan de modo que los elementos deinformación están relacionados entre sí a través de ramas. El árbol genealógico es el ejemplo típico más representativo del concepto de árbol general. Un árbol consta de un conjunto finito de elementos, denominados nodos y de un conjunto finito de líneas dirigidas, denominadas ramas, que conectan los nodos (Luis Joyanes 368). A , 2007, p.

A B C D
Figura 1.

E F

Terminologías básicas Padre oraíz. Si un árbol no está vacío , entonces el primer nodo se llama raíz. Además del nodo raíz , existen muchos términos utilizados en la descripción de los atributos de un árbol. Utilizando el concepto de árboles genealógicos, un nodo puede ser considerado como padre si...