Partie 2 Flashcards
Voisinage entrant de y
N-(y) = {x | xy ∈ A}
Voisinage sortant de y
N+(y) = {z | yz ∈ A}
Degré sortant de x
|N+(x)|
Degré entrant de x
|N-(x)|
Lien entre le degré entrant et le degré sortant
Σx∈V d-(x) = Σx∈V d+(x)
Qu’est-ce qu’un sous-digraphe couvrant ?
D’ = (V’, A’) est un sous-digraphe couvrant de D = (V, A) si V = V’, c’est-à-dire qu’on a retiré que des arêtes de D pour obtenir D’
Qu’est-ce qu’un sous-digraphe induit ?
D’ = (V’, A’) est un sous-digraphe induit de D = (V, A) si A’ = A ∩ (V’ × V’), c’est-à-dire qu’on a retiré que des sommets de D pour obtenir D’
Qu’est-ce qu’une arborescence sortante ?
Soit r un sommet, une arborescence sortant de racine r est un arbre orienté tel qu’il existe un chemin de r vers x pour tout sommet x de l’arborescence
Qu’est-ce qu’un out-branching ?
Une arborescence sortante couvrante
Qu’est-ce qu’un puits ?
Un sommet au degré sortant nul
Qu’est-ce qu’une source ?
Un sommet au degré entrant nul
Lien entre les graphes acycliques et les puits/sources
Tout digraphe acyclique admet une source et un puits
Propriété des digraphes aycliques (énoncé)
D est acyclique si et seulement si il admet un tri topologique, c’est-à-dire une numération de ses sommets x1, x2, …, xn telle que si xixj ∈ A, alors i < j
Propriété des digraphes aycliques (schéma de preuve)
⇐
un cycle doit contenir xixj tel que i > j, donc si D admet un tri topologique il est acyclique
⇒
Par récurrence sur n :
- ok pour n = 1
- supposé ok pour n
- pour n + 1, on rajoute x entre xi et xj tel que i = max{k | xk ∈ N-(x)} et j = min{k | xk ∈ N-(x)}, et on sait que ça respecte la condition de tri topologique car acyclique
Définition de la connexité forte
D est fortement connexe si ∀ x, y ∈ V, il existe un chemin orienté de x et y
Définition d’une composante connexe
Soit X ⊆ D est une composante fortement connexe de D si D[X] est fortement connexe et si X est maximal pour l’inclusion pour cette propriété
Lemme de décomposition en composantes fortement connexes (énoncé)
Les composantes fortement connexes partitionnent les sommets de D et le graphe obtenu en contractant toutes les composantes connexes de D est acyclique
Lemme de décomposition en composantes fortement connexes (schéma de preuve)
- Poser A l’ensemble des arcs de D qui n’appartiennent à aucun cycle et B l’ensemble de ceux qui appartiennent à un cycle au moins
- Si C est un composante connexe de (V, B), c’est une composante fortement connexe de D car s’il y a un chemin de x vers y dans B, il y en a également un de y vers x
- Les liens entre ces composantes connexes forment un graphe acyclique
Qu’est-ce qu’une composante fortement connexe initiale ?
Une composante fortement connexe dans laquelle aucun arc ne rentre
Qu’est-ce qu’une composante fortement connexe terminale ?
Une composante fortement connexe de laquelle aucun arc ne sort
Qu’est-ce qu’un feedback arc set ?
Un ensemble d’arcs F de D tel que D(V, A - F) est acyclique
Qu’est-ce qu’un tournoi ?
Un tournoi est l’orientation d’un graphe complet sans 2-cycle
Théorème sur les tournois et les chemins hamiltoniens (énoncé)
Tout tournois contient un chemin hamiltonien
Théorème sur les tournois et les chemins hamiltoniens (schéma de preuve)
Par induction sur n :
- pour n = 2, ok
- par hypothèse de récurrence, T \ {x} admet un chemin hamiltonien : x1 → x2 → … → xn - 1
- si x → x1, on a trouvé notre chemin hamiltonien
- sinon, i0 = max{i | xi → x} et si i0 = n, on a aussi trouvé notre chemin hamiltonien
- sinon, i0 < n et x → xi0+1, et on trouve que x1 → x2 → … → xi0 → x → xi0+1 → … → xn - 1 est un chemin hamiltonien de T