Matemáticas discretas: más sobre gráficos

Gráfico para colorear

La coloración de gráficos es el procedimiento de asignación de colores a cada vértice de un gráfico G de manera que ningún vértice adyacente obtenga el mismo color. El objetivo es minimizar el número de colores al colorear un gráfico. La menor cantidad de colores necesarios para colorear un gráfico G se denomina número cromático de ese gráfico. El problema de coloración de gráficos es un problema NP completo.

Método para colorear un gráfico

Los pasos necesarios para colorear un gráfico G con n número de vértices son los siguientes:

Step 1 - Organizar los vértices del gráfico en algún orden.

Step 2 - Elige el primer vértice y coloréalo con el primer color.

Step 3- Elija el siguiente vértice y coloréelo con el color con el número más bajo que no haya sido coloreado en ningún vértice adyacente a él. Si todos los vértices adyacentes están coloreados con este color, asígnele un nuevo color. Repite este paso hasta que todos los vértices estén coloreados.

Example

En la figura anterior, en el primer vértice $ a $ está coloreado de rojo. Como los vértices adyacentes del vértice a son nuevamente adyacentes, el vértice $ b $ y el vértice $ d $ están coloreados con un color diferente, verde y azul respectivamente. Entonces el vértice $ c $ se colorea de rojo, ya que ningún vértice adyacente de $ c $ se colorea de rojo. Por lo tanto, podríamos colorear el gráfico con 3 colores. Por tanto, el número cromático del gráfico es 3.

Aplicaciones de la coloración de gráficos

Algunas aplicaciones de la coloración de gráficos incluyen:

Gráfico transversal

El recorrido de gráfico es el problema de visitar todos los vértices de un gráfico en algún orden sistemático. Hay principalmente dos formas de recorrer un gráfico.

  • Amplitud primera búsqueda
  • Primera búsqueda en profundidad

Amplitud primera búsqueda

Breadth First Search (BFS) comienza en el vértice del nivel 0 inicial $ X $ del gráfico $ G $. Luego visitamos todos los vértices que son vecinos de $ X $. Después de visitar, marcamos los vértices como "visitados" y los colocamos en el nivel 1. Luego partimos de los vértices del nivel 1 y aplicamos el mismo método en cada vértice del nivel 1 y así sucesivamente. El recorrido BFS termina cuando se han visitado todos los vértices del gráfico.

BFS Algorithm

El concepto es visitar todos los vértices vecinos antes de visitar otros vértices vecinos de vértices vecinos.

  • Inicialice el estado de todos los nodos como "Listo".

  • Coloque el vértice de origen en una cola y cambie su estado a "En espera".

  • Repita los dos pasos siguientes hasta que la cola esté vacía:

    • Elimina el primer vértice de la cola y márcalo como "Visitado".

    • Agregue al final de la cola todos los vecinos del vértice eliminado cuyo estado sea "Listo". Marque su estado como "En espera".

Problem

Tomemos un gráfico (el vértice de origen es 'a') y apliquemos el algoritmo BFS para averiguar el orden transversal.

Solution -

  • Inicialice el estado de todos los vértices a "Listo".

  • Ponga una en cola y cambie su estado a "En espera".

  • Quite un de la cola, márquelo como "Visitado".

  • Añadir una ‘s vecinos en‘Listo’estado B, D y E al final de la cola y marcarlos como‘en espera’.

  • Quite b de la cola, márquelo como "Visitado", coloque su vecino "Listo" c al final de la cola y marque c como "Esperando".

  • Quite d de la cola y márquelo como "Visitado". No tiene vecino en estado "Listo".

  • Quite e de la cola y márquelo como "Visitado". No tiene vecino en estado "Listo".

  • Quite c de la cola y márquelo como "Visitado". No tiene vecino en estado "Listo".

  • La cola está vacía, así que deténgase.

Entonces el orden transversal es -

$ a \ rightarrow b \ rightarrow d \ rightarrow e \ rightarrow c $

Los órdenes alternativos de recorrido son:

$ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $

O $ a \ rightarrow d \ rightarrow b \ rightarrow e \ rightarrow c $

O $ a \ rightarrow e \ rightarrow b \ rightarrow d \ rightarrow c $

O $ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $

O $ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $

Application of BFS

  • Encontrar el camino más corto
  • Árbol de expansión mínimo para gráfico no ponderado
  • Sistema de navegación GPS
  • Detectar ciclos en un gráfico no dirigido
  • Encontrar todos los nodos dentro de un componente conectado

Complexity Analysis

Sea $ G (V, E) $ una gráfica con $ | V | $ número de vértices y $ | E | $ número de aristas. Si el algoritmo de búsqueda de amplitud primero visita todos los vértices del gráfico y verifica cada borde, entonces su complejidad de tiempo sería:

$$ O (| V | + | E |). O (| E |) $$

Puede variar entre $ O (1) $ y $ O (| V2 |) $

Primera búsqueda en profundidad

El algoritmo de Depth First Search (DFS) comienza desde un vértice $ v $, luego atraviesa su vértice adyacente (digamos x) que no ha sido visitado antes y marca como "visitado" y continúa con el vértice adyacente de $ x $ y pronto.

Si en algún vértice, encuentra que se visitan todos los vértices adyacentes, entonces retrocede hasta encontrar el primer vértice que tiene un vértice adyacente que no ha sido atravesado antes. Luego, atraviesa ese vértice, continúa con sus vértices adyacentes hasta que atraviesa todos los vértices visitados y tiene que retroceder nuevamente. De esta forma, atravesará todos los vértices alcanzables desde el vértice inicial $ v $.

DFS Algorithm

El concepto es visitar todos los vértices vecinos de un vértice vecino antes de visitar los otros vértices vecinos.

  • Inicializar el estado de todos los nodos como "Listo"

  • Coloque el vértice de origen en una pila y cambie su estado a "En espera"

  • Repita los dos pasos siguientes hasta que la pila esté vacía:

    • Saque el vértice superior de la pila y márquelo como "Visitado"

    • Coloque en la parte superior de la pila todos los vecinos del vértice eliminado cuyo estado sea "Listo". Marque su estado como "En espera".

Problem

Tomemos un gráfico (el vértice de origen es 'a') y apliquemos el algoritmo DFS para averiguar el orden transversal.

Solution

  • Inicialice el estado de todos los vértices a "Listo".

  • Introduzca una pila y cambie su estado a "En espera".

  • Haga estallar una y márquela como "Visitada".

  • Empuje a los vecinos de a en el estado "Listo" e, d y b hacia la parte superior de la pila y márquelos como "Esperando".

  • Saque b de la pila, márquelo como "Visitado", empuje su vecino "Listo" c sobre la pila.

  • Saque c de la pila y márquelo como "Visitado". No tiene vecino "Listo".

  • Saque d de la pila y márquelo como "Visitado". No tiene vecino "Listo".

  • Pop electrónico de pila y marcarlo como “Visitado”. No tiene vecino "Listo".

  • La pila está vacía. Así que deja de.

Entonces el orden transversal es -

$ a \ rightarrow b \ rightarrow c \ rightarrow d \ rightarrow e $

Los órdenes alternativos de recorrido son:

$ a \ rightarrow e \ rightarrow b \ rightarrow c \ rightarrow d $

O $ a \ rightarrow b \ rightarrow e \ rightarrow c \ rightarrow d $

O $ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $

O $ a \ rightarrow d \ rightarrow c \ rightarrow e \ rightarrow b $

O $ a \ rightarrow d \ rightarrow c \ rightarrow b \ rightarrow e $

Complexity Analysis

Sea $ G (V, E) $ una gráfica con $ | V | $ número de vértices y $ | E | $ número de aristas. Si el algoritmo DFS visita cada vértice del gráfico y verifica cada borde, entonces la complejidad del tiempo es:

$$ \ circleddash (| V | + | E |) $$

Applications

  • Detectando ciclo en un gráfico
  • Para encontrar la clasificación topológica
  • Para probar si una gráfica es bipartita
  • Encontrar componentes conectados
  • Encontrar los puentes de un gráfico
  • Encontrar la bi-conectividad en gráficos
  • Resolviendo el problema del Tour de los Caballeros
  • Resolver acertijos con una sola solución