Théorie des graphes : Graphes niveaux et coloria ge dut informatique sem2
Télécharger PDFDUT Informatique
semestre 2
Th ́eorie des Graphes
Niveaux et Coloriage
Math ́ematiques
Soutien n◦ 2
Exercice1
D ́ecomposer le graphe suivant en niveaux :1 23 45 67 8
Exercice2
colorier les graphes suivants et donner leur nombre chromatique.` A chaque fois justifier en
donnant une clique maximale.1.G 11 23 45 67 82.G 21 23 45 67 81 DUT Informatique
semestre 2
Th ́eorie des Graphes
Niveaux et Coloriage
Math ́ematiques
Soutien n◦ 23.G 31 23 45 67 84.G 41 23 45 67 8
Exercice3
La fonctionfindpermet de simplifier de nombreux algorithmes.L=find(T==x) renvoie
dansLles num ́eros des cases de la matriceTqui contiennent la valeurx.
fonction find
1. finir les fonctionColorie_CheminetColorie_Voisinagedu TP1.
2. ́
Ecrire une fonctioni=Numero_Arc(G,x,y)qui renvoie le num ́eroide l’arc(x,y)dans
le grapheGen utilisantfind
3. r ́e ́ecrire la fonctionArc_Existesans utiliser de boucles mais en utilisantfind.
4. ́
Ecrire une fonction[x,y]=Poids_max(G)qui trouve l’arc(x,y)de Poids maximum dans
le grapheG.
Indication :les poids sont dans la propri ́et ́eG.edge
weight, tester avec les graphes
exo390G1.graphetexo390G2.graphdu TP2