El origen de la teoría de grafos fue en los tiempos de Euler. Primero utilizó la teoría de grafos como un método para resolver el problema del puente de Koinsberg.
El problema se da siete puentes, es posible cruzar a través de todos los puentes de manera que se cruza a través de un puente solo una vez.
- Informática teórica: ¿cómo empiezo a resolver el problema P = NP?
- Algoritmos: ¿Cómo visualizo y resuelvo problemas de retroceso?
- ¿Por qué es más fácil verificar una respuesta que producirla?
- ¿Qué tipo de matemática se usa en la programación de computación paralela?
- Mi computadora portátil está enchufada pero no se carga. ¿Cómo soluciono este problema?
Resolvió el problema modelando cada ladmass como un vértice y un puente entre ellos como un borde. Señaló que al cruzar un puente, abandonas una masa terrestre y pasas a otra y, por lo tanto, si tienes que entrar y salir de una masa terrestre de manera que no repitas el puente, entonces el número de puentes que conectan esa masa continental debería ser uniforme.
En el problema anterior, cada vértice tenía un número impar de bordes, por lo tanto, era imposible caminar de tal manera que cada puente se tocara solo una vez.
Un camino que toca cada borde una vez se llama camino de Euler.
El requisito para que exista una ruta de Euler es que todos los vértices tienen bordes pares o si hay un vértice inicial y final, entonces todos menos esos dos vértices deben tener bordes pares.
Este fue el uso original de la teoría de grafos.
La teoría de gráficos también se ha utilizado para resolver el problema de las tres utilidades en negativo. El problema de las tres empresas de servicios públicos recibe una masa terrestre en 2D, donde hay tres casas y tres estaciones de servicios públicos, es posible conectarlas de manera que las tuberías no se crucen entre sí.
Si observa de manera abstracta una red neuronal profunda, incluso esa es una gráfica con neuronas como vértices y sus conexiones como bordes.
Encontrar amigos en una red social se modela como un problema teórico gráfico donde se hace una recomendación basada en el número de amigos comunes entre dos personas. Cada vértice representa a una persona y su amistad es una ventaja. El problema se reduce a encontrar dos vértices que tienen los vértices comunes máximos donde la longitud desde el vértice y el vértice común está por debajo de algún umbral (generalmente 1).
Un árbol B + que se usa comúnmente en bases de datos también está bajo la teoría de gráficos, ya que el árbol es un gráfico con solo una ruta entre dos vértices.
Espero que esto ayude. Por favor vota y comparte si lo hizo.
