Partie 3 Flashcards
1
Q
Définition d’un cycle
A
Chemin fermé sans répétition d’arêtes
2
Q
Définition d’un cycle minimal
A
Cycle sans répétition de sommets
3
Q
Définition d’un circuit
A
Ensemble des arêtes d’un cycle minimal
4
Q
Définition d’une coupe
A
Ensemble des arêtes joignant les deux parties d’une partition V = A ⨄ B
5
Q
Définition d’un co-circuit (ou coupe minimale)
A
Coupe qui n’est pas incluse dans une autre coupe
6
Q
Propriété partagée par les circuits et les co-circuits
A
Ils sont incomparables par inclusion
7
Q
Propriété des coupes minimales (énoncé)
A
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
8
Q
Propriété des coupes minimales (schéma de preuve)
A
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
[A1] [B] [A2] → [A1] [B ∪ A2]
9
Q
Définition d’un arbre couvrant
A
Sous-graphe sans cycle (arbre) qui connecte tous les sommets entre eux
10
Q
Définition d’une forêt couvrante
A
Union d’arbres couvrants de chaque composante connexe
11
Q
Définition d’une base
A
Ensemble des arêtes d’un arbre couvrant ou d’une forête couvrante
12
Q
Définition d’une cobase
A
Complémentaire dans E d’une base
13
Q
Propriété des arbres couvrants
A
Tous les arbres couvrants ou forêts couvrantes d’un graphe ont le même nombre d’arêtes, on l’appelle le rang
14
Q
Formule du rang d’un graphe
A
r(G) = |V| - c(G) où c(G) est le nombre e composantes connexes de G
15
Q
Définition d’un graphe planaire
A
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
16
Q
Définition d’un plongement
A
(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
17
Q
Définition de l’équivalence pour deux dessins
A
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
18
Q
Unicité du plongement d’un graphe planaire
A
Le plongement d’un graphe planaire n’est en général pas unique
19
Q
Définition du plongement dual
A
(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’, σ’)
20
Q
Plongements dual de deux dessins d’un même plongement
A
Les dessins obtenus avec les duaux de deux dessins d’un même plongement sont équivalents (appartiennent au même plongement dual)
21
Q
Composition de dualité de plongement
A
- 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
22
Q
Définition d’un isthme
A
Arête qui déconnecte le graphe si elle est supprimée
23
Q
Correspondance d’éléments entre le plongement et son dual
A
- Isthme dans le plongement → boucle dans le dual
- Boucle dans le plongement → isthme dans le dual
- Plongement arbre → dual constitué de boucles
24
Q
Correspondance d’éléments entre G et G’ où (G’, σ’) est le dual de (G, σ) plongement de G (énoncé)
A
- Circuit de G → cocircuits de G’
- Cocircuit de G → circuits de G’
- Bases de G → cobases de G’
- Cobases de G → bases de G’
25
Correspondance d'éléments entre G et G' où (G', σ') est le dual de (G, σ) plongement de G (schéma de preuve)
- 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)
26
Propriété reliant les cycles et les abres couvrants dans les graphes connexes quelconques (énoncé)
Un sous-graphe de G a un cycle si et seulement si il n'est sous-graphe d'aucun arbre couvrant de G
27
Propriété reliant les cycles et les abres couvrants dans les graphes connexes quelconques (schéma de preuve)
⇒ un arbre n'a pas de cycle
⇐ un sous-graphe sans cycle peut-être étendu en arbre couvrant
28
Reformulation de la propriété reliant les cycles et les abres couvrants dans les graphes connexes quelconques
A ⊆ E contient un circuit si et seulement si pour toute base B, A !⊆ B
29
Propriété reliant les coupes et les abres couvrants dans les graphes connexes quelconques (énoncé)
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 != ∅
30
Propriété reliant les coupes et les abres couvrants dans les graphes connexes quelconques (schéma de preuve)
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 = ∅
31
Reformulation de la propriété reliant les coupes et les abres couvrants dans les graphes connexes quelconques
A ⊆ E contient un cocircuit si et seulement si pour toute cobase B, A !⊆ B
32
Définition d'un dépendant pour un graphe
Partie A ⊆ E contenant un circuit
33
Définition d'un dépendant pour un matroïde
Partie A ⊆ E contenant un circuit
34
Définition d'un indépendant pour un graphe
Partie A ⊆ E qui n'est pas un dépendant
35
Définition d'un indépendant pour un matroïde
Partie A ⊆ E qui n'est pas un dépendant
36
Définition d'un dépendant du dual pour un graphe
Partie A ⊆ E contenant un cicorcuit
37
Définition d'un indépendant du dual pour un graphe
Partie A ⊆ E qui n'es pas un dépendant du dual
38
(Diagramme fondamental) Comment passer des circuits aux dépendants ?
Sur-ensembles
39
(Diagramme fondamental) Comment passer des dépendants aux indépendants ?
Négation
40
(Diagramme fondamental) Comment passer des indépendants aux bases ?
Maximaux
41
(Diagramme fondamental) Comment passer des bases aux cobases ?
Complémentaire
42
(Diagramme fondamental) Comment passer des cobases aux indépendants du dual ?
Sous-ensembles
43
(Diagramme fondamental) Comment passer des indépendants du dual aux dépendants du dual?
Négation
44
(Diagramme fondamental) Comment passer des dépendants du dual aux cocircuits ?
Minimaux
45
(Diagramme fondamental) Comment passer des cocircuits aux dépendants du dual ?
Sur-ensembles
46
(Diagramme fondamental) Comment passer des dépendants du dual aux indépendants du dual ?
Négation
47
(Diagramme fondamental) Comment passer des indépendants du dual aux cobases ?
Maximaux
48
(Diagramme fondamental) Comment passer des cobases aux bases ?
Complémentaire
49
(Diagramme fondamental) Comment passer des bases aux indépendants ?
Sous-ensembles
50
(Diagramme fondamental) Comment passer des indépendants aux dépendants ?
Négation
51
(Diagramme fondamental) Comment passer des dépendants aux circuits ?
Minimaux
52
Axiomes des circuits d'un matroïde (définition d'un circuit)
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 C1, C2 ∈ C et C1 ⊆ C2 alors C1 = C2 (propriété de minimalité ou d'incomparabilité)
-Si C1, C2 ∈ C et e ∈ C1 ∩ C2, alors il existe C3 ∈ C tel que C3 = (C1 ∪ C2)\{e} (propriété d'élminitation)
53
Définition d'une base pour un matroïde
Indépendant maximal pour l'inclusion
54
Définition d'une cobase pour un matroïde
Complémentaire d'une base
55
Définition d'un cocircuit pour un matroïde
Partie minimale pour l'inclusion contenuee dans aucune cobase
56
Comment définir les dépendants à partir des circuits et inversement ?
D = {A ⊆ E | ∃ c ∈ C, c ⊆ A}
C = {A ⊆ E | A ∈ D et A est minimal pour l'inclusion dans D}
57
Comment définir les indépendants à partir des dépendants et inversement ?
I = {A ⊆ E | A !∈ D}
D = {A ⊆ E | A !∈ I}
58
Comment définir les bases à partir des indépendants et inversement ?
B = {A ⊆ E | A ∈ I et A est maximal pour l'inclusion dans I}
I = {A ⊆ E | ∃ b ∈ B, A ⊆ b}
59
Comment définir les cobases à partir des bases et inversement ?
B* = {A ⊆ E | E \ A ∈ B}
B = {A ⊆ E | E \ A ∈ B*}
60
Comment définir les cobases à partir des indépendants du dual et inversement ?
B* = {A ⊆ E | A ∈ I* et A est maximal pour l'inclusion dans I*}
I* = {A ⊆ E | ∃ b ∈ B*, A ⊆ b}
61
Comment définir les indépendants du dual à partir des dépendants du dual et inversement ?
I* = {A ⊆ E | A !∈ D*}
D* = {A ⊆ E | A !∈ I*}
62
Comment définir les dépendants dual à partir des cocircuits et inversement ?
D* = {A ⊆ E | ∃ c ∈ C*, c ⊆ A}
C* = {A ⊆ E | A ∈ D* et A est minimal pour l'inclusion dans D*}
63
Soit I un indépendant mais pas I ∪ {e}, que sait-on de I ∪ {e} ? (énoncé)
Pour un indépendant I, si I ∪ {e} n'est pas indépendant, alors il existe un unique circuit contenu dans I ∪ {e}
64
Soit I un indépendant mais pas I ∪ {e}, que sait-on de I ∪ {e} ? (schéma de preuve)
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
65
Théorème fondamental de la dualité des matroïdes
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
66
Qu'est-ce que le matroïde dual de M ?
Le matroïde noté M* dont les circuits sont les cocircuits de M
67
Composition de dualité de matroïdes
(M*)* = M
68
À quoi correspondent les circuits de M dans M* ?
Aux co-circuits
69
À quoi correspondent les cocircuits de M dans M* ?
Aux circuits
70
À quoi correspondent les dépendants de M dans M* ?
Aux dépendants du dual
71
À quoi correspondent les dépendants du dual de M dans M* ?
Aux dépendants
72
À quoi correspondent les indépendants de M dans M* ?
Aux indépendants du dual
73
À quoi correspondent les indépendants du dual de M dans M* ?
Aux indépendants
74
À quoi correspondent les bases de M dans M* ?
Aux cobases
75
À quoi correspondent les cobases de M dans M* ?
Aux bases
76
Correspondance entre les circuits d'un graphe et d'un matroïde (énoncé)
L'ensemble des circuits de G est l'ensemble des circuits d'un matroïde sur E l'ensemble des arêtes de G
77
Correspondance entre les circuits d'un graphe et d'un matroïde (schéma de preuve)
- 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
78
Qu'est-ce que le matroïde des cycles de G ?
Le matroïde sur l'ensemble E des arêtes de G, qui a le même ensemble de circuits que G
79
Qu'est-ce qu'un matroïde graphique ?
Un matroïde qui est le matroïde des cycles d'un graphe
80
Correspondance entre les cocircuits d'un graphe et d'un matroïde (énoncé)
L'ensemble des cocircuits du grapcocircuitshe G est l'ensemble des cocircuits du matroïde M(G) sur E
81
Correspondance entre les cocircuits d'un graphe et d'un matroïde (schéma de preuve)
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
82
Correspondance entre les bases d'un graphe et d'un matroïde (énoncé)
L'ensemble des bases du graphe G est l'ensemble des bases du matroïde M(G) sur E
83
Correspondance entre les bases d'un graphe et d'un matroïde (schéma de preuve)
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
84
Caractérisation des cocircuits d'un graphe (énoncé)
L'ensemble des cocircuits d'un graphe vérifie l'axiomatique des cricuits d'un matroïde
85
Caractérisation des cocircuits d'un graphe (schéma de preuve)
- 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 (A1, A'1) et (A2, A'2) de chacune des deux coupes et qu'on calcule (A1 ∩ A2) ∪ (A'1 ∩ A'2) et (A1 ∩ A'2) ∪ (A'1 ∩ A2), 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
86
Correspondance entre le matroïde dual et le plongement dual
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')
87
Qu'est-ce que le matroïde des coupes ou matroïde des cocyles de G ?
Le matroïde M(G)* dual du matroïde des cycles M(G)
88
Caractérisation de Whitney des graphes planaires
Soit G un graphe, alors G est planaire si et seulement si le matroïde M(G)* est graphique
89
Qu'est-ce qu'un Whitney flip ?
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
90
Théorème des Whitney flips
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
91
Exemple du théorème des Whitney flips
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
92
Quand est-ce qu'un graphe est déterminé par son matroïde des cycles ? (énoncé)
Un graphe G est déterminé par son matroïde des cycles si et seulement si il est 3-connexe
93
Quand est-ce qu'un graphe est déterminé par son matroïde des cycles ? (schéma de preuve)
Un graphe 3-connexe de permet aucun Whitney flip
94
Axiomes des indépendants d'un matroïde (énoncé)
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 I1 ∈ I et I2 ⊂ I1, alors I2 ∈ I (propriété d'hérédité)
- Si I1, I2 ∈ I et | I1| < | I2|, ∃ e ∈ I2\I1 tel que I1 ∪ {e} ∈ I (propriété d'augmentation)
95
Axiomes des indépendants d'un matroïde ⇒ axiomes des circuits d'un matroïde (schéma de preuve)
- Axiome 1 trivial
- Axiome 2 trivial
- Axiome 3 : par contradiction
- supposer que C1 ∪ C2 \ {e} ne contient pas de circuit
- prendre f ∈ C2 \ C1 et X ⊆ C1 ∪ C2 tel que C2 \ f ⊆ X, X indépendant et X maximal avec ces propriétés
- prendre g ∈ C1 != f et tel que g !∈ X
- |X| ≤ |C1 ∪ C2| \ {f ∪ g} = |C1 ∪ C2| - 2 < |C1 ∪ C2| \ e qui est indépendant par hypothèse
- appliquer le troisième axiome des indépendants pour trouver h ∈ (C1 ∪ C2) \ e \ X tel que X ∪ h est indépendant, ce qui est une contradiction
96
Axiomes des circuits d'un matroïde ⇒ axiomes des indépendants d'un matroïde (schéma de preuve)
- 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
97
Axiomes des bases d'un matroïde
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 B1, B2 ∈ B et x ∈ B1 \ B2, ∃ y ∈ B2 \ B1 tel que ∈ (B1 \ x) ∪ y ∈ B (propriété d'échange)
98
Propriété des bases d'un matroïde (énoncé)
Les bases d'un matroïde sont équi-cardinales
99
Propriété des bases d'un matroïde (schéma de preuve)
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é
100
Qu'est-ce que le rang d'une partie A de E dans M un matroïde sur E ?
Le rang rM(A) est le cardinal d'un indépendant contenu dans A et maximal pour l'inclusion : rM(A) = max{|Y| | Y ⊆ A, Y ∈ I}
101
Qu'est-ce que le rang d'une partie stricte X de E dans M* un matroïde dual sur E ?
Pour X ⊂ E, rM*(X) = |X| + rM(E\X) - rM
102
Qu'est-ce que le rang d'un matroïde M ?
Le rang r(M) d'un matroïde est le rang de E dans M rM(E), c'est-à-dire la taille d'un indépendant maximal (ou base)
103
Que vaut le rang du matroïde dual M* ?
r(M*) = |E| - r(M), c'est-à-dire la taille d'un co-base
104
Correspondance entre le rang des graphes et des matroïdes graphiques
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
105
Axiomes de la fonction rang d'un matroïde
La fonction r de 2E 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)
106
Expression de l'ensemble des indépendants en fonction du range
I = {A ⊆ E | r(A) = |A|}
107
Qu'est-ce que les fermés du matroïe M ?
Ce sont les parties A ⊆ E telles que si C est un circuit tel que e ∈ C et C \ {e} ⊆ A, alors C ⊆ A
108
Comment caractériser les cocircuits à partir des fermés d'un matroïde ?
C* = {E \ A ⊆ E | A est un fermé de M et rM(A) = r(M) - 1}
109
Contexte de l'algorithme Glouton
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
110
Algorithme Glouton (entrée, sortie, algorithme)
- Entrée : I ⊆ 2E, w : E → {R}
- Sortie : X ∈ I
- Glouton(I, w) :
- X0 = ∅
- j = 0
- Tant qu'il existe e ∈ E\Xj tel que Xj ∪ {e} ∈ I :
- Choisir un tel ej+1 de poids maximum
- Xj+1 = Xj ∪ {ej+1}
- j = j + 1
- Renvoyer Xj
111
Axiomes des indépendants d'un matroïde
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 I1 ∈ I et I2 ⊂ I1, alors I2 ∈ 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)
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 ?
Lorsque I est l'ensemble des indépendants d'un matroïde
113
Définition d'un matroïde vectoriel sur le corps K (énoncé)
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 {ue | e ∈ E}, l'ensemble des A ⊆ E tels que la famille de vecteurs ua 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)
114
Définition d'un matroïde vectoriel sur le corps K (schéma de preuve)
- 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 αeue = 0 et Σe∈E α'eue = 0
- prendre f appartenant aux deux et construire αfΣe∈E αeue - α'fΣe∈E α'eue = Σe∈E (αfα'e - α'fαe)ue = 0
- le coefficient de uf est nul et tous les autres non-nuls sont toujours non-nuls, donc c'est fini
115
Définition d'un dépendant d'un matroïde vectoriel sur K
Pour toute relation de dépendance linéaire Σe∈E αeue = 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)
116
Définition alternative d'un matroïde vectoriel : à partir des indépendants
M(U) est le matroïde dont l'ensemble des indépendants est l'ensemble des A ⊆ E tels que la famille de vecteus (ua)a∈A est linéairement indépendante
117
Définition alternative d'un matroïde vectoriel : à partir des bases
M(U) est le matroïde dont l'ensemble des bases est l'ensemble des A ⊆ E tels que la famille de vecteus (ua)a∈A forme une base de l'espace vectoriel engendré par la famille des (ue)e∈E
118
Définition alternative d'un matroïde vectoriel : à partir du rang
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 (ua)a∈A, c'est-à-dire le rang de la sous-matrice de U formée par les colonnes de A
119
Définition alternative d'un matroïde vectoriel : à partir des circuits
M(U) est le matroïde dont l'ensemble des circuits est l'ensemble des A ⊆ E tels que la famille de vecteus (ua)a∈A est linéairement dépendante et toute sous-famille est linéairement indépendante
120
Représentation de Whitney d'un matroïde vectoriel
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|
121
Représentation affine dans le cas réel d'un matroïde vectoriel
Soit K = {R}, soit Vec l'espace engendré par (ue)e∈E, et considérons un hyperplan affine de Vec (c'est-à-dire un ensemble de points d'équation Σ1≤i≤r αibi = 1) en supposant qu'aucun vecteur ue n'est parallèle à cet hyperplan, alors chaque vecteur de (ue)e∈E peut être remplacé par un vecteur dont l'extrêmité appartient à cet hyperplan sans changer le matroïdes des dépendance
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 ?
Par des droites (points alignés)
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 ?
Par des circuits non-alignés
124
Lien entre les matroïdes graphiques et les matroïdes vectoriels (énoncé)
Les matroïdes graphiques sont vectoriels sur tout K
125
Lien entre les matroïdes graphiques et les matroïdes vectoriels (construction)
Soit G = (V, E) un graphe tel que V = {v1, ..., vk}, on considère v1, ..., vk comme la base canonique d'un espace vectoriel sur K et pour toute arête e ∈ E d'extrêmités (vi, vj), on définit le vecteur correspondant ue = vj - vi et on obtient U la matrice formée par les ue, pour laquelle M(U) = M(G)
126
Lien entre les matroïdes graphiques et les matroïdes vectoriels (schéma de preuve)
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
127
Définition du matroïde uniforme par ses bases
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
128
Définition du matroïde uniforme par ses circuits
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
129
Définition du matroïde uniforme par ses cobases
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
130
Définition du matroïde uniforme par ses cocircuits
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
131
Définition du matroïde uniforme par ses inépendants
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
132
Définition du matroïde uniforme par ses dépendants
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
133
Dualité du matroïde uniforme de taille n et de rang r
U*r, n = Un-r, r
134
Lien entre le matroïde uniforme et les matroïdes vectoriels
Le matroïde uniforme Ur, n est vectoriel sur {R} et s'obtient à partir de n vecteur en position générale dans un espace de dimension r
135
Quel est le plus petit exemple de matroïde non-graphique ?
Le matroïde uniforme U2,4
136
Qu'est-ce que le matroïde de Fano ?
C'est le matroide des vecteurs de ({Z}/2{Z}) \ {0}
137
Quand est-ce que le matroïde U2, 4 est un matroïde vectoriel ?
Sur {R}
138
Quand est-ce que le matroïde de Fano est un matroïde vectoriel ?
Sur {Z}/2{Z}
139
Quand est-ce que le matroïde non-Pappus est un matroïde vectoriel ?
Jamais
140
Théorème de Pappus
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
141
Qu'est-ce que le matroïde non-Pappus ?
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
142
Définition alternative d'un matroïde vectoriel : à partir des cocircuits
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 VecA engendré par (ua)a∈A est de dimension rang(U) - 1, et tel que VecA ∩ E = A, alors E \ A est un cocircuit
143
Propriété du matroïde dual d'un matroïde vectoriel
Le matroïde dual d'un matroïde vectoriel est également un matroïde vectoriel
144
Comment obtenir le matroïde dual d'un matroïde vectoriel ?
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
145
Qu'est-ce qu'une boucle (ou loop) du point de vue des matroïdes ?
Un élément de E qui n'appartient à aucune base, et qui forme donc un circuit à lui tout seul
146
Qu'est-ce qu'un isthme (ou coloop) du point de vue des matroïdes ?
Un élément de E qui n'appartient à toutes les bases, et qui forme donc un cocircuit à lui tout seul
147
Lien entre les boucles et les isthmes
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
148
Boucles dans le cas graphique
Les boucles de M(G) sont les boucles de G
149
Isthmes dans le cas graphique
Les isthmes de M(G) sont les isthmes de G
150
Boucles dans le cas vectoriel
Les boucles de M(U) sont les colonnes vides de U
151
Isthmes dans le cas vectoriel
Les isthmes de M(U) sont les colonnes qui diminuent le rang de U si on les en supprime
152
Définition du matroïde mineur obtenu par suppression de A (M \ A) par ses circuits
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
153
Définition du matroïde mineur obtenu par contraction de A (M / A) par ses circuits
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
154
Définition du matroïde mineur obtenu par suppression de A (M \ A) par ses indépendants
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
155
Définition du matroïde mineur obtenu par contraction de A (M / A) par ses indépendants
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
156
Définition du matroïde mineur obtenu par suppression de A (M \ A) par ses bases
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| = rM(E \ A)} où I est l'ensemble des indépendants de M
157
Définition du matroïde mineur obtenu par contraction de A (M / A) par ses bases
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
158
Définition du matroïde mineur obtenu par suppression de A (M \ A) par ses cocircuits
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
159
Définition du matroïde mineur obtenu par contraction de A (M / A) par ses cocircuits
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
160
Définition du matroïde mineur obtenu par suppression de A (M \ A) par sa fonction de rang
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, rM \ A(X) = rM(X)
161
Définition du matroïde mineur obtenu par contraction de A (M / A) par sa fonction de rang
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, rM / A(X) = rM(X ∪ A) rM(A)
162
Qu'est-ce que la restriction de M à A ?
Le matroïde M \ (E \ A) et noté M(A) ou M|A
163
Propriétés de la contraction et de la suppression
Les opérations de contraction et de suppressions sont conmmutatives pour des sous-parties A et A' disjointes
164
Définition d'un mineur de M
Un mineur de M est un matroïde obtenu à partir de M par une suite quelconques de suppressions et de contractions
165
Lien entre les mineurs et les boucles et isthmes
Un élément e de E est une boucle ou un isthme si et seulement si M / {e} = M \ {e}
166
Lien entre la contraction et la suppression
Les contractions et les suppressions sont des notions duales, donc :
- (M \ A)* = M* / A
- (M / A)* = M* \ A
167
Mineurs dans le cas graphique
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
168
Mineurs dans le cas vectoriel
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
169
Définition d'une somme directe de sous-matroïdes par son rang
Soit un matroïde sur E fini et E1 et E2 une partition de E, M est la somme disjointe des sous-matroïdes M(E1) et M(E2), noté M = M(E1) ⊕M(E2), si et seulement si : rM(E) = rM(E1) + rM(E2)
170
Définition d'une somme directe de sous-matroïdes par ses bases
Soit un matroïde sur E fini et E1 et E2 une partition de E, M est la somme disjointe des sous-matroïdes M(E1) et M(E2), noté M = M(E1) ⊕M(E2), si et seulement si : B est une base de M si et seulement si B = B1 ⊎ B2 où B1 est une base de M(E1) et B2 une base de M(E2)
171
Définition d'une somme directe de sous-matroïdes par ses indépendants
Soit un matroïde sur E fini et E1 et E2 une partition de E, M est la somme disjointe des sous-matroïdes M(E1) et M(E2), noté M = M(E1) ⊕M(E2), si et seulement si : si X ⊂ E1 et Y ⊂ E2 sont des indépendants de M alors X ∪ Y est indépendant
172
Définition d'une somme directe de sous-matroïdes par ses circuits
Soit un matroïde sur E fini et E1 et E2 une partition de E, M est la somme disjointe des sous-matroïdes M(E1) et M(E2), noté M = M(E1) ⊕M(E2), si et seulement si : pour tout circuit C de M, C ⊂ E1 ou C ⊂ E2
173
Définition d'une somme directe de sous-matroïdes par le rang de ses parties
Soit un matroïde sur E fini et E1 et E2 une partition de E, M est la somme disjointe des sous-matroïdes M(E1) et M(E2), noté M = M(E1) ⊕M(E2), si et seulement si : pour tout circuit X ⊂ E1 et Y ⊂ E2, rM(X ∪ Y) = rM(X) + rM(Y)
174
Qu'est-ce qu'un matroïde connexe ?
Un matroïde qui n'est pas une somme directe non-triviale
175
Qu'est-ce que les composantes connexes d'un matroïde M ?
Un matroïde M s'écrit comme une unique somme directe de matroïdes connexes qu'on appelle composantes connexes de M
176
Lien entre la connexité et les circuits
Un matroïde est connexe si et seulement si deux éléments distincts quelconques sont contenus dans un circuit
177
Connexité dans le cas des matroïdes graphiques
Un matroïde graphique M(G) est connexe si et seulement si G est 2-connexe
178
Lien entre la connexité et les boucles et isthmes
Si e est une boucle ou un isthme du matroïde M, alors M(e) est une composante connexe de M
179
Qu'est-ce qu'un matroïde de partition ?
Un matroïde de partition est la somme directe de matroïdes uniformes, c'est-à-dire que si on considère k ensembles E1, ..., Ek munis de leur tailles et rangs respectifs n1, ..., nk et r1, ..., rk, alors les C1 ∪ ... ∪ Ck avec Ci ⊆ Ei forment l'ensemble des indépendants d'un matroïde, qui est un matroïde de partition isomorphe à Ur1,n1 ⊕ ... ⊕ Urk,nk
180
Théorème sur l'intersection des indépendants de deux matroïdes
Soient M1 et M2 deux matroïdes sur le même ensemble E et ayant pour ensembles d'indépendants I1 et I2 et pour fonction de rang r1 et r2, alors maxI∈I1∩I2 = minA⊆E (r1(A) + r2(E \ A))
181
Conséquence algorithmique du théorème sur l'intersection des indépendants de deux matroïdes
Soient M1 et M2 deux matroïdes sur le même ensemble E et ayant pour ensembles d'indépendants I1 et I2 certifiés par des oracles en temps constant, alors un élément le plus grand possible de I1 ∩ I2 peut être construit en temps polynomial
