¿Cuál es la diferencia entre un gráfico y un árbol en estructuras de datos y algoritmos?

Estrictamente hablando, un gráfico es una colección de aristas y vértices, donde el conjunto de vértices no puede estar vacío. En otras palabras, incluso si tenemos un solo vértice y no hay bordes, podemos llamarlo un gráfico.

Un árbol también es un gráfico ya que también tiene vértices y aristas. Por lo tanto, cada árbol es un gráfico. Ahora, naturalmente, surge la pregunta, ¿cuándo llamamos que una gráfica es un árbol? Esto es interesante.

Cualquier gráfico que satisfaga las siguientes propiedades de una vez, se clasifica como un árbol.

• [matemáticas] Sin dirección [/ matemáticas]
• [matemáticas] Conectado [/ matemáticas]
• [matemáticas] Acílico [/ matemáticas]

Además de las propiedades anteriores, observamos que estas propiedades también implican colectivamente (bi-implicación, de hecho) que hay exactamente un camino entre cualquier par de vértices en un árbol.

Un árbol también se define a veces como un ” Gráfico Acíclico Débilmente Conectado” , el término ” débilmente ” enfatiza que no está dirigido.

Todo lo que pueda dibujar en una hoja de papel, que tiene vértices y bordes, distribuidos de cualquier manera, siempre formará parte de un gráfico, pero para asegurarse de que sea un árbol, debe cumplir con las condiciones anteriores.

• Un gráfico con 4 vértices que es un árbol.

• Un gráfico con 4 vértices que NO es un árbol.

También tenga en cuenta que cualquier árbol con vértices [matemáticos] n [/ matemáticos] siempre tendrá bordes [matemáticos] n-1 [/ matemáticos].

Un árbol es una subclase de un gráfico. Un árbol pertenece a la familia de gráficos conocidos como Gráficos Acíclicos Dirigidos (DAG). En una estructura de datos de árbol, cada nodo tiene exactamente un padre y no hay ciclos de ningún tipo.

Tenga en cuenta que debido a que un árbol es esencialmente un gráfico, la mayoría de los algoritmos diseñados para gráficos deberían y funcionan para los árboles. Sin embargo, la estructura relativamente más simple de un árbol (dependiendo del problema con el que esté lidiando) le permite hacer ciertos ajustes en sus algoritmos gráficos para un mejor rendimiento en los árboles.

En palabras simples, el árbol no contiene ciclos y dónde puede hacerlo el gráfico. Entonces, cuando hacemos búsquedas, debemos evitar los ciclos en los gráficos para no entrar en bucles infinitos.

Otro aspecto es que el árbol generalmente tendrá algún tipo de clasificación topológica o una propiedad como el árbol de búsqueda binaria que hace que la búsqueda sea tan rápida y fácil en comparación con los gráficos.