¿Cuáles son ejemplos de problemas difíciles que existen en la vida que se pueden resolver fácilmente con la teoría de grafos?

No sucede en la vida real, pero es un juego llamado Instant Insanity. Estoy seguro de que puedes googlear eso. Este juego involucra cuatro cubos con caras coloreadas en uno de los cuatro colores que deseas. Luego, organícelos en una fila o apílelos de manera que las cuatro superficies en una fila estén coloreadas en cuatro colores diferentes.

Otra aplicación es encontrar el camino más corto. Esto se puede hacer usando el algoritmo de Dijkstra si los bordes están ponderados. Por ejemplo, para la logística, quieren ir de A a H en el camino más corto, pero hay algunos intermedios como B, C, etc. Suponga que va de A a B en 40 minutos y puede calcular el tiempo necesario para cada ruta inmediata. Luego usa ese algoritmo para ayudarte a resolver el camino más rápido.

Esto puede suceder en química, pero no del todo útil porque restringe a cada átomo a obedecer la regla del octeto. El algoritmo Havel Hakimi puede ayudarlo a determinar la estructura de la sustancia dada la fórmula. Esto se puede hacer anotando cuántos enlaces tiene que formar cada átomo, y organícelos en orden no descendente, obteniendo una secuencia de grados, usando ese algoritmo le ayudará a resolver la forma en que estos átomos pueden unirse.

O simplemente demuestre que en Facebook, debe existir dos cuentas que tengan el mismo número de amigos. Eso se puede explicar usando grados.

Flujo máximo / corte mínimo. Es un problema de optimización encontrar el flujo máximo en una red de flujo con una fuente y un sumidero solamente. Las soluciones del problema se utilizan en sistemas de energía eléctrica, redes de comunicación y logística.


En realidad, el problema surgió durante la Guerra Fría, cuando los estadounidenses exploraban el sistema ferroviario soviético. Su interés se centraba en las capacidades netas ferroviarias de la Unión Soviética occidental, por lo que se trataba más del problema de corte mínimo.

Aquí hay un diagrama de la red ferroviaria de la Unión Soviética Occidental y los países de Europa del Este, con un flujo máximo de valor de 163,000 toneladas desde Rusia a Europa del Este, y un corte de capacidad de 163,000 toneladas indicado como “El cuello de botella”.

Ref .: TEHarris, FS Ross, “Fundamentos de un método para evaluar las capacidades de la red ferroviaria”, 1955.

El camino más corto entre dos personas con bordes dados por la amistad

Un ejemplo simple de esto es cuando conoces a alguien y le hablas largamente, sin esperar tener amigos en común, solo para luego agregarlo en Facebook y descubrir que sí.

Esto me ha pasado en varias ocasiones. Puedes pensar en los 6 grados de Kevin Bacon y en lo mucho más trivial que resulta con cosas como Facebook, almacenar tu red social como un gráfico.

El camino más corto es un buen ejemplo. Supongamos que desea encontrar el camino más corto (a lo largo de las carreteras) de una ubicación a otra. Sus nodos son todos los edificios e intersecciones, y los bordes son las carreteras.