Les matroïdes

1) Introduction

Le matroïde est une structure logique formelle, introduite par H. Whitney en 1935, qui généralise la notion de dépendance linéaire en ne retenant que ses principales propriétés ensemblistes.

Un matroïde est une structure mathématique, mettant en oeuvre une logique du second ordre, comprenant un ensemble servant de support et des familles de sous-ensembles.

Le matroïde possède `10` facettes qui correspondent à `10` façons courantes de le définir. Il possède 4 familles d'ensembles que sont ; la famille des circuits, la famille des dépendants, la famille des indépendants, et la famille des bases. Et il possède une fonction dimension qui appliquée à un ensemble de points retourne un entier positif correspondant à la dimension de l' « espace » engendré par l'ensemble en quetion. Puis de façon symétrique, il possède 4 autres familles d'ensembles que sont ; la famille des coupures, la famille des dépendants duals, la famille des indépendants duals et la famille des base duales. Et il possède une fonction dimension duale qui appliquée à un ensemble de points retourne un entier positif correspondant à la dimension de l' "espace dual " engendré par cet ensemble. Chacune de ces familles satisfont une axiomatique spécifique et détermine le matroïde tout entier, et donc détermine les autres familles. Et chacune des deux fonctions détermine également le matroïde tout entier.

Cours de M. Las Vergnas - Université Paris 6
Jean-Sébastien Sereni, cours "Matroïdes", 2012
Jean-Sébastien Sereni, "Matrroïdes - Complément sur la dualité", 2012
Emeric Gioan, Jorge Ramírez Alfonsín, "Eléments de théorie des matroïdes et matroïdes orientés", 2013
Vanessa Chatelain "Contribution à la théorie des matroïdes: polytope des bases, orientations et algorithmes", 2013

Le cadre logique de cette structure est propice à la conception d'un langage logique du troisième ordre, et d'un système original de démonstration automatique.

Voir Logique du premier ordre.
Voir Logique d'ordre supérieur.

 

On pose un ensemble `E` comme support. Par commodité les éléments de cet ensemble sont appellés des points. Le terme d'ensemble sera réservé pour désigner les sous-ensembles de `E`. Les variables représentant des points sont des lettres minuscules `a,b,c...`. Les variables représentant des ensembles sont des majuscules `A,B,C,...`. Les variables représentant des familles d'ensembles sont des majuscules à double-barre `bbbA,bbbB,bbbC,...`.

Il y a ainsi `3` types de variables. L'expression `AA a` signifie quelque soit un point `a` appartenant à `E`. L'expression `AA A` signifie quelque soit un ensemble `A` appartenant à `ccP(E)`. Et l'expression `AA bbbA` signifie quelque soit une famille `bbbA` appartenant à `ccP(ccP(E))`.

On désigne les différentes familles du matroïde comme suit :

`bbbC` : Famille des circuits
`bbbD` : Famille des dépendants
`bbbI` : Famille des indépendants
`bbbB` : Famille des bases
`bbbB^**` : Famille des bases duales
`bbbI^**` : Famille des indépendants duals
`bbbD^**` : Famille des dépendants duals
`bbbC^**` : Famille des coupures

2) Circuits

La famille des circuits est nommée `bbbC`. Un circuit est ensembles de points liés par une relation de dépendance définie par le matroïde, et où chaque point est indispensable pour maintenir cette dépendance. Un circuit est un dépendant minimum. Si l'on retire un point quelconque d'un circuit celui-ci devient un indépendant. La famille des circuits obéït à trois axiomes :

`bbbC" ne possède pas "Ø`
Un circuit ne peut pas être vide.
 `Ø "∉" bbbC`
`bbbC" est une frontière"`
Un circuit ne peut pas être inclus strictement dans un autre.
`AAX "∈" bbbC, AAY"∈"bbbC, X"⊄"Y`
`bbbC" permet l'élimination"`
Si un point appartient à la fois à deux circuits distincts alors
il existe un circuit inclus dans la réunion des deux circuits
qui ne le contient pas.
`AAX "∈" bbbC, AAY "∈" bbbC"/"(X"≠"Y "et" EEe "∈" X"∩"Y), EE Z"∈"bbbC, Z"⊆"(X"∪"Y)"-"{e}`

3) Dépendants

La famille des dépendants est nommée `bbbD`. Un dépendant contient un ensemble de points liés par une relation de dépendance définie par le matroïde. Autrement dit, un dépendant contient un circuit. La famille des dépendants obéït à trois axiomes :

`bbbC" ne possède pas "Ø`
Un dépendant ne peut pas être vide.
 `Ø "∉" bbbD`
`bbbC" est clos par agrandissement"`
Tout ensemble contenant un dépendant est un dépendant.
`AAX "∈" bbbD, AAY"/"X"⊆"Y, Y"∈" bbbD`
`bbbC" permet l'élimination"`
Si un point appartient à la fois à deux dépendants distincts, alors
il existe un dépendant inclus dans la réunion des deux dépendants
qui ne le contient pas.
`AAX "∈" bbbD, AAY "∈" bbbD"/"(X"≠"Y "et" EEe "∈" X"∩"Y), EE Z "∈"bbbD, Z"⊆"(X"∪"Y)"-"{e}`

4) Indépendants

La famille des indépendants est nommée `bbbI`. Un indépendant est un ensemble qui n'est pas un dépendant. C'est un ensemble de points dans lequel aucune relation de dépendance n'existe. Un indépendant ne contient pas de circuit. La famille des indépendants obéït à trois axiomes :

`bbbF" possède "Ø`
L'ensemble vide est un indépendant.
 `Ø "∈" bbbI`
`bbbF" est clos par inclusion"`
Tout ensemble inclus dans un indépendant est un indépendant.
`AAX "∈" bbbI, AAY"/"Y"⊆"X, Y"∈" bbbI`
`bbbF" permet l'agrandissement"`
Si un indépendant est de cardinal plus grand qu'un autre indépendant,
alors il possède au moins un élément qu'il peut lui donner pour constituer
un indépendant plus grand.
`AAX "∈" bbbI, AAY "∈" bbbI"/"|X|">"|Y|, EEe "∈" X"\"Y, Y"+"{e}"∈"bbbI`

5) Bases

La famille des bases est nommée `bbbB`. Une base correspond à un indépendant maximal. C'est à dire que l'adjonction de tout point le transforme en un circuit. Autrement dit, une base ne contient pas de circuit et est maximale avec cette propriété. La famille des bases obéït à deux axiomes :

`bbbB" n'est pas vide"`
Il existe au moins une base.
 `bbbB"≠"Ø`
`bbbB" permet l'échange"`
Si un point appartient à une base et n'appartient pas à une autre base,
alors il existe un autre point dans cette autre base qui peut se substituer
à ce point dans cette base pour former une nouvelle base.
`AAX "∈" bbbB, AAY "∈" bbbB, AAe"∈"X"\"Y, EE f "∈" Y"\"X, (X"-"{e}"+"{f})"∈" bbbB`

6) Fonction dimension

La fonction dimension, noté `"dim"`, s'applique à un ensemble de points et retourne un entier positif appellé la dimension de l'espace engendré par cet ensemble de points. `"dim∈"ccP(E)->NN`. La dimension d'un ensemble est égale au plus grand cardinal rencontré parmis les sous-ensembles indépendants. La fonction dimension obéït à 3 axiomes :

`"dim"(Ø) = 0`
`"dim"(Ø) = 0`
`"dim respecte l'ordre"`
`AA X, AA Y"/"Y"⊆"X, "dim"(Y)<="dim"(X)`
`"dim permet l'agrandissement"`
`AAX, AA Y"/dim"(X)">dim"(Y), EEe "∈" X, "dim"(Y"+"{e})">dim"(Y)`

7) Matroïde dual

Les familles des circuits `bbbC`, des dépendants `bbbD`, des indépendants `bbbI` et des bases `bbbB`, ont les mêmes systèmes d'axiome que leur dual, c'est à dire les familles respectivement des coupures `bbbC^**`, dépendant duals `bbbD^**`, des indépendants duals `bbbI^**` et des bases duales `bbbB^**`.

La famille des coupures obéït aux axiomes suivants :
{`bbbC^**" ne possède pas "Ø, bbbC^**" est une frontière", bbbC^**" permet l'élimination"}`

La famille des dépendants duals obéït aux axiomes suivants :
{`bbbD^**" ne possède pas "Ø, bbbD^**" est clos par agrandissement", bbbD^**" permet l'élimination"}`

La famille des indépendants duals obéït aux axiomes suivants :
{`bbbI^**" possède "Ø, bbbI^**" est clos par inclusion", bbbI^**" permet l'agrandissement"}`

La famille des bases duales obéït aux axiomes suivants :
{`bbbB^**" n'est pas vide", bbbB^**" permet l'échange"}`

8) Axiomatiques

On dépersonnalise les axiomes en les faisants s'appliquer à une famille inconnue nommée `bbbF`.

Une famille `bbbF` correspondra à la famille des circuits d'un martroïde si et seulement si elle satisfait les trois axiomes suivants :

`bbbF" ne possède pas "Ø`
 `Ø "∉" bbbF`
`bbbF" est une frontière"`
`AAX "∈" bbbF, AAY"∈"bbbF, X"⊄"Y`
`bbbF" permet l'élimination"`
`AAX "∈" bbbF, AAY "∈" bbbF"/"(X"≠"Y "et" EEe "∈" X"∩"Y), EE Z"∈"bbbF, Z"⊆"(X"∪"Y)"-"{e}`

Une famille `bbbF` correspondra à la famille des dépendants d'un martroïde si et seulement si elle satisfait les trois axiomes suivants :

`bbbF" ne possède pas "Ø`
 `Ø "∉" bbbF`
`bbbF" est clos par agrandissement"`
`AAX "∈" bbbF, AAY"/"X"⊆"Y, Y"∈" bbbF`
`bbbF" permet l'élimination"`
`AAX "∈" bbbF, AAY "∈" bbbF"/"(X"≠"Y "et" EEe "∈" X"∩"Y), EE Z "∈"bbbF, Z"⊆"(X"∪"Y)"-"{e}`

Une famille `bbbF` correspondra à la famille des indépendants d'un matroïde si et seulement si elle satisfait les trois axiomes suivants :

`Ø "∈" bbbF`
 `Ø "∈" bbbF`
`bbbF" est clos par inclusion"`
`AAX "∈" bbbF, AAY"/"Y"⊆"X, Y"∈" bbbF`
`bbbF" permet l'agrandissement"`
`AAX "∈" bbbF, AAY "∈" bbbF"/"|X|">"|Y|, EEe "∈" X"\"Y, Y"+"{e}"∈"bbbF`

Une famille `bbbF` correspondra à la famille des bases d'un martroïde si et seulement si elle vérifie les deux axiomes suivants :

`bbbB" n'est pas vide"`
 `bbbF"≠"Ø`
`bbbB" permet l'échange"`
`AAX "∈" bbbF, AAY "∈" bbbF, AAe"∈"X"\"Y, EE f "∈" Y"\"X, (X"-"{e}"+"{f})"∈" bbbF`

Une application `rho` de `ccP(E)->NN` correspondra à la fonction dimension d'un matroïde si et seulement si elle vérifie les 3 axiomes suivants :

`rho(Ø) "=" 0` `rho(Ø) "=" 0`
`rho" respecte l'ordre"` `AA X, AA Y"/"Y"⊆"X, rho(Y)"≤"rho(X)`
`rho" permet l'agrandissement"`
`AAX, AA Y"/"rho(X)">"rho(Y), EEe "∈" X, rho(Y"+"{e})">"rho(Y)`

9) Six opérateurs sur `ccP(ccP(E))`

Étant donné une famille quelconque `bbbF`. La famille `"sup"(bbbF)` regroupe tous les ensembles contenant au moins un membre de `bbbF`. C'est la clôture par agrandissement. Une famille invariante par l'opérateur `"sup"` est dite close par agrandissement. La famille `"inf"(bbbF)` regroupe tous les ensembles contenus dans au moins un membre de `bbbF`. C'est la clôture par inclusion. Une famille invariante par l'opérateur `"inf"` est dite close par inclusion. La famille `"max"(bbbF)` regroupe les membres maximaux c'est à dire qui ne sont contenues strictement par aucun membre. C'est la maximalisation. Une famille invariante par l'opérateur `"max"` constitue une frontière. La famille `"min"(bbbF)` regroupe les membres minimaux c'est à dire qui ne contiennent strictement aucun membre. C'est la minimalisation. Une famille invariante par l'opérateur `"min"` constitue une frontière. La famille `"¬"(bbbF)` regroupe les familles qui ne sont pas membres de `bbbF`. C'est la négation de `bbbF`. Le complément de `"∁"(bbbF)` regroupe toutes les négations de ses membres. C'est le complément. En résumé :

Opération
Description
Définition formelle
`"sup"(bbbF)`
Clôture par agrandissement. `"sup"(bbbF) = {X "/" EEA"∈"bbbF, A"⊆"X}`
`"inf"(bbbF)`
Clôture par inclusion. `"inf"(bbbF) = {X "/" EEA"∈"bbbF, X"⊆"A}`
`"max"(bbbF)`
Maximalisation `"max"(bbbF) = {X "/" X"∈"bbbF "et" AAA"∈"bbbF, X"⊄"A}`
`"min"(bbbF)`
Minimalisation `"min"(bbbF) = {X "/"  X "∈"bbbD "et" AA D "∈"bbbD, D"⊄"X}`
`¬(bbbF)`
Négation `"¬"(bbbF) = {X "/" X "∉"bbbD}`
`"∁"(bbbF)`
Complément `"∁"(bbbF) = {E"-"X "/" X "∈"bbbF}`
 
Propriété
Description
Définition formelle
`bbbF "=sup"(bbbF)`
Clos par agrandissement `AAX "∈" bbbF, AAY"/"X"⊆"Y, Y"∈" bbbF`
`bbbF "=inf"(bbbF)`
Clos par minimalisation `AAX "∈" bbbF, AAY"/"Y"⊆"X, Y"∈" bbbF`
`bbbF "=max"(bbbF)`
Frontière `AAX"∈"bbbF,AAY"∈"bbbF,X"⊄"Y`
`bbbF "=min"(bbbF)`
Frontière `AAX"∈"bbbF,AAY"∈"bbbF,X"⊄"Y`

 

 

---- 17 mai 2017 ----

 

 

 

On définie la famille des indépendants à partir de la famille des dépendants comme suit : Un ensemble est un indépendant si et seulement si il n'est pas un dépendant.

`X"∈"bbbI   <=>   X "∉"bbbD`

`bbbI = {X "/" X "∉"bbbD}`

La construction des indépendants à partir des dépendants et réciproquement, consiste à prendre la famille complémentaire. Ce procédé de construction s'appelle la négation et se note sous forme d'un opérateur `"¬(.)"`. La famille des indépendants s'obtient par négation de la famille des dépendants et réciproquement.

`¬(bbbD) = bbbI`
`¬(bbbI) = bbbD`

9) La négation `"¬(.)"` La famille des compléments

 

`X"∈""¬"(bbbF)  <=>   X "/" X "∉"bbbD`

`"¬"(bbbF) = {X "/" X "∉"bbbD}`

L'opérateur `"¬"` agit dans l'espace des familles c'est à dire que c'est une application sur `ccP(ccP(E))`.

11) Construction des indépendants à partir des circuits

On définie la famille des indépendants à partir de la famille des circuits comme suit : Un ensemble est un indépendant s'il ne contient pas de circuits

`bbbI = {X "/" AAC"∈"bbbC, C "⊈"X}`
`X"∈"bbbI   <=>   AAC"∈"bbbC, C "⊈"X`

---- 15 mai 2017 ----

La construction des indépendants à partir des circuits, consiste à prendre la famille complémentaire. Ce procédé de construction s'appelle la négation et se note sous forme d'un opérateur `"¬(.)"`. La famille des indépendants s'obtient par négation de la famille des dépendants et réciproquement.

`¬(bbbD) = bbbI`
`¬(bbbI) = bbbD`

`bbbI = {X "/" X"∉"D}`
`bbbI = {X "/" AAC"∈"bbbC, C "⊈"X}`

Un ensemble est un dépendant si et seulement si il contient un circuit.

`X"∈"bbbD   <=>   EE C "∈"bbbC, C"⊆"X`

`bbbD = {X "/" EEC"∈"bbbC, C "⊆"X}`

La construction des dépendants à partir des circuits consiste à ajouter dans la famille tous les ensembles contenant un membre de cette famille. Ce procédé de construction s'appelle la clôture par agrandissement et se note sous forme d'un opérateur `"sup(.)"`. La famille des dépendants s'obtient en prenant la cloture par agrandissement de la famille des circuits.

`"sup"(bbbC) = bbbD`

Réciproquement, on définie la famille des circuits à partir de la famille des dépendants comme suit : Un ensemble est un circuit si et seulement si il est un dépendant minimal, c'est à dire si c'est un dépendant qui ne contient strictement aucun autre dépendant.

`X"∈"bbbC   <=>   X "∈"bbbD "et" AA D "∈"bbbD, D"⊄"X`

`bbbC = {X "/" X "∈"bbbD "et" AA D "∈"bbbD, D"⊄"X}`

La construction des dépendants à partir des circuits consiste à retirer dans la famille tous les ensembles contenant un membre de cette famille. Ce procédé de construction s'appelle la minimalisation et se note sous forme d'un opérateur `"min(.)"`. La famille des circuits s'obtient en minimalisant la famille des dépendants.

`"min"(bbbD) = bbbC`

10) Les opérateurs `"inf(.)"` et `"max(.)"`

Etant donné une famille quelconque `bbbF`.

La famille `"inf"(bbbF)` regroupe tous les ensembles contenus dans au moins un membre de `bbbF`. C'est la clôture par inclusion.

`"inf"(bbbF) = {X "/" EEA"∈"bbbF, X"⊆"A}`

La propriété pour une famille d'être invariante par l'opérateur `"inf"` est équivalente à celle d'être close par inclusion. Autrement dit, la famille satisfait la propriété `P_5(bbbF)` dite "Inf".

`bbbF "=inf"(bbbF)   <=>   P_5(bbbF)`
`bbbF "=inf"(bbbF)   <=>   AAX "∈" bbbF, AAY"/"Y"⊆"X, Y"∈" bbbF`

La famille `"max"(bbbF)` regroupe tous les membres de `bbbF` qui sont maximaux (sous entendu selon l'ordre d'inclusion). C'est la frontière des maximums.

`"max"(bbbF) = {X "/" X"∈"bbbF "et" AAA"∈"bbbF, X"⊄"A}`

La propriété pour une famille d'être invariante par l'opérateur `"max"` est équivalente à celle d'être composée de membres qui ne sont jamais inclus strictement l'un dans l'autre. Autrement dit, la famille satisfait la propriété `P_2(bbbF)` dite "Frontière".

`bbbF "=max"(bbbF)   <=>   P_2(bbbF)`
`bbbF "=max"(bbbF)   <=>   AAX"∈"bbbF,AAY"∈"bbbF,X"⊄"Y`

11) Passage entre les indépendants et les bases

On définie la famille des bases à partir de la famille des indépendants comme suit : Un ensemble est une base si et seulement si il est un indépendant maximal.

`X"∈"bbbB   <=>   X "∈"bbbI "et" AA I "∈"bbbI, X "⊄"I`

La construction des bases à partir des indépendants consiste à retirer de la famille tous les membres contenus strictement dans au moins un membre. Le procédé de construction est l'opérateur `"max"`. Nous avons :

`"max"(bbbI) = bbbB`.

Réciproquement on définie la famille des indépendants à partir de la famille des bases comme suit : Un ensemble est un indépendant si et seulement si il est inclus dans une base.

`X"∈"bbbI  <=>   EE B "∈"bbbB, X "⊆"B`

La construction des indépendants à partir des bases consiste à ajouter dans la famille tous les ensembles inclus dans au moins un membre de cette famille. Le procédé de construction est l'opérateur `"inf"`. Nous avons :

`"inf"(bbbB) = bbbI`

Les opérérations `"max"` et `"inf"` sont l'inverse l'une de l'autre pour les familles `bbbF` possèdant la caractéristique `P_2(bbbF)` dite "Frontière" ou bien la caractéristique `P_5(bbbF)` dite "Inf", et font passer les familles d'une caractéristique à l'autre.

12) L'opérateurs de complément `"∁(.)"`

Etant donné une famille quelconque `bbbF`.

La famille des compléments `"∁"(bbbF)` regroupe tous les compléments de ses membres. C'est la famille des compléments. À ne pas confondre avec la famille complémentaire qui est `¬(bbbF) = {X "/" X "∉"bbbF}`

`"∁"(bbbF) = {¬X "/" X "∈"bbbF}`
`"∁"(bbbF) = {E"-"X "/" X "∈"bbbF}`

13) Passage entre les bases et les bases duales

On définie la famille des bases duales à partir de la famille des bases comme suit : Un ensemble est une base duale si et seulement si il est le complément d'une base.

`X"∈"bbbB^**  <=>   EE B "∈"bbbB, X "="¬B`

La construction des bases duales à partir des bases consiste à parcourire l'ensemble des base et à regrouper dans une nouvelle famille les compléments de chaque base rencontrée. Le procédé de construction est l'opérateur de complément `"∁"`. Et réciproquement on définie la famille des bases à partir de la famille des bases duales par le même procédé :

`"∁"(bbbB) = bbbB^**`
`"∁"(bbbB^**) = bbbB`

14) Les bases duales

La famille des bases duales est nommée `bbbB^**`. Les bases duales sont les complémentaires des bases. Une base duales intersecte tous les circuits et est minimal avec cette propriété. Une base duales intersecte tous les circuits, et tout point de la base peut se regrouper avec des points en dehors de la base pour former un circuit.

`bbbB^** = {¬X "/" X "∈"bbbB}`
`bbbB^** = "∁"(bbbB)`
`bbbB^** = "∁"("max"(bbbI))`
`bbbB^** = "∁"("max"({X "/" X"∉"D}))`
`bbbB^** = "∁"("max"({X "/" AAC"∈"bbbC, C "⊈"X}))`
`bbbB^** = "min"({X "/" AAC"∈"bbbC, X"∩"C"≠"Ø})`
`bbbB^** = {X "/" (AAC"∈"bbbC, X"∩"C"≠"Ø) "et" (AAe"∈"X, EEC"∈"bbbC, (X"-"{e})"∩"C"="Ø)}`

La famille des bases duales d'un matroïde possède les mêmes axiomes que ceux de la famille des bases d'un matroïde. Autrement dit une famille `bbbF` correspondra à la famille des bases duales d'un martroïde si elle satisfait l'axiome du non vide `P_7(bbbF)` et l'axiome d'échange `P_8(bbbF)`.

15) Preuve que la famille des compléments des bases d'un matroïde est encore la famille des bases d'un matroïde.

Etant donné la famille des bases `bbbF` d'un matroïde. C'est à dire une famille `bbbF` satisfaisant les deux axiomes `P_7(bbbF)` et `P_8(bbbF)`. Nous allons vérifier que la famille des compléments `"∁"(bbbB)` satisfait également ces deux propriétés.

D'après l'axiome de non vide, il existe au moins une base. Le complément de cette base constitue une base duale. On en déduit qu'il existe au moins une base duale.

 `bbbF"≠"Ø` donc `"∁"bbbF"≠"Ø`

Etant donné deux bases `A`, `B` et un élément `e` appartenant à `A"\"B`, d'après l'axiome d'échange, il exite un élément `f` appartenant à `B"\"A` tel que `(A"-"{e}"+"{f})` est une base.

Les formules suivantes sont équivalentes :

`AAX "∈" bbbF, AAY "∈" bbbF, AAe"∈"X"\"Y, EE f "∈" Y"\"X, (X"-"{e}"+"{f})"∈" bbbF`

`AAX "∈" bbbF, AAY "∈" bbbF, AAe"∈"¬Y"\"¬X, EE f "∈" ¬X "\"¬Y, ¬(¬X"+"{e}"-"{f})"∈" bbbF`

`AAX "∈" "∁"bbbF, AAY "∈" "∁"bbbF, AAe"∈"Y"\"X, EE f "∈" X "\"Y, (X"+"{e}"-"{f})"∈""∁" bbbF`

`AAX "∈" "∁"bbbF, AAY "∈" "∁"bbbF, AAe"∈"X"\"Y, EE f "∈" Y "\"X, (Y"+"{e}"-"{f})"∈""∁" bbbF`

`AAX "∈" "∁"bbbF, AAY "∈" "∁"bbbF, AAe"∈"X"\"Y, EE f "∈" Y "\"X, (Y"+"{e}"-"{f})"∈""∁" bbbF`

et à cause d'une symétrie (qui reste à formaliser...)

`AAX "∈" "∁"bbbF, AAY "∈" "∁"bbbF, AAe"∈"X"\"Y, EE f "∈" Y "\"X, (X"+"{f}"-"{e})"∈""∁" bbbF`

`AAX "∈" "∁"bbbF, AAY "∈" "∁"bbbF, AAe"∈"X"\"Y, EE f "∈" Y "\"X, (X"-"{e}"+"{f})"∈""∁" bbbF`

16) Les indépendants duals

La famille des indépendants duals est nommée `bbbI^**`. Les indépendants duals s'obtiennent à partir des bases duales de la même façon que les indépendants s'obtiennent des bases, par cloture par inclusion.

`bbbI^** = "inf"(bbbB^**)`
`bbbI^** = {X "/" EEB"∈"bbbB^**, X"⊆"B}`

Tout point appartenant à un indépendant dual admet un circuit composé du point en question et d'autres points tous à l'exterieur de l'indépendant dual.

`X"∈"bbbD^**  <=>   AAe"∈"X, EE C"∈"bbbC, C"∩"X"="{e}`

La famille des indépendants duals d'un matroïde possède les mêmes axiomes que ceux de la famille des indépendants d'un matroïde. Autrement dit une famille `bbbF` correspondra à la famille des indépendants duals d'un martroïde si et seulement si elle satisfait l'axiome du vide inclus `¬P_1(bbbF)`, l'axiome de clôture par inclusion `P_5(bbbF)` et l'axiome d'agrandissement `P_6(bbbF)`.

17) Les dépendants duals

La famille des dépendants duals est nommée `bbbD'`. Les dépendants duals s'obtiennent à partir des indépendants duals de la même façon que les dépendants s'obtiennent des indépendants, par la négation.

`bbbD^** = ¬(bbbI^**)`
`bbbD^** = {X "/" X "∉"bbbI^**}`

La famille des dépendants duals d'un matroïde possède les mêmes axiomes que ceux de la famille des dépendants d'un matroïde. Autrement dit une famille `bbbF` correspondra à la famille des dépendants duals d'un martroïde si et seulement si elle satisfait l'axiome du vide exclus `P_1(bbbF)`, l'axiome clôture par agrandissement.`P_4(bbbF)` et l'axiome d'élimination `P_3(bbbF)`

18) Les coupures

La famille des coupures est nommée `bbbC'`. Les coupures s'obtiennent à partir des dépendants duals de la même façon que les circuits s'obtiennent des dépendants, par frontière minimum.

`bbbC^** = "min"(bbbD^**)`
`bbbC^** = {X "/" X"∈"bbbD^** "et" AAY"∈"bbbD^**, Y "⊄"X}`

La famille des coupure d'un matroïde possède les mêmes axiomes que ceux de la famille des circuits d'un matroïde. Autrement dit une famille `bbbF` correspondra à la famille des coupures d'un martroïde si et seulement si elle satisfait l'axiome du vide exclus `P_1(bbbF)`, l'axiome de frontière `P_2(bbbF)` et l'axiome d'élimination `P_3(bbbF)`

---- 14 mai 2017 ----

 

Les opérérations `"min"` et `"sup"` sont l'inverse l'une de l'autre pour les familles `bbbF` possèdant la caractéristique `P_2(bbbF)` dite "Frontière" ou bien la caracteristique `P_4(bbbF)` dite "Sup", et font passer les familles d'une caractéristique à l'autre.



Dominique Mabboux-Stromberg