# data[].attributes.body
Teoría de GRAFOS en INFORMÁTICA: Qué es un grafo, Tipos, Representación y Ejemplos Prácticos

# data[].attributes.attachment_link.title
Teoría de GRAFOS en INFORMÁTICA: Que es un grafo, Tipos de Grafos, como representarlos y ejemplos

# data[].attributes.body
Profundicemos en cómo los grafos se utilizan en situaciones específicas

# data[].attributes.attachment_link.title
10 Graph Theory Applications In Real Life - Number Dyslexia

# data[].attributes.attachment_link.description
What originated in the 18th century as a recreational math puzzle later opened to the world as a different branch of mathematics called Graph Theory. Whether to find the shortest route of virtual maps or to create a database link between search engines, Graph Theory, a concept that might seem challenging and arduous has a ... Read more

# data[].attributes.body
Un grafo es una estructura de datos no lineal que se utiliza para representar un conjunto de elementos y las conexiones entre ellos. Se compone principalmente de dos partes: nodos (o vértices) y aristas (o bordes). Son fundamentales en informática para modelar diversas situaciones.

Nodos (Vértices)

Son los puntos o elementos individuales que conforman el grafo. Representan las entidades o ítems de interés en el problema que se está modelando.

Ejemplos: personas en una red social, ciudades en un mapa o páginas web en Internet.

# data[].attributes.body
Aristas (o Bordes): Son las conexiones o enlaces que unen un par de nodos. Indican una relación, interacción o flujo entre los nodos, por ejemplo, una amistad, una ruta de transporte o un hipervínculo.

Adicionalmente, las aristas pueden tener

pesos (o ponderaciones), que son valores numéricos asignados para representar alguna magnitud o costo asociado a esa conexión, como la distancia entre dos ciudades, el tiempo de viaje, el costo de una conexión de red o la intensidad de una relación

Representan la "fuerza", el "costo", la "distancia" o alguna otra métrica de la conexión entre dos nodos.

Ejemplos: el tiempo o la distancia de una ruta entre ciudades, el costo de una llamada telefónica, la frecuencia de interacción en una red social.

# data[].attributes.body
•  Grafos Dirigidos (Digrafos):

En contraste, en un grafo dirigido (o digrafo), las aristas tienen una dirección específica, lo que significa que la relación va solo en un sentido.

Una arista de A a B no implica automáticamente una arista de B a A.

Ejemplo: Calles de sentido único en una ciudad, seguidores en redes sociales (yo sigo a alguien, pero esa persona no necesariamente me sigue a mí), o enlaces web (una página enlaza a otra, pero no viceversa).

# data[].attributes.body
•  Grafos No Dirigidos:

En un grafo no dirigido, las aristas representan conexiones bidireccionales, es decir, si existe una arista entre el nodo A y el nodo B, la relación va en ambas direcciones (de A a B y de B a A) sin distinción de sentido.

No hay una "dirección" específica en la relación.

Ejemplo: Una amistad en una red social (si A es amigo de B, B es amigo de A).

# data[].attributes.body
A continuación se presenta un video sobre la teoría de grafos para ampliar el conocimiento

# data[].attributes.attachment_link.title
Matemáticas Discretas - Teoría de Grafos (Parte 1/2)

# data[].attributes.body
Logística de Suministro y Rutas de Entrega (Optimización de Rutas):

¿Qué modela? En este escenario, cada almacén, centro de distribución o punto de entrega (clientes) se representa como un nodo en el grafo. Las carreteras o rutas posibles entre estos puntos son las aristas.

¿Qué son los pesos? Los pesos en las aristas pueden ser la distancia física, el tiempo estimado de viaje (considerando el tráfico), el costo del combustible, o incluso factores como la capacidad de carga del camión.

¿Cómo se optimiza? Los algoritmos de grafos (como el algoritmo de Dijkstra para la ruta más corta o algoritmos de ruteo de vehículos) se aplican para encontrar la secuencia óptima de visitas para un camión o una flota. El objetivo es minimizar la distancia total recorrida, el tiempo de entrega o el costo operativo, asegurando que todas las entregas se realicen eficientemente. Esto es crucial para empresas como Amazon, UPS o cualquier servicio de paquetería

# data[].attributes.body
Grafos Ponderados:

• Un grafo ponderado es cualquier grafo (dirigido o no dirigido) cuyas aristas tienen un "peso" o valor asociado.

Estos pesos pueden representar costos, distancias, tiempos, capacidades o cualquier otra magnitud relevante para la conexión entre los nodos.

Ejemplo: Un mapa de carreteras donde el peso de cada arista es la distancia en kilómetros entre dos ciudades, o una red de telecomunicaciones donde el peso es el costo de una conexión

# data[].attributes.body
Es una matriz cuadrada A de tamaño N x N, donde N es el número de nodos en el grafo. Cada celda A[i][j] indica si existe una arista que va del nodo i al nodo j.

¿Cómo funciona?

Para grafos no dirigidos: A[i][j] = 1 si hay una arista entre i y j, y 0 en caso contrario. La matriz es simétrica (A[i][j] = A[j][i]).

Para grafos dirigidos: A[i][j] = 1 si hay una arista de i a j, y 0 en caso contrario. La matriz no tiene por qué ser simétrica.

Para grafos ponderados: En lugar de 1, la celda A[i][j] almacena el peso de la arista entre i y j, y 0 (o infinito, según la convención) si no hay arista.

Ventajas: Facilita la comprobación rápida de la existencia de una arista entre dos nodos y la identificación de aristas paralelas. Útil para grafos densos (con muchas aristas).

Desventajas: Consume mucha memoria para grafos dispersos (con pocas aristas), ya que la mayoría de las celdas serán cero.

# data[].attributes.body
Es una matriz B de tamaño N x M, donde N es el número de nodos y M es el número de aristas. Cada celda B[i][j] indica la relación entre el nodo i y la arista j.

¿Cómo funciona?

Para grafos no dirigidos: B[i][j] = 1 si el nodo i es un extremo de la arista j, y 0 en caso contrario.

Para grafos dirigidos: B[i][j] = 1 si el nodo i es el punto de partida de la arista j, -1 si es el punto de llegada, y 0 si no está relacionado con la arista.

Ventajas: Es útil para identificar rápidamente las aristas incidentes a un nodo y para manejar grafos con múltiples aristas entre los mismos dos nodos.

Desventajas: Puede ser menos intuitiva para operar directamente y también puede ser densa en memoria para grafos muy grandes.

# data[].attributes.headline
Alternativa Eficiente para Representar Grafos

# data[].attributes.subject
Alternativa Eficiente para Representar Grafos

# data[].attributes.body
Listas de Adyacencia

Esta es la alternativa más popular a las matrices para grafos dispersos (con pocas aristas). Consiste en un array (o un diccionario/mapa) de V listas. Por cada vértice i, hay una lista que contiene todos los vértices adyacentes a él.

Usando el mismo ejemplo gráfico (A, B, C, D):

A -> [ B, C ]

B -> [ A, C ]

C -> [ A, B, D ]

D -> [ C ]

Para grafos ponderados, la lista no solo almacena el vértice adyacente, sino también el peso de la arista, usualmente como un par (vértice, peso).

# data[].attributes.body
La elección de la representación depende de las características del grafo (denso o disperso) y de las operaciones que se realizarán con más frecuencia.

# data[].attributes.body
Concepto y comparación con otras representaciones

# data[].attributes.attachment_link.description
En papel, un grafo se puede representar dibujando una imagen en la que los vértices se representan con puntos y las aristas con líneas ó flechas, o podemos representarlo haciendo una lista de los vértices y aristas.

# data[].attributes.body
Explicaciones conceptuales sobre representación de grafos (El artículo es muy visual e intuitivo).

# data[].attributes.attachment_link.description
When you visit any website, it may store or retrieve information on your browser, mostly in the form of cookies. This information might be about you, your preferences or your device and is mostly used to make the site work as you expect it to. The information does not usually directly identify you, but it can give you a more personalized web experience. Because we respect your right to privacy, you can choose not to allow some types of cookies. Click on the different category headings to find out more and change our default settings. However, blocking some types of cookies may impact your experience of the site and the services we are able to offer. More information

# data[].attributes.body
Camino: Un camino en un grafo es una secuencia de vértices donde cada vértice adyacente está conectado por una arista. Imagina que es una ruta que puedes seguir de un punto a otro a través de las conexiones del grafo.

Camino Simple: Es un camino que no repite vértices, a excepción, posiblemente, del primero y el último si es un ciclo. Es la ruta más "directa" sin pasar dos veces por el mismo lugar.

Ciclo: Un ciclo es un camino que comienza y termina en el mismo vértice. Es una ruta cerrada.

Ciclo Simple: Es un ciclo que no repite vértices intermedios. Solo el vértice de inicio y fin son el mismo.

# data[].attributes.body
definiciones claras y ejemplos sencillos de estos conceptos.

# data[].attributes.attachment_link.readable_text
En este post voy a presentar otro grupo de conceptos de la teoría de grafos, ligados a la noción de camino --la metáfora obvia es un mapa de carreteras. El significado usual de camino es una vía, una ruta, por la que se transita para ir de un lugar geográfico a otro --quizá pasando por otros lugares. El significado es tan básico que su definición sale sobrando. En teoría de grafos

Un camino es una sucesión de aristas de manera que, a excepción de la primera, el segundo vértice de una es el primer vértice de la siguiente.

Una definición alternativa sería

Un camino es una sucesión de vértices $v_0,v_1,v_2,\ldots,v_n$ de manera que $v_{i-1}$ es adyacente de $v_i$, para $i=1,2,\ldots,n$

Al igual que las nociones básicas de vértice, arista, y adyacencia están basadas en la metáfora geométrica del poliedro, los de camino, ciclo, y conexidad conviene asociarlos a la metáfora geográfica de un mapa de carreteras.

A partir de la definición de camino se definen varios otros conceptos:

Longitud de un camino: número de aristas que lo componen.

Camino simple: es un camino en que todas sus vértices son diferentes (no repite vértices).

Teorema: Si $u,v$ son vértices de un grafo $G$ y hay un camino de $a$ a $b$, entonces hay un camino simple de $a$ a $b$.

Por hipótesis existe un camino entre $a$ y $b$. Elegimos el de longitud más corta, digamos $a,v_1,v_2,\ldots,v_n,b$. Si este camino no fuera simple, ello significaría --por definición-- que un vértice se repite, digamos el $v_k$ y el $v_m$, con $k<m$. Entonces, eliminando los vértices intermedios $v_{k+1}, v_{k+2}\ldots,v_{m-1}$, tenemos un camino entre $a$ y $b$ más corto que el mínimo. Contradicción.

Ciclo: es un camino que empieza y acaba en el mismo vértice.

Ciclo simple: es un ciclo en que todos sus vértices son diferentes (no repite vértices.

Problema: Sea $G$ un grafo de la amistad (friendship graph), es decir, si $u,v$ son dos vértices distintos de $G$ entonces existe exactamente un vértice $z$ adyacente a $u$ y $v$. Demostrar que $G$ no tiene ciclos de longitud 4.

Si un tal ciclo existiera en $G$, entonces $G$ no cumpliría la condición de la amistad. (Sean $t,u,v,w,t$ los vértices del ciclo. Entonces $v$ y $t$ tienen a dos vértices adyacentes en común: $u$ y $w$.)

Grafo conexo: Es un grafo que tiene un camino entre cualquiera dos de sus vértices.

Teorema: Si $G$ es un grafo conexo, entonces existe un camino simple entre cualesquiera dos vértices de $G$.

Demostración: Se deja al lector (Sugerencia: ver l teorema arriba demostrado.)

Construir un grafo cuyos vértices son las 3-cadenas de ceros y unos y sus aristas representan la relación "difieren al menos en tres posiciones" (Por ejemplo, existe una arista entre 000 y 110.)

# data[].attributes.attachment_link.title
Grafos --caminos, ciclos, conexidad | MaTeTaM

# data[].attributes.attachment_link.description
En este post voy a presentar otro grupo de conceptos de la teoría de grafos, ligados a la noción de camino --la metáfora obvia es un mapa de carreteras. El significado usual de camino es una vía, una ruta, por la que se transita para ir de un lugar geográfico a otro --quizá pasando por otros lugares.

# data[].attributes.body
Conectividad: Este concepto se refiere a cómo de "unidos" están los vértices en un grafo. Un grafo con alta conectividad significa que hay muchas formas de llegar de un vértice a otro.

Grafo Conexo: Un grafo es conexo si existe un camino entre cualquier par de vértices. Es decir, no hay ninguna parte del grafo que esté aislada del resto.

Componentes Conexas: Si un grafo no es conexo, se puede dividir en "trozos" que sí lo son. Cada uno de estos subgrafos conexos se llama componente conexa.

# data[].attributes.headline
Búsqueda en Profundidad (DFS - Depth-First Search)

# data[].attributes.subject
Búsqueda en Profundidad (DFS - Depth-First Search)

# data[].attributes.body
¿Cómo funciona? Este algoritmo explora tan lejos como sea posible a lo largo de cada rama antes de retroceder (backtracking).

Imagina que estás en un laberinto y sigues un camino hasta el final; si no es la salida, vuelves al último cruce y pruebas otro camino.

Uso: Es útil para encontrar componentes conectadas, detectar ciclos o en topología. Utiliza una estructura de datos de tipo Pila (LIFO - Last In, First Out).

# data[].attributes.attachment_link.title
Algoritmo de Búsqueda en Profundidad o Depth First Search (DFS) para grafos | Explicación detallada

# data[].attributes.headline
Búsqueda en Anchura (BFS - Breadth-First Search

# data[].attributes.subject
Búsqueda en Anchura (BFS - Breadth-First Search

# data[].attributes.body
¿Cómo funciona? Explora todos los vecinos de un nodo antes de pasar a los vecinos de los vecinos. Es como lanzar una piedra al agua: las ondas se expanden uniformemente en todas las direcciones.

Uso: Es ideal para encontrar el camino más corto en grafos no ponderados. Utiliza una estructura de datos de tipo Cola (FIFO - First In, First Out).

# data[].attributes.attachment_link.title
Algoritmos DFS y BFS en un grafo | Asimov Ingeniería WhatsAppWhatsApp

# data[].attributes.attachment_link.description
DFS y BFS son algoritmos de Búsqueda em grafos y Arboles

# data[].attributes.body
Grafo Euleriano

Enfoque en las aristas: Un grafo es euleriano si se puede encontrar un circuito que recorra cada arista exactamente una vez y regrese al punto de partida. A este se le llama circuito euleriano.

Condición clave: Un grafo conexo es euleriano si y solo si todos sus vértices tienen grado par. Si tiene exactamente dos vértices de grado impar, tendrá un camino euleriano (recorre todas las aristas una vez, pero no termina en el inicio).

El origen: Este problema se origina con el famoso problema de los Siete Puentes de Königsberg, resuelto por Leonhard Euler.

Grafo Hamiltoniano

Enfoque en los vértices: Un grafo es hamiltoniano si se puede encontrar un ciclo que visite cada vértice exactamente una vez (excepto por el regreso al vértice inicial). A este se le conoce como ciclo hamiltoniano.

Sin condición simple: A diferencia de los grafos eulerianos, no existe una condición simple y necesaria para determinar si un grafo es hamiltoniano.

La gran diferencia:

Euleriano: Se enfoca en recorrer TODAS las aristas.

Hamiltoniano: Se enfoca en visitar TODOS los vértices.

# data[].attributes.body
Un recurso visual que compara ambos tipos de grafos con ejemplos claros.

# data[].attributes.attachment_link.title
Teoría de grafos CAMINOS EULERIANOS Y HAMILTONIANOS

# data[].attributes.attachment_link.title
2. Grafos eulerianos | Optimización de rutas

# data[].attributes.attachment_link.description
Saltar la navegación Buscar en todas las páginas

# data[].attributes.body
Imagina que estás dibujando el circuito con un lápiz sin levantarlo del papel.

1. Paso 1: Verificación. Comprueba que el grafo es conexo y todos sus vértices tienen grado par. Si no, el algoritmo no se puede aplicar.

2. Paso 2: Punto de Partida. Elige cualquier vértice como tu punto de inicio. Será tu vértice_actual.

3. Paso 3: El Recorrido (Bucle Principal). Mientras queden aristas sin recorrer en el grafo:

a. Contar opciones: Mira todas las aristas que salen de tu vértice_actual.

b. Elegir la arista:

Si solo hay una arista disponible, tómala.

Si hay varias aristas, elige una que NO sea un puente. Para saber si una arista es un puente, simula que la eliminas temporalmente y comprueba si el grafo sigue siendo conexo.

Si todas las aristas disponibles son puentes (esto solo ocurrirá hacia el final del recorrido), elige cualquiera de ellas.

c. Moverse y Actualizar:

Añade la arista elegida a tu circuito.

Muévete al siguiente vértice a través de esa arista. Este se convierte en tu nuevo vértice_actual.

Elimina la arista que acabas de usar del grafo.

4. Paso 4: Finalización. Una vez que hayas recorrido todas las aristas, el algoritmo termina. La secuencia de aristas que elegiste forma el circuito euleriano.

# data[].attributes.body
La clase de problemas NP (Tiempo Polinomial No Determinista) incluye problemas cuya solución, si se te da, puede ser verificada rápidamente (en tiempo polinomial).

Un problema es NP-Completo si es de los más "difíciles" en la clase NP. Esto significa que no se conoce ningún algoritmo eficiente (que se ejecute en tiempo polinomial) para encontrar una solución. Si se encontrara un algoritmo eficiente para un solo problema NP-completo, se podría resolver eficientemente todos los problemas de la clase NP.

Qué Significa que un Problema sea NP-Completo? 🤯

NP (Tiempo Polinomial No Determinista): Son problemas cuya solución puede ser verificada rápidamente. Si alguien te da una posible solución para un ciclo hamiltoniano, puedes seguir el camino en el grafo y comprobar fácilmente si visita todos los vértices una sola vez. El desafío no es la verificación, sino el hallazgo de esa solución.

NP-Completo: Son los problemas más difíciles dentro de la clase NP. Son tan complejos que si se encontrara una solución eficiente para uno solo de ellos, se podría adaptar para resolver eficientemente todos los demás problemas NP. A día de hoy, no se conoce ningún algoritmo eficiente para resolverlos.

# data[].attributes.body
Problema del Ciclo Hamiltoniano: Este es el problema más conocido. Consiste en determinar si, dado un grafo no dirigido G=(V,E), existe un ciclo simple que visite cada vértice de V exactamente una vez y regrese al vértice de partida. Si tal ciclo existe, se le llama ciclo Hamiltoniano.

Problema del Camino Hamiltoniano: Similar al problema del ciclo, pero en este caso se busca determinar si existe un camino simple que visite cada vértice de V exactamente una vez, sin necesidad de regresar al vértice de inicio.

# data[].attributes.body
El problema de decisión: "¿Tiene un grafo G un ciclo hamiltoniano?" es un problema NP-completo clásico.

¿Por qué es importante? Aunque es fácil verificar si un camino dado es un ciclo hamiltoniano (solo sigues la ruta y marcas los vértices), encontrar ese ciclo desde cero en un grafo grande es computacionalmente muy costoso.

Problemas relacionados: El famoso Problema del Vendedor Viajero (encontrar la ruta más corta que visita una serie de ciudades y vuelve al origen) es una generalización del problema del ciclo hamiltoniano y también es NP-completo.

# data[].attributes.body
Un árbol es una estructura de datos no lineal que consta de un conjunto de nodos conectados. A diferencia de las listas enlazadas o las pilas, donde los datos se organizan secuencialmente, en un árbol los datos se organizan de forma jerárquica, similar a un árbol genealógico.

Raíz (Root): Es el nodo principal y el punto de partida de un árbol. No tiene un nodo padre y es único.

Hojas (Leaves): Son los nodos que se encuentran en el nivel más bajo del árbol. No tienen nodos hijos.

Nodos Internos (Internal Nodes): Son todos los nodos que no son ni la raíz ni una hoja. Tienen al menos un nodo hijo.

Padre (Parent): Un nodo que tiene uno o más nodos hijos conectados directamente debajo de él.

Hijo (Child): Un nodo que tiene un nodo padre directamente encima de él.

# data[].attributes.body
Árboles Generales

A diferencia de los binarios, un árbol general no tiene restricciones en el número de hijos que puede tener un nodo. Son más flexibles y se utilizan para representar estructuras jerárquicas complejas, como los sistemas de archivos de una computadora, donde cada carpeta (nodo padre) puede contener múltiples subcarpetas y archivos (nodos hijos).

# data[].attributes.body
Árboles Binarios

Un árbol binario es un tipo de árbol en el que cada nodo tiene como máximo dos hijos: uno izquierdo y uno derecho. Son muy utilizados debido a la simplicidad de su estructura, lo que permite implementar algoritmos eficientes para la búsqueda, inserción y eliminación de datos.

Dentro de los árboles binarios, hay subtipos como:

Árbol Binario de Búsqueda (BST): Un árbol binario donde todos los nodos del subárbol izquierdo de un nodo son menores que él, y todos los nodos del subárbol derecho son mayores. Esto facilita enormemente la búsqueda de datos.

Árbol Binario Completo: Un árbol en el que todos los niveles, excepto posiblemente el último, están completamente llenos, y todos los nodos del último nivel están lo más a la izquierda posible.

Árbol Binario Balanceado (AVL, Red-Black): Árboles que mantienen su altura lo más baja posible para garantizar que las operaciones de búsqueda se realicen en tiempo logarítmico.

# data[].attributes.body
Recorridos en Árboles

Un recorrido es una forma de visitar todos los nodos de un árbol una vez. Los tres tipos de recorrido más comunes son preorden, inorden y postorden.

Para los siguientes ejemplos, usaremos este árbol:

Nodo Raíz: A

Hijos de A: B (izquierdo), C (derecho)

Hijos de B: D (izquierdo), E (derecho)

Hijos de C: F (izquierdo)

# data[].attributes.body
Recorrido en Preorden (Root-Left-Right)

En este recorrido, se visita primero el nodo raíz, luego se recorre el subárbol izquierdo y finalmente el subárbol derecho.

Orden de visita: Raíz -> Subárbol Izquierdo -> Subárbol Derecho

Recorrido del ejemplo: A, B, D, E, C, F

Este recorrido se utiliza comúnmente para crear una copia de un árbol.

# data[].attributes.body
Recorrido en Inorden (Left-Root-Right)

Este es el recorrido más común en los árboles binarios de búsqueda. Primero se visita el subárbol izquierdo, luego el nodo raíz y finalmente el subárbol derecho.

Orden de visita: Subárbol Izquierdo -> Raíz -> Subárbol Derecho

Recorrido del ejemplo: D, B, E, A, F, C

En un árbol binario de búsqueda, un recorrido inorden siempre devuelve los nodos en orden ascendente.

# data[].attributes.body
Recorrido en Postorden (Left-Right-Root)

En este recorrido, se visita primero el subárbol izquierdo, luego el subárbol derecho y finalmente el nodo raíz.

Orden de visita: Subárbol Izquierdo -> Subárbol Derecho -> Raíz

Recorrido del ejemplo: D, E, B, F, C, A

Este recorrido es útil para borrar los nodos de un árbol, ya que se eliminan primero los nodos hijos antes que sus padres.

# data[].attributes.attachment_link.title
Tree Traversal Techniques - GeeksforGeeks

# data[].attributes.attachment_link.description
Your All-in-One Learning Portal: GeeksforGeeks is a comprehensive educational platform that empowers learners across domains-spanning computer science and programming, school education, upskilling, commerce, software tools, competitive exams, and more.

# data[].attributes.attachment_link.authors[].name
Tutorías con Ingenio Universidad Nacional

# data[].attributes.body
Un ABB es un árbol binario que cumple con la siguiente propiedad en todos sus nodos:

Todos los nodos en el subárbol izquierdo de un nodo X tienen un valor menor que el valor de X.

Todos los nodos en el subárbol derecho de un nodo X tienen un valor mayor que el valor de X.

Esta propiedad de ordenamiento permite que las operaciones de búsqueda, inserción y eliminación se realicen en un tiempo promedio de O(logn), lo que es muy eficiente.

# data[].attributes.body
El Problema del Desbalance

El principal problema de los ABB es que su rendimiento óptimo depende de que el árbol se mantenga balanceado. Si los datos se insertan en un orden estrictamente ascendente o descendente, el árbol puede degenerar en una lista enlazada, donde la altura es n. En este caso, el tiempo de búsqueda se degrada a O(n), perdiendo su principal ventaja.

# data[].attributes.body
Árboles AVL

Los árboles AVL (llamados así por sus creadores Adelson-Velsky y Landis) son una solución al problema de desbalance de los ABB. Son árboles binarios de búsqueda auto-balanceables.

Balanceo y Factor de Equilibrio

La propiedad definitoria de un árbol AVL es su factor de equilibrio (balance factor). Para cada nodo, este factor se calcula como:

factor_equilibrio=altura(subaˊrbol_derecho)−altura(subaˊrbol_izquierdo)

Un árbol AVL se mantiene balanceado si el factor de equilibrio de cada nodo es -1, 0 o 1. Si en algún momento una inserción o eliminación rompe esta regla, el árbol debe ser re-equilibrado.

# data[].attributes.body
Rotaciones

El re-balanceo se logra a través de rotaciones, que son operaciones que cambian la estructura del árbol para mantener su altura mínima. Existen cuatro tipos de rotaciones:

Rotación Simple a la Izquierda (LL): Se utiliza cuando un nodo está desbalanceado hacia la izquierda debido a la inserción en el subárbol izquierdo de su hijo izquierdo.

Rotación Simple a la Derecha (RR): Es la operación simétrica a la rotación a la izquierda. Se usa cuando un nodo está desbalanceado hacia la derecha debido a la inserción en el subárbol derecho de su hijo derecho.

Rotación Doble Izquierda-Derecha (LR): Se aplica cuando un nodo está desbalanceado a la izquierda, pero la inserción ocurrió en el subárbol derecho de su hijo izquierdo. Consiste en una rotación a la izquierda del hijo, seguida de una rotación a la derecha del padre.

Rotación Doble Derecha-Izquierda (RL): Es la operación simétrica a la rotación LR.

El costo de las rotaciones es bajo, lo que permite que las operaciones de inserción y eliminación en un árbol AVL mantengan un rendimiento garantizado de O(logn).

# data[].attributes.body
Árboles B y B+

Mientras que los árboles AVL están optimizados para el almacenamiento en memoria RAM, los árboles B y B+ están diseñados para minimizar el número de accesos a disco, lo cual es crucial en aplicaciones de bases de datos.

Árbol B (B-Tree)

Un árbol B es un árbol de búsqueda auto-balanceable, pero a diferencia de los ABB, cada nodo puede tener múltiples hijos. Se caracteriza por:

Estructura de Bloques: Los nodos de un árbol B corresponden a bloques de datos en disco.

Alto Factor de Ramificación: Cada nodo puede contener un gran número de claves y punteros a sus hijos. Esto resulta en árboles muy "chatos" (poca altura), lo que minimiza el número de lecturas de disco.

Datos en Nodos Internos: Las claves y los datos pueden estar almacenados en los nodos internos y en las hojas.

Balanceo de Altura: Todos los nodos hoja están en el mismo nivel, a la misma distancia de la raíz.

Las operaciones de inserción y eliminación en un árbol B son más complejas, ya que pueden requerir la división (splitting) o la unión (merging) de nodos para mantener el balance y el factor de ramificación.

# data[].attributes.body
Árbol B+ (B+-Tree)

El árbol B+ es una variante del árbol B, diseñada para mejorar aún más el rendimiento en bases de datos. Sus características principales son:

Datos Solo en las Hojas: La principal diferencia es que todos los datos se almacenan exclusivamente en los nodos hoja. Los nodos internos solo contienen copias de las claves para guiar la búsqueda, pero no los datos asociados.

Hojas Enlazadas: Todos los nodos hoja están conectados entre sí en una lista enlazada.

Duplicación de Claves: Las claves en los nodos internos son un índice para las claves en las hojas, lo que puede llevar a cierta duplicación.

La estructura del árbol B+ lo hace más eficiente para ciertas operaciones, como las consultas de rango.

# data[].attributes.body
Los árboles B y B+ son la columna vertebral de los sistemas de gestión de bases de datos (DBMS).

Índices de Bases de Datos: Su aplicación más importante es la implementación de índices. Cuando creas un índice en una columna de una tabla (por ejemplo, CREATE INDEX idx_user_id ON users(id)), el sistema de gestión de bases de datos internamente construye un árbol B+ para esa columna.

¿Por qué son ideales?

Minimización de E/S (Entrada/Salida): Al tener una altura muy pequeña, se necesitan muy pocas lecturas de disco para encontrar un registro, lo que es el cuello de botella más grande en el rendimiento de una base de datos. Un árbol B+ con millones de registros puede tener solo 3 o 4 niveles de altura.

Consultas de Rango Eficientes: La estructura enlazada de las hojas del árbol B+ permite realizar consultas de rango (ej. SELECT * FROM users WHERE id BETWEEN 100 AND 200) de manera extremadamente rápida. Una vez que se encuentra el primer registro (id=100), se puede recorrer la lista enlazada de hojas para encontrar todos los registros siguientes de forma secuencial, sin tener que volver a la raíz del árbol.

Ejemplos de Motores de Almacenamiento: El motor de almacenamiento InnoDB de MySQL y los índices de PostgreSQL utilizan variantes del árbol B+ para organizar los datos de las tablas.

# data[].attributes.attachment_caption
Ejemplo de como Facebook utiliza un sistema de grafos para la sugerencia de amigos en común

# data[].attributes.body
La importancia y versatilidad que tienen los grafos y árboles en la informática moderna, se ven reflejadas en las siguientes áreas:

1. Redes sociales: Análisis de conexiones y recomendaciones

Grafos: Representan usuarios como nodos y sus interacciones (amistades, mensajes) como aristas.

Permiten analizar comunidades, influenciadores (ej.: PageRank de Google) o propagación de información.

Algoritmos como BFS/DFS o Detección de Clústeres identifican grupos conexos.

Árboles: Usados en jerarquías (ej.: organigramas) o para modelar relaciones padre-hijo (ej.: comentarios en un post).

Ejemplo en concreto: Facebook sugiere amigos basado en caminos cortos en el grafo.

2. Algoritmos de ruteo: Optimización de rutas en sistemas GPS

Grafos: Calles son aristas e intersecciones nodos.

Algoritmos como Dijkstra (rutas más cortas) o A* (heurística) optimizan tiempo/distancia.

Árboles: Los árboles de expansión mínima (Prim/Kruskal) ayudan en diseño de redes eficientes (ej.: cableado urbano).

Ejemplo en concreto: Google Maps calcula la ruta más rápida usando grafos dinámicos con tráfico en tiempo real.

3. Análisis de datos: Estructuración y búsqueda eficiente

Árboles:

Árboles-B o Árboles Binarios Balanceados aceleran búsquedas en bases de datos (índices).

Tries almacenan palabras para búsqueda rápida (ej.: autocompletado).

Grafos: Modelan relaciones complejas en datos (ej.: grafos de conocimiento de Google).

Ejemplo en concreto: MongoDB usa árboles-B para indexar documentos.

4. Sistemas de recomendación (Amazon, Spotify)

Grafos: Conectan ítems (nodos) basado en preferencias (aristas).

Filtrado colaborativo: Usa grafos bipartitos (usuarios-productos) para sugerencias.

Árboles de decisión: Clasifican preferencias (ej.: "si te gusta X, quizás Y también te guste").

Ejemplo en concreto: Netflix recomienda películas analizando grafos de visualización.

5. Seguridad informática: Detección de fraudes y análisis de patrones

Grafos:

Identifican patrones anómalos (ej.: transacciones fraudulentas como subgrafos inusuales).

Modelan redes de ataques (ej.: nodos = IPs, aristas = intentos de intrusión).

Árboles: Árboles de decisión en machine learning detectan comportamientos sospechosos.

Ejemplo en concreto: Sistemas bancarios usan grafos para detectar "lavado de dinero" con caminos complejos.

Conclusión

Grafos y árboles son estructuras fundamentales por su capacidad para modelar relaciones (grafos) y organizar datos jerárquicamente (árboles). Su eficiencia en algoritmos (como búsquedas o optimizaciones) los hace indispensables en aplicaciones que van desde redes sociales hasta seguridad cibernética, de allí la gran importancia de su conocimiento para el perfil de un Ingeniero Informático.

# data[].attributes.body
Miguel Bethancourt / C.I:30.717.851

Saúl Ramírez / C.I: 30.671.390

Fabio Romero / C.I: 30.670.913

Daniel Pérez / C.I: 30.670.857

José Faria / C.I: 30.535.948