Algorithme graphique

Un graphe est une notation abstraite utilisée pour représenter la connexion entre des paires d'objets. Un graphique se compose de -

• Vertices- Les objets interconnectés dans un graphe sont appelés sommets. Les sommets sont également appelésnodes.

• Edges - Les arêtes sont les liens qui relient les sommets.

Il existe deux types de graphiques -

• Directed graph - Dans un graphe orienté, les arêtes ont une direction, c'est-à-dire que les arêtes vont d'un sommet à l'autre.

• Undirected graph - Dans un graphe non orienté, les arêtes n'ont pas de direction.

Coloration graphique

La coloration de graphe est une méthode permettant d'attribuer des couleurs aux sommets d'un graphe afin qu'aucun sommet adjacent n'ait la même couleur. Certains problèmes de coloration des graphiques sont -

• Vertex coloring - Une manière de colorer les sommets d'un graphe de façon à ce qu'aucun sommet adjacent ne partage la même couleur.

• Edge Coloring - C'est la méthode d'attribution d'une couleur à chaque bord de sorte qu'aucun bord adjacent n'ait la même couleur.

• Face coloring - Il attribue une couleur à chaque face ou région d'un graphe plan afin qu'aucune face qui partage une frontière commune n'ait la même couleur.

Numéro chromatique

Le nombre chromatique est le nombre minimum de couleurs requis pour colorer un graphique. Par exemple, le nombre chromatique du graphique suivant est 3.

Le concept de coloration graphique est appliqué dans la préparation des horaires, l'attribution des fréquences radio mobiles, le Suduku, l'attribution des registres et la coloration des cartes.

Étapes de la coloration des graphiques

• Définissez la valeur initiale de chaque processeur du tableau à n dimensions sur 1.

• Maintenant, pour attribuer une couleur particulière à un sommet, déterminez si cette couleur est déjà attribuée aux sommets adjacents ou non.

• Si un processeur détecte la même couleur dans les sommets adjacents, il définit sa valeur dans le tableau sur 0.

• Après avoir effectué n ² comparaisons, si un élément du tableau vaut 1, alors c'est une coloration valide.

Pseudocode pour la coloration des graphiques

begin

   create the processors P(i0,i1,...in-1) where 0_iv < m, 0 _ v < n
   status[i0,..in-1] = 1
	
   for j varies from 0 to n-1 do
      begin
		
         for k varies from 0 to n-1 do
         begin
            if aj,k=1 and ij=ikthen
            status[i0,..in-1] =0
         end
			
      end
      ok = ΣStatus
		
   if ok > 0, then display valid coloring exists
   else
      display invalid coloring
      
end

Arbre couvrant minimal

Un arbre couvrant dont la somme du poids (ou de la longueur) de tous ses arêtes est inférieure à tous les autres arbres couvrant possibles du graphe G est appelé minimal spanning tree ou minimum cost spanningarbre. La figure suivante montre un graphe connexe pondéré.

Quelques arborescences possibles du graphique ci-dessus sont présentées ci-dessous -

Parmi tous les arbres couvrants ci-dessus, la figure (d) est l'arbre couvrant minimum. Le concept d'arbre couvrant à coût minimum est appliqué dans le problème du voyageur de commerce, la conception de circuits électroniques, la conception de réseaux efficaces et la conception d'algorithmes de routage efficaces.

Pour implémenter l'arborescence de coûts minimaux, les deux méthodes suivantes sont utilisées -

• Algorithme de Prim
• Algorithme de Kruskal

Algorithme de Prim

L'algorithme de Prim est un algorithme glouton, qui nous aide à trouver l'arbre couvrant minimum pour un graphe non orienté pondéré. Il sélectionne d'abord un sommet et trouve une arête avec le poids le plus faible incident sur ce sommet.

Étapes de l'algorithme de Prim

• Sélectionnez n'importe quel sommet, disons v ₁ du graphique G.

• Sélectionnez une arête, disons e ₁ de G telle que e ₁ = v ₁ v ₂ et v ₁ ≠ v ₂ et e ₁ a un poids minimum parmi les arêtes incidentes sur v ₁ dans le graphique G.

• Maintenant, après l'étape 2, sélectionnez l'incident d'arête pondéré minimum sur v ₂ .

• Continuez jusqu'à ce que n – 1 arêtes aient été choisies. Icin est le nombre de sommets.

L'arbre couvrant minimum est -

Algorithme de Kruskal

L'algorithme de Kruskal est un algorithme glouton, qui nous aide à trouver l'arbre couvrant minimum pour un graphe pondéré connecté, en ajoutant des arcs de coût croissants à chaque étape. Il s'agit d'un algorithme d'arborescence minimale qui trouve une arête du poids le plus faible possible qui relie deux arbres de la forêt.

Étapes de l'algorithme de Kruskal

• Sélectionnez une arête de poids minimum; disons que e ₁ du graphique G et e ₁ n'est pas une boucle.

• Sélectionnez l'arête pondérée minimale suivante connectée à e ₁ .

• Continuez jusqu'à ce que n – 1 arêtes aient été choisies. Icin est le nombre de sommets.

L'arbre couvrant minimum du graphique ci-dessus est -

Algorithme de chemin le plus court

L'algorithme de chemin le plus court est une méthode pour trouver le chemin le moins coûteux du nœud source (S) au nœud de destination (D). Ici, nous discuterons de l'algorithme de Moore, également connu sous le nom d'algorithme de recherche en largeur d'abord.

L'algorithme de Moore

• Étiquetez le sommet source, S et étiquetez-le i Et mettre i=0.

• Trouvez tous les sommets non étiquetés adjacents au sommet étiqueté i. Si aucun sommet n'est connecté au sommet S, alors le sommet D n'est pas connecté à S. S'il y a des sommets connectés à S, nommez-lesi+1.

• Si D est étiqueté, passez à l'étape 4, sinon passez à l'étape 2 pour augmenter i = i + 1.

• Arrêtez-vous après avoir trouvé la longueur du chemin le plus court.