Fiche N° 10Chapitre 10 — Graphes
Vocabulaire, matrices, chaînes de Markov

★

Graphe G : sommets {A,B,C,D,E}, arêtes {AB,BC,CD,DE,AE,BD}.

1. Dessiner G.
2. Degré de chaque sommet.
3. G est-il complet ? Eulérien ?

Écrire la matrice d'adjacence de G (sommets {A,B,C,D}, arêtes {AB,AC,BC,CD}).

1. La matrice est-elle symétrique ? Pourquoi ?
2. Que représente la diagonale ?

G : A−B−C−D−B−E.

1. Est-ce un chemin ? Une chaîne ?
2. Y a-t-il un cycle ? Lequel ?
3. G est-il connexe ?

Fiche N° 10Chapitre 10 — Graphes
Fiche N° 10

★★

Un graphe est biparti si on peut 2-colorier ses sommets (arête toujours entre les deux couleurs).

1. Le graphe {A,B,C,D} avec arêtes {AB,AC,BD,CD} est-il biparti ?
2. Un graphe avec un cycle impair est-il biparti ?

Déterminer si le graphe peut être tracé sans lever le crayon :

1. Graphe du problème des ponts de Königsberg (4 sommets, degrés 3,3,3,5).
2. Graphe : {A,B,C,D} degrés 2,2,2,2.

A=[[0,1,1],[1,0,1],[1,1,0]]. Calculer A² et interpréter.

Fiche N° 10Chapitre 10 — Graphes
Fiche N° 10

★★

Graphe orienté : A→B, B→C, C→A, A→D, D→C.

1. Écrire la matrice d'adjacence orientée.
2. Y a-t-il un circuit ? Lequel ?
3. Le graphe est-il fortement connexe ?

Temps ensoleillé (S) ou nuageux (N). P(S→S)=0.7, P(S→N)=0.3, P(N→S)=0.4, P(N→N)=0.6.

1. Écrire la matrice de transition T.
2. Si aujourd'hui S, probabilité qu'il soit S dans 2 jours ?

Pour la chaîne de Markov (Ex.8).

1. Trouver la distribution stationnaire π telle que πT=π et π₁+π₂=1.
2. Interpréter : à long terme, quelle fraction du temps est-il ensoleillé ?

Fiche N° 10Chapitre 10 — Graphes
Fiche N° 10

★★★

Graphe G : {1,2,3,4,5,6}, arêtes {12,13,23,45,56}.

1. Quelles sont les composantes connexes ?
2. Construire l'arbre couvrant de chaque composante.

Graphe pondéré (distances) : A−B(4), A−C(2), B−D(5), C−B(1), C−D(8), B−D(5).

1. Appliquer Dijkstra depuis A vers D.
2. Quel est le plus court chemin ?

Théorème de Handshaking : la somme des degrés d'un graphe est égale à deux fois le nombre d'arêtes.

1. Démontrer ce résultat en comptant les incidences sommet-arête.
2. Déduire que le nombre de sommets de degré impair est pair.
3. Application : un graphe de 6 sommets peut-il avoir tous ses sommets de degré 3 ? Et de degré 4 ?

✦ Auto-évaluation

Mon score : _____ / 48 pts