Les Graphes

Question 1

Déf : Graphe

Answer 1

Ensemble fini de sommets

Question 2

Déf : Arc

Answer 2

Couple de sommets. L’ordre des sommets donne le sens de l’arc.

Question 3

Déf : Arête

Answer 3

Couple de sommets sans notions de sens (donc symétrique)

Question 4

Le sommet W est adjacent au sommet V si ..

Answer 4

il existe un arc (V,W) existe.

Question 5

Déf : Chemin

Answer 5

suite de noeuds où chaque paire de noeuds consécutifs est liée
par un arc (ou arête)

Question 6

Déf : Degré d’un sommet (pour un graph NON-orienté)

Answer 6

le degré d’un sommet est le nombre d’arêtes dont ce sommet est
une extrémité

Question 7

Déf : Degré d’un sommet (pour un graph ORIENTÉ)

Answer 7

• Degré (ou arité) de sortie d’un sommet: nombre d’arcs sortant
• Degré (ou arité) d’entrée d’un sommet: nombre d’arcs entrant

Question 8

Synonyme de Degré

Answer 8

Arité

Question 9

Synonyme de Sommet

Answer 9

Noeud

Question 10

Synonyme de Cycle

Answer 10

Circuit

Question 11

Déf : Cycle

Answer 11

chemin où l’origine est égale au dernier noeud;

tous les autres noeuds étant visités une seule fois.

Question 12

Déf : Boucle

Answer 12

Cycle constitué d’un seul Arc

Question 13

Déf : Graphe Acyclique

Answer 13

Graphe ne contenant aucun cycle

Question 14

Déf : Puits

Answer 14

Noeud dont l’arité de sortie est 0

Question 15

Déf : Source

Answer 15

Noeud dont l’arité d’entrée est 0

Question 16

Déf : Graph pondéré

Answer 16

Dans un graphe pondéré (ou valué), chaque arc (u,v) possède une
valeur numérique w(u,v) qui est appelée le poids de l’arc.

Question 17

Synonyme : Réseau

Answer 17

Graph pondéré et pondéré

Question 18

Synonyme : Graph Valué

Answer 18

Graph pondéré

Question 19

Soit p(u,v) un chemin  allant de u à v
dans un graphe pondéré. 

La longueur d(p(u, v))

Answer 19

est la somme des poids des arcs constituants le chemin.

Question 20

Un plus court chemin p(u,v) allant de u à v est

Answer 20

un chemin tel qu’il n’existe pas

d’autre chemin p’(u,v) allant de u à v ayant d(p’(u,v)) < d(p(u,v)).

Question 21

Déf : Longueur dans un graphe NON pondéré

Answer 21

Le nombre d’arc du chemin

Question 22

Théorème du plus court chemin

Answer 22

Théorème: Soit p(i,j) un plus court chemin entre i et j. Soit r et s deux
noeuds intermédiaires appartenant à ce chemin . Alors le sous-chemin b(r,s)
de p(i,j) est un plus court chemin allant de r à s.

Question 23

Quand un graphe non orienté G est connexe ?

Answer 23

Un graphe non orienté G est connexe ssi il existe un chemin

entre n’importe quelle paire de sommets distincts du graphe.

Question 24

Nombre d’arêtes d’un graphe non orienté connexe de n sommets ?

Answer 24

n-1

Question 25

Propriété d'un graph non orienté connexe ayant PLUS n-1 arêtes

Answer 25

il possède au moins un cycle!

Question 26

Que se passe-t-il si le graphe non orienté G n'est pas connexe?

Answer 26

G apparaîtra comme un ensemble de sous-graphes connexes.

Question 27

Déf : Composante connexe d'un graphe G.

Answer 27

Est un sous graphe connexe qui ne peut pas être étendu (le plus grand sous ensemble connexe qu'on puisse formé)

Question 28

Un graphe orienté G est "faiblement connexe"

Answer 28

ssi son | graphe non orienté sous-jacent G’ est connexe.

Question 29

Un graphe orienté G est "fortement connexe"

Answer 29

ssi pour n’importe quelle paire de sommets distincts (a,b) de G, il existe un chemin du sommet a au sommet b.

Question 30

Un graph faiblement connexe peut il avoir des composantes fortement connexes ?

Answer 30

Oui (figure slide 14 de Graphe_1)

Question 31

Déf : Un arbre (en terme de notion de graphe)

Answer 31

est un graphe orienté, acyclique, faiblement connexe avec: • 1 seul noeud source = racine • des noeuds puits = feuilles • degré d ’entrée de tout noeud = 1, sauf la racine • il existe un chemin de la racine à tout autre noeud

Question 32

Quelles sont les manières de représenter un graphe en mémoire ?

Answer 32

- Dans une matrice de noeud adjacents | - Par chainage dynamique des noeuds

Question 33

Avantages et Inconvénients de la matrice d'adjacence

Answer 33

- A : Temps O(1) pour savoir si un arc existe - I : Temps Θ(n) I : Mémoire en Θ(n²)

Question 34

Déf : Matrice de valuation

Answer 34

Matrice d'ajacence pour les graph valués. L'intersections x,y de la matrice représente les poids de l'arc x,y. Poid 0 si x=y ; infini si pas d'arc.

Question 35

Avantages et Inconvénients de la Liste d'adjacence vs Matrice d'ajacence.

Answer 35

- A : Mémoire en Θ(n+m) vs Θ(n²) n sommets, m arcs - A : parcourir de tous les k noeuds adjacents se fait en Θ(k) vs Θ(n) - I: L’accès à l’arc (i,j) se fait en temps O(k) vs O(1)

Question 36

Principe de la représentation d'un graphe avec une Liste d'adjacence

Answer 36

Une liste chainée pour lister les successeurs direct d'un sommet. Généralement l'ordre de la liste n'a pas d'importance.

Question 37

Quelles sont les 2 méthodes générales d'exploration de graphe

Answer 37

- En profondeur | - En Largeur

Question 38

Temps d’exécution du parcours en profondeur

Answer 38

Θ(n+m) Un traitement pour les n sommets une seule fois chaque + Un traitement pour les m arcs une seule fois chaque

Question 39

Explorer en profondeur un graph non orienté permet de

Answer 39

trouver ses composantes connexes.

Question 40

Déf : Tri topologique d'un graph orienté

Answer 40

- est une séquence de noeuds trié de manière à ce que pour tout arc(u,v) de G u figue avant v dans la séquence. - est possible seulement si le graphe est acyclique

Question 41

Comment obtenir un tri topologique d'un graphe orienté acyclique ?

Answer 41

En dépilant la pile de ses sommets obtenu lors de son parcours en profondeur.

Question 42

Algorithme de Kosaraju

Answer 42

Permet de trouver les composantes fortement connexes d'un graphe orienté. Principe : 1- Parcours en profondeur du graphe inverse 2- Parcours en profondeur du graphe original en dépilant les noeuds empilés précédement - Chaque graphe trouvé est une composante fortement connexe.

Question 43

Propriétés du parcours en largeur

Answer 43

• À l’aide des prédécesseurs on peut obtenir tous les plus courts chemins de v aux autres noeuds accessibles depuis v (pour les graphes non pondérés). • L’algorithme fonctionne pour les graphes orientés ou non •Le temps d’exécution en Θ(n+m)