Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphes(Partie 1) (Terminologie (Adjacence (W est adjacent au noeud V si…
Graphes(Partie 1)
Terminologie
Adjacence
W est adjacent au noeud V si l’arc (V,W) existe
Chemin
Suite de noeuds où chaque paire de noeuds consécutifs est liée
par un arc (ou arête dans le cas d’un graphe non orienté)
Cycle
Chemin où l’origine est égale au dernier noeud;
tous les autres noeuds étant visités une seule fois
Boucle
Cycle constitué d’un seul arc
Graphe acyclique
Graphe ne contenant aucun cycle
Sources
Noeud dont l’arité d’entrée est 0
Puits
Noeud dont l’arité de sortie (degré) est 0
Types de graphes
Pondéré
:star: Chaque arc (u,v) possède une valeur
numérique w(u,v) qui est appelée le poids de l’arc
Poids "w(u,v)"
Valeur numérique d'un arc
Longueur "d(p(u, v))"
Somme des poids des arcs constituant ce chemin
Plus court chemin "p(u,v)"
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))
Non pondéré
Longueur "d(p(u, v))"
Longueur d’un chemin p(u,v) est donné par la somme des arcs constituant ce chemin
Non orienté
:star:G = (S, A)
S ensemble fini des sommets
A ensemble des arêtes
Degré
Le degré d’un sommet -> le nombre d’arêtes dont ce sommet est
une extrémité
Connexe
:star: Il existe un chemin
entre n’importe quelle paire de sommets distincts du graphe
:warning: Un graphe non orienté connexe de n sommets
comporte au moins n-1 arêtes
Non connexe
G apparaîtra comme un ensemble de sous-graphes connexes (composantes connexes)
Orienté
Connexe
Faiblement connexe
Acyclique
Arbre
Degré d ’entrée de tout noeud = 1, sauf la racine
∃ un chemin de la racine à tout autre noeud
Des noeuds puits -> feuilles
1 seul noeud source -> racine
:star: Son
graphe non orienté sous-jacent G’ est connexe
Déterminer si un graph est faiblement connexe
:warning: 1)Remplacer les arcs par des arêtes 2)On doit pouvoir se rendre d'un sommet n'importe quel autre sommet
Fortement connexe
:star: Pour n’importe quelle
paire de sommets distincts (a,b) de G, il existe un chemin du sommet a
au sommet b
:star: Une composante fortement connexe de G est un sous graphe de G (de
taille maximal) qui est fortement connexe
Déterminer si un graphe est fortement connexe
:warning: En respectant la direction des flèches, on doit pouvoir se rendre d'un sommet à n'importe quel autre sommet
:star: Il existe un chemin
entre n’importe quelle paire de sommets distincts du graphe
Non connexe
:star: Il n'existe pas de chemin
entre n’importe quelle paire de sommets distincts du graphe
:star:G = (S, A)
S ensemble fini des sommets
A ensemble des arcs
Degré
Degré (ou arité) d’entrée d’un sommet -> nombre d’arcs entrant
Degré (ou arité) de sortie d’un sommet -> nombre d’arcs sortant
Implémenter un graphe (stocker en mémoire)
Dans une matrice de noeuds adjacents
Graphe valué
Matrice de valuation
:star: La matrice de valuation du graphe orienté valué G = (S,F,w), avec n = |S|, est la matrice W définie par :
• W[i,j] = 0 quand i = j
• W[i,j] = w(i,j) quand (i,j) ∈ F
• W[i,j] = +∝ quand i ≠ j et (i,j) ∉ F
:check: :timer_clock: Accès aléatoire à W[i,j] en temps O(1)
:red_cross: :timer_clock: Temps en Θ(n) pour obtenir les sommets adjacents à un sommet
:red_cross: :file_cabinet: Espace mémoire en Θ(n2)
Graphe non valué
Matrice d'adjacence
:check: :timer_clock: Temps en O(1) pour savoir si l’arc (i,j) existe
:red_cross: :timer_clock: Temps en Θ(n) pour obtenir les voisins d’un sommet
:star:La matrice d’adjacence du graphe orienté G = (S,F) est la matrice A définie par :
• A[i][j] = 1 si et seulement si (i,j) est un arc
• A[i][j] = 0 si et seulement si (i,j) n'est pas un arc
:red_cross: :file_cabinet: Espace mémoire en Θ(n2)
Graphe non orienté
Chaque arête stocké 2 fois (symétrie avec la diagonale)
Graphe orienté
Chaque arête stocké 1 fois
Pour obtenir l'arité de sortie d'un noeud -> somme des chiffre de sa ligne
Pour obtenir l'arité d'entré d'un noeud -> somme des chiffre de sa colonne
Par chaînage dynamique des noeuds
Listes d’adjacence (listes de successeurs)
:star: La liste des successeurs du sommet i d’un graphe orienté G = (S,F) est la liste L[i] = { j ∈ S, (i,j) ∈ F }
S est l'ensemble des sommets à { 1, 2, …, n }
Graphe non valué
Graphe valué
:check: :file_cabinet: Espace mémoire en Θ(n+m) où m = |F| et n = |S|
:check: :timer_clock: Parcours de tous les v(i) noeuds adjacents au sommet i se fait en Θ(v(i))
:red_cross: :timer_clock: Accès à l’arc (i,j) se fait en temps O(v(i))
Théorèmes
Principe d’optimalité des plus courts chemins
Soit p(i,j) un plus court chemin entre i et j. Soit r et s deux
noeuds intermédiaires appartenant à ce plus court (noté par: i ≤ r ≤ s ≤ j).
Alors le sous-chemin b(r,s) de p(i,j) est un plus court chemin allant de r à s
Algorithmique des graphes
Algorithmes d’explorations
Ordres de visite
Parcours en profondeur (Depth-First Search: DFS)
:star: L’algorithme utilise une variable booléenne par sommet et une pile.
• La variable booléenne permet de marquer un sommet visité.
• La pile permet de revenir en arrière et d’explorer d’autres arcs
Algorithme
2)Empiler et marquer (à «vrai») le noeud de départ
3)Tant et aussi longtemps que la pile n’est pas vide:
a) Dépiler un noeud, et lui faire le traitement voulu (par exemple, afficher sa valeur à l’écran).
b) Pour chacun de ses voisins qui n’est pas marqué:
i. Le marquer.
ii. L’empiler.
1)Initialiser (mettre à « faux ») une marque (une valeur booléenne)
associée à chaque noeud
:timer_clock: L’algorithme de parcours en profondeur prend un temps en Θ(n+m) = Θ(max{n,m}) pour un graphe de n noeuds et m arcs (lorsque le graphe est implémenté par des listes d’adjacence)
Algorithme de Kosaraju
2)Faire un parcours en profondeur complet de GI (donc, en empilant les
noeuds selon l’ordre croissant des valeurs de fin[] )
3)Faire un parcours en profondeur complet de G, mais selon l’ordre des noeuds empilés par le parcours de GI
4)À chaque retour de explore() lors du parcours de G, les noeuds visités depuis le dernier appel de explore() constituent une comp. fortement connexe de G
1)Obtenir l’inverse GI du graphe original G
:timer_clock: Temps total d’exécution est en Θ(n+m)
Parcours en largeur (Breadth-First Search: BFS)
:star: Visite les noeuds les plus près en premier. Ce parcours nous donne tous les plus courts chemins du noeud de départ dans un graphe non valué
Algorithme
2)Enfiler et marquer (à « vrai ») le noeud de dépa
3)Tant et aussi longtemps que la file n’est pas vide:
a) Défiler le prochain noeud et le traiter.
b) Pour chaque voisin qui n’est pas marqué:
i. Le marquer
ii. L’enfiler
1)Initialiser (mettre à « faux ») une marque (une valeur booléenne)
associée à chaque noeud
:star: L'algorithme utilise une file pour le parcours du graphe à partir
d'un sommet donné.
Si on veut la description de ce chemin.
Fouille en largeur avec prédecesseur
Notons par p(u) le prédécesseur de u pour le plus court chemin de v à u.
Mémoriser le prédécesseur
pour chaque noeud sur ce plus court chemin
:timer_clock: Temps d'exécution en O(n+m) pour les mêmes
raisons l’algorithme de fouille en profondeur
:warning: L’algorithme nous donne les plus courts chemins mais seulement pour les graphes non pondérés/valués
Tri topologique
:star: Une séquence de noeuds est un tri topologique d’un grahe G ssi pour tout
arc(u,v) de G on a que u précède v dans la séquence.
:warning: Seuls les graphes acycliques admettent un ordre topologique
:warning: Possibilité de présence de cycles : alors il faut marquer les noeuds
déjà visités pour éviter de revenir continuellement sur les mêmes
noeuds
