Définition de Graphes et MST

Question 1

Graphe orienté

Answer 1

Couple (S, A) sommets arcs tels que A définit une relation binaire non symétrique.

(si , sj ) ∈ A =/=> (sj , si ) ∈ A

Question 2

Graphe non orienté

Answer 2

Couple (S,A) sommets arêtes tel que
A définit une relation binaire symétrique

∀(si , sj ) ∈ S × S, (si , sj ) ∈ A ⇔ (sj , si ) ∈ A (noté {si , sj })

Question 3

Degré d’un sommet

Answer 3

Nombre de sommets adjacents : d°(s) = #adj(s)

Question 4

Demi-degré

Answer 4

Demi-degré extérieur d°+(si) = #succ(si)
Demi-degré intérieur d°−(si) = #pred(si)

Question 5

Graphe non-orienté complet

Answer 5

si ∀{si , sj} ⊆ S, {si , sj } ∈ A

Question 6

Graphe partiel

Answer 6

G′ = (S, A′) est un graphe partiel de G = (S, A) si A′ ⊆ A
==> graphe obtenu en supprimant certains arcs ou arêtes

Question 7

Sous-graphe

Answer 7

G′ = (S′, A′) est un sous-graphe de G = (S, A) si S′ ⊆ S et A′ = A ∩ S′ × S′
; G′ est le sous-graphe de G induit par S

Question 8

Graphe connexe

Answer 8

Un graphe non orienté est connexe si chaque sommet est accessible à partir de n’importe quel autre.
∀(si , sj ) ∈ S2, si ∼ sj

Question 9

Graphe fortement connexe

Answer 9

Un graphe orienté est fortement connexe si chaque sommet est accessible à partir de n’importe quel autre.
∀(si , sj ), si ∼> sj et sj ∼> si.

Question 10

Composante connexe de G

Answer 10

Sous-graphe de G connexe et maximal

Question 11

Composante fortement connexe de G

Answer 11

Sous-graphe de G fortement connexe maximal

Question 12

Chaîne/chemin

Answer 12

Séquence de sommets < s0, s1, s2, …, sk >
telle que ∀i ∈ [1, k], {si−1, si } ∈ A ( ou (si−1, si ) ∈ A )

Question 13

Cycle/circuit

Answer 13

Chaîne/chemin commençant et terminant par un même sommet

Question 14

Arbre

Answer 14

Graphe non orienté G = (S, A) vérifiant
<=> G est connexe et sans cycle
<=> G est sans cycle et possède #S − 1 arêtes
<=> G est connexe et admet #S − 1 arêtes
<=> G est sans cycle, et en ajoutant une arête, on crée un cycle élémentaire
<=> G est connexe, et en supprimant une arête, il n’est plus connexe
<=> ∀(si , sj ) ∈ S × S, il existe exactement une chaine entre si et sj

Question 15

Forêt

Answer 15

Graphe non orienté dont chaque composante connexe est un arbre

Question 16

Arborescence

Answer 16

Graphe orienté sans circuit admettant une racine s0 ∈ S tel que ∀si ∈ S, il existe un chemin unique allant de s0 vers si

Question 17

Structures de données pour représenter un graphe

Answer 17

Liste d’adjacence et Matrice d’adjacence

Question 18

Matrice d’adjacence

Answer 18

Matrice M telle que M[si ][sj ] = 1 si (si , sj ) ∈ A
et M[si ][sj ] = 0 sinon

Question 19

Liste d’adjacence

Answer 19

Tableau succ tel que succ[s] = liste des successeurs de s

Question 20

M^k[si][sj]

Answer 20

Nombre de chemins de longueur k allant de si à sj

Question 21

Utilité des matrices d’adjacence

Answer 21

Déterminer si un arc existe

Question 22

Utilité des listes d’adjacence

Answer 22

Accéder à tous les successeurs

Question 23

Arbre couvrant minimal (MST)

Answer 23

Graphe partiel G ′ = (S, E) de G tel que :
- G′ est un arbre couvrant (G ′ est connexe et sans cycle)
- La somme des coûts des arêtes de E est minimale

Question 24

MST : coupure d’un graphe

Answer 24

Coupure d’un graphe G = (S, A) : Partition de S en 2 parties (P, S \ P)

Une coupure respecte E ⊆ A si aucune arête de E n’est traversée.

Une arête {si , sj } traverse une coupure (P, S \ P) si #(P ∩ {si , sj }) = 1

Question 25

Algorithmes pour trouver un MST

Answer 25

Algorithme de Prim et de Kruskal

Question 26

Comment représente-t-on un arbre ?

Answer 26

On utilise un tableau π des prédecesseurs

Question 27

Algorithme de Kruskal

Answer 27

1 Fonction Kruskal(g, cout) 2 E ← ∅ 3 Trier les arêtes de A par ordre de coût croissant 4 pour chaque arête {si , sj } prise par ordre de coût croissant faire 5 si si et sj sont dans 2 composantes connexes différentes de (S, E) alors 6 Ajouter {si , sj } dans E 7 retourne E

Question 28

Structure de données pour Kruskal

Answer 28

Tableau π Pour effectuer efficacement le test de la ligne 5 : composantes connexes de (S, E) = disjoint sets

Question 29

Complexité Kruskal

Answer 29

O(p log p) (graphe à n sommets et p arcs)

Question 30

Algorithme de Prim

Answer 30

``` 1 Fonction Prim(g, cout) 2 Soit s0 un sommet de S choisi arbitrairement 3 P ← {s0} ; E ← ∅ 4 pour chaque sommet si ∈ S faire 5 si si ∈ adj(s0) alors π[si ] ← s0 ; c[si ] ← cout(s0, si ) ; 6 sinon π[si ] ← null ; c[si ] ← ∞ ; 7 tant que P 6 = S faire 8 Ajouter dans P le sommet si ∈ S \ P ayant la plus petite valeur de c 9 Ajouter (si , π[si ]) à E 10 pour chaque sommet sj ∈ adj(si ) faire 11 si sj 6 ∈ P et cout(si , sj ) < c[sj ] alors π[sj ] ← si ; c[sj ] ← cout(si , sj ) ; 12 retourne E ```

Question 31

Structure de données pour Prim

Answer 31

Tableaux π (prédecesseurs) et c (coûts) Ligne 8 : File de priorité implémentée par un tas binaire

Question 32

Complexité Prim

Answer 32

O(p log n) (sous réserve d’une implémentation par listes d’adjacence)