Partie 2 Flashcards

1
Q

Voisinage entrant de y

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Voisinage sortant de y

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Degré sortant de x

A

|N+(x)|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Degré entrant de x

A

|N-(x)|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Lien entre le degré entrant et le degré sortant

A

Σx∈V d-(x) = Σx∈V d+(x)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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’

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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’

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Qu’est-ce qu’une arborescence sortante ?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

Une arborescence sortante couvrante

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Qu’est-ce qu’un puits ?

A

Un sommet au degré sortant nul

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Qu’est-ce qu’une source ?

A

Un sommet au degré entrant nul

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Lien entre les graphes acycliques et les puits/sources

A

Tout digraphe acyclique admet une source et un puits

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A


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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Définition de la connexité forte

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Définition d’une composante connexe

A

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é

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

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

18
Q

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

A
  • 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
19
Q

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

A

Une composante fortement connexe dans laquelle aucun arc ne rentre

20
Q

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

A

Une composante fortement connexe de laquelle aucun arc ne sort

21
Q

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

A

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

22
Q

Qu’est-ce qu’un tournoi ?

A

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

23
Q

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

A

Tout tournois contient un chemin hamiltonien

24
Q

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

A

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

25
Théorème sur les tournois et les cycles hamiltoniens (énoncé)
Si T est un tournoi fortement connexe, alors il admet un cycle hamiltonien
26
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
27
Qu'est-ce que α(D) ?
La taille du plus grand indépendant d'un digraphe D
28
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
29
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
30
Qu'est-ce que χ(D) ?
Le nombre chromatique du digraphe D, c'est-à-dire aussi la taille d'une partition minimale en indépendants
30
Théorème sur les chemins longs dans les digraphes (énoncé)
Tout digraphe D contient un chemin sur au moins χ(D) sonnets
31
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
32
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
33
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
34
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
35
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
36
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
37
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)
38
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
39
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