Algoritmo gráfico

Un gráfico es una notación abstracta que se utiliza para representar la conexión entre pares de objetos. Un gráfico consta de:

Vertices- Los objetos interconectados en un gráfico se denominan vértices. Los vértices también se conocen comonodes.
Edges - Los bordes son los enlaces que conectan los vértices.

Hay dos tipos de gráficos:

Directed graph - En un gráfico dirigido, las aristas tienen dirección, es decir, las aristas van de un vértice a otro.
Undirected graph - En un gráfico no dirigido, los bordes no tienen dirección.

Gráfico para colorear

La coloración de gráficos es un método para asignar colores a los vértices de un gráfico de modo que no haya dos vértices adyacentes del mismo color. Algunos problemas de coloración de gráficos son:

Vertex coloring - Una forma de colorear los vértices de un gráfico para que no haya dos vértices adyacentes que compartan el mismo color.
Edge Coloring - Es el método de asignar un color a cada borde para que no haya dos bordes adyacentes del mismo color.
Face coloring - Asigna un color a cada cara o región de un gráfico plano para que dos caras que comparten un límite común no tengan el mismo color.

Número cromático

El número cromático es el número mínimo de colores necesarios para colorear un gráfico. Por ejemplo, el número cromático del siguiente gráfico es 3.

El concepto de coloración de gráficos se aplica en la preparación de horarios, asignación de radiofrecuencia móvil, Suduku, asignación de registros y coloración de mapas.

Pasos para colorear gráficos

Establezca el valor inicial de cada procesador en la matriz n-dimensional en 1.
Ahora, para asignar un color particular a un vértice, determine si ese color ya está asignado a los vértices adyacentes o no.
Si un procesador detecta el mismo color en los vértices adyacentes, establece su valor en la matriz en 0.
Después de hacer n ² comparaciones, si cualquier elemento de la matriz es 1, entonces es un color válido.

Pseudocódigo para colorear gráficos

begin

   create the processors P(i₀,i₁,...i_n-1) where 0_i_v < m, 0 _ v < n
   status[i0,..i_n-1] = 1
	
   for j varies from 0 to n-1 do
      begin
		
         for k varies from 0 to n-1 do
         begin
            if a_j,k=1 and i_j=i_kthen
            status[i₀,..i_n-1] =0
         end
			
      end
      ok = ΣStatus
		
   if ok > 0, then display valid coloring exists
   else
      display invalid coloring
      
end

Árbol de expansión mínimo

Un árbol de expansión cuya suma de peso (o longitud) de todos sus bordes es menor que todos los demás árboles de expansión posibles del gráfico G se conoce como minimal spanning tree o minimum cost spanningárbol. La siguiente figura muestra un gráfico conectado ponderado.

A continuación se muestran algunos árboles de expansión posibles del gráfico anterior:

Entre todos los árboles de expansión anteriores, la figura (d) es el árbol de expansión mínimo. El concepto de árbol de expansión de costo mínimo se aplica en el problema del viajante de comercio, el diseño de circuitos electrónicos, el diseño de redes eficientes y el diseño de algoritmos de enrutamiento eficientes.

Para implementar el árbol de costo mínimo, se utilizan los siguientes dos métodos:

Algoritmo de Prim
Algoritmo de Kruskal

Algoritmo de Prim

El algoritmo de Prim es un algoritmo codicioso, que nos ayuda a encontrar el árbol de expansión mínimo para un gráfico no dirigido ponderado. Primero selecciona un vértice y encuentra una arista con el peso más bajo que incide en ese vértice.

Pasos del algoritmo de Prim

Seleccione cualquier vértice, digamos v ₁ del Gráfico G.
Seleccione un borde, digamos e ₁ de G tal que e ₁ = v ₁ v ₂ y v ₁ ≠ v ₂ ye ₁ tenga un peso mínimo entre los bordes incidentes en v ₁ en el gráfico G.
Ahora, siguiendo el paso 2, seleccione el incidente de borde ponderado mínimo en v ₂ .
Continúe con esto hasta que se hayan elegido n – 1 bordes. aquín es el número de vértices.

El árbol de expansión mínimo es:

Algoritmo de Kruskal

El algoritmo de Kruskal es un algoritmo codicioso, que nos ayuda a encontrar el árbol de expansión mínimo para un gráfico ponderado conectado, agregando arcos de costos crecientes en cada paso. Es un algoritmo de árbol de expansión mínima que encuentra un borde del menor peso posible que conecta dos árboles cualesquiera en el bosque.

Pasos del algoritmo de Kruskal

Seleccione un borde de peso mínimo; digamos que e ₁ del Gráfico G ye ₁ no es un bucle.
Seleccione el siguiente borde ponderado mínimo conectado a e ₁ .
Continúe con esto hasta que se hayan elegido n – 1 bordes. aquín es el número de vértices.

El árbol de expansión mínimo del gráfico anterior es:

Algoritmo de ruta más corta

El algoritmo de ruta más corta es un método para encontrar la ruta de menor costo desde el nodo de origen (S) al nodo de destino (D). Aquí, discutiremos el algoritmo de Moore, también conocido como Algoritmo de búsqueda primero en amplitud.

Algoritmo de Moore

Etiquetar el vértice de origen, S y etiquetarlo i y establecer i=0.
Encuentra todos los vértices sin etiquetar adyacentes al vértice etiquetado i. Si no hay vértices conectados al vértice, S, entonces el vértice, D, no está conectado a S. Si hay vértices conectados a S, etiquételosi+1.
Si D está etiquetado, vaya al paso 4, de lo contrario, vaya al paso 2 para aumentar i = i + 1.
Deténgase después de encontrar la longitud del camino más corto.

↰ Previous page