Partie 2

Question 1

Voisinage entrant de y

Answer 1

N^-(y) = {x | xy ∈ A}

Question 2

Voisinage sortant de y

Answer 2

N⁺(y) = {z | yz ∈ A}

Question 3

Degré sortant de x

Answer 3

|N⁺(x)|

Question 4

Degré entrant de x

Answer 4

|N^-(x)|

Question 5

Lien entre le degré entrant et le degré sortant

Answer 5

Σ_x∈V d^-(x) = Σ_x∈V d⁺(x)

Question 6

Qu’est-ce qu’un sous-digraphe couvrant ?

Answer 6

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’

Question 7

Qu’est-ce qu’un sous-digraphe induit ?

Answer 7

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’

Question 8

Qu’est-ce qu’une arborescence sortante ?

Answer 8

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

Question 9

Qu’est-ce qu’un out-branching ?

Answer 9

Une arborescence sortante couvrante

Question 10

Qu’est-ce qu’un puits ?

Answer 10

Un sommet au degré sortant nul

Question 11

Qu’est-ce qu’une source ?

Answer 11

Un sommet au degré entrant nul

Question 12

Lien entre les graphes acycliques et les puits/sources

Answer 12

Tout digraphe acyclique admet une source et un puits

Question 13

Propriété des digraphes aycliques (énoncé)

Answer 13

D est acyclique si et seulement si il admet un tri topologique, c’est-à-dire une numération de ses sommets x₁, x₂, …, x_n telle que si x_ix_j ∈ A, alors i < j

Question 14

Propriété des digraphes aycliques (schéma de preuve)

Answer 14

⇐
un cycle doit contenir x_ix_j 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 x_i et x_j tel que i = max{k | x_k ∈ N^-(x)} et j = min{k | x_k ∈ N^-(x)}, et on sait que ça respecte la condition de tri topologique car acyclique

Question 15

Définition de la connexité forte

Answer 15

D est fortement connexe si ∀ x, y ∈ V, il existe un chemin orienté de x et y

Question 16

Définition d’une composante connexe

Answer 16

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é

Question 17

Lemme de décomposition en composantes fortement connexes (énoncé)

Answer 17

Les composantes fortement connexes partitionnent les sommets de D et le graphe obtenu en contractant toutes les composantes connexes de D est acyclique

Question 18

Lemme de décomposition en composantes fortement connexes (schéma de preuve)

Answer 18

• 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

Question 19

Qu’est-ce qu’une composante fortement connexe initiale ?

Answer 19

Une composante fortement connexe dans laquelle aucun arc ne rentre

Question 20

Qu’est-ce qu’une composante fortement connexe terminale ?

Answer 20

Une composante fortement connexe de laquelle aucun arc ne sort

Question 21

Qu’est-ce qu’un feedback arc set ?

Answer 21

Un ensemble d’arcs F de D tel que D(V, A - F) est acyclique

Question 22

Qu’est-ce qu’un tournoi ?

Answer 22

Un tournoi est l’orientation d’un graphe complet sans 2-cycle

Question 23

Théorème sur les tournois et les chemins hamiltoniens (énoncé)

Answer 23

Tout tournois contient un chemin hamiltonien

Question 24

Théorème sur les tournois et les chemins hamiltoniens (schéma de preuve)

Answer 24

Par induction sur n :
- pour n = 2, ok
- par hypothèse de récurrence, T \ {x} admet un chemin hamiltonien : x₁ → x₂ → … → x_{n - 1}
- si x → x₁, on a trouvé notre chemin hamiltonien
- sinon, i₀ = max{i | x_i → x} et si i₀ = n, on a aussi trouvé notre chemin hamiltonien
- sinon, i₀ < n et x → x_i0+1, et on trouve que x₁ → x₂ → … → x_i0 → x → x_i0+1 → … → x_{n - 1} est un chemin hamiltonien de T

Question 25

Théorème sur les tournois et les cycles hamiltoniens (énoncé)

Answer 25

Si T est un tournoi fortement connexe, alors il admet un cycle hamiltonien

Question 26

Théorème sur les tournois et les cycles hamiltoniens (schéma de preuve)

Answer 26

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 x₁, …, x_k de taille k dans T
- si x ∈ T \ C → x₁ on pose i₀ = max{i | x → x_i} et si i₀ < k, on peut insérer x dans C, sinon C domine x
- si x₁ → x ∈ T \ C on pose i₀ = max{i | x_i → x} et si i₀ < 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

Question 27

Qu’est-ce que α(D) ?

Answer 27

La taille du plus grand indépendant d’un digraphe D

Question 28

Théorème sur les partitions de digraphes en chemins (énoncé)

Answer 28

Tout digraphe D admet une
partition de ses sommets en au plus α(D) chemins

Question 29

Théorème sur les partitions de digraphes en chemins (schéma de preuve)

Answer 29

• Montrer plutôt que si D se partitionne en k > α(D) chemins de début Deb = {d₁, …, d_k}, 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 P₁, …, P_k une partition en k > α(D) chemins dont les début sont respsectivement d₁, …, d_k et puisque k > α(D), on sait qu’il existe d_i et d_j tels qu’il y a une arête entre eux
  • si |P_i| = 1, il suffit de prendre comme k chemins P₁, …, d_iP_j, …, P_k et on a fini
  • sinon, soit d’_i le premier sommet de P_i \ d_i et on peut appliquer l’hypothèse de récurrence sur P₁, …, P_i \ d’_i, …, P_k et Deb’ = {d₁, …, d’_i, …, d_k} : on suppose qu’il existe P’₁, …, P’_k-1 partitionnant D \ {d_i} et dont les débuts sont dans Deb’
    
    • si d’_i est le début d’un des chemins P’_i, on y rattache d_i et on a fini
    • sinon, d’_i n’est pas dans les début et d_j y est forcément, donc on rattache d_i à d_j et on a fini

Question 30

Qu’est-ce que χ(D) ?

Answer 30

Le nombre chromatique du digraphe D, c’est-à-dire aussi la taille d’une partition minimale en indépendants

Question 30

Théorème sur les chemins longs dans les digraphes (énoncé)

Answer 30

Tout digraphe D contient un chemin
sur au moins χ(D) sonnets

Question 31

Théorème sur les chemins longs dans les digraphes (preuve)

Answer 31

• On considère D’ un sous-digraphe couvrant, acyclique et maximal par inclusion de D, et on décompose D en sous-ensembles X_i tels que X₀ = {sources de D} et X_i>0 = {sources de X_i} jusqu’à X_k le dernier ensemble non-vide obtenu
• Chaque X_i est un stable de D car s’il y a un arc entre deux sommets d’un même X_i, 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

Question 32

Théorème sur les out-branching dans les digraphes (énoncé)

Answer 32

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

Question 33

Qu’est-ce qu’un digraphe k-arc-strong ?

Answer 33

D est k-arc-strong si ∀ F ⊆ A(D) tel que |F| ≤ k - 1, D - F est fortement connexe

Question 34

Lien entre un graphe k-arc-strong et des chemins

Answer 34

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

Question 35

Qu’est-ce qu’un graphe k-arc-linked ?

Answer 35

D est k-arc-linked si ∀ x₁, …, x_k, y₁, …, y_k, il existe k chemin arcs-disjoints P₁, …, P_k tels que deb(P_i) = x_i et fin(P_i) = y_i

Question 36

Lien entre les propriétés k-arc-strong et k-arc-linked

Answer 36

D est k-arc-strong si et seulement si il est k-arc-linked

Question 37

Définition d’un matroïde

Answer 37

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)

Question 38

Complexité du calcul d’une base d’un matroïde pour lequel on a un oracle

Answer 38

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

Question 39

Algorithme glouton qui calcule une base poids maximum pour un matroïde

Answer 39

• 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