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
Théorème sur les tournois et les cycles hamiltoniens (énoncé)
Si T est un tournoi fortement connexe, alors il admet un cycle hamiltonien
Théorème sur les tournois et les cycles hamiltoniens (schéma de preuve)
Par récurrence sur n :
- pour n = 3, ok car les seules composantes connexes sont les deux cycles hamiltoniens (horaire et anti-horaire)
- supposer qu’il y a un cycle C x1, …, xk de taille k dans T
- si x ∈ T \ C → x1 on pose i0 = max{i | x → xi} et si i0 < k, on peut insérer x dans C, sinon C domine x
- si x1 → x ∈ T \ C on pose i0 = max{i | xi → x} et si i0 < k, on peut insérer x dans C, sinon x domine C
- pour chaque x, si on l’insère on peut agrandir le cycle
- pour les autres x, on construit A = {x | C domine x} et B = {x | | x domine C} et a aussi un cycle agrandit A → B → C
Qu’est-ce que α(D) ?
La taille du plus grand indépendant d’un digraphe D
Théorème sur les partitions de digraphes en chemins (énoncé)
Tout digraphe D admet une
partition de ses sommets en au plus α(D) chemins
Théorème sur les partitions de digraphes en chemins (schéma de preuve)
- Montrer plutôt que si D se partitionne en k > α(D) chemins de début Deb = {d1, …, dk}, alors D a une partition en k - 1 chemins dont les débuts sont dans Deb
- Récurrence sur n :
- pour n = 1, α(D) = 1 et on ne peut faire plus de partitions
- on considère P1, …, Pk une partition en k > α(D) chemins dont les début sont respsectivement d1, …, dk et puisque k > α(D), on sait qu’il existe di et dj tels qu’il y a une arête entre eux
- si |Pi| = 1, il suffit de prendre comme k chemins P1, …, diPj, …, Pk et on a fini
- sinon, soit d’i le premier sommet de Pi \ di et on peut appliquer l’hypothèse de récurrence sur P1, …, Pi \ d’i, …, Pk et Deb’ = {d1, …, d’i, …, dk} : on suppose qu’il existe P’1, …, P’k-1 partitionnant D \ {di} et dont les débuts sont dans Deb’
- si d’i est le début d’un des chemins P’i, on y rattache di et on a fini
- sinon, d’i n’est pas dans les début et dj y est forcément, donc on rattache di à dj et on a fini
Qu’est-ce que χ(D) ?
Le nombre chromatique du digraphe D, c’est-à-dire aussi la taille d’une partition minimale en indépendants
Théorème sur les chemins longs dans les digraphes (énoncé)
Tout digraphe D contient un chemin
sur au moins χ(D) sonnets
Théorème sur les chemins longs dans les digraphes (preuve)
- On considère D’ un sous-digraphe couvrant, acyclique et maximal par inclusion de D, et on décompose D en sous-ensembles Xi tels que X0 = {sources de D} et Xi>0 = {sources de Xi} jusqu’à Xk le dernier ensemble non-vide obtenu
- Chaque Xi est un stable de D car s’il y a un arc entre deux sommets d’un même Xi, l’un des deux n’est pas une source, donc on a une partition en stables et on peut prendre un sommet dans chaque partition en partant de la deernière pour construire un chemin
Théorème sur les out-branching dans les digraphes (énoncé)
Soit D un digraphe et r un sommet de D, D admet k out-branchings arc-disjoints de racine r si et seulement si ∀ X ⊆ V tel que r !∈ X, d-(X) ≥ k
Qu’est-ce qu’un digraphe k-arc-strong ?
D est k-arc-strong si ∀ F ⊆ A(D) tel que |F| ≤ k - 1, D - F est fortement connexe
Lien entre un graphe k-arc-strong et des chemins
Si un graphe D est k-arc-strong, alors pour toute paire de sommets, il y a k chemins arcs-disjoints entre les deux sommets
Qu’est-ce qu’un graphe k-arc-linked ?
D est k-arc-linked si ∀ x1, …, xk, y1, …, yk, il existe k chemin arcs-disjoints P1, …, Pk tels que deb(Pi) = xi et fin(Pi) = yi
Lien entre les propriétés k-arc-strong et k-arc-linked
D est k-arc-strong si et seulement si il est k-arc-linked
Définition d’un matroïde
Un matroïde M sur E un ensemble fini est un ensemble des parties de E tel que
- ∀ X ∈ M, ∀ Y ⊆ X, Y ∈ M (clos vers le bas)
- ∀ X, Y ∈ M avec |X| < |Y|, ∃ y ∈ Y \ X tel que X ∪ {y} ∈ M (augmentation)
Complexité du calcul d’une base d’un matroïde pour lequel on a un oracle
Avec un algorithme glouton, on peut calculer en temps polynomial une base de poids maximum pour un matroïde pour lequel on possède un oracle
Algorithme glouton qui calcule une base poids maximum pour un matroïde
- Trier U par poids décroissant
- X ← ∅
- Pour u ∈ U dans l’ordre
- Si X ∪ {u} est indépendant (oracle) :
- X ← X ∪ {u}
Retourner X
- X ← X ∪ {u}
- Si X ∪ {u} est indépendant (oracle) :
