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

Gráficos para colorear

La coloración de gráficos es un procedimiento para asignar un color a cada vértice del gráfico G para que ningún vértice vecino tenga el mismo color. El objetivo es minimizar la cantidad de colores al colorear el gráfico. La menor cantidad de colores necesarios para colorear un gráfico G se denomina número cromático de este gráfico. El problema de colorear gráficas es el problema NP completo.

Método de coloración gráfica

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

Paso 1 – Organizar los vértices del gráfico en un orden específico.

Paso 2 – Selecciona el primer vértice y píntalo con el primer color.

Paso 3 – Seleccione el siguiente vértice y coloréelo con el color numerado más bajo que no haya sido coloreado en ninguno de sus vértices adyacentes. 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.

Ejemplo

Gráficos para colorear

En la imagen de arriba, el $ a $ superior se colorea primero en rojo. Dado que los vértices adyacentes del vértice a son adyacentes nuevamente, el vértice $ b $ y el vértice $ d $ están coloreados en diferentes colores, verde y azul, respectivamente. Entonces el vértice $ c $ es de color rojo, ya que ningún vértice adyacente $ c $ es de color rojo. Por lo tanto, podemos colorear el gráfico en 3 colores. Por tanto, el número cromático del gráfico es 3.

Aplicar coloración gráfica

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

Recorrido del gráfico

El recorrido del gráfico es el problema de visitar todos los vértices del gráfico en algún orden sistemático. Básicamente, hay dos formas de recorrer el gráfico.

  • Primera búsqueda de amplitud
  • Búsqueda de profundidad

Primera búsqueda de amplitud

Breadth First Search (BFS) comienza en el vértice inicial del nivel 0 $ 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 comenzamos en los vértices del nivel 1 y aplicamos el mismo método a cada vértice del nivel 1, y así sucesivamente. El recorrido BFS se completa después de visitar cada vértice del gráfico.

Algoritmo BFS

La idea es visitar todos los picos vecinos antes de visitar otros picos vecinos de los picos vecinos.

  • Inicialice el estado de todos los nodos como «Listo».

  • Coloque el vértice original en la cola y cambie su estado a Pendiente.

  • 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 de todos los vecinos del vértice remoto con el estado «Listo». Marque su estado como Pendiente.

Problema

Tomemos un gráfico (el vértice original es ‘a’) y apliquemos el algoritmo BFS para averiguar el orden transversal.

Amplitud primera parcela de búsqueda

Decisión

  • Inicialice el estado de todos los vértices como «Listo».

  • Poner y en la cola y cambie su estado a Pendiente.

  • Borrar y de la cola marca como «Visitado».

  • Agregar yvecinos en estado «Listo» b, d y mi al final de la cola y márquelos como «Pendientes».

  • Borrar B de la cola, márquelo como «Visitado», ponga su vecino «Listo» C al final de la línea y comprobar C como «Esperando».

  • Borrar D de la cola y márquelo como visitado. No tiene un vecino en el estado Listo.

  • Borrar mi de la cola y márquelo como «Visitado». No tiene un vecino en el estado Listo.

  • Borrar C de la cola y márquelo como visitado. No tiene un vecino en el estado Listo.

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

Entonces el orden transversal es

$ a rightarrow b rightarrow d rightarrow e rightarrow c $

Órdenes de recorrido alternativas:

$ 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 $

Aplicación BFS

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

Análisis de complejidad

Sea $ G (V, E) $ una gráfica con el número de vértices $ | V | $ y el número de aristas $ | E | PS Si el algoritmo Breadth First Search visita cada vértice del gráfico y verifica cada borde, entonces su complejidad de tiempo será:

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

Puede oscilar entre $ O (1) $ y $ O (| V2 |) $.

Búsqueda de profundidad

La búsqueda de profundidad primero (DFS) comienza en $ v $, luego va a un vértice vecino (digamos x) que no se ha visitado antes y está marcado como «visitado», y continúa con $ x $ adyacentes y pronto.

Si en cualquier vértice encuentra que se han visitado todos los vértices vecinos, regresa hasta que encuentra el primer vértice que tiene un vértice adyacente que no se ha atravesado anteriormente. Luego pasa este pico, sigue avanzando por los picos vecinos, hasta pasar todos los picos visitados, y tendrá que volver de nuevo. Así, pasará por todos los vértices alcanzables desde el vértice inicial $ v $.

Algoritmo DFS

La idea es visitar todos los picos vecinos de un pico vecino antes de visitar otros picos vecinos.

  • Inicialice el estado de todos los nodos como «Listo»

  • Coloque el vértice original en la pila y cambie su estado a Pendiente.

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

    • Extraiga 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 con el estado «Listo». Marque su estado como Pendiente.

Problema

Tomemos un gráfico (el vértice original es ‘a’) y apliquemos el algoritmo DFS para averiguar el orden transversal.

Gráfico de búsqueda en profundidad

Decisión

  • Inicialice el estado de todos los vértices como «Listo».

  • Empujar y en la pila y cambie su estado a Pendiente.

  • Música pop y y márquelo como visitado.

  • Empujar yvecinos en el estado «Listo» d, d y B a la parte superior de la pila y márquelos como Pendientes.

  • Música pop B de la pila, márquelo como «Visitado», presione su vecino «Listo» C en la pila.

  • Música pop C de la pila y márquelo como visitado. No tiene un vecino «confeccionado».

  • Música pop D de la pila y márquelo como visitado. No tiene un vecino «confeccionado».

  • Música pop mi de la pila y márquelo como visitado. No tiene un vecino «confeccionado».

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

Entonces el orden transversal es

$ a rightarrow b rightarrow c rightarrow d rightarrow e $

Órdenes de recorrido alternativas:

$ 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 $

Análisis de complejidad

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

$$ circledash (| V | + | E |) $$

Aplicaciones

  • Detectar un ciclo en un gráfico
  • Buscar clasificación topológica
  • Para comprobar si un gráfico es bipartito
  • Encuentra componentes relacionados
  • Encontrar puentes de gráficos
  • Detectar conexiones dobles en gráficos
  • Resolviendo el problema del Tour del Caballero
  • Resolver acertijos con una solución

🚫