Les graphes

1) La notion de graphe

Un graphe est un ensemble de sommets reliés totalement ou partiellement par des arcs.

Un graphe partiel s'obtient en enlevant des arcs. Un sous-graphe s'obtient en enlevant des sommets, ce qui enlève les arcs dont la définition utilise des sommets enlevés. Un sous-graphe partiel s'obtient en enlevant des sommets et des arcs, ce qui enlève en plus les arcs dont la définition utilise des sommets enlevés.

Est associé à la notion de graphe, une notion plus physique qu'est le libre déplacement selon le sens des arcs. Le graphe se présente alors comme un labyrinthe et il y a deux sortes d'arcs, les arcs orientés en forme de flèche appelés arcs et les arcs non orientés que nous appelons arêtes. Dans un arc le passage ne peut se faire que dans le sens de la flèche. Dans une arête le passage peut se faire dans les deux sens.

Le graphe est dit orienté si tous les arcs sont orientés et forment des flèches. Le graphe est dit non orienté si tous les arcs sont non orientés et sont donc des arêtes . Le graphe est dit mixte s'il peut contenir à la fois des arcs orientés et des arcs non orientés c'est à dire s'il peut contenire à la fois des arcs et des arêtes.

Le graphe est valué si chaque arc possède une valeur appelée poids.

2) La notion d'indiscernabilité

Remarquez que le concept de valuation et d'identification sont de même nature. Ainsi une identification est une forme de valuation. Et réciproquement une valuation peut permettre d'identifier, de discerner.

La notion d'indiscernables joue un rôle essentiel en combinatoire comme en physique quantique, c'est pourquoi on lui donne une place importante d'emblée.

Dans la définition classique des graphes, implicitement, tous les sommets sont identifiés. Par contre les arcs (arcs orientés) ne sont identifiés que par leurs couples de sommets, sommet de départ et sommet d'arrivé. Et les arêtes (arcs non orientés) ne sont identifiés que par l'ensemble de leur extrémités, c'est à dire par une paire ou un singleton ou dit autrement par un multiensemble de deux sommets. Les sommets sont tous distincts mais pas les arcs. Il peut y avoir plusieurs fois un même arc. On appel cela des arcs multiples. Les arcs multiples d'un même arc sont indiscernables entre eux. Ainsi on parle d'ensembles des sommets et de multiensembles d'arcs. L'ensemble ne contient que des sommets distincts tandis que le multiensemble peut contenir un même arc plusieurs fois.

Or il est tout à fait possible de considérer la position inverse, que tous les arcs soient identifiés, c'est à dire qu'ils portent un nom distinct, qu'ils soient numérotés, et que les sommets ne soient identifiés que par leur agencement vis-à-vis des arcs, c'est à dire, dans un graphe non-orienté, par l'ensemble des arcs qui leurs sont incidents, ou dans un graphe orienté, par deux ensembles que sont l'ensemble des arcs partant du sommet en question et l'ensemble des arcs arrivant sur le sommet en question.

3) Les théories incomplètes

Une théorie est une proposition et il n'y a pas de différence entre théorie et proposition. Toutes deux sont soumises à la même restriction d'être de type fini, c'est à dire, pour résumer sous forme d'un pléonasmes, engendrées par un nombre fini de propositions.

Une théorie est définie de manière intuitionniste. Elle doit être engendrée par un ensemble fini de propositions. La théorie est la conjonction de ces propositions.

On associe à chaque théorie `T` sa cloture `"<"T">"` qui est l'ensemble de toutes les propositions qu'elle peut démontrer. Ainsi la proposition `T|--A` qui signifie que `T` démontre `A`, est équivalente à la proposition d'appartenance `A in "<"T">"`, et est aussi équivalente à la proposition d'inclusion `"<"A">" sub "<"T">"`. Deux théorie `A, B` sont équivalentes si et seulement si `"<"A">"="<"B">"`.

Une théorie `T` est par nature incomplète, c'est à dire qu'il existe toujours des propositions que la théorie ne peut pas trancher. Lorsque on rencontre une telle proposition `A` non tranchée par `T`, alors il existe deux façons de complété la théorie `T`, en lui ajoutant la proposition `A` ou bien en lui ajoutant sa négation `¬A`, toutes deux n'étant pas contradictoires avec `T`.

La théorie `A` est dite non tranchée par la théorie `T` si et seulement si `T` ne peut pas démontrer ni `A` ni sa négation `¬A`. Et la théorie `A` est dite tranchée par la théorie `T` si et seulement si la théorie `T` démontre `A` ou bien démontre sa négation `¬A`. Notez que ce n'est pas le tiers exclu qui est remis en cause ici, mais l'incomplétude de la théorie `T` qui est affirmée.

`(A` n'est pas tranché par `T) <=> ((T⊬A)" et "(T⊬¬A))`
   `(A` est tranché par `T) <=> ((T|--A)" ou "(T|--¬A))`

La théorie `T` peut être complétée en lui ajoutant une théorie `A` qui n'est pas tranché par `T` pour obtenir une théorie `W` plus complète.

`W <=> (T " et " A)`
`"<"W">" = "<" T " et " A ">"`
`"<"W">" = "<" "<T>" uu "<"A">" ">"`

`W |-- T`
`W |-- A`
`"<"T">" sub"<"W">"`
`"<"A">" sub"<"W">"`

On dira que `W` contient strictement `T` ou compléte `T`. On dira également que `T` est inclus strictement dans `W` ou réduit `W`. Et on écrira :

`(W|--T) " et " (T⊬W)`

Pour chaque théorie `T`, l'ensembles des théories se partitionnent en 3 parties que sont  `"<"T">"`, `"<"¬T">"` et `ccIT`.

  1. L'ensemble `"<"T">"` regroupe les théories démontrables par `T`.
  2. L'ensemble `"<"¬T">"` regroupe les théories démontrables par `¬T`.
  3. L'ensemble `ccIT` regroupe les théorie non tranchées par `T`.

Notez que contrairement à l'ensemble `<T>` et l'ensemble `<¬T>`, l'ensemble `ccIT` n'est pas une théorie, car c'est un ensemble infini de propositions avec leurs négations et qui est évidement non clos.

4) La notion d'indiscernabilité logique

Deux éléments `x`, `y` sont dits d'égalité non tranchée par la théorie `T` si et seulement si `T` ne peut pas démontrer ni leur égalité ni leur inégalité. Et ils sont dits d'égalité tranché par la théorie `T` si et seulement si `T` démontre leur égalité ou démontre leur inégalité.

`(x=y` n'est pas tranché par `T) <=> ((T⊬x=y)" et "(T⊬x!=y))`
    `(x=y` est tranché par `T) <=> ((T|--x=y)" ou "(T|--x!=y))`

Parcontre la notion d'indiscernabilité ne cherche pas à respecter la symétrie logique de la négation. Deux éléments `x`, `y` sont dits indiscernables logiquement par la théorie `T` si et seulement si la théorie `T` ne peut pas démontrer leur inégalité.

`{x,y}` est  `T`-indiscernable `   <=>    (T⊬x!=y)`
`{x,y}` est  `T`-discernable `   <=>    (T|--x!=y)`

Et `{x,y}` est  `T`-discernable se note simplement `x!=_Ty`

Mais la pertinence de cette notion réside néanmoins dans le fait que l'on discerne `x` de `y` dans une théorie plus forte, faisant qu'il est possible de poser la question : Est-ce que la théorie plus faible `T` discerne toujours `x` de `y` ?.

Les ensembles sont notés en énumérant leurs éléments entre crochet `{...}`. Si un même élément est répété plusieurs fois, il ne compte que pour un même élément. Par exemple, considérons un ensemble `E` définie par `E={x,y,z}`. Si on ne ne précise pas que les éléments `x, y, z` sont distincts, alors le nombre d'éléments de `E`, appellé cardinalité de `E` et que l'on note `|E|`, peut être égale à `1`,`2` ou `3`.

Un graphe peut être décrit par une théorie `T` trés incomplète ne permettant pas d'identifier tous les sommets et tous les arcs. Il est alors possible de compléter la théorie `T` de façon appropriée en une théorie `W` afin d'identifier tous les sommets et tous les arcs du graphe que l'on veut concevoir. On définie ainsi deux niveaux théoriques, un premier niveau défini par une théorie complété `W` dite forte, et un second niveau défini par la théorie trés incomplète `T` dite faible. Cela permet de définir précisement ce qu'est l'indiscernabilité. La théorie forte discerne davantage que la théorie faible. Et on les mets dans cette ordre, au niveau le plus bas, la théorie la plus forte permettant de manipuler tous les éléments puisque discernés par la théorie, et au niveau le plus haut, la théorie faible qui indifférencie un certain nombre d'éléments et ne tranche plus un certain nombre de propriétées.

5) Les graphes

Un graphe est définie classiquement par le couple `(X, U)``X` est un ensemble de sommets et où `U` est un multiensemble d'arcs définis sur ces sommets. Un arc est identifié par ses sommets de départ et d'arrivé, et s'il y a plusieurs arcs reliant deux mêmes sommets, implicitement ces arcs sont indiscernables, l'arc est dit multiple, sa multiplicité est le nombre d'arc indiscernables. C'est pourquoi `U` est un multiensemble pour pouvoir contenir plusieurs fois le même arcs, autant de fois qu'il y en a sur le graphe.

Le nombre de sommets se note `N = |X|` et s'appel l'ordre du graphe. Le nombre d'arcs se note `M = |U|`, c'est la sommes des valeurs de répétition de chaque arcs dans le multiensemble `U`, c'est le nombre totale d'éléments du multiensemble `U` comprenant les éléments identiques qui peuvent être répétés plusieurs fois dans le multiensemble.

La propriété logique de pouvoir passer de `x` à `y` par un arc du graphe, dans un sens autorisé, se note toujours `x U y`. Le symbole `U` désigne alors un prédicat binaire, une relation, définie sur `X`.

On dira qu'un arc part du sommet `x` s'il est possible d'emprunté cet arc à partir de `x` en respectant un sens autorisé de l'arc en question. De même on dira qu'un arc arrive sur le sommet `x` s'il est possible d'arrivé sur `x` en empruntant cet arc dans un sens autorisé.

Un sommet isolé est un sommet sur lequel ne part et n'arrive aucun arc. Notez qu'un sommet sur lequel les seuls incidences sont faites par un ou plusieurs arcs boucles n'est pas considéré ici comme un sommet isolé contrairement à la vision classique, mais comme une composante connexe isolée comprenant un sommet et un ou plusieurs arcs boucles sur ce sommet. Cette position se justifie par le fait qu'un arc est une composante du graphe aussi importante qu'un sommet. Et le fait pour un sommet d'être relié à un arc, fait qu'il n'est plus isolé. Le sommet munie de ses boucles forme une composante connexe qui peut être, elle, isolée, c'est à dire telle qu'aucun autre sommet ni arc du graphe ne viennent en interaction.

Une boucle est un arc partant et arrivant sur le même sommet.

Un sommet terminal est un sommet sur lequel ne part aucun arc, par contre il peut en arriver. Par analogie avec les arbres, les sommets terminaux s'appellent des feuilles.

Un sommet initial est un sommet sur lequel n'arrive aucun arc, par contre il peut en partir. Par analogie avec les arbres, les sommets initiaux s'appellent des racines.

Il ne nous semble pas pertinent pour l'instant de définir d'emblée des notations symétriques selon l'orientation des arcs car cela correspond à l'utilisation du graphe orienté inversé où tous les arcs sont inversées ou bien du graphe désorienté où chaque arc est dépourvue de son orientation, etc..., toute chose qui peut être faite par des macro-opérations.

Aussi nous serons amené à poser des définitions sans se préoccuper de leur définition symétrique sachant que pour obtenir leur version symétrique on usera de macro-opérations sur le graphe entier.

Mais il est toujours utile de rechercher une grammaire et les noms en français pour désigner les objets et concepts, fussent-t-il symétriques (comme par exemple feuille et racine), qui soient les mieux adaptés c'est à dire dont le sens intuitif commun épouse l'intuition de l'objet ou du concept en question. D'une part on donne matière à réflechir à nos académiciens, et d'autre part on vulgarise la science, et on la démocratise.

Dans cette approche constructive on remarque que le multiensemble des arcs `U` contient toute l'information nécessaire pour définir le sous-graphe obtenu en enlevant les sommets isolés. C'est pourquoi il existe une façon plus courte de définir un graphe sans sommets isolés, on le définie par un multiensemble d'arcs `U`, les sommets du graphe étant désignés par les extrèmités des arcs. Autrement dit un graphe sans sommet isolé est défini par un multiensemble d'arcs.

6) Les relations binaires et les relations unaires

Un ensemble `E` muni d'une relation binaire `R` définie un graphe orienté dans lequel aucun arc n'est multiple. On note ce graphe `(E,R)`. Les sommets sont les éléments de `E`. Les arcs sont les couples `(x,y)` d'éléments de `E` satisfaisant la relation `R` c'est à dire tel que `xRy`. La relation `R` est identifiée à son graphe c'est à dire à un ensemble de couples inclus dans `E×E`. Les arcs sont les couples `(x,y) in R`.

`(E,R)` est un graphe sans boucle si et seulement si la relation `R` est antireflexive, `AAx, AAy,  ¬ xRy`.

`(E,R)` est un graphe non orienté si et seulement si la relation `R` est symétrique, `AAx, AAy,  xRy => yRx`, et si à chaque fois que `x!=y`, on compte pour un seul arc non orienté les deux arcs `xRy` et `yRx` qui sont ainsi en tête-bêche.

`(E,R)` est un graphe simple si et seulement si la relation `R` est symétrique et antireflexive, et si à chaque fois que `x!=y`, on compte pour un seul arc non orienté les deux arcs `xRy` et `yRx` qui sont ainsi en tête-bêche.

L'étude des graphes passe par l'étude des relations binaires, qui peuvent vues comme des prédicats binaires. Mais il y a une structure plus simple qui doit être étudiée avant, qu'est la relation unaire, le prédicat unaire, c'est à dire les ensembles et multi-ensembles.

Les structures mathématiques dans l'approche intuitionniste ne sont rien d'autre que des structures de données. Et la maîtrise de ces structures premières constitue la base de la programmation en informatique.

Un ensemble `E` peut être vu comme un prédicat unaire `E"(.)"` opérant dans un ensemble mère `bbbM` beaucoup plus vaste et souvent plus simple à la fois.

`E : bbbM->{0,1}`
      `x|->0`  si `x` n'appartient pas à `E`
      `x|->1`  si `x` apart iet à `E`

Comme on ne considère ici que des ensembles finis, la troisième possibilité, celle qui n'est pas tranchée, n'existe pas. Car un ensemble est défini par un énumérateur de ses éléments. Et donc s'il est fini, l'appartenance ou pas d'un élément est nécessairement tranchée.

On identifie la valeur logique faux à `0` et la valeur logique vrai à `1`. La proposition `E(a)` signifie que l'élément `a` appartient à `E` et la proposition `¬E(a)` signifie que `a` n'appartient pas à `E`. Ces ensembles munis des opérations logiques forment l'algèbre de Boole comme nous allons le voir.

Puis il faut considéré les éléments multiples, qui sont par nature indiscernables entre eux. On obtient la définition des multi-ensembles qui peuvent contenir un même élément plusieurs fois. Cela se fait en considérant à la place du prédicat `E(.)` qui est une fonction de `bbbM->{0,1}`, une valuation plus riche notée de la même façon `E(.)` et qui est une fonction `bbbM->NN`, la valeur de cette valuation indiquant la multiplicité de l'élément.

Ces multiensembles munis des opérations logiques forment également une algèbre de Boole comme nous allons le voir, et dans laquelle il existe des éléments indifférentiés qui se comportent d'une façon particuliaire et que nous allons décrire. Ces multiensembles munis de l'opération d'union, qui correspond au `"ou"` logique, forme un monoïde commutatif libre comme nous allons le voir.

7 Les ensembles

Un ensemble est constitué d'éléments distincts donc discernables. Et il est donc ordonnable. Il est ordonné par le système de représentation que le contexte a choisie pour permettre de désigner chaque élément distinctement, de tel sorte que chaque élément de `E` est identifié et est numéroté.

On note entre accolades `{...}` les éléments d'un ensemble. Si entre les accolades un élément est répété plusieurs fois, alors il n'est comptabilisé que comme un seul élément. Le nombre d'élément de l'ensemble correspond au nombre d'éléments distincts de l'ensemble. Exemple `{a,b,a} = {a,b}`.

Étant donné un ensemble `E`, on note `|E|` la cardinalité de l'ensemble `E`. C'est le nombre d'éléments de l'ensemble `E`. Dans la suite du document on pose que `E` possède `n` éléments.

`|E|=n`

On note `ccP(E)` l'ensemble des sous-ensembles de `E`. Un sous-ensemble de `E`, appellé aussi une partie de `E`, peut être représenté par l'ensemble des éléments de `E` valués par des booléens `{0,1}`, ce booléen déterminant si l'élément appartient ou non au sous-ensemble en question. Autrement dit, un sous-ensemble de `E` peut être représenté par une application de `E->{0,1}` que l'on note aussi `{0,1}^E`, et qui représente un `n`-uplet de booléen. C'est pourquoi on les identifie quelque fois comme suit :

`ccP(E)   =   E->{0,1}   =   {0,1}^E`

Notez que l'expression `A->B` désigne l'ensemble des applications de `A` vers `B`. On déduit la cardinalité de l'ensemble des parties de `E`.

`|ccP(E)| = 2^n`

On note `ccP_2(E)` l'ensemble des sous-ensembles de `E` de cardinalité `2`. C'est l'ensemble des paires d'éléments de `E`. On appel une paire, un ensemble de deux éléments distincts que l'on peut ordonner. Ici, les éléments étant numérotés, on peut toujours les ordonner.

`|ccP_2(E)| = (n(n-1))/2`

On note `ccP_q(E)` l'ensemble des sous-ensembles de `E` de cardinalité `q`.

`|ccP_q(E)| = (n(n-1)(n-2)...(n-q+1))/(q!)`

Remarquez que `|ccP_0(E)| = 1` et que `|ccP_1(E)| = n`.

On note `ccP_(<=q)(E)` l'ensemble des sous-ensemble de `E` et de cardinalité au plus égale à `q`. Nous avons :

`ccP_(<=q)(E) = ccP_0(E) uu ccP_1(E) uu ccP_2(E) uu ccP_3(E) uu ... uu ccP_q(E)`

Et il s'agit d'une réunion d'ensembles disjoints donc :

`|ccP_(<=q)(E)| = |ccP_0(E)| + |ccP_1(E)| + |ccP_2(E)| + |ccP_3(E)| + ... + |ccP_q(E)|`

`|ccP_(<=q)(E)| = 1 + n + (n(n-1))/2 + (n(n-1)(n-2))/(3!) + ... + (n(n-1)(n-2)...(n-q+1))/(q!)`

8) Les algèbres de Boole

L'ensemble des parties de `E` munie des opérations logiques forme une structure mathématique appelée algèbre de Boole. Voici comment sont définis ces opérations logiques. On considère deux sous-ensembles `A` et `B` de `E` :

Intitulé
Notation
ensembliste
Expression
Notation
logique
Autre notation
logique
Complément
`barA`
`{x"/" x in E " et " x!inA}`
`¬A`
Intersection
`AnnB`
`{x "/" x in A " et " x in B}`
`A " et " B`
Réunion
`AuuB`
`{x "/" x in A " ou " x in B}`
`A" ou " B`
Différence
`A\\B`
`{x "/" x in A " et " x !in B}`
`A " et " ¬B`
`¬(A=>B)`
Différence symétrique
`ADeltaB`
`{x "/" x in A " w " x in B}`
`A " w " B`
`¬(A<=>B)`

Par soucis de simplifier la notation, on utilise directement les opérateurs logiques pour opérer sur les ensembles. L'algèbre de Boole est définissable comme un treillis `(ccP(E), "et", "ou", Ø, E )` ou bien comme un anneaux de caractéristique 2 , `(ccP(E), "w", "et", Ø, E)`.

On remarque que certains opérateurs logiques sont définis indépendament de l'ensemble mère, ceux qui ne font pas intervenir le complément `"et"`, `"ou"`, `"¬"=>`, `"w"`.

Chaque algèbre de Boole de type fini est isomorphe à une algèbre de Boole des parties d'un ensemble fini.

9 Les multi-ensembles

On note entre accolades doubles `"{{"..."}}"` les éléments d'un multiensemble, aussi appelé sac. Étant donné un ensemble `E`, un sac de support `E` est un sac composé d'éléments de `E` qui peuvent être répétés en nombre quelconque.

On note `ccS(E)` l'ensemble des sacs de support `E`.

Notez que dans un sac les éléments multiples sont indifférenciés.

La cardinalité d'un sac est la sommes des valeurs de répétition de chaque élément dans le sac, c'est le nombre totale d'éléments du sac comprenant les éléments identiques qui peuvent être répétés plusieurs fois dans le sac.

La base d'un sac est l'ensemble des éléments apparaissant dans le sac. La cardinalité de la base du sac est évidement inférieur ou égale à la cardinalité du sac, c'est le nombre d'éléments distincts du sac.

Un sac de support `E` peut être représenté par l'ensemble des éléments de `E` valués par des entiers naturels `NN={0,1,2,3,...}`, cet entier déterminant combien de fois l'élément est répété. Autrement dit, un sac de support `E` peut être représenté par une application de `E->NN` que l'on note aussi `NN^E`, et qui représente un `n`-uplet d'entiers naturels. Mais on peut également ne compter que les répétitions strictes. Cela nous permet de représenter le sac `E` par un sous ensemble `A` de `E` dont les éléments sont valués par des entiers strictement positif `{1,2,3,...}`. Autrement dit, un sac de support `E` peut être représenté par une application de `A->{1,2,3,...}``A in ccP(E)`. C'est pourquoi on les identifie quelque fois comme suit :

`ccS(E)   =   E->NN   =   NN^E   =   uuu_(AinccP(E)) A->{1,2,3,...}`

On note `ccS^((p))(E)` l'ensemble des sacs de support `E` où les éléments ne peuvent être répétés qu'au plus `p` fois. Par une même analogie, cet ensemble peut être représenté par l'ensemble des éléments de `E` valués par des entiers appartenant à `{0,1,2,...,p}` qui indique combien de fois ils sont répétés. Autrement dit, `ccS^((p))(E)` peut être représenté par une application de `E->{0,1,2,...,p}` que l'on note aussi `{0,1,2,...,p}^E`, et qui représente un `n`-uplet d'entiers appartenant à `{0,1,2,...,p}`. C'est pourquoi on les identifie souvent :

`ccS^((p))(E)   =   E->{0,1,2,...,p}  =   {0,1,2,...,p}^E   =   uuu_(AinccP(E)) A->{1,2,3,...,p}`

On en déduit la cardinalité de l'ensemble des sacs de `E` où les éléments ne peuvent être répétés qu'au plus `p` fois.

`|ccS^((p))(E)| = p^n`

On note `ccS_q(E)` l'ensemble des sacs de support `E` de cardinalité `q`.

`|ccS_0(E)| = |ccP_0(E)|` `= 1`

`|ccS_1(E)| = |ccP_1(E)|`

`= n`
`|ccS_2(E)| = |ccP_2(E)| + |ccP_1(E)|` `= (n(n-1))/2 + n`
`|ccS_3(E)| = |ccP_3(E)| + |ccP_2(E)| + |ccP_1(E)| ` `= (n(n-1)(n-2))/(3!) + (n(n-1))/2 + n`

`|ccS_4(E)| = |ccP_4(E)| + |ccP_3(E)| + ``2``|ccP_2(E)| + |ccP_1(E)| = (n(n-1)(n-2)(n-3))/(4!) + (n(n-1)(n-2))/(3!) + ``2``(n(n-1))/2 + n`

Le facteur 2 provient du fait qu'un sac de 4 éléments basé sur 2 éléments distincts est de la forme `{{x,x,x,y}}` ou `{{x,x,y,y}}`

`|ccS_5(E)| = |ccP_5(E)| + |ccP_4(E)| + ``2``|ccP_3(E)| + ``2``|ccP_2(E)| + |ccP_1(E)|`

Le premier facteur 2 provient du fait qu'un sac de 5 éléments basé sur 3 éléments distincts est de la forme `{{x,x,x,y,z}}` ou `{{x,x,y,y,z}}`. Le second facteur 2 provient du fait qu'un sac de 5 éléments basé sur 2 éléments distincts est de la forme `{{x,x,x,x,y}}` ou `{{x,x,x,y,y}}`.

On note `ccS_q^((p))(E)` l'ensemble des sacs de support `E` de cardinalité `q` et où chaque élément ne peut être répété qu'au plus `p` fois.

Et on note `ccS_(<=q)^((p))(E)` l'ensemble des sacs de support `E` de cardinalité au plus `q` éléments et où chaque élément ne peuvent être répété qu'au plus `p` fois.

8) Les algèbres de Boole

L'ensemble des parties de `E` munie des opérations logiques forme une structure mathématique appelée algèbre de Boole. Voici comment sont définis ces opérations logiques. On considère deux sous-ensembles `A` et `B` de `E` :

Intitulé
Notation
ensembliste
Expression
Notation
logique
Autre notation
logique
Complément
`barA`
`{x"/" x in E " et " x!inA}`
`¬A`
Intersection
`AnnB`
`{x "/" x in A " et " x in B}`
`A " et " B`
Réunion
`AuuB`
`{x "/" x in A " ou " x in B}`
`A" ou " B`
Différence
`A\\B`
`{x "/" x in A " et " x !in B}`
`A " et " ¬B`
`¬(A=>B)`
Différence symétrique
`ADeltaB`
`{x "/" x in A " w " x in B}`
`A " w " B`
`¬(A<=>B)`

Par soucis de simplifier la notation, on utilise directement les opérateurs logiques pour opérer sur les ensembles. L'algèbre de Boole est définissable comme un treillis `(ccP(E), "et", "ou", Ø, E )` ou bien comme un anneaux de caractéristique 2 , `(ccP(E), "w", "et", Ø, E)`.

On remarque que certains opérateurs logiques sont définis indépendament de l'ensemble mère, ceux qui ne font pas intervenir le complément `"et"`, `"ou"`, `"¬"=>`, `"w"`.

Chaque algèbre de Boole de type fini est isomorphe à une algèbre de Boole des parties d'un ensemble fini.

 

 

 

9 Les monoïdes commutatifs de type fini

L'ensemble des sacs de support `E` munie de l'opérations d'union forme une structure mathématique appelée un monoïde commutatif. La structure est engendré par les éléments de `E`. Un élément d'un sac se présente comme un mot composé de lettre où les lettres sont des éléments de `E`. Par exemple le sac `{a,b,b,a,c,a,b,b,a,c,c}` correspond au mot `abbacabbacc` qui grace à la commutativité est égale au mot `aaaabbbbccc`. Cette représentation admet une forme normal où les éléments sont rangés dans l'ordre alphabétique.

En identifiant `E` à l'ensemble des sacs singletons de support `E`, c'est à dire `E = ccS_1(E)`, la structure `(ccS(E), uu)` correspond au monoïde commutatif libre engendré par `E`.

Il est possible de munir l'ensemble des sacs de supports des mêmes opérations logiques opérant sur les ensembles mais en tenant compte de la multiplicité des éléments. La réunion ajoute les multiplicités, l'intersection prend le minimum des multiplicités. On obtient alors une algèbre de Boole. Voici comment sont définis ces opérations logiques. On considère deux sous-ensembles `A` et `B` de `E` :

 

 

 

8) Les algèbres de Boole

L'ensemble ccS(p)(E) muni des opérations logiques forme une algèbre de Boole. Voici comment sont définis ces opérations logiques. On considère deux sous-ensembles `A` et `B` de `E` :

Intitulé
Notation
ensembliste
Expression
Notation
logique
Autre notation
logique
Complément
`barA`
barA(x) = p-A(x)
`¬A`
Intersection
`AnnB`
`(AnnB)(x) = Min(A(x),B(a))`
`A " et " B`
Réunion
`AuuB`
`(AuuB)(x) = A(x)+B(a)`
`A" ou " B`
Différence
`A\\B`
`(A\\B)(x) = Max(0,A(x)-B(x))`
`A " et " ¬B`
`¬(A=>B)`
Différence symétrique
`ADeltaB`
`(ADeltaB)(x) = ||A(x)-B(x)||`
`A " w " B`
`¬(A<=>B)`

 

Par soucis de simplifier la notation, on utilise directement les opérateurs logiques pour opérer sur les ensembles. L'algèbre de Boole est définissable comme un treillis `(ccP(E), "et", "ou", Ø, E )` ou bien comme un anneaux de caractéristique 2 , `(ccP(E), "w", "et", Ø, E)`.

On remarque que certains opérateurs logiques sont définis indépendament de l'ensemble mère, ceux qui ne font pas intervenir le complément `"et"`, `"ou"`, `"¬"=>`, `"w"`.

Chaque algèbre de Boole de type fini est isomorphe à une algèbre de Boole des parties d'un ensemble fini.

 

 

 

 

 

 

8) Les différents types de graphe

Un arc non orienté correspond à deux arcs orientés tête-bêches indifférenciés. La différence tient dans le dénombrement des arcs, et sur la propriété physique de l'arc qu'est le libre déplacement selon les deux sens.

Etant donné un graphe `(X,U)``X` est l'ensemble des sommets et `U` est le multiensemble des arcs. L'ordre du graphe se note `N=|X|`. Le nombre d'arcs du graphe se note `M=|U|`.

Dans notre exploration différents types de graphe vont apparaîtrent. Et pour chaque type de graphe, le graphe sera dit complet si et seulement si on ne peut pas ajouter d'arc ou d'arête sans changer le type du graphe.

La notion de complétude sous-entend une propriété supplémentaire importante qu'est l'unicité de cette complétude pour chaque valeur d'état du système, ces variables d'état étant décrites dans la définiton du type de graphe considéré. Cela constitue une restriction sur ce que l'on appelle un type de graphe pouvant être complet.

On commence par ne considérer comme variable d'état, que l'ordre du graphe `N=|X|`. Et on commence par considérer les graphes sans arcs multiples, sans boucle ou avec d'éventuelles boucles, des graphes orientés, non orientés ou mixtes, puis des graphes avec arcs multiples :

 

 

 

Par convention on ajoute un entier en préfixe du nom du type de graphe pour préciser le nombre de répétitions maximum autorisées par un arc. Par exemple dans un 3-graphe tous les arcs peuvent être répétés 3 fois.

Puis par défaut, le nom d'un type de graphe tel que par exemple "graphe" désignera un "1-graphe" en laissant le soin au contexte de lever l'ambiguité au cas ou l'on parlerait non pas d'un "1-graphe" mais d'un "`omega`-graphe", graphe ou les arcs peuvent être répétés un nombre fini quelconque de fois. Puis le nom particulier de "graphe" est très générale et peut être utilisé pour désigner autre chose qu'un "1-graphe" ou un "`omega`-graphe, il peut être utilisé pour désigner tout type de graphe qui aura été préalablement décrit dans le contexte.

Un arc non orienté désigne un arc autorisant les deux sens de déplacement. On qualifie cette propriété physique comme étant la troisième orientation possible d'un arc mixte. L'arc mixte possède 3 sens possibles ; le sens normal partant du grand sommet vers le petit sommet, le sens inverse partant du petit sommet vers le gransd sommet, et les deux sens en même temps.

Graphe

Un arc orienté est un couple de sommets de `X`. L'ensemble de tous les arcs orientés possibles est `X^2`. Le nombre d'arcs orientés distincts possibles est égale au carré du nombre de sommets `M=N^2`.

Un 1-graphe est un graphe ne possédant que des arcs orientés distincts. Le 1-graphe complet de `N` sommets possède `M=N^2` arcs. Le sac `U` regroupant les arcs d'un 1-graphe complet est `U = X^2`.

Graphe sans boucle

Un arc orienté qui n'est pas une boucle est un couple de sommets distincts de `X` c'est à dire un ensemble d'exactement 2 sommets distincts, que l'on ordonne par commodité afin d'avoir une forme normale unique, et on ajoute à cette structure de donnée, un booléen `{s1,s2}` indiquant le sens de l'arc. Le sens `s1` précise que l'arc part du grand sommet pour aller sur le petit sommet, et le sens `s2` précise l'inverse que l'arc part du petit sommet pour aller sur le grand sommet. L'ensemble de tous les arcs orientés non bouclés possibles est donc `ccP_2(X)×{s1,s2}`. Le nombre d'arcs orientés non bouclés distincts possibles est donc égale à `N(N-1)`.

Un 1-graphe sans boucle est un graphe ne possédant que des arcs orientés non bouclés distincts. Le 1-graphe sans boucle complet de `N` sommets possède `M=N^2-N` arcs. Le sac `U` regroupant les arcs d'un 1-graphe sans boucle complet est `U = ccP_2(X)×{s1,s2}`.

Graphe non orienté

Un arc non orienté est un sac de deux sommets de `X`. L'ensemble de tous les arcs non orientés possibles est donc `ccS_2(X)`. Le nombre d'arcs non orientés distincts possibles est égale au nombre de paires de sommet auquel on ajoute le nombre de sommets, c'est à dire `M = (N(N-1))"/"2 + N` et donc ` M = (N(N+1))"/"2`.

Un 1-graphe non orienté est un graphe ne possédant que des arcs non orientés distincts. Le 1-graphe non orienté complet de `N` sommets possède `M=N^2"/"2+N"/"2` arcs. Le sac `U` regroupant les arcs d'un 1-graphe non orienté complet est `U = ccS_2(X)`.

Graphe simple

Un arc non orienté qui n'est pas une boucle est une paire de sommets de `X` c'est à dire un ensemble d'exactement 2 sommets distincts de `X`. L'ensemble de tous les arcs non orientés non bouclés possibles est donc `ccP_2(X)`. Le nombre d'arcs non orientés non bouclés distincts possibles est donc égale à `N(N-1)"/"2`.

Un 1-graphe simple est un graphe ne possédant que des arcs non orientés non bouclés distincts. Le graphe simple complet de `N` sommets possède `M=N^2"/"2-N"/"2` arcs. Le sac `U` regroupant les arcs d'un 1-graphe simple complet est `U = ccP_2(X)`.

Graphe mixte

La définition des graphes mixtes nécessite quelque précision. L'orientation d'un arc dans un sens ou dans l'autre ou dans les deux sens à la fois, ne constitue pas une valuation. Car elle ne fait que traduire une propriété physique de l'arc, la capacité de libre déplacement dans les sens autorisés. Tout autre information constituerait un début de valuation arbitraire.

Se pose alors la question des arcs boucles. Quel différence physique y a-t-il entre un arc boucle orienté et un arc boucle non orienté ?... à cette étape de la définition classique d'un graphe mixte, et au vu de la façon dont est défini un arc, il n'y a pas de différence physique exprimable entre un arc boucle orienté et un arc boucle non orienté.

La conséquence de cela, est que la définition académique du graphe mixte ne fait pas la différence entre un arc boucle orienté et un arc boucle non orienté. Il y a donc `N` arcs boucles distincts possibles, et `3N(N-1)"/"2` arcs non bouclés distincts possibles. On utilise une troisième valeur de valuation `s3` pour désigner que l'arc non bouclé est non orienté, c'est à dire dans lequel les deux sens de déplacement sont autorisés.

Un 1-graphe mixte est un graphe ne possédant que des arcs distincts sachant qu'une boucle orienté n'est pas distincte d'une boucle non orienté. Le 1-graphe mixte complet de `N` sommets possède `M=3N(N-1)"/"2 + N` et donc `M=3N^2"/"2-N"/"2` arcs. Le sac `U` regroupant les arcs d'un 1-graphe mixte complet est `U = (ccP_2(X)×{s1,s2,s3})uuX`.

Graphe simple mixte

Un arc qui n'est pas une boucle est une paire de sommets de `X` c'est à dire un ensemble d'exactement 2 sommets distincts de `X`, que l'on ordonne par commodité afin d'avoir une forme normale unique, et on ajoute à cette structure de donnée, un booléen {s1,s2,s3} indiquant le sens de l'arc. Le sens `s1` précise que l'arc part du grand sommet pour aller sur le petit sommet, le sens `s2` précise l'inverse que l'arc part du petit sommet pour aller sur le grand sommet, et le sens `s3` précise que les deux directions sont autorisées. L'ensemble de tous les arcs non bouclés possibles est donc `ccP_2(X)×{s1,s2,s3}`. Le nombre d'arcs non bouclés distincts possibles est donc égale à `3N(N-1)/2`.

Un 1-graphe simple mixte est un graphe ne possédant que des arcs distincts sans boucle. Le graphe simple mixte complet de `N` sommets possède `M=3N(N-1)"/"2 + N` et donc `M=3N^2"/"2-3N"/"2` arcs. Le sac `U` regroupant les arcs d'un graphe simple mixte complet est `U = ccP_2(X)×{s1,s2,s3}`.

Nous avons ainsi définie 6 types de graphe que sont les graphes, les graphes sans boucle, les graphes non orientés, les graphes simples, les graphes mixtes, les graphes simples mixtes. Voici un description pour chacun d'eux :

Graphes complets
Dessin exemple
à deux sommets

Graphe avec d'éventuelles
boucles
Graphe sans boucle
Graphe orienté
1-graphes

`U=ccS(X^2)`
M=N^2
1-graphes sans boucle
dessin
`U=ccP_2(X)×{s1,s2}`
`M=N^2+N`
Graphe non orienté
1-graphes non orientés
dessin
`U=ccS_2(X)`
M=(N(N+1))/2
1-graphes simples
dessin
`U= ccP_2(X)`
`M=N^2"/"2-N"/"2`
Graphe mixte
1-graphes mixtes
dessin
`U=(ccP_2(X)×{s1,s2,s3})uu X`
`M=3N(N-1)"/"2 + N`
1-graphes simples mixtes
dessin
`U=ccP_2(X)×{s1,s2,s3}`
`M=3N^2"/"2-3N"/"2`

Puis on considère les `p`-graphes pour chacun des 6 types de graphe précédement décrits. Ce sont des graphes où les arcs peuvent être répétés au plus `p` fois. On remarque qu'un `p`-graphe correspond à un 1-graphe valué par `{1,2,3,...,p}`, et correspond aussi à un 1-graphe complet valué par les facteurs de multiplicité `{0,1,2,...,p}`.

Considérons un ensemble de sommets `X` et un des 6 types de graphe précédement décrits. Considérons le nombre `M` d'arcs du 1-graphe complet :

10) La fonction `Gamma` produisant l'ensemble des successeurs

Un sommet `y` est un successeur du sommet `x` s'il existe un arc partant de `x` pour aller sur `y`, ce qui se note par l'expression logique `xUy``U` représente le sac des arcs, et est utilisé ici comme une relation binaire qui affirme que l'on peut passer de `x` à `y` en parcourant un arc dans un sens autorisé.

On note `Gamma(x)` l'ensemble des successeurs de `x`. L'application `Gamma` est une application multivoque définie sur `X`, c'est à dire que appliquée à un élément elle retourne un ensemble d'éléments. On étend cette application, par union, à l'ensemble des parties de `X`. On définie ainsi l'ensemble des successeurs d'un ensemble `A` :

`Gamma(A) = uuu_(x in A)Gamma(x)`

Les successeurs de `x` sont les sommets que l'on peut atteindre à partir de `x` en traversant un arc dans son sens autorisé.

Les adjacents à `x` sont les successeurs de `x` autre que `x` lui-même. Le terme adjacent laisse pourtant sous-entendre que cette relation est symétrique. On choisie de dépasser cette signification en tenant compte de l'orientation des arcs. Ainsi dans le cas d'un graphe constitué de 2 sommets `a,b` et d'un seul arc `(a,b)`, le sommet `b` est adjacent au sommet `a` mais le sommet `a` n'est pas adjacent au sommet `b`. Pour obtenir la notion d'adjacence symétrique c'est à dire sans tenir compte de l'orientation des arcs, il suffit de transformer préalablement le graphe en graphe non orienté, où autrement dit de permettre dans les arcs de circuler dans les deux sens.

Voici quelques définitions relatives à la notion de succession et d'adjacence :

Libellé
Formule
Formule développée
Description
`y` est un successeur de `x`
`y in Gamma(x)`
`xUy`
Il existe un arc partant de `x` pour aller sur `y`
`B` est un successeur de `x`
`B sub Gamma(x)`
`AAy in B,  xUy`
Tous les sommets de `B` sont des successeurs de `x`
`y` est un successeur de `A`
`y in Gamma(A)`
`EE x in A,  xUy`
Il existe au moins un sommet de `A` qui possède `y` comme successeur.
`B` est un successeur de `A`
`B sub Gamma(A)`
`AAy in B,  EEx in A,  xUy`
Chaque sommet de `B` est un successeur d'au moins un sommet de `A`
`y` est adjacent à `A`
`y!in A "et" y in Gamma(A)`
`y!in A "et" EE x in A,  xUy`
`y` est un successeur de `A` sans appartenir à `A`
`B` est adjacent à `A`
`BnnA=Ø"  et  " B sub Gamma(A)`
`AAy in B,  y!in A "et" EEx in A,  xUy`
Chaque sommet de `B` est un successeur de `A` sans appartenir à `A`

11) Le graphe adjoint

La même terminalogie est appliquée aux arcs. Les successeurs d'un arc `m` sont les arcs que l'on peut composer pour faire un chemin de 2 arcs en commençant par l'arc `m`.

De même on définie les adjacents d'un arcs `m` comme étant les successeurs de `m` autre que `m` lui-même.

 

On complète l'analogie en définissant la notion de successeur non orientée à l'aide toujours d'une description uniquement physique. Le sommet `x` est un successeur non orienté à `y` si et seulement si on peut passer de `x` à `y` et de `y` à `x` par un même arc. Cette relation est plus fine, c'est à dire qu'un successeur non orienté est un successeur.

Un sommet adjacent non orienté et un sommet successeur non orienté autre que lui-même.

La même terminalogie est appliquée aux arcs. Les arcs successeurs non orientés d'un arc `m` sont les arcs `k` que l'on peut composer pour faire un chemin de 2 arcs `mk` et qui inversement peuvent être composés dans l'ordre opposé pour faire un chemin de deux arcs `km` mais en passant par le même sommet intermédiaire.

De même on peut définir un arc adjacent non orienté comme étant un arc successeur non orienté autre que lui-même.

Puis les arcs multiples se comportant identiquement il arait plus judicieux de les regrouper en un arc valué par un facteur de multiplicité. On complète l'analogie en définissant la notion de successeur de multiplicité p à l'aide toujours d'une description uniquement physique. L'arc `(x,y)` est un successeur de multiplicité p à l'arc (y,z) si et seulement si p est la valeur minimal entre la multiplicité de l'arc (x,y) et la multiplicité de l'arc (y,z).

On peut alors construire un graphe à l'aide de cette relation successeur. Cela dévoile une symétrie transformant les arcs distincts en sommets, et les sommets en des ensembles d'arcs formants des 1-graphes ****. On procède comme suit : On considère l'ensemble des arcs distinct du graphe `G` initial. Et on munie cet ensemble des relations binaires que sont les relations successeurs de multiplicité p et les relations successeurs non orientés de multiplicité p. Cela définie un nouveau graphe qui s'appelle le graphe adjoint ou le line graph noté `L(G)` mais qui n'est classiquement définie que pour les 1-graphes simples et en utilisant les relations d'adjacences et non de successeurs.

Le graphe est **** ssi l'ensemble des sommets `X` admet deux parties non nécessairement disjointes `X = X_1 uu X_2`, de telle sorte que chaque sommet de la première partie soit reliés à tous les sommets de la seconde partie, `AA x in X_1,  AA y in X_2,  xUy " et " yUx`, et qu'il n'y a pas d'arc entre les sommets de `X_1\X_2` ni entre les sommets de `X_2\X_1`.

12) Le graphe vu comme un automate sourd et muet

Le graphe peut être perçu comme un automate ne prenant aucune entré et ne produisant aucune sortie. Les sommets correspondent aux différents états possibles et exlusifs de l'automate. Les arcs correspondent à des transitions d'états possibles. L'automate est dit indéterministe lorsqu'il y a, à partir d'un état, plusieurs transitions possibles.

Le graphe définie une chaine de Markov. À chaque sommet, les arcs partants désignent un ensemble de transitions équiprobables. Ainsi si `k` arcs partent d'un sommet alors chacun des `k` arcs en question possède un probabilité `1"/"k` d'être emprunté. Comme il n'y a pas d'état initial ni final, il est posé une équiprobabilité entre tous les sommets pour déterminer l'état initial. Le calcul se fait en parallèle sur chaque sommet et chaque arc à la fois. La chaine de Markov converge nécessairement puisqu'il s'agit d'un phénomène physique qui peut être mesuré. Elle produit une probabilité de présence dans chaque sommet du graphe. Et dans les cas de probabilité nulle, elle produit une demi-vie dans chaque sommet de probabilité de présence nulle. La demi-vie est le nombre moyen de transitions pour diviser la probabilité de présence par 2, au cours de la phase asymptotique, phase nécessaire pour que cette valeur devienne constante.

13) La notion d'indiscernabilité combinatoire

Il existe une seconde notion d'indiscernabilité appelée indiscernabilité combinatoire ou simplement permutabilité.

Deux éléments `x` et `y` sont dits permutables si et seulement si pour toute fonction propositionelle binaire `P"(.,.)"` nous avons `P(x,y) <=> P(y,x)`. Et cette notion peut être plus faible encore, en autorisant qu'un groupe de permutation. Un ensemble de `n` éléments est dit `G`-permutable si et seulement si pour toute fonction propositionelle `n`-air `P(...)` et pour toute permutation `sygma` appartenant au groupe `G`, nous avons `P(x_1,x_2,x_3,...,x_n) <=> P(sygma(x_1,x_2,x_3,...,x_n))`.

---- 5 Septembre 2016 ----

 

 

 

 

 

 

 

 

Un arc non orienté correspond à deux arcs orientés symétriques l'un de l'autre et indifférenciés. Le caractère indifférencié signifie qu'il est représenté par un seul élément ce qui change son aspect combinatoire.

Aussi devrons-nous considérer des graphes mixtes comprenant à la fois des arcs orientés et des arcs non orientés. Et davantage encore nous devrons considérer des graphes dans les quels différentes composantes peuvent être indifférentiées où plus précisement ordonnées à une permutations près...

La notion d'indiscernable joue un rôle essentiel en combinatoire comme en physique quantique.

Il est possible de la formaliser davantage. On peut concevoir par exemple `5` sommets indiscernables. Cela correspond à un sac, un multiensemble contenant `5` fois le même élément. On note le multiensemble avec une double accolade :

`X = {{s, s, s, s, s}}`

Mais si on ajoute un arc orienté, celui-ci va discerner deux éléments (ou un seul s'il s'agit d'une boucle). L'indiscernabilité est relative à un contexte, un contexte qui évolue lorsque l'on ajoutes de nouveaux éléments ou de nouvelles propriétées, et en particulier, lorsque l'on ajoute des propriétés discernantes. Deux objets définis indiscernables peuvent devenir discernables par la suite, lors d'un tel ajout. Le contexte se formalise en une théorie qui peut être ainsi complétée.

L'arc orienté `u` que l'on ajoute va identifier deux sommets constructibles, le sommet de départ noté `u[1]` et le sommet de fin noté `u[2]`, les autres sommets restent alors indiscernables entre eux. Et il semble qu'il y ait deux façons d'ajouter un arc orienté déterminant ses sommets. Soit c'est une boucle partant et arrivant sur un même sommet, ce qui se traduit par la propriété :

`X = {{ u[1], s, s, s, s}}`
`u[1]!=s`
`u[1]=u[2]`

Ou soit c'est un arc entre deux sommets distincts, ce qui se traduit par la propriété :

`X = {{ u[1], u[2], s, s, s}}`
`u[1]!=s`
`u[2]!=s`
`u[1]!=u[2]`

Mais il est possible de ne pas trancher la question, et d'ajouter un arc déterminant toujours ses sommets mais sans savoir si elle constitue une boucle ou non. La théorie associé est simplement incomplète à ce sujet et ne précise pas si `u[1]!=u[2]` :

`X = {{ u[1], u[2], s, s, s}}`
`u[1]!=s`
`u[2]!=s`

Dans cette approche théorique, on voit bien comment est défini l'indiscernabilité de deux élément. Deux éléments sont indiscernables si et seulement si la théorie en cours ne peut pas démontrer leur inégalité. Etant donné deux éléments `x, y`. La propriété que `x` est indiscernable de `y` signifie que la théorie en cours, noté `Self`, ne peut pas démontrer leur inégalité.

`x` et `y` sont indiscernables si et seulement si `"Self" ⊬ x=y`

Le même raisonnement peut donc être porté plus loin. On peut ajouter un arc orienté sans changer la nature indifférentiable des sommets de l'arc. On obtient simplement la théorie incomplète :

`X = {{ u[1], u[2], s, s, s}}`

C'est une théorie qui ne précise pas si `u[1]!=s` ni si `u[2]!=s` ni si `u[1]!=u|2]`. Dans cette esprit, pour désigner un ensemble de 4 éléments distincts, la théorie se note :

`X={{a,b,c,d}}`
`a!=b`
`a!=c`
`a!=d`
`b!=c`
`b!=d`
`c!=d`

 

6) Autre définition d'un graphe construit à partir d'un ensemble d'arcs.

Un graphe sur E est une Relation ternaire, possèdant la propriété d'exclusion qui dit qu'un élément de E et soi un arc ou un sommet mais pas les deux à la fois.

 

5) Autre définition d'un graphe construit à partir d'un ensemble indiférentié E de sommets et d'arcs.

Un graphe sur E est une Relation ternaire, possèdant la propriété d'exclusion qui dit qu'un élément de E et soi un arc ou un sommet mais pas les deux à la fois.

 

7) La notion d'hypergraphe.

 

8) Les propriétés d'un graphe sans préciser aucune de ses composantes.

 

 

 

 

 

 

3) Les graphes orientés

Un 1-graphe est un graphe orienté où il ne peut y avoir au plus qu'un arc allant d'un sommet à un autre, et au plus qu'une boucle par sommet. Un 1-graphe est une relation binaires définie sur l'ensemble des sommets `X`. Un arc partant de `x` pour aller sur `y` est identifié au couple `(x,y)`. L'ensemble des arcs `U` est un ensemble de couples `(x,y)`. S'il existe un arc permettant de passer de `x` en `y` alors nous avons `(x,y) in U`, autrement dit `x` est en relation avec `y` ce qui se note `xUy`. L'ensemble de tous les arcs possibles est `X^2`. Nous avons `U sub X^2`.

Un graphe est complet ssi on ne peut pas ajouter d'arcs sans changer la nature du graphe. On choisie ici de distinguer les deux notions complet et full-connexe. Classiquement complet signifie full-connexe. Ici on lui donne un autre sens. Avec la notion de graphe complet vient la notion de graphe complémentaire. Le graphe complémentaire comprent les mêmes sommets et comprent tous les arcs du graphe complet n'appartenant pas au graphe.

Un 1-graphe complet correspond à la relation binaire complète `U=X^2`. C'est un 1-graphe full-connexe dans lequel il y a une boucle sur chaque sommet. Il possède `N^2` arcs.


Le 1-graphe complet à 2 sommets

La densité d'un 1-graphe est le quotient `M"/"N^2` c'est à dire le rapport entre le nombre d'arcs et le nombre maximal d'arcs théoriquement possible.

Lorsque le graphe est valué, chaque arc possède une valeur. On note `bbbA` l'ensemble des valeurs possibles.

La différence entre une fonction et une application tient dans le fait que la fonction peut ne pas être définie partout sur l'ensemble de départ et possède un domaine de définition, alors que l'application est définie partout sur l'ensemble de départ.

Un 1-graphe valué est défini par une fonction `f` de `X^2` sur `bbbA`. L'égalité `f(x,y) = a` signifie qu'il existe un arc allant de `x` à `y` dont le poids vaut `a`. Si la fonction `f` n'est pas définie sur `(x,y)` cela signifie qu'il n'existe pas d'arc allant de `x` à `y`. Le lien entre la relation binaire `U` et la fonction binaire `f` est : `xUy` ssi `f` est définie sur `(x,y)`, autrement dit `U` est le domaine de définition de `f`.

On note entre accolades `{...}` les éléments d'un ensemble sachant qu'ils sont nécessairement distincts. Étant donné un ensemble `E`, on note `ccP(E)` l'ensemble des sous-ensemble de `E`.

On note `ccP_2(E)` l'ensemble des sous-ensemble de `E` de cardinalité 2, c'est à dire l'ensemble des couples d'éléments distincts de `E`.

On note `ccP_(<=q)(E)` l'ensemble des sous-ensemble de `E` et de cardinalité au plus égale à `q`.

On note entre accolades doubles `"{{"..."}}"` les éléments d'un sac (multiensemble) sachant qu'ils peuvent se répéter. Étant donné un ensemble `E`, un sac de support `E` est un sac composé d'éléments de `E` qui peuvent être répétés en nombre quelconque. On note `ccS(E)` l'ensemble des sacs de support `E`. Notez que dans cette représentation les éléments multiples sont indifférenciés.

On note `ccS^((p))(E)` l'ensemble des sacs de support `E` où les éléments ne peuvent être répétés qu'au plus `p` fois.

On note `ccS_q^((p))(E)` l'ensemble des sacs de support `E` de cardinalité `q` et où les éléments ne peuvent être répétés qu'au plus `p` fois.

Et on note `ccS_(<=q)^((p))(E)` l'ensemble des sacs de support `E` comprenant au plus `q` éléments et où les éléments ne peuvent être répétés qu'au plus `p` fois.

Ajouter des arcs multiples, des arcs ayant le même sommet de départ et le même sommet d'arrivé, ne change pas grand chose à la forme générale du graphe, mais constitue une transformation simple d'un graphe, un degrés de liberté de construction. C'est pourquoi on considère le cas des arcs multiples. Et pour en circonscrire un domaine on pose une borne arbitraire `p`. On s'autorise un maximum de `p` arcs multiples pour chaque couple de sommet, et on s'autorise un maximum de `p` boucles multiples pour chaque sommet.

Un p-graphe est un graphe orienté où il ne peut y avoir au plus que `p` arcs allant d'un sommet à un autre, et où il ne peut y avoir au plus que `p` boucles sur chaque sommet. Un arc partant de `x` pour aller sur `y` est identifié au couple `(x,y)`, et il peut y en avoir plusieurs identiques jusqu'à `p` fois. L'ensemble des arcs `U` est identifié au sac des couples `(x,y)`, sachant qu'un arc ne peut être répété qu'au plus `p` fois. Nous avons `U sub ccS^((p))(X^2)`. Notez que dans cette représentation, les arcs multiples sont indiscernables. La propriété logique de pouvoir passer de `x` à `y` par un arc se note toujours `xUy`.

Un p-graphe valué est défini par une application `f` de `X^2` vers `ccS_(<=p)(bbbA)`, l'ensemble des sacs de support `bbbA` d'au plus `p` éléments. L'égalité `f(x,y) = Ø` signifie qu'il n'existe pas d'arc allant de `x` à `y`. L'égalité `f(x,y) = "{{" a_1, a_2, a_3 "}}"` signifie qu'il existe 3 arcs allant de `x` à `y` dont les poids sont `a_1`, `a_2` et `a_3`, et ces poids peuvent être égaux. Notez que dans cette représentation, les arcs multiples de même poids sont indiscernables.

4) Les graphes non orientés

Un multigraphe est un graphe non orienté où il peut y avoir plus d'une arête reliant deux sommets, et où il peut y avoir plus d'une boucle sur chaque sommet. Une arête reliant deux sommets distincts `x` et `y` est identifiée par le doublon `{x,y}`, et il peut y en avoir plusieurs identiques. Une arête reliant `x` à `x` est une boucle identifiée au singleton `{x}`, et il peut y en avoir plusieurs identiques. L'ensemble des arêtes `U` est identifié au sac regroupant les doublons `{x,y}` correspondant aux arêtes reliant `x` à `y`, et regroupant les singletons `{z}` correspondant aux boucles sur `z`. Nous avons `U sub ccS(ccP_2(X) uu ccP_1(X))`. Notez que dans cette représentation les arêtes multiples sont indiscernables. La propriété logique de pouvoir passer de `x` à `y` par une arête se note toujours `xUy`.

On peut toujours ajouter des arêtes sur un multigraphe, aussi n'est il jamais complet. La notion de multigraphe complet n'a pas de sens. Parcontre la notion de multigraphe full-connexe a un sens précis, chaque couple de sommets distincts doit être relié par au moins une arête.

Lorsqu'une fonction `f` s'applique à un ensemble `{x,y}`, on note simplement `f{x,y}` pour signifier `f({x,y})`.

Le multigraphe valué est défini par une application `f` de `ccP_(2)(X) uu ccP_1(X)` vers `ccS_(bbbA)`, l'ensemble des sacs de support `bbbA`. L'égalité `f{x,y} = Ø` signifie qu'il n'existe pas d'arc reliant `x` et `y`. L'égalité `f{x,y} = "{{" a_1, a_2, a_3 "}}"` signifie qu'il existe 3 arcs reliant `x` et `y` dont les poids sont `a_1`, `a_2` et `a_3`, les poids pouvant être égaux. Notez que dans cette représentation les arcs multiples de même poids sont indiscernables. L'égalité `f{x} = Ø` signifie qu'il n'existe pas de boucle sur `x`. L'égalité `f{x} = "{{" b_1, b_2, b_3 "}}"` signifie qu'il existe 3 boucles sur `x` dont les poids sont `b_1`, `b_2` et `b_3`, les poids pouvant être égaux. Notez que dans cette représentation les boucles multiples de même poids sont indiscernables.

Un p-graphe non-orienté est un multigraphe où il ne peut y avoir au plus que `p` arcs multiples pour chaque couple de sommet. les arcs sont identifiés à des doublons, et les boucles sont identifiées à des singletons. L'ensemble des arcs `U` est identifié au sac regroupant ces doublons et ces singletons sachant qu'ils ne peuvent être répétés qu'au plus `p` fois. Nous avons `U sub ccS^((p))(ccP_2(X) uu ccP_1(X))`. Notez que dans cette représentation les arcs multiples sont indiscernables.

Le p-graphe non-orienté valué est défini par une application `f` de `ccP_(2)(X) uu ccP_1(X)` vers `ccS_(<=p)(bbbA)`, l'ensemble des sacs de support `bbbA` d'au plus `p` éléments. L'égalité `f{x,y} = Ø` signifie qu'il n'existe pas d'arc reliant `x` à `y`. L'égalité `f{x,y} = "{{" a1, a2, a3 "}}"` signifie qu'il existe 3 arcs reliant `x` et `y` dont les poids sont `a1`, `a2` et `a3`, les poids pouvant être égaux. Notez que dans cette représentation les arcs multiples de même poids sont indiscernables. L'égalité `f{x} = Ø` signifie qu'il n'existe pas de boucle sur `x`. L'égalité `f{x} = "{{" b1, b2, b3 "}}"` signifie qu'il existe 3 boucles sur `z` dont les poids sont `b1`, `b2` et `b3`, les poids pouvant être égaux. Notez que dans cette représentation les arcs multiples de même poids sont indiscernables.

Un graphe simple est un graphe non orienté où il ne peut y avoir au plus qu'un arc reliant deux sommets, et où il n'y a pas de boucle. Un graphe simple est un 1-graphe non orienté antiréflexif c'est à dire sans boucle. L'ensemble des arcs `U` est un ensemble de doublons, `U sub ccP_2(X)`. Chaque doublon de sommets tel que `{x,y} in U` correspond à un arc reliant les deux sommets `{x,y}`.

Un graphe simple complet est un graphe simple full-connexe. Il possède `N(N-1)"/"2` arcs.


`K_4`, le graphe simple complet à 4 sommets

La densité d'un graphe simple est le quotient `M"/"(N(N-1))` c'est à dire le rapport entre le nombre d'arcs et le nombre maximale d'arcs théoriquement possible. Un graphe simple complet (ou full-connexe) de `n` sommets s'appelle une n-clique et se note `K_n`.

Un graphe simple valué est défini par une fonction `f` de `ccP_2(X)` sur `bbbA`. L'égalité `f{x,y}= a` signifie qu'il existe un arc reliant les sommets `x` et `y` et dont le poids vaut `a`. Si la fonction `f` n'est pas définie sur `{x,y}` cela signifie qu'il n'existe pas d'arc reliant `x` à `y`. Le lien entre le sac des arcs non orientés `U` et la fonction binaire `f` est : `{x,y} in U` ssi `f` est définie sur `{x,y}`. Le domaine de définition de `f` est égale à `U`.

2) Glossaire de base pour la théorie des graphes

Multiplicité des arcs : Le nombre d'arcs allant de `x` à `y`, c'est à dire permettant de passer de `x` à `y`, est noté `m(x,y)`. Selon le contexte, la même notation désigne le nombre d'incidences c'est à dire le nombre d'arcs orientés, sachant qu'un arc non orienté comptant pour deux arcs orientés mis en tête bêche.

Le degré d'un sommet `x` notée `d(x)` est le nombre d'arcs partant du sommet `x`, indépendament du nombre d'arcs entrant. Selon le contexte, la même notation désigne le nombre d'incidences sortantes c'est à dire le nombre d'arcs orientés vers l'exterieur, sachant qu'un arc non orienté comptera pour deux arcs orientés mis en tête bêche.

`d(x) = sum_(y in X)m(x,y)`

Classiquement le degré d'un sommet `x` est définie comme étant le nombre d'incidences sortantes. Dans ce cas, une boucle non-orientée est comptée deux fois. La multiplicité d'un arcs allant de `x` à `y` est définie comme étant le nombre d'incidences sortantes de `x` pour aller sur `y`. Comme un arc non-orienté possède une incidence entrante et sortante à chaque bout, s'il forme une boucle, il est compté deux fois. Et nous avons toujours la formule `d(x) = sum_(y in X)m(x,y)`. Les deux définitions sont à prendre en compte. Soit on compte les arcs ou soit on compte les incidences, ce qui est identique lorsque le graphe est orienté.

Matrice associée d'un graphe : On numérote les sommets `X = {1, 2, 3, ..., n}`. La matrice associée du graphe est la matrice `((a_j^i))` avec `a_j^i = m(i, j)`, placé à la `i`ième ligne et à la `j`ième colonne. Elle indique le nombre d'arcs (ou d'incidences) permettant de passer du sommet `i` au sommet `j`.

`((a_j^i)) = ((1,1,0,0),(1,2,1,0),(0,0,0,1),(2,0,0,0))`
Un 2-graphe de 4 sommets et sa matrice associée

`((a_j^i)) = ((4,2,1),(2,0,1),(1,1,2))` `((a_j^i)) = ((2,2,1),(2,0,1),(1,1,1))`
Un multigraphe de 3 sommets, sa matrice d'incidences associée et sa matrice d'arcs associés

Etant donné deux graphes `bbA` et `bbB`, définis sur les mêmes sommets, et de matrice d'arcs associées `A` et `B`, alors la matrice `A**B` correspond à celle d'un graphe définie sur les mêmes sommets, et obtenue en comptant une arrète entre `x` et `y` pour chaque chemin distinct allant de `x` à `y` en passant un arc de `bbA` suivie d'un arc de `bbB`. De même pour les matrices d'incidences en remplacant chaque arcs non orientés par deux arcs orientés mis en tête bêches.

Le graphe est symétrique ssi `AA(x,y)inX^2,  m(x,y)=m(y,x)`. Dans le cas d'un 1-graphe, il est symétrique ssi `AA(x,y)inX^2,  xUy => yUx`.

Le graphe est anti-symétrique ssi `AA(x,y)inX^2,  xUy => ¬ yUx`.

Le complèmentaire d'un 1-graphe ou d'un graphe simple est obtenu en prenant le complément de l'ensemble des arcs `U` parmis l'ensemble des arcs possibles pour la nature du graphe considéré.

L'inverse d'un graphe orienté est obtenue en inversant le sens de tous ses arcs.

La désorientation d'un graphe est obtenue en enlevant l'orientation de ses arcs.

La singularisation d'un graphe est obtenue en regroupant pour chaque sommet ses arcs multiples en un seul arcs.

Le graphe est full-connexe ssi `AA(x,y) in X^2 "/" x!=y,  xUy`.

Le graphe est biparti ssi l'ensemble des sommets `X` peut être partitionné en deux parties `X = X_1 uu X_2` et `X_1 nn X_2 = Ø`, de telle sorte que deux sommets d'une même partie ne soient jamais relié par un arc. `(AA x in X_1,  AA y in X_1,  ¬ xUy) "et" (AA x in X_2,  AA y in X_2,  ¬ xUy)`.

Le graphe est biparti-full-connexe ssi il est biparti et `AA x in X_1,  AA y in X_2,  xUy  "et" yUx`.

Un graphe simple biparti-full-connexe est un graphe simple biparti complet. On ne peut pas ajouter d'arc sans changer la nature du graphe simple biparti. Un graphe simple biparti-full-connexe avec `|X_1|= p` et `|X_2|=q` se note `K_(p*q)`.

Deux arcs sont adjacents ssi le premier arrive sur un sommet et le second part de ce même sommet. Mis bout à bout dans le même ordre, ils forment un chemin de deux arcs.

Un chemin est une séquence non vide d'arcs adjacents deux à deux. La longueur du chemin est le nombre d'arcs de la séquence. Le chemin est simple s'il n'utilise pas deux fois le même arc. Dans le cas d'arcs non-orientés, le chemin simple ne doit pas emprunter un même arc même dans l'autre sens. Selon le contexte, la même notion de chemin simple désigne un chemin n'empruntant pas deux fois le même arc orienté, permettant ainsi de passer par le même arc non orienté deux fois, une fois par sens différents. Dans cette deuxième interprétation dite d'incidence (chemin d'incidence simple) chaque arc non orienté correspond en faite à deux arcs orientés mis en tête bêche.

Le chemin est élémentaire s'il ne rencontre pas deux fois le même sommet. Un chemin élémentaire est nécessairement simple. Dans le cas d'un 1-graphe ou d'un graphe simple, un chemin est déterminée par une succession de sommets distincts où chaque sommet suivant est un successeur.

Un sommet `y` est descendant de `x` s'il est situé sur un chemin d'origine `x`.

Un circuit est un chemin simple où les deux sommets aux extrémités du chemin coïncident. Un circuit peut passer plusieurs fois par un même sommet, mais n'utilise jamais deux fois le même arc. Dans le cas d'arcs non-orientés, le chemin simple ne doit pas emprunter un même arc même dans l'autre sens. Selon le contexte, la même notion de circuit désigne un chemin partant et arrivant sur même sommet et n'empruntant pas deux fois le même arc orienté, permettant ainsi de passer par le même arc non orienté deux fois, une fois par sens différents. Dans cette deuxième interprétation dite d'incidence (circuits d'incidence) chaque arc non orienté correspond en faite à deux arcs orientés mis en tête bêche.

Un circuit est élémentaire s'il ne rencontre pas deux fois le même sommet excepté bien entendu le sommet initial qui coïncide avec le sommet terminal.

La fermeture transitive de `x`, noté `hat Gamma(x)` est la limite de `{x}uu Gamma(x) uu Gamma(Gamma(x)) uu ...`, c'est à dire l'ensemble des descendants de `x`. De même pour un ensemble de sommets `A`, la fermeture transitive de `A`, noté `hat Gamma(A)` est la limite de `A uu Gamma(A) uu Gamma(Gamma(A)) uu ...`, c'est à dire l'ensemble des descendants d'au moins un éléments de `A`.

Un graphe est connexe si on peut passer de n'importe quel sommet à n'importe quel autre sommet par un chemin. On définie une relation d'équivalence, `x-=y` ssi il existe un chemin passant de `x` à `y` et il existe un chemin passsant de `y` à `x`, c'est à dire ssi il existe un circuit contenant `x` et `y`. Les classes d'équivalences sont appelés les composantes connexes du graphe.

Classiquement la connexité est définie indépendament de l'orientation des arcs, c'est à dire sur le graphe non-orienté correspondant. Ici, on choisit d'utiliser le terme connexe dans le sens de fortement connexe c'est à dire limité à une condition sur l'orientation des arcs. Nous faisons le choix de poser des définitions non symétriques sachant que pour obtenir leur version symétrique on usera de macro-opérations sur le graphe entier.

Un sommet est individuel s'il forment une partie connexe à lui tout seul, c'est à dire s'il n'existe pas d'autre sommet partageant avec lui un même circuit.

Un point d'articulation est un sommet qui augmente le nombre de composantes connexes si on l'enlève.

Un isthme est un arc qui augmente le nombre de composantes connexes si on l'enlève.

Une forêt est un graphe sans circuit. Un arbre est un graphe sans circuit possédant une racine `r`, c'est à dire tel que chaque sommet soit descendant de `r`.

Un graphe est planaire si on peut le dessiner dans le plan sans croisement d'arcs. Tous les graphes de 4 sommets sont planaires. Tous les graphes bipartis de 5 sommets sont planaires. Par contre les graphes `K_5` et `K_(3*3)` ne sont pas planaires. Un résultat connu en théorie des graphes stipule qu'un graphe simple connexe planaire avec un nombre d'arêtes `M>2` possède la propriété `M <= 3N-6`, où `N` est le nombre de sommets. Tous les graphes qui ne passent pas ce test sont donc non planaire.

Pour les autres graphes, on peut décider grâce au théorème de Kuratowski : Un graphe est planaire ssi il ne contient aucun sous-graphe réductible à `K_5` et `K_(3*3)`. Un graphe `U` est réductible en un graphe `V` ssi on peut rendre `U` égale à `V` en utilisant 3 types d'opérations : enlever des arêtes, renuméroter les sommets, contracter chaque sommet de degrés 2 et ses deux arêtes incidentes en une arête unique.

Jeux "rendre planaire un graphe"

Claude Berge , "Graphes", gauthier-villars,1983
Philippe Lacomme, Christian Prins, Marc Sevaux, "Algorithmes de graphes", Eyrolles, 2003

 

 

3) Le graphe adjoint

Pour bien appréhender les choix de constructions à faire, il faut dévoiler les symétries profondes des graphes, et ont commence par des constructions par symétrie transformant les arcs en sommets, et les sommets en un ensemble d'arcs. Le graphe adjoint (appellé aussi le line graph) en est un exemple.

Pour un graphe non orienté `G`, le graphe adjoint `L(G)` est définie de la façon suivante :

  1. Chaque sommet de `L(G)` représente une arête de `G`.
  2. Deux sommets de `L(G)` sont adjacents si et seulement si les arêtes correspondantes sont adjacentes

 

Exemple :

 

On peut aussi éxiger une adjacence stricte entre arêtes, au sens où une même arête n'est adjacente strictement à elle-même que si elle constitue une boucle. On parlera alors de graphe adjoint stricte de `G` que l'on notera de la même façon `L(G)` en laissant au contexte le soin de levé lambiguité, car il n'y a pas de différence si on enlève les boucle dans `G` et dans `L(G)`.

L'ensemble des arcs partant d'un même sommet, s'ils sont posés indiscernables, forment ce que l'on appel un hyper-arc dans un hypergraphe.

4) La notion d'indiscernabilité (2ème partie)

L'étude des hypergraphes nous amènes à concevoir une définition de l'indiscernabilité plus forte. Deux arcs sont dit indiscernables s'il se fondent dans un hyper arcs c'est à dire s'ils se fondent dans un ensembles d'arcs indiscernables formant une clique..

Une autre approche plus simple consiste à définir l'indiscernabilité comme une libre permutation dans les règles de déduction. Ce faisant, l'ajout d'un arc sans autre précsion, sur 5 sommets indiscernables (et donc restant indiscernables), correspond à l'ajout d'une boucle. Puisque partant d'un sommet quelconque `s`, par permutation d'indifférentiabilité je peux me trouver sur le départ de l'arrête puis passer à l'arrivée de l'arête et toujours par permutation d'indifférentiabilité me retrouver sur n'importe quel sommet `s`. Dans ce cas de figure l'ajout d'un arcs se traduit par un 1-graphe complet dans lequel tous les sommets entre eux sont indifférentiables et toutes les arêtes orientées entre elles sont indiscernables.

Pour que les arcs que l'on ajoute ne differencient pas les sommets indiscernables on peut en ajouter pareillement pour chaque couples de sommets indiscernables et ils doivent être eux-mêmes indiscernables entre eux. Ils forment alors un hyper-arc capable de relier de façon symétrique en une fois un grand nombre de sommets pouvant être eux-même indiscernables.

Des éléments peuvent n'être que partiellement indiscernables tels que trois sommets définie dans un ordre à une permutation circulaire près.

 

 

 

 

 

Pour un graphe orienté `G`, le graphe adjoint `L(G)` se complexifie un peu en spécifiant pour chacun de ses arcs un sens parmis 2*2 valeurs possibles {orienté, inversé, divergeant, convergeant} et qui dénote les 4 cas de figures d'ajacence d'arcs orientés. Cela introduit deux types d'arcs non orienté labellisés divergeant ou convergeant. Si nous réitérions la construction d'un graphe adjoint, alors le graphe L(L(G)) se complexifie encore en spécifiant pour chacun de ses arcs un sens parmis 4*4 valeurs possibles et qui dénote les 16 cas de figures d'ajacence d'arcs à 4 valeurs. Si nous réitérions la construction d'un graphe adjoint, alors le graphe L(L(L(G))) se complexifie encore en spécifiant pour chacun de ses arcs un sens parmis 16*16 valeurs possibles et qui dénote les 256 cas de figures d'ajacence d'arcs à 16 valeurs. Et ainsi de suite...

 

Graphe où plusieurs sommets ont même nom et plusieurs arcs ont même nom...

 

Graphe où sur chaque sommet les incidences sont selon un ordre posé.

 

 

 

 

 

 

5) Le rotor-routeur

Considérons un labyrinthe composé de sommets et d'arcs. Nous sommes sur un sommet, point de départ, et nous cherchons un sommet, point d'arrivé, qui désigne la sortie du labyrinthe. Un moyen de sortir du labyrinthe à l'aide d'un crayon consiste à effectuer à partir du point de départ, une succesion de chemins s'arrétant sur chaque nouveau sommet découvert et à chaque fois et partant toujours du même point de départ, en obéissant à la logique des rotor-routeurs : à chaque carrefour, on marque la direction que l'on choisie, et s'il y a déjà un marquage, on prend et on marque la direction suivante. Après avoir emprunté toutes les directions d'un carrefour on revient à la première direction. Ainsi à chaque carrefour on privilègie la diversité des directions selon un ordre arbitraire avant de reprendre une même direction.

Chaque carrefour possède une liste de directions possibles et mémorise le numéro de la direction prise. Chaque carrefour constitue un rotor-routeur, c'est à dire par analogie aux réseaux informatiques, constitue à la fois un routeur et un automate tournant qui indique la direction à prendre et qui incrémente cette direction à chaque passage, et lorsqu'on incrémente la dernière direction de la liste, on retombe sur la permièrer direction de la liste.

En posant des conditions initiales à chaque rotor-routeur, c'est à dire une direction initiale pour chaque carrefour, le mécanisme du rotor-routeur constitue un modèle déterministe de la diffusion centrale. Il explore tous les chemins possibles en ordre croissant selon une notion de distance que l'on décrira plus-tard et qui est minimalisé par le nombre d'arcs du chemin.

Le procédé intératif consiste a effectuer ces chemins qui s'arrétentau premier sommet découvert. Chaque chemin est fait par un agent qui constitue un processus et qui s'arrète dès qu'il trouve un nouveau sommet non encore exploré. Une propriété étonnante est que ces agents peuvent opérer dans un ordre quelconque sans que cela ne change le résultat final. C'est la propriété de commutativité.

3.1) Propriété de commutativité

Le mécanisme du rotor-routeur est abélien. Si nous considérons deux points de départ `A` et `B`. Faire partir un agent du point `A` puis faire partir un agent du point `B`, a pour résultat la même configuration finale que si on fait partir l'agent `B` avant l'agent `A`. Les cheminement de l'agent `A` et de l'agent `B` pourront être interchangé à un ou plusieur carrefours où ils se croisent, et cela ne change pas la configuration finale des sommets découverts.

En conséquence on peut faire partir `n` agents sans attendre l'arrivé des agents précédents et procéder ainsi à un calcul parallèle entre agents sachant que la résolution de deux agents sur un même carrefour s'effectura forcement séquentiellement, et l'on obtiendra le même résultat global, la même configuration finale des sommets découverts.

 

 

 

 

 

 

--- 19 décembre 2015 ---

Voir Les matroïdes

 

 

 




D. Mabboux-Stromberg

2 ) Langage mathématique

Le mot "ssi" signifie "si et seulement si".

Pour éviter l'usage intensif des parenthèses, on fixe un ordre de priorité syntaxique des opérateurs, du plus prioritaire au moins prioritaire :

`**` `+` `in`,`!in` `<,<=,>,>=` `"et", "ou"` `=>, iff` `=,!=` `AA, EE`

Ainsi par exemples, pour tout élément `x,y,z`, pour tout prédicat unaire `A,B` et pour tout booléen `P,Q,R`, nous avons :

l'expression `x**y + z` signifie `(x**y) + z` et non `x**(y+z)`,
l'expression `AA x,  A(x) => B(x)` signifie `AA x,  (A(x) => B(x))` et non `(AAx,  A(x)) => B(x)`,
l'expression `P " et " Q => R` signifie `(P" et "Q) => R` et non `P" et "(Q => R)`,
l'expression `P => Q " ou " R` signifie `P => (Q " ou " R)` et non `(P => Q) " ou " R`,
l'expression `x + y = z` signifie `(x + y) = z` et non `x + (y = z)`,

On définie les opérations `+, **`, indifféremment sur des éléments ou des ensembles d'éléments. Ainsi par exemple, pour un élément `a` et des ensembles `U` et `V`, nous avons :

`a+U = {a+u " / " u in U}`,
`aU = {au " / " u in U}`,
`U+V = {u+v " / " u in U " et " v in V}`,
`UV={uv " / " u in U " et " v in V}`.

On définie une conversion implicite de type entre les booléans et les entiers, le vrai est transformé en `1` et le faux est transformé en `0`. Ainsi l'expression `(a=b)+(a=c)+(b=c)` vaut `3` ssi `a` et `b` et `c` désignent le même élément.

 

Dénombrement

`|A| = a`
`|B| = b`

`|A×B| = ab`

`|ccP_0(A)| = 1`
`|ccP_1(A)| = a`
`|ccP_2(A)| = a(a-1)"/"2`
`|ccP_3(A)| = a(a-1)(a-2)"/"3!`

Pour `p>0`, nous avons `|ccP_p(A)| = a(a-1)(a-2)...(a-(p-1))"/"p!`

`|ccS_0(A)| = 1`
`|ccS_1(A)| = a`
`|ccS_2(A)| = a^2"/"2`
`|ccS_3(A)| = a^3"/"3!`

Pour `p>0`, nous avons `|ccS_p(A)| = a^p"/"p!`

ccS_3^((2))(A) =

On note `ccS_2(E)` l'ensemble des sacs de support `E` et de cardinalité 2, c'est à dire l'ensemble des couples à l'ordre près dans `E`.

Un sommet `x` est final ssi `Gamma(x) sube {x}`. Une partie `A` est finale ssi `Gamma(A) sube A`

 

3) Circuits et cocircuits

Dans un graphe un circuit est une séquence d'arcs `(u_1,u_2,u_3,...,u_q)` vérifiant les 3 propriétées suivantes ::

  1. Chaque arc est adjacent avec l'arc suivant.
  2. Le dernier arc `u_q` est adjacent au premier arc `u_1`.
  3. Chaque arc est distinct. Dans le cas d'un graphe non orienté, l'arête reliant `x` à `y` est identifié par l'ensemble `{x,y}` et constitue une même arête, qu'elle soit utilisée dans un sens pour passer de `x` à `y` ou dans l'autre sens pour passer de `y` à `x`. Donc un circuit ne peut pas rebrousser chemin par la même arête.

On numérote les arêtes `U = {1,2,3,...,n}`. On fait correspondre à tout circuit `µ` un vecteur de booléens `µ = (µ_1, µ_2, µ_3,..., µ_q)` avec `µ_i = 0` si l'arc numéro `i` n'est pas utilisé et `µ_i = 1` si l'arc numéro `i` est utilisé dans le circuit `µ`.

 

Le degré sortant d'un sommet `x` que l'on note `d^+(x)` est le nombre d'incidences sortantes, c'est à dire le nombre d'arrêtes partant de `x`.

Le degré entrant d'un sommet `x` que l'on note `d^-(x)` est le nombre d'incidences entrantes, c'est à dire le nombre d'arrêtes arrivant sur `x`.

Le degré d'un sommet `x` que l'on note `d(x)` est le nombre d'incidences entrantes et sortantes, c'est à dire le nombre d'arrêtes touchants `x`, les arrêtes boucles étant comptées deux fois.

`d(x) = d^+(x) + d^-(x)`

Le graphe est régulier si tous les sommets ont le même degré, c'est à dire ont le même nombre d'arcs partant.

 

 

---------------------

 

Le dénombrement des structures mathématiques nous oblige a donner une définition parfaitement constructive des structures considérés. Nous avons besoin d'identificateurs, et qu'est-ce qu'un identificateur sans autre précision ? c'est un entier naturel. Puis nous avons quelquefois besoin d'identificateurs dans la seul mesure de distinguer les éléments considérés, dans ce cas si on doit considérer un ensemble de n éléments distincts, on les numérotera de 0 à n-1, et il s'agit alors d'une liste d'éléments, la place de l'élément dans la liste correspondant à son numéro. Toute l'information d'identification de l'élément se trouve alors dans la place qu'il occupe dans la liste, et les éléments considérés peuvent alors être tous égaux. Par exemple considéront la liste X de 3 éléments identiques a :

X = [a,a,a]

Il n'y a qu'un seul élément `a` membre de la liste `X`, mais il y a 3 places dans la liste `X`. Chaque place peut être désignée par son indice. Il faut donc faire la distinction entre la valeur de la ième place X_i avec la ième place. Nous avons X_0=a, X_1=a, X_2=a, tandis que X[0], X[1], X[2] désignent 3 nouveaux éléments distincts représentant les 3 mémoires de la liste à 3 places. C'est un jeux de construction

 

Par symétrie, la théorie `¬T` augmentée de `A` contient `¬W`, et la théorie `¬W` augmenté de `A` contient `¬T`,

`W <=> (T " et " A)`
`¬W <=> ¬(T " et " A)`
`¬W <=> (¬T " ou " ¬A)`

`(¬W " et " A) <=> ((¬T " ou " ¬A) " et " A)`
`(¬W " et " A) <=> (¬T " et " A)`

`(¬T" et "A) => ¬W`
`(¬T uu A) sup ¬W`
`(¬W" et "A) => ¬T`
`(¬W uu A) sup ¬T`

`(¬W " et " ¬A) <=> ((¬T " ou " ¬A) " et " ¬A)`
`(¬W " et " ¬A) <=> ¬A`
`¬A => (¬W " et " ¬A)`
`¬A => ¬W`
`¬A sup ¬W`

 

Pour dénombrer le nombre de sacs différents possibles, on choisie un autre ordre. On choisi l'ordre selon le facteurs de répétition, c'est à dire l'ordre des éléments selon leur coefficient de multiplicité. Et en cas de même coefficient de multiplicité, on choisie l'ordre du système. On obtient ainsi une signature du sac qui est une somme d'entiers décroissants égale à la cardinalité du sac.

Ainsi pour calculer le nombre de sac de support `E`, il nous faut connaitre le nombre de décomposition de l'entier `n` en sommes d'entiers ordonnées décroissantes. Par exemple l'entier `4` possède `5` décomposition en sommes décroisantes :

`4 = 4`
`4= 3+1`
`4=2+2`
`4=2+1+1`
`4=1+1+1+1`

Par ailleur, Srinivasa Ramanujan, mathématicien indien (22 décembre 1887 - 26 avril 1920), démontra que le nombre de décompositions en sommes décroisantes de `n`, que l'on note `p(n)`, lorsque `n` tend vers l'infini, tend vers :

`lim_(n->oo)p(n) = 1/(4nsqrt(3))e^(pi sqrt((2n)/3))`

....

 

Chaque expression de théorie admet une forme normale constitué d'une conjonction de clauses de littéraux à l'ordre près des conjonctions et à l'ordre près des clauses dans chaque conjontion et aux permutation près des variables universelles de même types.