Partie 3

Question 1

Définition d’un cycle

Answer 1

Chemin fermé sans répétition d’arêtes

Question 2

Définition d’un cycle minimal

Answer 2

Cycle sans répétition de sommets

Question 3

Définition d’un circuit

Answer 3

Ensemble des arêtes d’un cycle minimal

Question 4

Définition d’une coupe

Answer 4

Ensemble des arêtes joignant les deux parties d’une partition V = A ⨄ B

Question 5

Définition d’un co-circuit (ou coupe minimale)

Answer 5

Coupe qui n’est pas incluse dans une autre coupe

Question 6

Propriété partagée par les circuits et les co-circuits

Answer 6

Ils sont incomparables par inclusion

Question 7

Propriété des coupes minimales (énoncé)

Answer 7

Une coupe est minimale si et seulement si G[A’] et G[B’] sont des sous-graphes connexes de G, où A’ et B’ sont les sommets de A et B extrémités d’arêtes de la coupe respectivement

Question 8

Propriété des coupes minimales (schéma de preuve)

Answer 8

Si une des deux partitions est partagée en plusieurs composantes connexes, il est possible de faire rentrer l’autre partition dans celle-ci afin d’obtenir deux partitions connexes
[A₁] [B] [A₂] → [A₁] [B ∪ A₂]

Question 9

Définition d’un arbre couvrant

Answer 9

Sous-graphe sans cycle (arbre) qui connecte tous les sommets entre eux

Question 10

Définition d’une forêt couvrante

Answer 10

Union d’arbres couvrants de chaque composante connexe

Question 11

Définition d’une base

Answer 11

Ensemble des arêtes d’un arbre couvrant ou d’une forête couvrante

Question 12

Définition d’une cobase

Answer 12

Complémentaire dans E d’une base

Question 13

Propriété des arbres couvrants

Answer 13

Tous les arbres couvrants ou forêts couvrantes d’un graphe ont le même nombre d’arêtes, on l’appelle le rang

Question 14

Formule du rang d’un graphe

Answer 14

r(G) = |V| - c(G) où c(G) est le nombre e composantes connexes de G

Question 15

Définition d’un graphe planaire

Answer 15

Graphe qui peut être dessiné dans le plan sans croisement, c’est-à-dire de sorte que :
- toute arête est représentée par une courbe du plan affine
- deux arêtes distinctes ne se rencontrent pas sauf en leurs potentielles extrêmités communes

Question 16

Définition d’un plongement

Answer 16

(G, σ) est un plongement de G (ou G est un graphe sous-jacent de (G, σ)) si c’est une classe d’équivalence de dessins de G sur la sphère ou dans le plan

Question 17

Définition de l’équivalence pour deux dessins

Answer 17

Deux dessins d’un graphe planaire représentent le même plongement (sont équivalents) si on peut passer de l’un à l’autre continuement en les considérant sur une sphère

Question 18

Unicité du plongement d’un graphe planaire

Answer 18

Le plongement d’un graphe planaire n’est en général pas unique

Question 19

Définition du plongement dual

Answer 19

(G, σ)* le plongement dual de (G, σ) est (G’, σ’) défini et dessiné tel que :
- les sommets de G’ sont les régions délimitées par le dessin de (G, σ)
- les arêtes de G’ sont en bijection avec les arêtes de G telles que chaque arête séparant deux régions de (G, σ) est une arête reliant deux sommets de (G’, σ’)

Question 20

Plongements dual de deux dessins d’un même plongement

Answer 20

Les dessins obtenus avec les duaux de deux dessins d’un même plongement sont équivalents (appartiennent au même plongement dual)

Question 21

Composition de dualité de plongement

Answer 21

• Pour un graphe planaire connexe, ((G, σ)*)* = (G, σ)
• Pour un graphe planaire non-connexe, ((G, σ)*)* est connexe avec un sommet de chaque composante connexe confondu en un seul sommet

Question 22

Définition d’un isthme

Answer 22

Arête qui déconnecte le graphe si elle est supprimée

Question 23

Correspondance d’éléments entre le plongement et son dual

Answer 23

• Isthme dans le plongement → boucle dans le dual
• Boucle dans le plongement → isthme dans le dual
• Plongement arbre → dual constitué de boucles

Question 24

Correspondance d’éléments entre G et G’ où (G’, σ’) est le dual de (G, σ) plongement de G (énoncé)

Answer 24

• Circuit de G → cocircuits de G’
• Cocircuit de G → circuits de G’
• Bases de G → cobases de G’
• Cobases de G → bases de G’

Question 25

Correspondance d’éléments entre G et G’ où (G’, σ’) est le dual de (G, σ) plongement de G (schéma de preuve)

Answer 25

• Circuits et cocircuits : les circuits séparent des régions intérieures et extérieures au circuits donc c’est une coupe dans le dual
• Bases et cobases : un arbre couvrant trace un chemin séparant les différentes régions, donc pour y accéder il faut utiliser les arêtes qui ne sont pas dans l’arbre (et qui sont donc dans son complémentaire)

Question 26

Propriété reliant les cycles et les abres couvrants dans les graphes connexes quelconques (énoncé)

Answer 26

Un sous-graphe de G a un cycle si et seulement si il n’est sous-graphe d’aucun arbre couvrant de G

Question 27

Propriété reliant les cycles et les abres couvrants dans les graphes connexes quelconques (schéma de preuve)

Answer 27

⇒ un arbre n’a pas de cycle
⇐ un sous-graphe sans cycle peut-être étendu en arbre couvrant

Question 28

Reformulation de la propriété reliant les cycles et les abres couvrants dans les graphes connexes quelconques

Answer 28

A ⊆ E contient un circuit si et seulement si pour toute base B, A !⊆ B

Question 29

Propriété reliant les coupes et les abres couvrants dans les graphes connexes quelconques (énoncé)

Answer 29

A ⊆ E contient un coupe de G si et seulement si pour tout arbre couvrant de H ayant comme ensemble d’arêtes B, on a A ∩ B != ∅

Question 30

Propriété reliant les coupes et les abres couvrants dans les graphes connexes quelconques (schéma de preuve)

Answer 30

Montrer que A coupe ⇔ G\A non-connexe
⇒ un arbre couvrant doit couvrir G donc relier les composantes connexes de G\A donc A ∩ B != ∅
⇐ si G\A connexe, un arbre couvrant de G\A couvre G donc A ∩ B = ∅

Question 31

Reformulation de la propriété reliant les coupes et les abres couvrants dans les graphes connexes quelconques

Answer 31

A ⊆ E contient un cocircuit si et seulement si pour toute cobase B, A !⊆ B

Question 32

Définition d’un dépendant pour un graphe

Answer 32

Partie A ⊆ E contenant un circuit

Question 33

Définition d’un dépendant pour un matroïde

Answer 33

Partie A ⊆ E contenant un circuit

Question 34

Définition d’un indépendant pour un graphe

Answer 34

Partie A ⊆ E qui n’est pas un dépendant

Question 35

Définition d’un indépendant pour un matroïde

Answer 35

Partie A ⊆ E qui n’est pas un dépendant

Question 36

Définition d’un dépendant du dual pour un graphe

Answer 36

Partie A ⊆ E contenant un cicorcuit

Question 37

Définition d’un indépendant du dual pour un graphe

Answer 37

Partie A ⊆ E qui n’es pas un dépendant du dual

Question 38

(Diagramme fondamental) Comment passer des circuits aux dépendants ?

Answer 38

Sur-ensembles

Question 39

(Diagramme fondamental) Comment passer des dépendants aux indépendants ?

Answer 39

Négation

Question 40

(Diagramme fondamental) Comment passer des indépendants aux bases ?

Answer 40

Maximaux

Question 41

(Diagramme fondamental) Comment passer des bases aux cobases ?

Answer 41

Complémentaire

Question 42

(Diagramme fondamental) Comment passer des cobases aux indépendants du dual ?

Answer 42

Sous-ensembles

Question 43

(Diagramme fondamental) Comment passer des indépendants du dual aux dépendants du dual?

Answer 43

Négation

Question 44

(Diagramme fondamental) Comment passer des dépendants du dual aux cocircuits ?

Answer 44

Minimaux

Question 45

(Diagramme fondamental) Comment passer des cocircuits aux dépendants du dual ?

Answer 45

Sur-ensembles

Question 46

(Diagramme fondamental) Comment passer des dépendants du dual aux indépendants du dual ?

Answer 46

Négation

Question 47

(Diagramme fondamental) Comment passer des indépendants du dual aux cobases ?

Answer 47

Maximaux

Question 48

(Diagramme fondamental) Comment passer des cobases aux bases ?

Answer 48

Complémentaire

Question 49

(Diagramme fondamental) Comment passer des bases aux indépendants ?

Answer 49

Sous-ensembles

Question 50

(Diagramme fondamental) Comment passer des indépendants aux dépendants ?

Answer 50

Négation

Question 51

(Diagramme fondamental) Comment passer des dépendants aux circuits ?

Answer 51

Minimaux

Question 52

Axiomes des circuits d’un matroïde (définition d’un circuit)

Answer 52

L’ensemble C des parties de E fini est l’ensembles des circuits d’un matroïde si et seulement si C vérifie les axiomes suivants :
- ∅ !∈ C
- Si C₁, C₂ ∈ C et C₁ ⊆ C₂ alors C₁ = C₂ (propriété de minimalité ou d’incomparabilité)
-Si C₁, C₂ ∈ C et e ∈ C₁ ∩ C₂, alors il existe C₃ ∈ C tel que C₃ = (C₁ ∪ C₂){e} (propriété d’élminitation)

Question 53

Définition d’une base pour un matroïde

Answer 53

Indépendant maximal pour l’inclusion

Question 54

Définition d’une cobase pour un matroïde

Answer 54

Complémentaire d’une base

Question 55

Définition d’un cocircuit pour un matroïde

Answer 55

Partie minimale pour l’inclusion contenuee dans aucune cobase

Question 56

Comment définir les dépendants à partir des circuits et inversement ?

Answer 56

D = {A ⊆ E | ∃ c ∈ C, c ⊆ A}
C = {A ⊆ E | A ∈ D et A est minimal pour l’inclusion dans D}

Question 57

Comment définir les indépendants à partir des dépendants et inversement ?

Answer 57

I = {A ⊆ E | A !∈ D}
D = {A ⊆ E | A !∈ I}

Question 58

Comment définir les bases à partir des indépendants et inversement ?

Answer 58

B = {A ⊆ E | A ∈ I et A est maximal pour l’inclusion dans I}
I = {A ⊆ E | ∃ b ∈ B, A ⊆ b}

Question 59

Comment définir les cobases à partir des bases et inversement ?

Answer 59

B* = {A ⊆ E | E \ A ∈ B}
B = {A ⊆ E | E \ A ∈ B*}

Question 60

Comment définir les cobases à partir des indépendants du dual et inversement ?

Answer 60

B* = {A ⊆ E | A ∈ I* et A est maximal pour l’inclusion dans I}
I = {A ⊆ E | ∃ b ∈ B*, A ⊆ b}

Question 61

Comment définir les indépendants du dual à partir des dépendants du dual et inversement ?

Answer 61

I* = {A ⊆ E | A !∈ D}
D = {A ⊆ E | A !∈ I*}

Question 62

Comment définir les dépendants dual à partir des cocircuits et inversement ?

Answer 62

D* = {A ⊆ E | ∃ c ∈ C, c ⊆ A}
C = {A ⊆ E | A ∈ D* et A est minimal pour l’inclusion dans D*}

Question 63

Soit I un indépendant mais pas I ∪ {e}, que sait-on de I ∪ {e} ? (énoncé)

Answer 63

Pour un indépendant I, si I ∪ {e} n’est pas indépendant, alors il existe un unique circuit contenu dans I ∪ {e}

Question 64

Soit I un indépendant mais pas I ∪ {e}, que sait-on de I ∪ {e} ? (schéma de preuve)

Answer 64

Si ajouter {e} rajoute plusieurs circuits, c’est qu’il y avait déjà au moins un circuit dans I, ce qui n’est pas possible

Question 65

Théorème fondamental de la dualité des matroïdes

Answer 65

Soit C l’ensemble des circuits d’un matroïde M sur E, alors l’ensemble C* des cocircuits est l’ensemble des circuits d’un matroïde

Question 66

Qu’est-ce que le matroïde dual de M ?

Answer 66

Le matroïde noté M* dont les circuits sont les cocircuits de M

Question 67

Composition de dualité de matroïdes

Answer 67

(M) = M

Question 68

À quoi correspondent les circuits de M dans M* ?

Answer 68

Aux co-circuits

Question 69

À quoi correspondent les cocircuits de M dans M* ?

Answer 69

Aux circuits

Question 70

À quoi correspondent les dépendants de M dans M* ?

Answer 70

Aux dépendants du dual

Question 71

À quoi correspondent les dépendants du dual de M dans M* ?

Answer 71

Aux dépendants

Question 72

À quoi correspondent les indépendants de M dans M* ?

Answer 72

Aux indépendants du dual

Question 73

À quoi correspondent les indépendants du dual de M dans M* ?

Answer 73

Aux indépendants

Question 74

À quoi correspondent les bases de M dans M* ?

Answer 74

Aux cobases

Question 75

À quoi correspondent les cobases de M dans M* ?

Answer 75

Aux bases

Question 76

Correspondance entre les circuits d’un graphe et d’un matroïde (énoncé)

Answer 76

L’ensemble des circuits de G est l’ensemble des circuits d’un matroïde sur E l’ensemble des arêtes de G

Question 77

Correspondance entre les circuits d’un graphe et d’un matroïde (schéma de preuve)

Answer 77

• Axiome 1 trivial
• Axiome 2 ok car incomparabilité par l’inclusion
• Axiome 3 ok car si on prend les deux extrêmités de l’arête en commun et qu’on essaye de les relier sans passer par celle-ci, on obtient un circuit inclu ans l’union des deux circuits initiaux

Question 78

Qu’est-ce que le matroïde des cycles de G ?

Answer 78

Le matroïde sur l’ensemble E des arêtes de G, qui a le même ensemble de circuits que G

Question 79

Qu’est-ce qu’un matroïde graphique ?

Answer 79

Un matroïde qui est le matroïde des cycles d’un graphe

Question 80

Correspondance entre les cocircuits d’un graphe et d’un matroïde (énoncé)

Answer 80

L’ensemble des cocircuits du grapcocircuitshe G est l’ensemble des cocircuits du matroïde M(G) sur E

Question 81

Correspondance entre les cocircuits d’un graphe et d’un matroïde (schéma de preuve)

Answer 81

Les cocircuits des graphes et des matroïdes se déduisent de la même façon à partir des circuits, et les circuits sont les mêmes

Question 82

Correspondance entre les bases d’un graphe et d’un matroïde (énoncé)

Answer 82

L’ensemble des bases du graphe G est l’ensemble des bases du matroïde M(G) sur E

Question 83

Correspondance entre les bases d’un graphe et d’un matroïde (schéma de preuve)

Answer 83

Les bases des graphes et des matroïdes se déduisent de la même façon à partir des circuits, et les circuits sont les mêmes

Question 84

Caractérisation des cocircuits d’un graphe (énoncé)

Answer 84

L’ensemble des cocircuits d’un graphe vérifie l’axiomatique des cricuits d’un matroïde

Question 85

Caractérisation des cocircuits d’un graphe (schéma de preuve)

Answer 85

• Preuve immédiate avec le théorème de dualité des matroïdes et la correspondance entre les cocircuits de G et de M(G)
• Preuve non immédiate :
  
  • Axiome 1 trivial
  • Axiome 2 ok car incomparabilité par l’inclusion
  • Axiome 3 ok car si on prend les deux partitions (A₁, A’₁) et (A₂, A’₂) de chacune des deux coupes et qu’on calcule (A₁ ∩ A₂) ∪ (A’₁ ∩ A’₂) et (A₁ ∩ A’₂) ∪ (A’₁ ∩ A₂), on obtient d’une part les deux extrêmités de l’arête e en commun, et d’autre part le reste des sommets, ce qui nous donne une nouvelle coupe qui ne contient pas e

Question 86

Correspondance entre le matroïde dual et le plongement dual

Answer 86

Soit G un graphe planaire, soit (G, σ) un plongement de ce graphe, et soit (G’, σ’) le plongement dual de ce graphe, alors M(G)* = M(G’)

Question 87

Qu’est-ce que le matroïde des coupes ou matroïde des cocyles de G ?

Answer 87

Le matroïde M(G)* dual du matroïde des cycles M(G)

Question 88

Caractérisation de Whitney des graphes planaires

Answer 88

Soit G un graphe, alors G est planaire si et seulement si le matroïde M(G)* est graphique

Question 89

Qu’est-ce qu’un Whitney flip ?

Answer 89

Une transformation du type suivant :
- On identifie deux sommets de deux composantes connexes distinctes, ou alors inversement on sépare une composante connexe en deux au niveau d’un sommet d’articulation
- Pour deux sommets u et v d’une même composante connexe dont la suppresion la déconnecte, on sépare la composante en deux composantes G’ et G’’ dans lesquelles u devient u’ dans G’ et u’’ dans G’’, et v devient v’ dans G’ et v’’ dans G’’, puis on recolle les deux composantes en identifiant u’ et v’’ d’un côté, et u’’ et v’ de l’autre

Question 90

Théorème des Whitney flips

Answer 90

Soient G et G’ deux graphes dont les ensembles d’arêtes sont labélisés par le même ensemble E et M(G) et M(G’) sont définis sur ce même ensemble E, alors M(G) = M(G’) si et seulement si on peut passer de G à G’ par une suite de Whitney flips

Question 91

Exemple du théorème des Whitney flips

Answer 91

Si une coupe est constituée de deux arêtes, alors les labels de ces arêtes peuvent être échangés sans changer le matroïde des cycles

Question 92

Quand est-ce qu’un graphe est déterminé par son matroïde des cycles ? (énoncé)

Answer 92

Un graphe G est déterminé par son matroïde des cycles si et seulement si il est 3-connexe

Question 93

Quand est-ce qu’un graphe est déterminé par son matroïde des cycles ? (schéma de preuve)

Answer 93

Un graphe 3-connexe de permet aucun Whitney flip

Question 94

Axiomes des indépendants d’un matroïde (énoncé)

Answer 94

L’ensemble I des parties de E fini est l’ensembles des indépendants d’un matroïde si et seulement si I vérifie les axiomes suivants :
- ∅ ∈ I
- Si I₁ ∈ I et I₂ ⊂ I₁, alors I₂ ∈ I (propriété d’hérédité)
- Si I₁, I₂ ∈ I et | I₁| < | I₂|, ∃ e ∈ I₂\I₁ tel que I₁ ∪ {e} ∈ I (propriété d’augmentation)

Question 95

Axiomes des indépendants d’un matroïde ⇒ axiomes des circuits d’un matroïde (schéma de preuve)

Answer 95

• Axiome 1 trivial
• Axiome 2 trivial
• Axiome 3 : par contradiction
  
  • supposer que C₁ ∪ C₂ \ {e} ne contient pas de circuit
  • prendre f ∈ C₂ \ C₁ et X ⊆ C₁ ∪ C₂ tel que C₂ \ f ⊆ X, X indépendant et X maximal avec ces propriétés
  • prendre g ∈ C₁ != f et tel que g !∈ X
  • |X| ≤ |C₁ ∪ C₂| \ {f ∪ g} = |C₁ ∪ C₂| - 2 < |C₁ ∪ C₂| \ e qui est indépendant par hypothèse
  • appliquer le troisième axiome des indépendants pour trouver h ∈ (C₁ ∪ C₂) \ e \ X tel que X ∪ h est indépendant, ce qui est une contradiction

Question 96

Axiomes des circuits d’un matroïde ⇒ axiomes des indépendants d’un matroïde (schéma de preuve)

Answer 96

• Axiome 1 trivial
• Axiome 2 trivial
• Axiome 3 : récurrence sur |X ∪ Y| avec X et Y des indépendants tels que |X| < |Y|
  
  • cas de base (X ∪ Y) indépendant
  • sinon C le cycle de |X ∪ Y| tel que |C \ Y| est minimal, e ∈ C \ X, f ∈ C \ Y et Y’ = (Y \ e) ∪ f qu’on prouve indépendant par l’absurde
  • |X| < |Y’| = |Y| et |X ∪ Y’| < |X ∪ Y| donc on peut appliquer la récurrence : ∃ e ∈ Y’\X ⊆ Y\X tel que X ∪ {e} ∈ I

Question 97

Axiomes des bases d’un matroïde

Answer 97

L’ensemble B des parties de E fini est l’ensembles des bases d’un matroïde si et seulement si B vérifie les axiomes suivants :
- ∅ !∈ B
- Si B₁, B₂ ∈ B et x ∈ B₁ \ B₂, ∃ y ∈ B₂ \ B₁ tel que ∈ (B₁ \ x) ∪ y ∈ B (propriété d’échange)

Question 98

Propriété des bases d’un matroïde (énoncé)

Answer 98

Les bases d’un matroïde sont équi-cardinales

Question 99

Propriété des bases d’un matroïde (schéma de preuve)

Answer 99

Les bases sont des indépendants maximaux, si elles ne sont pas de la même taille, on peut en prendre deux et leur appliquer la propriété d’augmentation des indépendants qui contredit alors leur maximalité

Question 100

Qu’est-ce que le rang d’une partie A de E dans M un matroïde sur E ?

Answer 100

Le rang r_M(A) est le cardinal d’un indépendant contenu dans A et maximal pour l’inclusion : r_M(A) = max{|Y| | Y ⊆ A, Y ∈ I}

Question 101

Qu’est-ce que le rang d’une partie stricte X de E dans M* un matroïde dual sur E ?

Answer 101

Pour X ⊂ E, r_M*(X) = |X| + r_M(E\X) - r_M

Question 102

Qu’est-ce que le rang d’un matroïde M ?

Answer 102

Le rang r(M) d’un matroïde est le rang de E dans M r_M(E), c’est-à-dire la taille d’un indépendant maximal (ou base)

Question 103

Que vaut le rang du matroïde dual M* ?

Answer 103

r(M*) = |E| - r(M), c’est-à-dire la taille d’un co-base

Question 104

Correspondance entre le rang des graphes et des matroïdes graphiques

Answer 104

Le rang de G(A) obtenu à partir de G en ne gardant que les arêtes de A est égal au rang de A dans le matroïde graphique M(G), et en particulier le rang d’un graphe G et de son matroïde graphique M(G) sont égaux

Question 105

Axiomes de la fonction rang d’un matroïde

Answer 105

La fonction r de 2^E les parties de E fini dans les entiers naturels est la fonction de rang d’un matroïde si et seulement si r vérifie les axiomes suivants :
- ∀ X ⊆ E, 0 ≤ r(X) ≤ |X|
- ∀ X ⊆ Y, r(X) ≤ r(Y) (propriété de croissance
- ∀ X, Y ⊂ E, r(X ∪ Y) + r(X ∩ Y) ≤ r(X) + r(Y) (inégalité sous-modulaire)

Question 106

Expression de l’ensemble des indépendants en fonction du range

Answer 106

I = {A ⊆ E | r(A) = |A|}

Question 107

Qu’est-ce que les fermés du matroïe M ?

Answer 107

Ce sont les parties A ⊆ E telles que si C est un circuit tel que e ∈ C et C \ {e} ⊆ A, alors C ⊆ A

Question 108

Comment caractériser les cocircuits à partir des fermés d’un matroïde ?

Answer 108

C* = {E \ A ⊆ E | A est un fermé de M et r_M(A) = r(M) - 1}

Question 109

Contexte de l’algorithme Glouton

Answer 109

Instance : Ensemble I de parties d’un ensemble fini E, fonction de poids w de E dans {R} telle que pour X ∈ I, w(X) = Σ_{x ∈ X} w(x), et w(∅) = 0
Problème : Trouver un élément de I de poids maximal

Question 110

Algorithme Glouton (entrée, sortie, algorithme)

Answer 110

• Entrée : I ⊆ 2^E, w : E → {R}
• Sortie : X ∈ I
• Glouton(I, w) :
  
  • X₀ = ∅
  • j = 0
  • Tant qu’il existe e ∈ E\X_j tel que X_j ∪ {e} ∈ I :
    
    • Choisir un tel e_j+1 de poids maximum
    • X_j+1 = X_j ∪ {e_j+1}
    • j = j + 1
  • Renvoyer X_j

Question 111

Axiomes des indépendants d’un matroïde

Answer 111

L’ensemble I des parties de E fini est l’ensembles des indépendants d’un matroïde si et seulement si I vérifie les axiomes suivants :
- ∅ ∈ I
- Si I₁ ∈ I et I₂ ⊂ I₁, alors I₂ ∈ I (propriété d’hérédité)
- Pour toute fonction de poids w : E → {R}, l’algorithme Glouton renvoie un élément maximal de I (pour l’inclusion) et de poids maximal (parmi les éléments de I maximaux pour l’inclusion)

Question 112

Dans quel cas l’agorithme Glouton renvoie-t-il une sortie optimale quelle que soit la fonction de poids pour un ensemble I héréditaire ?

Answer 112

Lorsque I est l’ensemble des indépendants d’un matroïde

Question 113

Définition d’un matroïde vectoriel sur le corps K (énoncé)

Answer 113

Soit U une matrice à valeur dans K dont les colonnes sont labélisées par l’ensemble E, c’est-à-dire que les colonnes de U forment un ensemble de vecteurs {u_e | e ∈ E}, l’ensemble des A ⊆ E tels que la famille de vecteurs u_a est linéairement dépendante forme l’ensemble des dépendants d’un matroïe sur E appelé matroïde des dépendances des colonnes de U et noté M(U)

Question 114

Définition d’un matroïde vectoriel sur le corps K (schéma de preuve)

Answer 114

• Puisque les matroïdes vectoriels sont définis à partir des dépendants, considérer les circuits commes les dépendants minimaux pour l’inclusion et prouver les trois axiomes des circuits de matroïdes :
  
  • Axiome 1 trivial
  • Axiome 2 : ok car incomparables pour l’inclusion
  • Axiome 3 : ok car
    
    • considérer deux dépendants minimaux Σ_e∈E α_eu_e = 0 et Σ_e∈E α’_eu_e = 0
    • prendre f appartenant aux deux et construire α_fΣ_e∈E α_eu_e - α’_fΣ_e∈E α’_eu_e = Σ_e∈E (α_fα’_e - α_‘fα_e)u_e = 0
    • le coefficient de u_f est nul et tous les autres non-nuls sont toujours non-nuls, donc c’est fini

Question 115

Définition d’un dépendant d’un matroïde vectoriel sur K

Answer 115

Pour toute relation de dépendance linéaire Σ_e∈E α_eu_e = 0 entre vecteurs colonnes de U, avec α_e ∈ K pour tout e (non tous nuls), l’ensemble A des e ∈ E tels que α_e est non-nul est un dépendant du matroïde M(U)

Question 116

Définition alternative d’un matroïde vectoriel : à partir des indépendants

Answer 116

M(U) est le matroïde dont l’ensemble des indépendants est l’ensemble des A ⊆ E tels que la famille de vecteus (u_a)_a∈A est linéairement indépendante

Question 117

Définition alternative d’un matroïde vectoriel : à partir des bases

Answer 117

M(U) est le matroïde dont l’ensemble des bases est l’ensemble des A ⊆ E tels que la famille de vecteus (u_a)_a∈A forme une base de l’espace vectoriel engendré par la famille des (u_e)_e∈E

Question 118

Définition alternative d’un matroïde vectoriel : à partir du rang

Answer 118

M(U) est le matroïde dont la fonction de rang r est définie, pour A ⊆ E, par : r(A) est la dimension de l’espace engendré par la famille de vecteurs (u_a)_a∈A, c’est-à-dire le rang de la sous-matrice de U formée par les colonnes de A

Question 119

Définition alternative d’un matroïde vectoriel : à partir des circuits

Answer 119

M(U) est le matroïde dont l’ensemble des circuits est l’ensemble des A ⊆ E tels que la famille de vecteus (u_a)_a∈A est linéairement dépendante et toute sous-famille est linéairement indépendante

Question 120

Représentation de Whitney d’un matroïde vectoriel

Answer 120

Réécriture des vecteurs de la matrice U sur une base qui est une base de M(U) et qui permet d’obtenir une matrice de la forme [I|N] avec I la matrice identité r × r et N une matrice r × (n - r) où r est le rang du matroïde et n = |E|

Question 121

Représentation affine dans le cas réel d’un matroïde vectoriel

Answer 121

Soit K = {R}, soit Vec l’espace engendré par (u_e)_e∈E, et considérons un hyperplan affine de Vec (c’est-à-dire un ensemble de points d’équation Σ_1≤i≤r α_ib_i = 1) en supposant qu’aucun vecteur u_e n’est parallèle à cet hyperplan, alors chaque vecteur de (u_e)_e∈E peut être remplacé par un vecteur dont l’extrêmité appartient à cet hyperplan sans changer le matroïdes des dépendance

Question 122

Comment sont traditionnellement représentés les circuits dans la représentation affine d’un matroïde vectoriel sur un hyperplan de dimension 2 ?

Answer 122

Par des droites (points alignés)

Question 123

Comment sont traditionnellement représentés les bases dans la représentation affine d’un matroïde vectoriel sur un hyperplan de dimension 2 ?

Answer 123

Par des circuits non-alignés

Question 124

Lien entre les matroïdes graphiques et les matroïdes vectoriels (énoncé)

Answer 124

Les matroïdes graphiques sont vectoriels sur tout K

Question 125

Lien entre les matroïdes graphiques et les matroïdes vectoriels (construction)

Answer 125

Soit G = (V, E) un graphe tel que V = {v₁, …, v_k}, on considère v₁, …, v_k comme la base canonique d’un espace vectoriel sur K et pour toute arête e ∈ E d’extrêmités (v_i, v_j), on définit le vecteur correspondant u_e = v_j - v_i et on obtient U la matrice formée par les u_e, pour laquelle M(U) = M(G)

Question 126

Lien entre les matroïdes graphiques et les matroïdes vectoriels (schéma de preuve)

Answer 126

Il suffit de montrer que les cycles de M(G) et de M(U) sont les mêmes : pour toute arête formant un cycle, la somme des vecteur est bien nulle (~ somme telescopiqie), et réciproquement

Question 127

Définition du matroïde uniforme par ses bases

Answer 127

Soit E un ensemble fini de taille n, et soit r un entier naturel tel que 1 ≤ r ≤ n, le matroïde uniforme de rang r et de taille n sur E est défini par la propriété suivante : ses bases sont toutes les parties de E de taille r

Question 128

Définition du matroïde uniforme par ses circuits

Answer 128

Soit E un ensemble fini de taille n, et soit r un entier naturel tel que 1 ≤ r ≤ n, le matroïde uniforme de rang r et de taille n sur E est défini par la propriété suivante : ses circuits sont toutes les parties de E de taille r + 1

Question 129

Définition du matroïde uniforme par ses cobases

Answer 129

Soit E un ensemble fini de taille n, et soit r un entier naturel tel que 1 ≤ r ≤ n, le matroïde uniforme de rang r et de taille n sur E est défini par la propriété suivante : ses cobases sont toutes les parties de E de taille n - r

Question 130

Définition du matroïde uniforme par ses cocircuits

Answer 130

Soit E un ensemble fini de taille n, et soit r un entier naturel tel que 1 ≤ r ≤ n, le matroïde uniforme de rang r et de taille n sur E est défini par la propriété suivante : ses cocircuits sont toutes les parties de E de taille n - r + 1

Question 131

Définition du matroïde uniforme par ses inépendants

Answer 131

Soit E un ensemble fini de taille n, et soit r un entier naturel tel que 1 ≤ r ≤ n, le matroïde uniforme de rang r et de taille n sur E est défini par la propriété suivante : ses indépendants sont toutes les parties de E de taille ≤ r

Question 132

Définition du matroïde uniforme par ses dépendants

Answer 132

Soit E un ensemble fini de taille n, et soit r un entier naturel tel que 1 ≤ r ≤ n, le matroïde uniforme de rang r et de taille n sur E est défini par la propriété suivante : ses dépendants sont toutes les parties de E de taille > r

Question 133

Dualité du matroïde uniforme de taille n et de rang r

Answer 133

U*_{r, n} = U_{n-r, r}

Question 134

Lien entre le matroïde uniforme et les matroïdes vectoriels

Answer 134

Le matroïde uniforme U_{r, n} est vectoriel sur {R} et s’obtient à partir de n vecteur en position générale dans un espace de dimension r

Question 135

Quel est le plus petit exemple de matroïde non-graphique ?

Answer 135

Le matroïde uniforme U_2,4

Question 136

Qu’est-ce que le matroïde de Fano ?

Answer 136

C’est le matroide des vecteurs de ({Z}/2{Z}) \ {0}

Question 137

Quand est-ce que le matroïde U_{2, 4} est un matroïde vectoriel ?

Answer 137

Sur {R}

Question 138

Quand est-ce que le matroïde de Fano est un matroïde vectoriel ?

Answer 138

Sur {Z}/2{Z}

Question 139

Quand est-ce que le matroïde non-Pappus est un matroïde vectoriel ?

Answer 139

Jamais

Question 140

Théorème de Pappus

Answer 140

Si on prend deux segments dans le plan et qu’on dessine trois points sur chacun d’entre eux puis qu’on les relie, les trois points des intersections formées par les reliures sont alignés

Question 141

Qu’est-ce que le matroïde non-Pappus ?

Answer 141

Le matroïde duquel les circuits sont exactement ceux de la configuration de Pappus, sauf que le triplet de point du milieu forme un indépendant et pas un circuit, ce qui signifie qu’ils ne sont pas alignés dans la représentation affine

Question 142

Définition alternative d’un matroïde vectoriel : à partir des cocircuits

Answer 142

M(U) est le matroïde dont l’ensemble des cocircuits sont déterminés de la façon suivante : soit A ⊆ E tel que le sous-espace Vec_A engendré par (u_a)_a∈A est de dimension rang(U) - 1, et tel que Vec_A ∩ E = A, alors E \ A est un cocircuit

Question 143

Propriété du matroïde dual d’un matroïde vectoriel

Answer 143

Le matroïde dual d’un matroïde vectoriel est également un matroïde vectoriel

Question 144

Comment obtenir le matroïde dual d’un matroïde vectoriel ?

Answer 144

Soit M(U) un matroïde vectoriel, il suffit de transformer U pour obtenir sa représentation de Whitney U’ = [I|N], et on a alors M(U)* = [-I|^tN] où ^tN est la transposée (n - r) × r de la matrice N

Question 145

Qu’est-ce qu’une boucle (ou loop) du point de vue des matroïdes ?

Answer 145

Un élément de E qui n’appartient à aucune base, et qui forme donc un circuit à lui tout seul

Question 146

Qu’est-ce qu’un isthme (ou coloop) du point de vue des matroïdes ?

Answer 146

Un élément de E qui n’appartient à toutes les bases, et qui forme donc un cocircuit à lui tout seul

Question 147

Lien entre les boucles et les isthmes

Answer 147

Les boucles et les isthmes sont des éléments duaux, c’est-à-dire que A est une boucle de M si et seulement si c’est un isthme de M* et inversement

Question 148

Boucles dans le cas graphique

Answer 148

Les boucles de M(G) sont les boucles de G

Question 149

Isthmes dans le cas graphique

Answer 149

Les isthmes de M(G) sont les isthmes de G

Question 150

Boucles dans le cas vectoriel

Answer 150

Les boucles de M(U) sont les colonnes vides de U

Question 151

Isthmes dans le cas vectoriel

Answer 151

Les isthmes de M(U) sont les colonnes qui diminuent le rang de U si on les en supprime

Question 152

Définition du matroïde mineur obtenu par suppression de A (M \ A) par ses circuits

Answer 152

Soit E \ A où E est un ensemble fini et A ⊆ E, le matroïde mineur M \ A est défini par la propriété suivante : l’ensemble de ses circuits est {X ⊆ E \ A | X ∈ C} où C est l’ensemble des circuits de M

Question 153

Définition du matroïde mineur obtenu par contraction de A (M / A) par ses circuits

Answer 153

Soit E \ A où E est un ensemble fini et A ⊆ E, le matroïde mineur M / A est défini par la propriété suivante : l’ensemble de ses circuits est {X ⊆ E \ A | X != ∅, X = c \ A pour c ∈ C et X est minimal avec ces propriétés} où C est l’ensemble des circuits de M

Question 154

Définition du matroïde mineur obtenu par suppression de A (M \ A) par ses indépendants

Answer 154

Soit E \ A où E est un ensemble fini et A ⊆ E, le matroïde mineur M \ A est défini par la propriété suivante : l’ensemble de ses indépendants est {X ⊆ E \ A | X ∈ I} où I est l’ensemble des indépendants de M

Question 155

Définition du matroïde mineur obtenu par contraction de A (M / A) par ses indépendants

Answer 155

Soit E \ A où E est un ensemble fini et A ⊆ E, le matroïde mineur M / A est défini par la propriété suivante : l’ensemble de ses indépendants est {X ⊆ E \ A | il existe une base b de M(A) telle que X ∪ b ∈ I} = {X ⊆ E \ A |pour toute base b de M(A), X ∪ b ∈ I} où I est l’ensemble des indépendants de M

Question 156

Définition du matroïde mineur obtenu par suppression de A (M \ A) par ses bases

Answer 156

Soit E \ A où E est un ensemble fini et A ⊆ E, le matroïde mineur M \ A est défini par la propriété suivante : l’ensemble de ses bases est {X ⊆ E \ A | X ∈ I et |X| = r_M(E \ A)} où I est l’ensemble des indépendants de M

Question 157

Définition du matroïde mineur obtenu par contraction de A (M / A) par ses bases

Answer 157

Soit E \ A où E est un ensemble fini et A ⊆ E, le matroïde mineur M / A est défini par la propriété suivante : l’ensemble de ses bases est {X ⊆ E \ A | il existe une base b de M(A) telle que X ∪ b ∈ B} = {X ⊆ E \ A |pour toute base b de M(A), X ∪ b ∈ B} où B est l’ensemble des bases de M

Question 158

Définition du matroïde mineur obtenu par suppression de A (M \ A) par ses cocircuits

Answer 158

Soit E \ A où E est un ensemble fini et A ⊆ E, le matroïde mineur M \ A est défini par la propriété suivante : l’ensemble de ses cocircuits est {X ⊆ E \ A | X != ∅, X = C \ A pour C ∈ C* et X est minimal avec ces propriétés} où C* est l’ensemble des cocircuits de M

Question 159

Définition du matroïde mineur obtenu par contraction de A (M / A) par ses cocircuits

Answer 159

Soit E \ A où E est un ensemble fini et A ⊆ E, le matroïde mineur M / A est défini par la propriété suivante : l’ensemble de ses cocircuits est {X ⊆ E \ A | X ∈ C} où C est l’ensemble des cocircuits de M

Question 160

Définition du matroïde mineur obtenu par suppression de A (M \ A) par sa fonction de rang

Answer 160

Soit E \ A où E est un ensemble fini et A ⊆ E, le matroïde mineur M \ A est défini par la propriété suivante : pour X ⊆ E \ A, r_{M \ A}(X) = r_M(X)

Question 161

Définition du matroïde mineur obtenu par contraction de A (M / A) par sa fonction de rang

Answer 161

Soit E \ A où E est un ensemble fini et A ⊆ E, le matroïde mineur M / A est défini par la propriété suivante : pour X ⊆ E \ A, r_{M / A}(X) = r_M(X ∪ A) r_M(A)

Question 162

Qu’est-ce que la restriction de M à A ?

Answer 162

Le matroïde M \ (E \ A) et noté M(A) ou M|_A

Question 163

Propriétés de la contraction et de la suppression

Answer 163

Les opérations de contraction et de suppressions sont conmmutatives pour des sous-parties A et A’ disjointes

Question 164

Définition d’un mineur de M

Answer 164

Un mineur de M est un matroïde obtenu à partir de M par une suite quelconques de suppressions et de contractions

Question 165

Lien entre les mineurs et les boucles et isthmes

Answer 165

Un élément e de E est une boucle ou un isthme si et seulement si M / {e} = M \ {e}

Question 166

Lien entre la contraction et la suppression

Answer 166

Les contractions et les suppressions sont des notions duales, donc :
- (M \ A)* = M* / A
- (M / A)* = M* \ A

Question 167

Mineurs dans le cas graphique

Answer 167

Pour M un matroïde graphique, les mineurs de M(G) sont les mineurs de G :
- M(G \ A) = M(G) \ A
- M(G / A) = M(G) / A

Question 168

Mineurs dans le cas vectoriel

Answer 168

Pour M un matroïde vectoriel, les mineurs de M(U) correspondent dans U à :
- La suppression des colonnes de A pour la suppression
- Une projection depuis le sous-espace engendré par A pour la contraction

Question 169

Définition d’une somme directe de sous-matroïdes par son rang

Answer 169

Soit un matroïde sur E fini et E₁ et E₂ une partition de E, M est la somme disjointe des sous-matroïdes M(E₁) et M(E₂), noté M = M(E₁) ⊕M(E₂), si et seulement si : r_M(E) = r_M(E₁) + r_M(E₂)

Question 170

Définition d’une somme directe de sous-matroïdes par ses bases

Answer 170

Soit un matroïde sur E fini et E₁ et E₂ une partition de E, M est la somme disjointe des sous-matroïdes M(E₁) et M(E₂), noté M = M(E₁) ⊕M(E₂), si et seulement si : B est une base de M si et seulement si B = B₁ ⊎ B₂ où B₁ est une base de M(E₁) et B₂ une base de M(E₂)

Question 171

Définition d’une somme directe de sous-matroïdes par ses indépendants

Answer 171

Soit un matroïde sur E fini et E₁ et E₂ une partition de E, M est la somme disjointe des sous-matroïdes M(E₁) et M(E₂), noté M = M(E₁) ⊕M(E₂), si et seulement si : si X ⊂ E₁ et Y ⊂ E₂ sont des indépendants de M alors X ∪ Y est indépendant

Question 172

Définition d’une somme directe de sous-matroïdes par ses circuits

Answer 172

Soit un matroïde sur E fini et E₁ et E₂ une partition de E, M est la somme disjointe des sous-matroïdes M(E₁) et M(E₂), noté M = M(E₁) ⊕M(E₂), si et seulement si : pour tout circuit C de M, C ⊂ E₁ ou C ⊂ E₂

Question 173

Définition d’une somme directe de sous-matroïdes par le rang de ses parties

Answer 173

Soit un matroïde sur E fini et E₁ et E₂ une partition de E, M est la somme disjointe des sous-matroïdes M(E₁) et M(E₂), noté M = M(E₁) ⊕M(E₂), si et seulement si : pour tout circuit X ⊂ E₁ et Y ⊂ E₂, r_M(X ∪ Y) = r_M(X) + r_M(Y)

Question 174

Qu’est-ce qu’un matroïde connexe ?

Answer 174

Un matroïde qui n’est pas une somme directe non-triviale

Question 175

Qu’est-ce que les composantes connexes d’un matroïde M ?

Answer 175

Un matroïde M s’écrit comme une unique somme directe de matroïdes connexes qu’on appelle composantes connexes de M

Question 176

Lien entre la connexité et les circuits

Answer 176

Un matroïde est connexe si et seulement si deux éléments distincts quelconques sont contenus dans un circuit

Question 177

Connexité dans le cas des matroïdes graphiques

Answer 177

Un matroïde graphique M(G) est connexe si et seulement si G est 2-connexe

Question 178

Lien entre la connexité et les boucles et isthmes

Answer 178

Si e est une boucle ou un isthme du matroïde M, alors M(e) est une composante connexe de M

Question 179

Qu’est-ce qu’un matroïde de partition ?

Answer 179

Un matroïde de partition est la somme directe de matroïdes uniformes, c’est-à-dire que si on considère k ensembles E₁, …, E_k munis de leur tailles et rangs respectifs n₁, …, n_k et r₁, …, r_k, alors les C₁ ∪ … ∪ C_k avec C_i ⊆ E_i forment l’ensemble des indépendants d’un matroïde, qui est un matroïde de partition isomorphe à U_r1,n1 ⊕ … ⊕ U_rk,nk

Question 180

Théorème sur l’intersection des indépendants de deux matroïdes

Answer 180

Soient M₁ et M₂ deux matroïdes sur le même ensemble E et ayant pour ensembles d’indépendants I₁ et I₂ et pour fonction de rang r₁ et r₂, alors max_I∈I1∩I2 = min_A⊆E (r₁(A) + r₂(E \ A))

Question 181

Conséquence algorithmique du théorème sur l’intersection des indépendants de deux matroïdes

Answer 181

Soient M₁ et M₂ deux matroïdes sur le même ensemble E et ayant pour ensembles d’indépendants I₁ et I₂ certifiés par des oracles en temps constant, alors un élément le plus grand possible de I₁ ∩ I₂ peut être construit en temps polynomial