Théorie des graphes : Graphes niveaux et coloria ge dut informatique sem2
Télécharger PDFDUT Informatique – Semestre 2 : Théorie des Graphes
Niveaux et Coloriage
Exercices
Exercice 1 : Décomposition en niveaux
Décomposer le graphe suivant en niveaux :
1 2 3 4 5 6 7 8
Exercice 2 : Coloriage et nombre chromatique
Colorier les graphes suivants et donner leur nombre chromatique. À chaque fois, justifier en indiquant une clique maximale.
Graphe 1
1 2 3 4 5 6 7 8
Graphe 2
2 1 2 3 4 5 6 7 8 1
Graphe 3
3 1 2 3 4 5 6 7 8
Graphe 4
4 1 2 3 4 5 6 7 8
Exercice 3 : Fonction find et algorithmes
La fonction find permet de simplifier de nombreux algorithmes.
L = find(T == x) renvoie dans L les numéros des cases de la matrice T qui contiennent la valeur x.
1. Compléter les fonctions Colorie_Chemin et Colorie_Voisinage du TP1
Utiliser la fonction find pour implémenter ces fonctions.
2. Écrire une fonction i = Numero_Arc(G, x, y) qui renvoie le numéro de l’arc (x, y) dans le graphe G en utilisant find
3. Réécrire la fonction Arc_Existe sans utiliser de boucles, mais en utilisant find
4. Écrire une fonction [x, y] = Poids_max(G) qui trouve l’arc (x, y) de poids maximum dans le graphe G
Indication : les poids sont dans la propriété G.edge.weight.
FAQ
1. Comment identifier une clique maximale dans un graphe ?
Une clique maximale est un sous-ensemble de sommets tous connectés entre eux, et qui ne peut pas être étendu avec un autre sommet. Pour la trouver, on peut utiliser des méthodes comme l’analyse des sous-graphes complets ou des algorithmes dédiés (ex. Bron-Kerbosch).
2. À quoi sert la fonction find en MATLAB ?
La fonction find permet de localiser les indices des éléments non nuls ou vérifiant une condition dans une matrice ou un tableau. Elle est utile pour extraire des données ou manipuler des structures sans boucles explicites.
3. Comment vérifier l’existence d’un arc sans boucle ?
Utiliser find sur une matrice d’adjacence pour détecter si l’arc existe. Par exemple, si G.edge contient les arcs, find(G.edge(:,1) == x & G.edge(:,2) == y) renvoie les indices si l’arc (x, y) est présent.