El complemento de un gráfico no es una idea específica de DFS. Es una noción general que se usa comúnmente en teoría de grafos y algoritmos en general. Por lo tanto, se deduce que no hay una respuesta única a “¿cuál es el objetivo del complemento”? Dicho esto, aquí hay algunas maneras en que podría usar la idea:
- (Isomorfismo gráfico) Se dice que dos gráficos G1 y G2 son isomórficos si son “básicamente iguales, excepto que están etiquetados / dibujados de manera diferente” (ver isomorfismo gráfico – Wikipedia para la formulación técnica). G1 es isomorfo a G2 si y solo si sus complementos son isomorfos. Esto es fácil de ver en base a las definiciones de isomorfismo gráfico y ejemplos simples. Usando esta idea, si tenemos dos gráficos muy densos, podemos comparar sus complementos, que no serían muy densos, y esto sería más fácil que comparar los gráficos originales completos.
- (Negación de predicados que definen un gráfico) Sea G un gráfico donde tenemos (u, v) es un borde si y solo si u R v. El complemento de G es el gráfico que tiene (u, v) como un borde si y solo si tenemos (u, v) NO en R. Por lo tanto, los complementos de gráficos le dan las conexiones que son opuestas a las conexiones originales, para hablar libremente.
- (Relacionar camarillas y conjuntos independientes) Sea G un gráfico. Definimos una camarilla en G como un conjunto de nodos {v1, v2, …, vn} de modo que cada par de nodos en la camarilla sean vecinos. Definimos un conjunto independiente en G como un conjunto de nodos en el que no hay dos pares de nodos vecinos. Es fácil ver que una camarilla en G es un conjunto independiente en complemento (G).
- (Relacionar un gráfico con gráficos completos) Una forma de pensar en un gráfico G en n nodos es el gráfico completo K_n con todos los bordes (u, v) no en E (G) eliminados. Como el complemento (G) es solo los mismos nodos con aristas (u, v) siempre que (u, v) no esté en E (G), entonces G = K_n \ complemento (G). De manera equivalente, la Suma Gráfica – de Wolfram MathWorld de un gráfico y su complemento es el gráfico completo con el mismo número de nodos.
Estos son solo algunos ejemplos que surgieron de mi cabeza y de una rápida búsqueda en Wikipedia y Wolfram. Realmente, cada vez que necesite hablar sobre los bordes que faltan en G, puede usar esta definición y puede estar seguro de que cualquiera que sepa algo sobre la teoría de grafos básicos comprenderá su terminología.
- ¿Es posible hacer un programa algorítmico de intercambio oscilante?
- Cómo comprar un algoritmo de creación de mercado para acciones
- ¿Cuáles son las diferencias entre Algorithmia y Amazon Lambda?
- ¿Habrá diferentes algoritmos para implementar la inserción y eliminación de una estructura de datos como b árboles?
- ¿Cuáles son algunos proyectos desafiantes en algoritmo genético para principiantes?
