¿Qué es Teoría de Grafos?
La Teoría de Grafos es una rama de las matemáticas discretas que estudia las relaciones entre objetos. Imagina un conjunto de puntos (llamados *vértices* o *nodos*) y líneas que conectan algunos de estos puntos (llamadas *aristas* o *lados*). Un grafo es simplemente esta colección de vértices y aristas. La teoría de grafos se utiliza para modelar una gran variedad de situaciones del mundo real. Por ejemplo, podemos representar una red social donde los vértices son las personas y las aristas representan las relaciones de amistad. También podemos modelar una red de carreteras donde los vértices son las ciudades y las aristas representan las carreteras que las conectan. Los grafos pueden ser *dirigidos* (las aristas tienen una dirección, como una calle de un solo sentido) o *no dirigidos* (las aristas no tienen dirección). Se estudian propiedades como la conectividad (si todos los vértices están conectados entre sí), la existencia de caminos entre vértices, y la presencia de ciclos (caminos que empiezan y terminan en el mismo vértice). La teoría de grafos es fundamental en informática, ingeniería, y ciencias sociales.
Fórmula Matemática
Ejemplo Resuelto
Considera un grafo con 4 vértices (A, B, C, D) y las siguientes aristas: AB, BC, CD, DA. Este grafo representa un cuadrado. Si queremos encontrar el camino más corto de A a C, podemos ver que hay dos caminos: A-B-C o A-D-C. Si todas las aristas tienen la misma longitud, ambos caminos son iguales. Si la arista AB tiene un peso de 1, BC tiene un peso de 2, CD tiene un peso de 1 y DA tiene un peso de 2, el camino A-B-C tendría una longitud de 1+2=3 y el camino A-D-C tendría una longitud de 2+1=3. En este caso, ambos caminos tienen la misma longitud. Otro ejemplo, un grafo puede representar una red de vuelos. Los vértices son las ciudades y las aristas representan los vuelos entre ellas. El peso de cada arista puede ser el tiempo de vuelo o el costo del vuelo. Entonces, podemos usar algoritmos de grafos para encontrar el vuelo más barato o el más rápido entre dos ciudades.