 |
`((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 d'incidences |
|
Un graphe est un ensemble de sommets reliés totalement ou partiellement par des arcs. Néanmoins le terme de graphe est parfois utilisé pour désigner seulement l'ensemble 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 physique qu'est le libre déplacement selon le sens des arcs. Le graphe se présente alors comme un labyrinthe. Mais dans un arc, le passage ne peut se faire que dans le sens de la flèche. D'autre part puisqu'on s'intéresse à l'aspet physique, les graphes sont par nature finis, ils ne possèdent qu'un nombre fini de sommets et d'arcs.
Noter que dans le cadre des définitions, l'usage du « si » signifie « si est seulement si ». Et on utilisera l'expression « est nécessaire » ou « est suffisant » dans une définition, lorsque seule une implication est invoquée.
Le graphe est valué si chaque arc possède une valeur appelée poids.
Le graphe est définie par un couple `(X,U)` où `X` est l'ensemble des sommets et `U` est l'ensemble des arcs, et où chaque arc stipule un sommet de départ et un sommet d'arrivé. Le nombre de sommets se note `N` et s'appelle l'ordre du graphe. Le nombre d'arcs du graphe se note `M`.
`N=|X|`
`M=|U|`
La relation associée au graphe est la relation qui lie le sommet `x` au sommet `y` s'il existe un arc permettant de passer de `x` à `y`. On la note par la lettre `R`. Ainsi l'expression `xRy` signifie qu'il existe au moins un arc passant de `x` à `y`.
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-ils 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 l'ensemble 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 l'ensemble de ses 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 ensemble d'arcs.
Notez, que pour chaque arc, seul la propriété de passage d'un sommet à un sommet est utilisée. C'est pourquoi pour les graphe non valuée où l'arc se résume complètement à cette seule propriété, l'ensemble des arcs `U` est identifiés à un multi-ensemble de base `X"×"X` c'est à dire de support inclus dans `X"×"X`.
Mais avant d'aller plus loin, il convient de décrire des objets plus rudimentaires que sont les relations unaires, les ensembles, les multi-ensembles appelés sacs, les arrangements, les suites, et leur dénombrement.
Un ensemble `E` muni d'une relation binaire `R` définie un graphe 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` qui appartiennent à la relation `R`. La possibilité de circuler du sommet `x` au sommet `y` en n'empruntant juste un arc, se note par `xRy` ou par `(x,y)"∈"R`.
L'étude des graphes passe par l'étude des relations binaires, qui peuvent être 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, les multi-ensembles appelés sacs, les suites, les arrangements...
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 `A` peut être vu comme un prédicat unaire `A"(.)"` opérant dans un ensemble mère `E` beaucoup plus vaste et souvent plus simple à la fois.
`A : E->{0,1}`
`x|->0` si `x` n'appartient pas à `A`
`x|->1` si `x` appartient à `A`
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 à la valeur `0` et la valeur logique vrai à la valeur `1`. La proposition `A(a)` signifie que l'élément `a` appartient à `A`, et la proposition `"¬"A(a)` signifie que `a` n'appartient pas à `A`. Ces ensembles munis des opérations d'union et d'intersection forment une algèbre de Boole.Toute algèbre de Boole est une algèbre de Boole des parties d'un ensemble `E`, définissable comme un treillis `(ccP(E), "∩", "∪", Ø, E )` ou bien comme un anneaux de caractéristique 2 , `(ccP(E), Delta, Ø, "∩", E)`. On utilise parfois les opérateurs logiques pour opérer sur les ensembles. Voici comment sont définis ces opérations logiques. On considère deux sous-ensembles `A` et `B` de `E` :
ensembliste
logique
Puis il faut considérer les éléments multiples qui sont par nature indiscernables entre eux. On obtient la définition des multi-ensembles appelés aussi sacs, qui peuvent contenir un même élément plusieurs fois. Cela se fait en considérant à la place du prédicat `A"(.)"` qui est une fonction de `E"→"{0,1}`, une valuation plus riche notée de la même façon `A"(.)"` et qui est une fonction de `E"→" NN`, la valeur de cette valuation indiquant la multiplicité de l'élément.
Ainsi, un sac `A` de base `E` peut être vu comme une application unaire de `E"→"NN` que l'on note sous forme d'opérateur `A"(.)"` opérant dans l'ensemble mère `E` beaucoup plus vaste et souvent plus simple à la fois.
`A : E->NN`
`x|->0` si `x` n'appartient pas à `A`.
`x|->1` si `x` appartient à `A` et n'est pas multiple.
`x|->2` si `x` est présent `2` fois dans `A`.
`...`
`x|->n` si `x` est présent `n` fois dans `A`.
Et les sacs de base `E` munis de l'opération d'union, forment un monoïde commutatif libre.
Et les listes de base `E` munis de l'opération de concatenation, forment le monoïde libre des mots d'alphabtet `E` que l'on note `E^**`.
Et les arrangements de base `E` forme une structure méconnue.
Mais commençons par le béaba qui correspond au base de la programmation.
Qu'est-ce qu'un élément ? c'est une construction dans un langage d'opérateurs, qui sert de référence pour désigner toute chose que nous créons.
Le premier type d'assemblage que l'on conçoit est la liste. Et dans un premier temps on ne concidèrera que des listes dont les éléments ne sont pas des listes. La liste devient une séquence d'éléments que l'on note entre parenthèse telle que `(a,b,a)`.
La première structure que l'on conçoit est l'ensemble des listes basées sur un ensemble d'éléments. Parfois la base est appelée l'alphabet, les éléments de l'alphabet sont appelés des caractères, et les listes en question sont appelés des mots.
On note `ccL_k(E)` l'ensemble des listes de longueur `k` d'éléments de `E`. On pose `n"="|E|`. Nous avons `ccL_k(E) "=" E^k`. Le dénombrement est :
`|ccL_k(E)|=n^k`
On note `ccL_(<=k)(E)` l'ensemble des listes de taille inférieure ou égale à `k`. Le dénombrement est donc :
`|ccL_(<=k)(E)| = 1+n+n^2+...+n^k = sum_(k=0)^k n^k`
`|ccL_(<=k)(E)| = (n^(k+1)-1)/(n-1)`
On note `ccL_k^r(E)` l'ensemble des listes de longueur `k` d'éléments de `E` où les éléments ne peuvent être répétés qu'au plus `r` fois. Le dénombrement est plus compliqué.
Le second type que l'on conçoit est l'arrangement. À la différence d'une liste, il ne comprend que des éléments distincts. L'arrangement est une séquence d'éléments distincts que l'on note entre chevrons tel que `(: a,b,c :)`. Notez que cette expression ajoute une condition implicite qui est que `a"≠"b` et `a"≠"c` et `b"≠"c`.
La seconde structure que l'on conçoit est l'ensemble des arrangements basées sur un ensemble d'éléments `E` de cardinal `n`, et que l'on note `ccA(E)`. On note `ccA_k(E)` l'ensemble des arrangements de `k` éléments de `E`. Le dénombrement est :
`|ccA_k(E)| = n(n-1)(n-2)...(n-(k-1)) `
`|ccA_k(E)| = (n!)/((n-k)!)`
Donc le dénombrement est :
`|ccA(E)| = 1 + n + n(n"-"1) + n(n"-"1)(n"-"2) + ... +( n(n"-"1)(n"-"2)...(n"-"(n"-"1)) )`
`|ccA(E)| = sum_(k=1)^n (n!)/((n-k)!)`
Le troisième type que l'on conçoit est le multi-ensemble appelé sac. À la différence d'une liste il ne tient pas compte de l'ordre. Le sac est une séquence d'éléments à l'ordre près que l'on note entre double accolades ou avec le symbole en forme de sac tel que `"⟅"a,b,a"⟆"`.
La troisième structure que l'on conçoit est l'ensemble des sacs basés sur un ensemble d'éléments `E`. Un sac basé sur `E` c'est à dire composé d'éléments de `E` en nombre quelconque, est déterminé par une application de `E"→"NN` qui inique la multiplicité de l'élément.
On note `ccS_k(E)` l'ensemble des sacs de `k` éléments appartenant à `E`. On pose `n"="|E|`. Le dénombrement n'est pas simple.
On note `ccS_(<=k)(E)` l'ensemble des sacs d'au plus `k` éléments appartenant à `E`.
`|ccS_(<=k)(E)| = ccS_0(E) + ccS_1(E) + ccS_2(E) + ... + ccS_k(E) = sum_(k=0)^k ccS_k(E)`
On note `ccS^k(E)` l'ensemble des sacs d'éléments de `E` où les éléments ne peuvent être répétés qu'au plus `k` fois. Un sac basé sur `E` et dont les éléments sont multiples au plus `k` fois, est déterminé par une application de `E"→"{0,1,2,...,k}` qui indique la multiplicité de l'élément. Il existe donc une bijection entre `ccS^k(E)` et `E"→"{0,1,2,...,k}`. Le dénombrement est
`|ccS^k(E)| = |E"→"{0,1,2,...,k}| = (k+1)^n`
Le quatrième type que l'on conçoit est l'ensemble. À la différence d'un sac, il ne comprent que des éléments distincts. Et à la différence d'un arrangement, il ne tient pas compte de l'ordre. L'ensemble est une séquence d'éléments distincts à l'ordre près que l'on note entre accolades tel que `{a,b,c}`. Notez que cette expression ajoute une condition implicite qui est que `a"≠"b` et `a"≠"c` et `b"≠"c`.
La quatrième structure est l'ensemble des sous-ensembles de `E` que l'on note `ccP(E)`. On pose `n"="|E|`. Le dénombrement est :
`|ccP(E)|=2^n`
On note `ccP_k(E)` l'ensemble des parties de `k` éléments de `E`. Le dénombrement est :
`|ccP_k(E)| = ( n(n"-"1)(n"-"2)...(n"-"(k"-"1)) ) / (k!) = (n!)/((n-k)!k!) `
Exposer la théorie n'est pas suffisant, car des erreurs peuvent être présentes sans qu'il soit facile de les détecter.
Point de rétention d'information de la part des concepteurs concernant la preuve. On ne se place pas dans le modèle d'économie néolibérale, qui fonde le mensonge, car à tous les étages d'un tel modèle sociologique, les cercles supérieurs désinforment les cercles inférieurs pour garder l'avantage de la position d'initié.
La charge de la preuve doit revenir à l'utilisateur final. Celui-ci doit être en mesure de pouvoir vérifier que la copie de la théorie qu'on lui a transmise n'est pas érronée, qu'elle est intègre. Et un moyen trés général existe qui consite à vérifier par une preuve partielle la cohérence de la théorie. Cela se fait en transmettant la théorie qui décrit un modèle avec le programme de simulation du modèle dans le quel la programmation s'appuit sur une expression lisible par un humain de la théorie qui l'accompagne. L'utilisateur finale vérifie la cohérence de la théorie par trois actes :
L'exécution du programme est une preuve partielle, et le programme est un élément du démonstrateur de théorème.
Dans l'exemple précédent concernant le dénombrement, le modèle est un énumérateur de mots dans l'ordre lexicographique.
On définie 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 une arête le passage peut se faire dans les deux sens. Comme on s'intéresse à l'apect géométrique et physique, on se doit de pouvoir distinguer une arète de deux arcs tête-bêches. Néanmoins la plus part du temps, l'arète est remplacé par deux arcs tête-bêches. Le graphe est dit orienté s'il ne comprend que des arcs. Le graphe est dit non orienté s'il ne comprend que des arètes. Et il est dit mixte s'il peut comprendre des arcs et des arètes.
Un arc partant du sommet `x`, s'appelle aussi une incidence sortante de `x`, c'est un arc qui permet une circulation qui part de `x`. Tandis qu'un arc arrivant sur `x` s'appelle une incidence entrante de `x`, c'est un arc qui permet une circulation qui arrive sur `x`.
Une arète vue uniquement en terme d'incidence compte pour deux arcs en tête bêche.
Une boucle est un arc partant et arrivant sur le même sommet.
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)`.
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. Il désigne le nombre d'incidences sortantes c'est à dire le nombre d'arcs partant de `x`. Une arète compte pour deux arcs mis en tête bêche donc une arète boucle sur `x` est comptée deux fois.
`d(x) = sum_(y in X)m(x,y)`
Matrice d'incidence : On numérote les sommets `X = {1, 2, 3, ..., n}`. La matrice d'incidence 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 passant 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))`
Etant donné deux graphes `A` et `B`, définis sur les mêmes sommets. On désignent par les mêmes lettre leur matrice d'incidence ou d'ajacence selon le contexte. Le produit des matrices d'incidence`A"∗"B` correspond à celle d'un graphe définie sur les mêmes sommets, et obtenue en plaçant un arc entre `x` et `y` pour chaque chemin distinct allant de `x` à `y` composé d'un arc de `A` et d'un arc de `B`, sachant qu'une arète est remplacé par deux arcs mis en tête bêches.
Matrice d'adjacence : Elle distingue arcs et arètes et ne compte plus les incidences mais les arcs et arrètes. Aussi dans cette situation qui n'est plus dite d'incidence mais d'adjacence, une arète n'est plus remplacée par deux arcs mis en tête bêche. La matrice d'adjacence indique le nombre d'arcs et arrètes passant du sommet `i` au sommet `j`.
`((a_j^i)) = ((4,2,1),(2,0,1),(1,1,2))` `((a_j^i)) = ((2,2,1),(2,0,1),(1,1,1))`
Le produit des matrices d'adjacence `A"∗"B` correspond à celle d'un graphe définie sur les mêmes sommets, et obtenue en comptant un arc entre `x` et `y` pour chaque chemin distinct allant de `x` à `y` composé d'un arc ou d'une arète de `A` et d'un arc ou d'une arète de `B`. On constate que la matrice d'adjacence se différentie de la matrice d'incidence que dans le seul fait qu'elle ne comptent qu'une fois chaque arète boucle.
La projection en un 1-graphe d'un graphe est obtenue en remplaçant chaque arète par deux arcs en tête bêches, puis en regroupant les arcs multiples en un seul arcs. C'est le 1-graphe qui possède la même relation associée, et que l'on identifit à la relation associée.
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.
Le graphe est symétrique si `AA(x,y)"∈"X^2, m(x,y)=m(y,x)`. C'est une condition plus forte que simplement la symétrie de la relation associée.
Le graphe est anti-symétrique si la relation associée `R` l'est. `AA(x,y)"∈"X^2, xRy => ¬ yRx`.
Le graphe est full-connexe si on peut passer de tout sommet à tous les autres sommets : `AA(x,y) "∈" X^2 "/" x "≠" y, xRy`.
Dans notre exploration, différents types de graphe vont apparaîtrent. Et pour chaque type de graphe, le graphe sera dit complet si on ne peut pas ajouter d'arc sans changer le type du graphe.
La complétude n'est pas toujours uniques, mais lorsqu'elle l'est pour un types de graphe, alors elle permet de définir une notion de graphe complémentaire propre à ce type de graphe comme étant le graphe complet dans lequel on a enlever les arcs du graphe d'origine.
Un graphe sans autre qualificatif est supposé être un type de graphe le plus générale possible, celui qui transporte toutes les informations définissables dans notre paradigme. Il est orienté et peut contenir un nombre d'arcs aussi grand que l'on veut, ce qui se désigne explicitement par le terme d'`omega`-graphe.
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 ne peuvent être répétés que 3 fois au maximum.
Un 1-graphe est un graphe qui pour chaque couple de sommet `(x,y)` ne possède au plus qu'un arc allant de `x` à `y`. Le 1-graphe est identifié à la relation associée au graphe. Dans le cas générale, la relation associée à un graphe `(X,U)` que l'on note `R` est le support du multiensemble `U`.
Le 1-graphe complet de `N` sommets possède `M=N^2` arcs. Le sac `U` est égale à `U = X^2`.
Le n-graphe complet de `N` sommets possède `M=nN^2` arcs.
Un arc 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 non bouclés possibles est donc `ccP_2(X)×{s1,s2}`. Le nombre d'arcs 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 non bouclés distincts. Le 1-graphe sans boucle complet de `N` sommets possède `M=N^2-N` arcs. Le sac `U` est en bijection avec `ccP_2(X)×{s1,s2}`.
Une arète est un sac de deux sommets de `X`. L'ensemble de toutes les arètea possibles est donc `ccS_2(X)`. Le nombre d'arètes distinctes 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 arètes distinctes. 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)`.
---- 7 mars 2021 ----
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)`.
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`.
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 :
Dessin exemple
à deux sommets
boucles
`U=ccS(X^2)`
M=N^2
dessin
`U=ccP_2(X)×{s1,s2}`
`M=N^2+N`
dessin
`U=ccS_2(X)`
M=(N(N+1))/2
dessin
`U= ccP_2(X)`
`M=N^2"/"2-N"/"2`
dessin
`U=(ccP_2(X)×{s1,s2,s3})uu X`
`M=3N(N-1)"/"2 + N`
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 :
Deux arcs sont consécutifs 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.
Deux arètes sont adjacentes si elles ont un sommet en comment.
Un chemin est une suite d'arcs consécutifs deux à deux. La longueur du chemin est le nombre d'arcs de la suite.
Le chemin simple n'utilise pas deux fois le même arc. Dans le cas d'arète, le chemin simple ne doit pas emprunter une même arète même dans l'autre sens. Le chemin simple d'incidence permet de passer par la même arète non orienté une fois dans un sens et une foi dans l'autre sens, ce qui revient à remplacer chaque arète par deux arcs mis en tête bêche.
Le chemin élémentaire ne rencontre pas deux fois le même sommet. Un chemin élémentaire est nécessairement simple.
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'arète, le chemin simple ne doit pas emprunter un même arc même dans l'autre sens. Le circuit d'incidence permet de passer par la même arète non orienté une fois dans un sens et une foi dans l'autre sens, ce qui revient à remplacer chaque arète par deux arcs 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 d'origine qui coïncide avec le sommet de la fin.
Un graphe est connexe si on peut passer de n'importe quel sommet à n'importe quel autre sommet par un chemin.
Deux sommets sont connectés s'il existe un chemin passant de l'un à l'autre et un chemin inverse passant de l'autre à l'un. C'est une relation d'équivalence appelée relation de connexion.
Les composantes connexes du graphe sont les classes d'équivalences de la relation de connexion.
La réduction d'un graphe est obtenue en fusionnant ses parties connexes.
Un graphe est semi-connexe s'il existe au moins un sommet qui peut atteindre tous les autres sommets par des chemins. Ou, autrement dit, s'il existe un graphe partiel consistant en un arbre couvrant tous les sommets.
Un sommet `y` est descendant de `x` s'il est situé sur un chemin d'origine `x`. Le relation de descendance est une relation d'ordre.
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`.
Les composantes racines sont les composantes connexes minimales pour la relation de descendance.
Les racines sont les sommets minimaux pour la relation de descendance. C'est une composante racine réduite à un sommet.
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é.
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.
Le concept de valuation et d'identification sont de même nature. Une identification est une forme de valuation. Et réciproquement, une valuation peut permettre d'identifier, de discerner.
La notion d'indiscernable 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 sac 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.
Puis il convient de considérer les graphes dans lequel ni les sommets ni les arcs ne sont préalablement identifiés. Exemple, Le graphe simple complet à `n` sommets dans le quel on remarquera que les `n` sommets ne sont pas identifiables et que les `n(n-1)"/"2` arètes ne sont également pas identifiables.
Une théorie est une proposition et il n'y a pas de différence entre théorie et proposition. Toutes deux doivent avoir une expression de taille finie dans un langage de type fini. 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"∈<"T">"`, et est aussi équivalente à la proposition d'inclusion `"<"A">⊂<"T">"`. Deux théories `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éter la théorie `T`, en lui ajoutant la proposition `A` ou bien en lui ajoutant sa négation `¬A`, chacune des 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`. 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>∪<"A">" ">"``W"⊢"T`
`W"⊢"A`
`"<"T">⊂<"W">"`
`"<"A">⊂<"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 cela s'écrit :
`(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`.
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 non énumérable.
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` ?.
On note entre accolades `{...}` les éléments d'un ensemble sachant que l'ordre n'y a pas d'importance mais que les éléments doivent nécessairement être deux à deux distincts. Ainsi l'expression `{a,b,c}`, en plus de définir un ensemble, signifie une condition supplémentaire portée à l'hypothèse, qui est que `a"≠"b` et `a"≠"c` et `b"≠"c`. Un ensemble est une liste d'éléments distincts et à permutation près.
On note entre double accolades `"⟅"a,a,b"⟆"` les éléments d'un sac sachant qu'ils peuvent être répétés plusieurs fois. L'ordre n'y a pas d'importance. Et dans l'exemple, rien n'empêche que `a` puisse être égale à `b`. Un sac est une liste d'éléments à l'ordre près.
---- 24 février 2021 ----
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` où `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` |
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`.
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.
Le graphe est biparti si l'ensemble des sommets `X` peut être partitionné en deux parties `X = X_1 "∪" X_2` et `X_1 "∩" X_2 = Ø`, de telle sorte que deux sommets d'une même partie ne soient jamais reliés par un arc. `(AA x "∈" X_1, AA y "∈" X_1, ¬ xRy) "et" (AA x "∈" X_2, AA y "∈" X_2, ¬ xRy)`.
Le graphe est biparti-full-connexe s'il est biparti et s'il vérifit : `AA x "∈" X_1, AA y "∈" X_2, xRy "et" yRx`.
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)`.
