Chapitre 10 — Graphes

M

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

→ 1) cycle A−B−C−D−E−A avec la diagonale supplémentaire BD

→ 2) degrés : A=2, B=3, C=2, D=3, E=2

→ 3) non complet (6 arêtes sur 10 possibles) ; non eulérien (B et D de degré impair)

= degrés 2,3,2,3,2 · non complet, non eulérien

sommets{A,B,C,D}, arêtes{AB,AC,BC,CD}

→ matrice (ordre A,B,C,D) : [[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]]

→ 1) symétrique car le graphe est non orienté (arête ij = arête ji)

→ 2) la diagonale vaut 0 : aucun sommet n'est relié à lui-même (pas de boucle)

= matrice ci-dessus · symétrique · diagonale=0

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

→ 1) c'est une chaîne (le sommet B est répété), pas un chemin (qui ne répète aucun sommet)

→ 2) cycle B−C−D−B (le sommet B est revisité)

→ 3) G est connexe : tous les sommets A,B,C,D,E sont reliés par cette chaîne

= chaîne (pas un chemin) · cycle B−C−D−B · connexe

2-coloriage possible ⟺ biparti

→ 1) {A,B,C,D} avec {AB,AC,BD,CD} : bipartition {A,D} et {B,C} fonctionne pour toutes les arêtes → biparti

→ 2) non : un graphe contenant un cycle impair ne peut pas être biparti

= biparti (bipartition {A,D},{B,C}) · non biparti si cycle impair

graphe connexe eulérien ⟺ tous les degrés sont pairs

→ 1) Königsberg (degrés 3,3,3,5, tous impairs) → non eulérien, impossible sans lever le crayon

→ 2) {A,B,C,D} degrés 2,2,2,2 (tous pairs) → eulérien, traçable sans lever le crayon

= non eulérien (Königsberg) · eulérien

coefficient (i,j) de Aᵏ = nb de chemins de longueur k

→ A=[[0,1,1],[1,0,1],[1,1,0]] (graphe complet K₃)

→ A² = [[2,1,1],[1,2,1],[1,1,2]]

→ interprétation : 2 chemins de longueur 2 d'un sommet à lui-même (via chacun des deux autres), 1 chemin de longueur 2 entre deux sommets distincts (via le troisième)

= A²=[[2,1,1],[1,2,1],[1,1,2]]

M

→ Matrice d'adjacence (ordre A,B,C,D, ligne=origine, colonne=destination) : A→(B,D), B→(C), C→(A), D→(C).

→

→ Circuit : A→B→C→A revient à son point de départ, c'est un circuit.

→ Fortement connexe : D→C→A→B montre que D atteint tous les sommets ; A→D, A→B→C→A→D, C→A→D montrent que tous atteignent D et s'atteignent mutuellement : le graphe est fortement connexe.

= Matrice d'adjacence ci-dessus ; circuit A→B→C→A ; le graphe est fortement connexe.

→ T = [[0.7,0.3],[0.4,0.6]] (ordre S,N ; ligne=état actuel, colonne=état suivant).

→ v₀=(1,0) (S aujourd'hui). v₁ = v₀T = (0.7, 0.3).

→ v₂ = v₁T = (0.7×0.7+0.3×0.4, 0.7×0.3+0.3×0.6) = (0.49+0.12, 0.21+0.18) = (0.61, 0.39).

= T = [[0.7,0.3],[0.4,0.6]] ; probabilité qu'il soit ensoleillé dans 2 jours = 0.61.

→ πT=π avec π=(π₁,π₂) : π₁ = 0.7π₁+0.4π₂ ⟹ 0.3π₁=0.4π₂ ⟹ π₁/π₂ = 43.

→ En posant π₁=4k, π₂=3k : π₁+π₂=7k=1 ⟹ k=17.

= π = (47, 37) ≈ (0.571, 0.429) : à long terme, il fait beau environ 47 (≈57%) du temps.

→ Composante 1 : {1,2,3} (reliés par les arêtes 12, 13, 23 — un triangle).

→ Composante 2 : {4,5,6} (reliés par les arêtes 45, 56 — une chaîne).

→ Arbre couvrant de {1,2,3} : ce triangle a 3 arêtes pour 3 sommets, il faut en retirer une pour obtenir un arbre (sans cycle) — par exemple {12, 13}.

→ Arbre couvrant de {4,5,6} : {45, 56} a déjà 2 arêtes pour 3 sommets, sans cycle : c'est déjà un arbre.

= 2 composantes connexes : {1,2,3} et {4,5,6} ; arbres couvrants : {12,13} et {45,56}.

→ Init : dist(A)=0, dist(B)=dist(C)=dist(D)=∞. Voisins de A : dist(B)=4, dist(C)=2.

→ Sommet non visité le plus proche : C (2). Visite de C : via C, dist(B)=min(4, 2+1)=3 ; dist(D)=min(∞, 2+8)=10.

→ Sommet non visité le plus proche : B (3). Visite de B : via B, dist(D)=min(10, 3+5)=8.

→ Sommet restant : D (8). Chemin reconstruit : A→C→B→D, de longueur 2+1+5=8.

= Plus court chemin de A à D : A→C→B→D, de longueur 8.

→ Chaque arête a exactement deux extrémités ; en comptant, pour chaque arête, les deux incidences sommet-arête qu'elle crée, on compte chaque arête exactement 2 fois au total sur l'ensemble des sommets.

→ Donc Σ_v deg(v) = 2×(nombre d'arêtes) — cette somme est toujours paire.

→ Si on sépare les sommets de degré pair et impair : la somme des degrés pairs est paire, donc (somme totale paire) − (somme des degrés pairs, paire) = somme des degrés impairs, qui doit aussi être paire. Une somme de nombres impairs n'est paire que s'il y en a un nombre pair : donc le nombre de sommets de degré impair est pair.

→ Pour 6 sommets tous de degré 3 : Σdeg=18=2E ⟹ E=9, réalisable (ex. le prisme triangulaire, deux triangles reliés par un couplage). Pour tous de degré 4 : Σdeg=24=2E ⟹ E=12≤C(6,2)=15, réalisable (ex. l'octaèdre K₂,₂,₂). Dans les deux cas, 6 étant pair, aucune obstruction de parité n'apparaît.

= Σdeg(v)=2×|arêtes| (chaque arête comptée deux fois) ; le nombre de sommets de degré impair est toujours pair ; un graphe à 6 sommets tous de degré 3 (prisme triangulaire) ou tous de degré 4 (octaèdre) existe bien dans les deux cas.