¿Cuáles son algunos de los grandes proyectos implementados utilizando los conceptos de la teoría de gráficos?

Uno de los mayores problemas en los compiladores se ha resuelto utilizando el problema de coloración de gráficos.

El problema de cómo asignar registros a las variables se ha resuelto utilizando el concepto de coloración gráfica.

Mientras escriben programas, los programadores no piensan en la asignación de variables y solo usan las variables en el programa según sus requisitos. Ahora el compilador tiene la responsabilidad de almacenar estas grandes cantidades de variables en un número limitado de registros. Esto es necesario porque las operaciones de registro son más rápidas que las operaciones de memoria. Por lo tanto, le interesa la eficiencia del programa para almacenar la mayor cantidad de variables posible en los registros.

Ahora, al asignar variables a la memoria, pocas variables pueden ocupar el mismo registro, mientras que otras no, y deben almacenarse en los diferentes registros. Entonces, básicamente, todas las variables que se utilizarán al mismo tiempo no se pueden almacenar en el mismo registro, ya que el valor de una variable anulará el valor de otra variable. Además, si hay una instrucción de movimiento, las variables de origen y destino pueden almacenarse en el mismo registro. Por ej. para b = a + 1, tanto a como b pueden almacenarse en el mismo registro.

También hay algunas variables que siempre deben estar en algún registro particular, como los contadores de programas, lo que reduce aún más el número de registros disponibles.

Entonces, para el proceso de asignación de registros, el compilador considera cada variable como un vértice del gráfico. Y si no se pueden asignar dos variables al mismo registro, se conectan utilizando el borde de interferencia. Del mismo modo, el borde de preferencia conecta variables a las que se les puede asignar el mismo registro. Por lo tanto, la asignación de registros se ha convertido en un problema de coloración K con pocos vértices que tienen un color fijo (asignaciones de registro fijas). Es decir, colorear el número máximo de vértices en el gráfico de modo que no haya dos extremos de los bordes de interferencia del mismo color.

Aquí hay algunas aplicaciones que vienen a la mente.

• La Búsqueda de Google utiliza pagerank como una señal de calidad importante.
• La fuente de noticias de Facebook usa algo similar llamado edgerank para clasificar la información de tus amigos.
• Facebook lanzó recientemente Facebook Graph Search .
• La segmentación de cadenas es un problema de procesamiento del lenguaje natural que ocurre en idiomas como el chino. Con frecuencia se aborda como un problema de ruta más corta.
• Google Navigation y Google Directions, además de Google Maps, utilizan algunos algoritmos de ruta más corta de gráfico plano muy eficientes.
• Los juegos de estrategia en tiempo real como Starcraft utilizan algoritmos rápidos de búsqueda de rutas como A star para enrutar unidades en el mapa.
• Los compiladores usan recorridos de gráficos para encontrar dependencias de código.
• Los algoritmos de coloración de gráficos se utilizan al optimizar el código para usos paralelos de los registros de la CPU.
• Los problemas de diseño del diseño de la CPU se modelan como problemas gráficos.
• Como menciona Erik, las estrategias de recolección de basura en la memoria pueden usar recorridos de gráficos.
• La asignación de inventario en la publicidad web se puede escribir como un problema de flujo de red.
• Se utilizan algoritmos de correspondencia estables para unir a los residentes con los hospitales y los riñones con los donantes. (el emparejamiento estable ganó el premio nobel en economía en 2012)
• Las rutas de Amictonean y las rutas de Euler ocurren en el problema de Secuenciación Genética .
• Los problemas de replicación de datos con frecuencia usan algoritmos de árbol de expansión mínimos para mantener bajo el uso del ancho de banda.
• La mayoría de las canalizaciones de procesamiento de datos grandes implican una serie de pasos interdependientes que se pueden modelar como un gráfico acíclico dirigido.
• Algunos problemas de segmentación de imagen se pueden modelar para que sean equivalentes a encontrar el corte mínimo en un gráfico.

Simplemente agregue algunas aplicaciones más a la lista de Cosmin Negruseri:

1. El gráfico plano se usa para determinar si un circuito se puede implementar en una placa de circuito plano o no (como en una placa madre de CPU, no hay dos líneas de conexión que se crucen entre sí).

2. La coloración de gráficos se utiliza para mapear las regiones en color, de modo que no se necesita un mínimo de colores sin que haya dos regiones adyacentes que tengan el mismo color.

3. La coloración de gráficos se usa para asignaciones de frecuencia para
Radio / Televisión / Redes telefónicas.

4. Muchos sistemas operativos / sistemas de bases de datos utilizan gráficos de asignación de recursos y de espera para la detección de puntos muertos y evitarlos.

5. Muchos sistemas de procesamiento de transacciones utilizan gráficos de precedencia para determinar la serialización de las transacciones (de modo que puedan programarse para ejecutarse de forma simultánea o en serie).

6. Los gráficos se utilizan en ecología para modelar la interacción de diferentes especies de animales para representar la superposición de nichos.

7. El isomorfismo en los gráficos se usa en química para modelar la estructura de los compuestos. Una aplicación es determinar los isómeros (diferentes compuestos que tienen la misma fórmula molecular pero diferente estructura).

8. El circuito euleriano se puede usar para resolver acertijos que solicitan que se dibuje una imagen en particular en un movimiento continuo sin levantar un lápiz para que ninguna parte de la imagen se vuelva a trazar.

9. Por último, pero no menos importante, los gráficos se pueden usar para modelar y resolver el problema de los esposos celosos :-).

Los dispositivos de audio USB pueden ser bastante complejos. El resultado son algunas estructuras estándar para facilitar su configuración y uso. Pero las estructuras estándar no son necesarias. La información de configuración electrónica disponible se puede utilizar para construir un gráfico dirigido, posiblemente cíclico, que represente las rutas de audio a través del dispositivo. Para reproducir audio a través de la salida del altavoz, el software encuentra una ruta acíclica desde la fuente de datos del lado de la computadora hasta el conector del altavoz. Luego configura todos los mezcladores, interruptores, silenciadores y controles de volumen en “encendido” para esa ruta y todo lo que no está en la ruta en “apagado”. Luego reproduce audio a través de él.

La programación de las tareas involucradas en un proyecto se realiza utilizando el método de ruta crítica (CPM) . Las tareas se representan como arcos en un gráfico dirigido y acíclico (DAG) con un peso de arco igual a la duración de la tarea, con nodos que representan puntos de coordinación donde algunas tareas deben completarse antes de que comiencen otras. CPM encuentra una ruta más larga en el DAG resultante, que es una ruta crítica a lo largo de la cual no se pueden acomodar retrasos sin retrasar la finalización del proyecto. Los arcos a lo largo de otras rutas tienen cierta holgura, y se puede calcular la cantidad de retraso que puede acomodarse en cada arco.

Microsoft Project y programas similares utilizan este método para calcular cronogramas críticos del proyecto.

¿Qué tal el descubrimiento de drogas? En http://www.etherapeutics.co.uk adoptamos el enfoque de modelar enfermedades en términos de una red, o gráfico, de proteínas que interactúan. Las técnicas de ciencia de redes, o teoría de grafos, se utilizan para analizar estos modelos en busca de puntos de intervención adecuados.

La Internet.
Se ejecuta en protocolos de enrutamiento IP, principalmente BGP.
Es un gráfico de gráficos.

Podemos crear grandes proyectos como la estrategia de supervivencia. Imagina tener una manzana. Es una manzana Granny Smith. Las manzanas son buenas metáforas, después de todo. Se ven normales en el exterior pero son oscuros y misteriosos y fatales en el interior. Si nos ponemos un sombrero de pingüino poseído por el alma de un niño pequeño, podemos usar la teoría de gráficos para realizar un seguimiento de cómo una manzana se divide en dos, y luego en tres, y luego se hace malabares con algo más que un pastel de carne mal cocinado. una mesa llena de plebeyos semi hambrientos.

“Compartamos el fruto del destino” -Oginome Momoka

Utilizo la teoría de grafos cuando encuentro una asignación estable de ciclos comerciales entre grupos de jugadores en un problema del mercado inmobiliario. El gráfico es un conjunto de vértices = jugadores y aristas dirigidas = preferencias sobre otros jugadores, y el objetivo completo es encontrar conjuntos de ciclos disjuntos en un gráfico muy complicado. Las aplicaciones del problema del mercado inmobiliario son extensas.

La teoría de grafos se utiliza para descubrir la conectividad cerebral en fMRI (resonancia magnética funcional).

Perspectiva de red del cerebro:

• Programación de aeronaves
• Programación de horarios
• Coloración de mapas y redes de telefonía móvil GSM
• Seguridad de la red informática
• Reconocimiento de símbolos
• Segmentación de imagen
• Búsqueda basada en gráficos
• Programación de tareas multiprocesador
• Reconocimiento de objetos
• La coincidencia de patrones

Google Maps y Búsqueda de Google