En la actualidad los sistemas informáticos capacitados para procesar grandes cantidades de información requieren de algoritmos capaces de incidir en la toma de decisiones.
Cuando hablamos de arboles nos referimos a un objeto que comienza con una raíz y se extiende en varias ramificaciones o líneas, cada una de las cuales pueden extenderse en ramificaciones hasta terminar, finalmente en una hoja.
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.
Propiedades de los nodos
- Tienen un modo al que se le llama raíz del árbol.
- Todos los nodos, excepto la raíz, tienen una sola raíz de entrada (el nodo raíz no tiene ninguna).Tienen un modo al que se le llama raíz del árbol.
- Existe una ruta única del nodo raíz a todos los demás nodos del árbol.Tienen un modo al que se le llama raíz del árbol.
- Si hay una ruta <a, b>, entonces a, b se le denomina “hijo” de “a” y es el modo raíz del subárbol. Tienen un modo al que se le llama raíz del árbol.
- Todos los nodos, excepto la raíz, tienen una sola raíz de entrada (el nodo raíz no tiene ninguna).Tienen un modo al que se le llama raíz del árbol.
- Existe una ruta única del nodo raíz a todos los demás nodos del árbol.Tienen un modo al que se le llama raíz del árbol.
Características y propiedades de los árboles
- 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 apuntado por el nodo Y, X es hijo de Y.
- Un nodo X es antecesor directo de un nodo Y, si el nodo X a punta al nodo Y, X apunta al nodo Y.
- Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), hermanos Nodo indica un elemento o ítem de información.
- Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja Nodo indica un elemento o ítem de información.
- Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.
- Grados es el numero de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol Nodo indica un elemento o ítem de información.
- Nivel es el número de arcos que debe ser recorrido para llegar a un determinado nodo. Por definición, la raíz tiene nivel 1. Nodo indica un elemento o ítem de información.
- La altura del árbol es el máximo numero de niveles de todos los nodos del árbol.
GRAFOS
La teoría de grafos es una disciplina que hoy en día presenta un desarrollo vertiginoso debido a su importancia en el desarrollo de programas y circuitos.
Sus ideas básicas las introdujo el matemático Suizo Leonhard Euler en el siglo XVIII.
¿Que son los grafos?
Son un conjunto de puntos, de los cuales algún par de ellos está conectado por unas lineas. Si estas lineas son flechas, hablaremos de grafos dirigidos (dígrafos), mientras que si son simples líneas estamos ante un grafo no dirigido.
¿Cuál es la importancia de la teoría de grafos en las ciencias de la computación?
En las ciencias de la computación hay una serie enorme de fenómenos que se pueden modelar como grafos. Por lo tanto, pueden aprovecharse las propiedades matemáticas de los grafos para estudiarlos desde un punto de vista teórico preciso. Y luego, aplicar mecanismos de optimización sobre esos fenómenos.
Algunos ejemplos obvios
- Redes de computadoras (locales o remotas),
- Los componentes internos de un computador, representados como nodos entre los cuales fluyen los datos.
- Redes neuronales (tan de moda en temas de IA o ML.
Ejemplos de fuera de las CC, donde se aplican grafos a la modelización:
- El sistema de transporte público de una ciudad.
- El sistema nacional de distribución eléctrica.
- Las relaciones entre los distintos actores de una economía y el flujo de dinero entre ellos.
Arboles Radix: una estructura de datos que es increíblemente rápida para realizar lookups. El kernel de linux los utiliza para encontrar rápidamente páginas de memoria «sucias”
Características de un grafo
- Se llama bucle o lazo a toda arista de la forma (v, v).
- Se llaman aristas múltiples a las aristas que aparecen repetidas en E.
- Se dice que dos vértices son adyacentes si están unidas por una arista.
- Se dice que dos aristas son adyacentes si tienen un vértice en común.
- Se dice que una arista y un vértice son incidentes si el vértice es extremo de la arista.
- Se dice que un vértice es aislado si no es adyacente a ningún otro vértice.
- Se dice que un grafo es simple si no tiene bucles ni aristas múltiples.
El siguiente vídeo explica más a detalle el tema árboles y grafos
Bibliografía
Reynoso, C. (Noviembre de 2015). Árboles y redes: Crítica del pensamiento rizomático. 39. Obtenido de http://carlosreynoso.com.ar/archivos/articulos/Reynoso-Critica-del-pensamiento-rizomatico-2ed.pdf
Tecnologia educativa UNAN - NANAGUA 