Les Graphes Flashcards
Déf : Graphe
Ensemble fini de sommets
Déf : Arc
Couple de sommets. L’ordre des sommets donne le sens de l’arc.
Déf : Arête
Couple de sommets sans notions de sens (donc symétrique)
Le sommet W est adjacent au sommet V si ..
il existe un arc (V,W) existe.
Déf : Chemin
suite de noeuds où chaque paire de noeuds consécutifs est liée
par un arc (ou arête)
Déf : Degré d’un sommet (pour un graph NON-orienté)
le degré d’un sommet est le nombre d’arêtes dont ce sommet est
une extrémité
Déf : Degré d’un sommet (pour un graph ORIENTÉ)
- 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
Synonyme de Degré
Arité
Synonyme de Sommet
Noeud
Synonyme de Cycle
Circuit
Déf : Cycle
chemin où l’origine est égale au dernier noeud;
tous les autres noeuds étant visités une seule fois.
Déf : Boucle
Cycle constitué d’un seul Arc
Déf : Graphe Acyclique
Graphe ne contenant aucun cycle
Déf : Puits
Noeud dont l’arité de sortie est 0
Déf : Source
Noeud dont l’arité d’entrée est 0
Déf : Graph pondéré
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.
Synonyme : Réseau
Graph pondéré et pondéré
Synonyme : Graph Valué
Graph pondéré
Soit p(u,v) un chemin allant de u à v dans un graphe pondéré.
La longueur d(p(u, v))
est la somme des poids des arcs constituants le chemin.
Un plus court chemin p(u,v) allant de u à v est
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)).
Déf : Longueur dans un graphe NON pondéré
Le nombre d’arc du chemin
Théorème du plus court chemin
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.
Quand un graphe non orienté G est connexe ?
Un graphe non orienté G est connexe ssi il existe un chemin
entre n’importe quelle paire de sommets distincts du graphe.
Nombre d’arêtes d’un graphe non orienté connexe de n sommets ?
n-1
Propriété d’un graph non orienté connexe ayant PLUS n-1 arêtes
il possède au moins un cycle!
Que se passe-t-il si le graphe non orienté G n’est pas connexe?
G apparaîtra comme un ensemble de sous-graphes connexes.
Déf : Composante connexe d’un graphe G.
Est un sous graphe connexe qui ne peut pas être étendu (le plus grand sous ensemble connexe qu’on puisse formé)
Un graphe orienté G est “faiblement connexe”
ssi son
graphe non orienté sous-jacent G’ est connexe.
Un graphe orienté G est “fortement connexe”
ssi pour n’importe quelle
paire de sommets distincts (a,b) de G, il existe un chemin du sommet a
au sommet b.
Un graph faiblement connexe peut il avoir des composantes fortement connexes ?
Oui (figure slide 14 de Graphe_1)
Déf : Un arbre (en terme de notion de graphe)
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
Quelles sont les manières de représenter un graphe en mémoire ?
- Dans une matrice de noeud adjacents
- Par chainage dynamique des noeuds
Avantages et Inconvénients de la matrice d’adjacence
- A : Temps O(1) pour savoir si un arc existe
- I : Temps Θ(n)
I : Mémoire en Θ(n²)
Déf : Matrice de valuation
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.
Avantages et Inconvénients de la Liste d’adjacence vs Matrice d’ajacence.
- 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)
Principe de la représentation d’un graphe avec une Liste d’adjacence
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.
Quelles sont les 2 méthodes générales d’exploration de graphe
- En profondeur
- En Largeur
Temps d’exécution du parcours en profondeur
Θ(n+m)
Un traitement pour les n sommets une seule fois chaque
+
Un traitement pour les m arcs une seule fois chaque
Explorer en profondeur un graph non orienté permet de
trouver ses composantes connexes.
Déf : Tri topologique d’un graph orienté
- 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
Comment obtenir un tri topologique d’un graphe orienté acyclique ?
En dépilant la pile de ses sommets obtenu lors de son parcours en profondeur.
Algorithme de Kosaraju
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.
Propriétés du parcours en largeur
• À 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)
