Teoremas I y II para Arboles Binarios

Autor: Victor Acosta

1er Teorema para árboles binarios.

Un grafo no dirigido es un árbol, si y solo si hay un único camino entre cada pareja de vértices.

Se puede observar en este grafo, que para cualquier par de vértices que se tomen, solo existirá un camino que los unos. Si hay más de un camino que uno este par de vértices inmediatamente deja de ser un árbol.

A continuación en la siguiente imagen se puede apreciar de una manera visual lo que se acaba de presentar en este teorema

Como se puede observar las dos figuras ubicadas hacia el lado izquierdo de esta imagen cumplen con la condición de este primer teorema debido a que cuenta con un solo camino mientras que en las dos imágenes que se ubican al lado derecho se puede apreciar que existen diversos caminos que recorren el grafo y por ende no se consideran un árbol.

2do Teorema para árboles binarios.

Un árbol de n vértices tiene n-1 aristas

El árbol consta de 13 vértices o nodos, por tanto tenemos que:

𝑛 = 13 𝑎𝑟𝑖𝑠𝑡𝑎𝑠 = 𝑛 − 1 𝑎𝑟𝑖𝑠𝑡𝑎𝑠 = 13 − 1 𝑎𝑟𝑖𝑠𝑡𝑎𝑠 = 12

Comentarios

Entradas populares de este blog

Tipos de Arboles (Binarios y HEAP)

Autor: Jesús Villasana Arboles Binarios Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre “binario”). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Como estructura de datos este sirve para organizar datos para facilitar su manipulación, ya sea el ingreso, borrado o búsqueda de datos, y precisamente una de las principales ventajas de los árboles binarios es la búsqueda, ya que como en muchos algoritmos de búsqueda necesitamos tener la información ordenada y en nuestros árboles binarios precisamente los datos van ingresando de forma ordenada. Recorridos con los conocidos métodos recursivos: Inorden Postorden Preorden Montículo o HEAP Un montículo (heap) es una ...

Conceptos Básicos de Arbol,Altura,Nivel,Grado.

Autor: Nicolas Hurtado Un árbol como estructura de datos es un conjunto jerárquico no-vacío de datos, llamados nodos. Posee un elemento designado como la raíz del árbol, mientras que el resto de los elementos son divididos en subconjuntos no-vacíos, cada uno de estos subconjuntos es un sub-árbol de la raíz (Descendiente de esta), esto se conoce como estructura recursiva. Los árboles pueden ser de distintos tipos, siendo los árboles binarios el tipo principal en uso. Los árboles binarios pueden tener uno o dos hijos (o ninguno) y son la base de la implementación del algoritmo de búsqueda binaria. También son usados para la representación de fórmulas matemáticas, utilizados en sistemas de datos y en circuitos eléctricos. Los árboles también son definidos como estructuras no-lineales basados en la teoría de grafos, representando una de las estructuras de datos más importantes. En los siempre existe una ruta única del nodo raíz...

Algoritmos INSERTAR y HEAPIFY

Autor: Victor Acosta Inserción Cuando se llega a un árbol vacío se crea el nodo en el puntero que se pasa como parámetro por referencia, de esta manera los nuevos enlaces mantienen la coherencia. Si el elemento a insertar ya existe entonces no se hace nada. void insertar(tarbol **a, int elem) { if (*a == NULL) { *a = (arbol *) malloc(sizeof(arbol)); (*a)->clave = elem; (*a)->izq = (*a)->der = NULL; } else if ((*a)->clave < elem) insertar(&(*a)->der, elem); else if ((*a)->clave > elem) insertar(&(*a)->izq, elem); } Para insertar un nuevo elemento se sitúa al final del vector (última hoja del árbol) y se asciende hasta que cumpla la propiedad. Algoritmo Heapify Llamada recursiva a Heapify para sus sub-árboles, si no cumplen con la propiedad del heap

Arboles como estructura de datos

Buscar este blog