Soit G(X, U) les graphes suivants :
1-
Les graphes suivants sont représentés par une matrice n*n (n=|X|) dite d’adjacence, contenant uniquement les valeurs 0 et 1. Chaque ligne et chaque colonne de la matrice représente un noeud. Ainsi, une case indique la relation qu’il existe entre deux noeuds.
Reconstituons les graphes suivants à partir de leurs matrices d’adjacences.
• 0 signifie que les deux noeuds ne sont pas reliés par un arc.
• 1 signifie que les deux noeuds sont reliés par un arc orienté.
Ainsi les graphes des matrices A, B et C sont représentés comme suit :
Plan :
EXERCICE 1 (Reconstitution d’un graphe orienté à partir de codage)
EXERCICE 2 (connexité et relation d’équivalence)
EXERCICE 3 : COULEURS A L’ECOLE
EXERCICE 4 : KONIGSBERG
1- Problèmes d’affectations
1-1Coloriage
1-2- Emploi du temps
2- ETAT D’UN RESEAU
3- CONCEPTION DE CIRCUIT
1- OPTIMISATION D’UN RESEAU INFORMATIQUE