Teoría de grafos es un tema súper bonito en matemáticas que vale mucho la pena estudiar ya que provee una nueva manera de modelar matemáticamente problemas del día a día. Dicho lo anterior, dejo la definición formal de un árbol y un grafo esperando que le despierte la curiosidad a algún estudiante de éste curso:
-
Formalmente un grafo G (gráfica o graph) consiste en un conjunto finito no vacío V de objetos llamados vértices (nodos) y un conjunto E, posiblemente vacío, de subconjuntos de pares de V llamado aristas. Por lo tanto un grafo G es un par ordenado de conjuntos V y E que representan a sus vértices y aristas respectivamente y usualmente se escribe como G=(V,E). En algunos casos se incluyen funciones disjuntas que agregan más información sobre las aristas, como menciona Ricardo, como pesos, propiedades o dirección.
-
Se dice que una gráfica G es un árbol si es acíclica y conexa. Esto implica propiedades como que toda arista de un árbol es un puente o que dan origen a teoremas como “Para todo par de vértices u, v en V(T), donde T es un árbol, existe un uv-camino en T que es único” y “En todo árbol T, si n es el número de vértices (órden), entonces existen n-1 aristas (tamaño) en T”
Links:
- https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)
- https://en.wikipedia.org/wiki/Connectivity_(graph_theory)
- https://en.wikipedia.org/wiki/Cycle_(graph_theory)
Saludos!
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?