Problème du second voisinage
Voici une question amusante en théorie des graphes proposée par P. Seymour en 1980.
J'ai une piste que je vous propose ensuite pour que vous puissiez me faire mentir car cela me semble trop simple.
On considère des graphes $G$ finis (non vides) dirigés avec des arcs notés $[x,y]$ tels que $x\not=y$ et $[y,x]$ n'est pas aussi un arc. C'est à dire qu'il n'y a pas de boucles ni de cycles de longueur $2$.
Pour un sommet $x$, on note :
$G_1(x)$ l'ensemble de ses voisins, c'est à dire les $y$ tels que $[x,y]$ est un arc.
$G_2(x)$ l'ensemble de ses voisins à distance $2$ : les voisins des voisins qui ne sont pas eux-mêmes des voisins de $x$.
La conjecture dit qu'il existe toujours au moins un sommet $x$ (une solution) tel que $\#G_2(x)\ge\#G_1(x)$.
Définition : le degré d'un sommet $x$ est le nombre $\#G_1(x)$.
Je propose cette "quasi-preuve" avec des propriétés supplémentaires : non seulement il existe une solution $x$ mais en plus, si elle est unique alors son voisinage $G_1(x)$ est vide. De plus pour tout sommet $x$ de degré non nul, il existe une solution $\sigma_G(x)$ différente de $x$ et on peut définir $\sigma_G$ telle que $\sigma_G(\sigma_G(x))\not=x$ si cela existe (c'est à dire que le degré du sommet $\sigma_G(x)$ est lui aussi non nul).
Preuve par induction sur le nombre d'arcs $m$.
Considérons le plus grand degré $k$ du graphe (le max des $\#G_1(x)$).
C'est clair que pour $k=0$, on a $m=0$ et tous les sommets sont solutions.
Pour $k>0$, on choisi un sommet $x$ ayant un degré égal à $k$. Il y a au moins un arc $[x,y]$ que l'on enlève.
On obtient un nouveau graphe $H$ plus petit que $G$ et qui a au moins une solution $s$.
Si $s\not=x$ alors remettre l'arc $[x,y]$ ne peut pas détériorer la situation de $s$ et ce sommet sera encore solution pour $G$.
Si $x$ est la seule solution, par hypothèse $\#H_1(x)=0$ et donc $k=1$.
Quand on remet l'arc $[x,y]$ :
a) soit $y$ n'a pas de voisin mais alors $y$ était aussi solution ce qui contredit l'unicité de la solution $x$ pour $H$.
b) soit $y$ a un voisin $z$ (qui doit être différent de $x$). Ce $z$ doit avoir un voisin sinon il est aussi solution. Ce voisin de $z$ est peut-être $x$ mais en tout cas $y$ est solution.
Je vous laisse trouver s'il y a une erreur...c'est pas complet, il manque les détails pour l'induction sur les hypothèses supplémentaires.
Mais en gros c'est l'idée.
Par exemple, se pose le problème si dans $H$ on a deux solutions $x$ et un $s$ et que $x$ ne l'est plus dans $G$. On a alors forcément $\#H_1(x)=0$ ou $\#H_1(s)=0$ sinon on aurait $\sigma_H(x)=s$ et $\sigma_H(s)=x$, c'est à dire $\sigma_H(\sigma_H(x))=x$. Bref...reste ce genre de trucs à voir en détails.
J'ai une piste que je vous propose ensuite pour que vous puissiez me faire mentir car cela me semble trop simple.
On considère des graphes $G$ finis (non vides) dirigés avec des arcs notés $[x,y]$ tels que $x\not=y$ et $[y,x]$ n'est pas aussi un arc. C'est à dire qu'il n'y a pas de boucles ni de cycles de longueur $2$.
Pour un sommet $x$, on note :
$G_1(x)$ l'ensemble de ses voisins, c'est à dire les $y$ tels que $[x,y]$ est un arc.
$G_2(x)$ l'ensemble de ses voisins à distance $2$ : les voisins des voisins qui ne sont pas eux-mêmes des voisins de $x$.
La conjecture dit qu'il existe toujours au moins un sommet $x$ (une solution) tel que $\#G_2(x)\ge\#G_1(x)$.
Définition : le degré d'un sommet $x$ est le nombre $\#G_1(x)$.
Je propose cette "quasi-preuve" avec des propriétés supplémentaires : non seulement il existe une solution $x$ mais en plus, si elle est unique alors son voisinage $G_1(x)$ est vide. De plus pour tout sommet $x$ de degré non nul, il existe une solution $\sigma_G(x)$ différente de $x$ et on peut définir $\sigma_G$ telle que $\sigma_G(\sigma_G(x))\not=x$ si cela existe (c'est à dire que le degré du sommet $\sigma_G(x)$ est lui aussi non nul).
Preuve par induction sur le nombre d'arcs $m$.
Considérons le plus grand degré $k$ du graphe (le max des $\#G_1(x)$).
C'est clair que pour $k=0$, on a $m=0$ et tous les sommets sont solutions.
Pour $k>0$, on choisi un sommet $x$ ayant un degré égal à $k$. Il y a au moins un arc $[x,y]$ que l'on enlève.
On obtient un nouveau graphe $H$ plus petit que $G$ et qui a au moins une solution $s$.
Si $s\not=x$ alors remettre l'arc $[x,y]$ ne peut pas détériorer la situation de $s$ et ce sommet sera encore solution pour $G$.
Si $x$ est la seule solution, par hypothèse $\#H_1(x)=0$ et donc $k=1$.
Quand on remet l'arc $[x,y]$ :
a) soit $y$ n'a pas de voisin mais alors $y$ était aussi solution ce qui contredit l'unicité de la solution $x$ pour $H$.
b) soit $y$ a un voisin $z$ (qui doit être différent de $x$). Ce $z$ doit avoir un voisin sinon il est aussi solution. Ce voisin de $z$ est peut-être $x$ mais en tout cas $y$ est solution.
Je vous laisse trouver s'il y a une erreur...c'est pas complet, il manque les détails pour l'induction sur les hypothèses supplémentaires.
Mais en gros c'est l'idée.
Par exemple, se pose le problème si dans $H$ on a deux solutions $x$ et un $s$ et que $x$ ne l'est plus dans $G$. On a alors forcément $\#H_1(x)=0$ ou $\#H_1(s)=0$ sinon on aurait $\sigma_H(x)=s$ et $\sigma_H(s)=x$, c'est à dire $\sigma_H(\sigma_H(x))=x$. Bref...reste ce genre de trucs à voir en détails.
Réponses
-
Bonjour, il me semble que l'induction ne fonctionne pas pour un seul arc de $x$ vers $y$.Les mathématiques ne sont pas vraies, elles sont commodes.Henri Poincaré
-
L'induction fonctionne.
$x$ est de degré maximal 1 (je parle toujours du degré sortant).
$y$ est solution car de degré 0.
$y$ est différent de $x$ et restera solution en remettant l'arc de $x$ à $y$.
précision : les voisins sont les sommets atteints par un arc. Dans ce cas particulier, $x$ a un seul voisin qui est $y$ et $y$ n'a pas de voisin. -
Si on note $(1,2,3,4)$ les sommets du carré que l'on parcoure dans le sens trigonométrique en ajoutant l'arc de $1$ vers $3$ alors $\sigma_G(2)=3$ et $\sigma_G(3)=4$. Le degré du sommet $2$ n'est pas nul mais on a bien $\#G_1(2)\leq\#G_2(2)$. Il me semble que la propriété $\exists x,\#G_1(x)\leq\#G_2(x)$ peut se démontrer par oubli de l'orientation et par la conjecture des $4$ couleurs prouvée par ordinateur (étant donné un graphe non orienté il existe pour chaque composante connexe un sous-graphe planaire). C'est une preuve compliquée sûrement pas du niveau d'un lycée ou d'un collège. Je suggère une preuve : pour chaque composante connexe du graphe non orienté on peut trouver un sous-graphe en cellules adjacentes (des cycles), de rajouter l'orientation, puis de faire une induction par cellules, enfin de rajouter les arc manquants.Les mathématiques ne sont pas vraies, elles sont commodes.Henri Poincaré
-
AlainLyon,
C'est une idée qui "sent assez bon" (intuitivement). Je suggère que vous la creusiez. Notez aussi que :
a) pour chaque composante il existera une solution (par induction).
b) pour un tournoi (graphe complet orienté) la conjecture est prouvée (voir mon pote Stéphan Thomassé de Lyon). J'avais aussi une preuve dans ce cas mais que je n'ai pas publiée. Je prouve un peu plus. Dans les tournois, il existe une énumération $x_1,x_2,...x_N$ des sommets telle que :
si partant de chaque $x_i$ avec un compteur $d_i=0$, en descendant vers $x_1$, quand on rencontre un sommet à distance $1$ de $x_i$, on diminue de $1$ ce compteur et quand on rencontre un sommet à distance $2$ de $x_i$, on augmente de $1$ ce compteur, alors tous les compteurs restent toujours positifs ou nuls. Donc au moins $x_N$ est solution. -
Je poursuis et simplifie l'idée d'induction et laisse AlainLyon creuser son sillon.
Il parait plus judicieux de faire une induction avec une notion un peu différente : le "degré potentiel".
Pour un sommet $x$, le $dp(x)$ est le nombre de voisins plus le nombre de sommets qui pourraient être voisins.
C'est à dire $dp(x)=\#G_1(x)+\#G_0(x)$ où $G_0(x)$ est l'ensemble des sommets différents de $x$ qui ne sont pas reliés à $x$ avec un arc dans un sens ou l'autre.
L'hypothèse d'induction devient : pour tout $x$ de degré potentiel maximal, il existe une solution différente de $x$. -
J'ai l'impression d'avoir une preuve complète en tête. Je vais la présenter ici au fur et à mesure.
Tout graphe $G$ a une solution $s$ avec $\#G_2(s)\ge\#G_1(s)$.
De plus, pour $x$ tel que $m=\#G_2(x)$ est minimal, soit $\#G_1(x)=0$ et $x$ est solution, soit il existe une solution différente de $x$.
Commençons la preuve....
Pour $m=0$.
a) Si $G_1(x)$ est vide, c'est clair que $x$ est solution.
b) Si $G_1(x)$ est non vide, alors la restriction de $G$ à ces sommets forme un graphe $H$ plus petit que $G$ et $H$ a donc une solution qui l'est aussi pour $G$ et qui est différente de $x$.
Le cas $m=1$....à suivre ( je vous laisse y réfléchir) -
Le cas $m=1$.
On a donc $\#G_1(x)>0$ et $\#G_2(x)=1$.
a) Si $\#G_1(x)=1$ alors $x$ a un voisin $y$ qui doit nécessairement avoir un voisin $z$ qui doit avoir au moins un voisin.
Donc $y$ est une solution différente de $x$.
b) Si $\#G_1(x)>1$ alors $x$ n'est pas solution. Il a au moins $2$ voisins dont un $y$ pour lequel on enlève l'arc $[x,y]$ et on obtient un plus petit graphe $H$ et $2$ cas possibles :
b1) soit $x$ est de $\#H_2$ minimal et il existe par hypothèse une solution $s\not=x$ pour $H$ qui le reste pour $G$.
b2) soit un prédécesseur $a$ de $x$ devient de $\#H_2$ minimal. Donc $a$ a perdu $y$ de son $G_2$ par la suppression de l'arc $[x,y]$.
On remet l'arc $[x,y]$ et on enlève l'arc $[a,x]$. Soit il existe une solution différente de $a$ (aussi différente de $x$ car $x$ n'est pas solution) et elle le reste en remettant $[a,x]$. Soit $a$ est l'unique solution et en remettant l'arc $[a,x]$ il gagne un voisin à distance $1$ ($x$) et un voisin à distance $2$ ($y$) et reste une solution différente de $x$. -
La voie la plus "simple" pour une preuve consiste à montrer que pour tout sommet $x$ de degré $1$, il existe une solution $s\not=x$.
Ensuite par induction, c'est trivial. -
Il suffit donc de montrer que si un graphe $G$ a une solution unique $s$, alors elle est de degré nul.
Par expérimentation, une solution unique (autre que l'unique sommet d'un graphe) est successeur de tous les sommets d'une sous composante connexe $C$ qui peut-être réduite à un sommet seul ou composée de sommets comme un cycle. Les sommets de cette composante $C$ n'ont comme successeurs que ce sommet $s$ et des sommets de cette composante $C$. Par induction, si on ne considère que $C$ sans $s$, elle a une solution propre $r$ qui n'est plus solution quand on la relie à $s$ mais le redevient quand on ajoute un successeur $t$ à $s$. Ce successeur $t$ ne pouvant pas faire partie de $C$ puisqu'il faut que $t$ n'ait pas $s$ comme successeur. Donc, quand on ajoute un arc à une solution unique, on en obtient au moins deux. -
Pour dire plus simplement mon intuition :
S'il y a une unique solution $s$ d'un graphe ayant plus d'un sommet, alors elle est de degré nul et il existe un prédécesseur $r$ de $s$ qui devient solution quand on enlève l'arc de $r$ à $s$ et qui n'est relié par aucun chemin aux possibles successeurs $t$ de $s$ si on complète le graphe, c'est à dire les $t$ (autres que $s$) qui ne sont pas prédécesseurs de $s$. Ainsi, si on rajoute un arc de $s$ vers un tel $t$, le prédécesseur $r$ devient une autre solution. -
Bonjour à celles et ceux qui suivent ce fil.
Je le dis depuis le début : une clé pour résoudre facilement cette conjecture est la suivante.
Conj 1. Si un digraphe $G$ a une solution unique $s$ alors son degré (sortant) est nul.
Je pense que la conjecture suivante est vraie aussi :
Conj 2. Tout sommet $x$ de degré sortant $k$ est à distance au plus $k$ d'une solution $s$ (par un chemin orienté de $x$ vers $s$). -
Les conjectures du message précédent (modifié pour le préciser) sont testées avec un programme Maple....pas de contrexemple.
-
Salut.
@serge burckel si $G$ est un graphe comme tu le décris, si tu prends un sommet $s$ quelconque :
- soit il n'a pas de voisin, donc pas de second voisin et donc $G_2(s) = G_1(s) = 0$. Il convient.
- soit il a au moins un voisin et dans ce cas :
$\bullet$ soit tous ses voisins ont chacun au moins un voisin et donc $G_2(s) \geq G_1(s)$. Il convient.
$\bullet$ soit il a un voisin $s'$ qui n'a pas de voisin et alors .$G_2(s') = G_1(s') = 0$. $s'$ convient.
cqfd. -
Ha excuse-moi, deux des ses voisins peuvent avoir le mème voisin, auquel cas mon raisonnement ne marche pas.
-
Mais on peut dire que si $s$ a $n$ voisins, ses $n$ voisins ont dans leur ensemble un nombre $m_2\leq (n-1)$ voisins, sinon $s$ convient (ie $G_2(s)\geq G_1(s)$) et en plus chaque voisin $s'$ de $s$ a au moins un voisin parmi ceux-là sinon $s'$ convient.
Mais ces $m_2\leq (n-1)$ voisins doivent aussi avoir dans leur ensemble un nombre $m_3\leq m_2 - 1$ voisins, sinon tous les $m_2$ second voisins de $s$ conviennent et en plus chaque sommet $s''$ parmi ces $m_2$ a au moins un voisin parmi les $m_3$ sommets sinon $s''$ convient.
On obtient ainsi par itération si le processus ne s'arrête pas, une suite $(m_i)_{i\geq 1}$, avec $m_1 = n$ décroissante de nombre de voisins à valeurs dans $\mathbb{N}$ qui est minoré par 0 (et donc forcément un sommet qui n'aura pas de voisin).
cqfd
Cordialement -
Babsgueye.
Ne pas oublier que $x\rightarrow y$ et $y\rightarrow z$, n'interdit en rien que $x\rightarrow z$.
Dit autrement, $x\rightarrow y$ et $x\rightarrow y'$, n'interdit en rien que $y\rightarrow y'$.
Les voisins de nos voisins peuvent être nos propres voisins.
Donc $x$ peut avoir $n$ voisins et certains de ses voisins peuvent en avoir plus (en étant voisins entre eux) sans pour autant que $x$ soit solution.
Par exemple, $x$ peut avoir $3$ voisins qui forment un cycle et qui ont encore chacun $2$ mêmes voisins à distance $2$ de $x$.
Tous les sommets sont de degré $3$ mais $x$ n'est pas solution.
Pour un degré minimal égal à $5$, les voisins d'un $x$ peuvent très bien ne contribuer qu'à $3$ sommets à distance $2$ de ce $x$....voyez comment. -
Ha Ok. J'avais pas noté ''...qui ne sont pas eux-mêmes des voisins de $x$''.
Je vais lire le fil.
Merci. -
Salut.
@serge buckel, je remarque d'abord que prouver ta conjecture 2, équivaut à résoudre le problème.
Mais je propose ici une démonstration par récurrence sur l'ordre du graphe.
On peut déjà noter que le graphe initial $G$ peut être considéré comme ''connexe'' avec tous ses sommets de degré $\geq 1$ (sinon le sommet de degré $0$ donne la solution).
Soit alors $P_i$ la propriété : ''Un graphe d'ordre $i$ a un sommet qui convient (au sens que le nombre de ses second voisins est $\geq$ au nombre de ses voisins).''
On a $P_1$ est vraie (et mème $P_2$ est vraie). C'est l'initialisation.
On suppose $P_n$ vraie et va démontrer qu'alors $P_{n+1}$ vraie, pour l'hérédité.
Soit Alors $G$ un graphe d'ordre $n+1$ contenant un sommet $s$.
Si on supprime le sommet $s$ de $G$, on obtient un graphe $G'$ d'ordre $n$, contenant donc un sommet $p$ qui convient (ie tel que $G'_2(p)\geq G'_1(p)$).
- Soit $G_2(p)\geq G_1(p)$ (c'est dans $G$), alors c'est fini.
- Soit $G_2(p)\lt G_1(p)$, alors $s$ est un voisin de $p$ ou bien un second voisin de $p$.
Montrons d'abord que $s$ ne peut être second voisin de $p$.
$\bullet$ Si $s$ était un second voisin de $p$, on a $G'_1(p) = G_1(p)$ et $G'_2(p) = G_2(p) - 1\geq G'_1(p)$. C'est-à-dire $G_2(p)\geq G'_1(p) + 1 = G_1(p) + 1$. Contradiction. Donc $s$ ne peut pas être second voisin de $p$.
$\bullet$ $s$ est donc voisin de $p$.
Mais $G_2(p)\lt G_1(p)$, alors $s$ a tous ses voisins dans l'ensemble des second voisins de $p$ dans $G'$ et $G'_2(p) = G'_1(p)$ ($G_1(p) = G'_1(p) + 1$).
Mais si on supprime le sommet $p$ de $G$, le graphe $G''$ obtenu est d'ordre $n$ et a donc un sommet $p_1$ tel que $G''_2(p_1)\geq G''_1(p_1)$
Si $p_1$ n'est pas solution dans le graphe $G$, le mème raisonnement que ci-dessus implique que $p$ est un voisin de $p_1$, que tous les voisins de $p$ sont dans l'ensemble des second voisins de $p_1$ et que $G''_2(p_1) = G''_1(p_1)$ ($G_1(p_1) = G''_1(p_1) + 1$).
Mais si tous les voisins de $p$ sont dans l'ensemble des second voisins de $p_1$ et que $p_1$ n'est pas solution dans $G$, alors le nombre de voisins de $p_1$ est supérieur au nombre de voisins de $p$.
Et si on supprime $p_1$, le mème raisonnement tenu ci-haut implique qu'on a dans $G$ un sommet $p_2$ tel que, si $p_2$ n'est pas solution alors $p_1$ est un voisin de $p_2$ et que le nombre de voisins de $p_2$ est supérieur au nombre de voisins de $p_1$.
(Remarquons que $p_2$ est différent de $p$, car le nombre de voisins de $p$ est inférieur au nombre de voisins de $p_1$, sinon contradiction).
Ainsi de proche en proche si le processus ne s'arrête pas ''assez tot'' (ie on tombe sur un $p_i,\,i\lt n$ tel que $G_2(p_i)\geq G_1(p_i)$), on obtient une suite $(p_i)_{(1\leq i\leq n)}$ de sommets de $G$ telle que $G_1(p)\lt G_1(p_1)\lt G_1(p_2)\lt \cdots\lt G_1(p_n)$.
Mais parmi les $p_i$ de la suite, il y a les voisins de $p$. Et donc si $p$ a $m$ voisins, le mieme voisin de $p$, $p^m$ dans cette suite des $p_i$ est lel que $G_1(p^m)\lt m + G_1(p)$.
Ce qui est en contradiction avec le fait que $p$ ne convient (au sens que $G_2(p)\geq G_1(p)$).
Donc si n'est pas solution, le processus s'arrête forcément en moins de $n$ étapes, c'est-à-dire qu'on trouve un sommet $p_i,\,i\lt n$ de $G$ tel que $G_2(p_i)\geq G_1(p_i)$.
D'où l'hérédité.
Donc pour tout graphe $G$ d'ordre fini, la conjecture est vraie.
Cqfd. -
Je vais lire attentivement ton argumentation quand j'aurai un moment.
Que l'on se comprenne bien : <<enlever $s$>> c'est bien enlever ce sommet, ses arcs entrants et ses arcs sortants...oui ? -
Dans le cas où $s$ est voisin de $p$, pourquoi $s$ aurait tous ses voisins à distance $2$ de $p$ ?
Il peut avoir des voisins à distance $1$ aussi...non ?
De plus $s$ n'existe plus dans $G'$, on l'a supprimé. -
serge burckel a écrit:Que l'on se comprenne bien : <<enlever s>> c'est bien enlever ce sommet, ses arcs entrants et ses arcs sortants
Oui.serge burckel a écrit:Il peut avoir des voisins à distance 1 aussi...non ?
C'est vrai. C'est la mème erreur de notation du texte que dans ma réponse précédente qui revient (une idée fixe !).
Je vais encore voir s'il y a moyen de s'en sortir avec cette récurrence quand mème... Pour le sommet $s$, il fallait tout juste conjuguer au passé.
Merci.
A plus. -
En tout cas c'est un travail intéressant et qui mérité d'être suivi.
J'ai aussi cherché un procédé itératif en considérant par exemple les cycles orientés minimaux du graphes.
Bonne continuation. Je vais aussi voir avec vous s'il y a une issue.
Vous semblez parfois oublier que l'on parle de plus courts chemins.
Si $x\rightarrow y\rightarrow z$ et $x\rightarrow z$ alors $z$ est dans le premier voisinage de $x$ et n'est pas dans le second. -
Salut @serge, je vois que tes notations sont plus formelles, moi je faisais une exploitation plutôt littéraire.
J'ai encore regardé ce qu'on pouvait faire pour la récurrence, mais j'ai finalement fait une pirouette pour proposer en fin de compte un contre-exemple à la conjecture.
Il s'agit d'un graphe $G$ à 15 sommets, qui n'est pas planaire et que je ne peux donc ici dessiner clairement. Mais je vous donne les arcs et les sommets que je note $a, b, \cdots, n, o$, en pensant que ce sera quand mème exploitable.
Les arcs sont :
$a\to b\to c\to a$
$a\to d, a\to e, a\to f, a\to k, a\to n$
$c\to d, b\to e, b\to f, b\to k, b\to n$
$c\to d, c\to e, c\to f, c\to k, c\to n$
$d\to e\to f\to d$
$d\to g, d\to h, d\to i, d\to l, d\to o$
$e\to g, e\to h, e\to i, e\to l, e\to o$
$f\to g, f\to h, f\to i, f\to l, f\to o$
$g\to h\to i\to g$
$g\to a, g\to b, g\to c, g\to j, g\to m$
$h\to a, h\to b, h\to c, h\to j, h\to m$
$i\to a, i\to b, i\to c, i\to j, i\to m$
$j\to a, j\to b, j\to c, j\to d, j\to e, j\to f$
$k\to d, k\to e, k\to f, k\to g, k\to h, g\to i$
$l\to g, l\to h, l\to i, l\to a, l\to b, l\to c$
$m\to j, m\to d, m\to e, m\to f, m\to a, m\to b, m\to c$
$n\to k, n\to g, n\to h, n\to i, n\to d, n\to e, n\to f$
$o\to l, o\to a, o\to b, o\to c, o\to g, o\to h, o\to i$
Il serait plus visible pour le décryptage de d'abord dessiner le graphe. J'espère ne pas avoir fait d'erreur en transmettant.
Cordialement. -
J'ai des doutes qu'il y ait un contre-exemple, surtout avec seulement 15 sommets.
De plus, la conjecture est vérifiée si le degré d'un sommet est inférieur ou égal à $6$
(Kaneko,....The minimum degree approach for Paul Seymour's distance 2 conjecture)
Tu as moyen de programmer et tester ?
Sinon écris tes arcs sous la forme d'une liste de paires $[i,j]$ avec des entiers.
Par exemple $a\rightarrow b$ devient $[1,2]$.
Je vérifierai ça. -
Le graphe vérifiant une certaine symétrie, je pense qu'il suffit de vérifier sur 3 sommets. Par exemple les sommets $a, k$ et $n$.
Si tu appelles degré uniquement le nombre d'arcs sortant, les sommets du graphe sont de degré 6 et 7. Sinon j'ai encore pas vraiment lu sur le sujet.
Je changerai la notation quand j'aurai du temps inchallah.
Edit : Il y avait erreur de comptage des degrés -
J'avais écrit un programme en Maple et vérifié que si le degré (sortant) minimal était inférieur ou égal à $6$ alors il y avait au moins une solution...et même pas trop loin d'un tel sommet.
-
C'est vrai, j'avais mal compté, le degré minimal est bien $6$. Je alors vais encore revérifier (peut-être que mon idée fixe ne m'a pas quitté).
Merci. -
Envoyez-moi la liste des paires $[i,j]$, je vérifierai avec Maple. Là pas le temps de tout convertir. Mais quasi certain que ça ne peut pas être un contre-exemple. Le degré minimal serait $8$....je dirais "why not".
-
J'ai encore décrypté. T'as raison le sommet $a$ a $6$ voisins et $8$ second voisins.
Le sommet $k$ a $6$ voisin et $7$ second voisins.
Merci. -
Salut.
Je suis toujours dans la recherche d'un contre-exemple après avoir mieux appréhendé le problème.
Le graphe que je propose et qui a $25$ sommets de degrés $10$ et $12$ que je nomme $1$ à $25$, est le suivant.
$[1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [1, 10], [1, 11], [1, 12], [1, 21], [1, 23]$
$[2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [2, 10], [2, 11], [2, 12], [2, 21], [2, 23]$
$[3, 5], [3, 6], [3, 7], [3, 8], [3, 9], [3, 10], [3, 11], [3, 12], [3, 21], [3, 23]$
$[4, 5], [4, 6], [4, 7], [4, 8], [4, 9], [4, 10], [4, 11], [4, 12], [4, 21], [4, 23]$
$[5, 9], [5, 10], [5, 11], [5, 12], [5, 13], [5, 14], [5, 15], [5, 16], [5, 22], [5, 24]$
$[6, 9], [6, 10], [6, 11], [6, 12], [6, 13], [6, 14], [6, 15], [6, 16], [6, 22], [6, 24]$
$[7, 9], [7, 10], [7, 11], [7, 12], [7, 13], [7, 14], [7, 15], [7, 16], [7, 22], [7, 24]$
$[8, 9], [8, 10], [8, 11], [8, 12], [8, 13], [8, 14], [8, 15], [8, 16], [8, 22], [8, 24]$
$[9, 13], [9, 14], [9, 15], [9, 16], [9, 17], [9, 18], [9, 19], [9, 20], [9, 23], [9, 25]$
$[10, 13], [10, 14], [10, 15], [10, 16], [10, 17], [10, 18], [10, 19], [10, 20], [10, 23], [10, 25]$
$[11, 13], [11, 14], [11, 15], [11, 16], [11, 17], [11, 18], [11, 19], [11, 20], [11, 23], [11, 25]$
$[12, 13], [12, 14], [12, 15], [12, 16], [12, 17], [12, 18], [12, 19], [12, 20], [12, 23], [12, 25]$
$[13, 17], [13, 18], [13, 19], [13, 20], [13, 1], [13, 2], [13, 3], [13, 4], [13, 24], [13, 21]$
$[14, 17], [14, 18], [14, 19], [14, 20], [14, 1], [14, 2], [14, 3], [14, 4], [14, 24], [14, 21]$
$[15, 17], [15, 18], [15, 19], [15, 20], [15, 1], [15, 2], [15, 3], [15, 4], [15, 24], [15, 21]$
$[16, 17], [16, 18], [16, 19], [16, 20], [16, 1], [16, 2], [16, 3], [16, 4], [16, 24], [16, 21]$
$[17, 1], [17, 2], [17, 3], [17, 4], [17, 5], [17, 6], [17, 7], [17, 8], [17, 25], [17, 22]$
$[18, 1], [18, 2], [18, 3], [18, 4], [18, 5], [18, 6], [18, 7], [18, 8], [18, 25], [18, 22]$
$[19, 1], [19, 2], [19, 3], [19, 4], [19, 5], [19, 6], [19, 7], [19, 8], [19, 25], [19, 22]$
$[20, 1], [20, 2], [20, 3], [20, 4], [20, 5], [20, 6], [20, 7], [20, 8], [20, 25], [20, 22]$
$[21, 5], [21, 6], [21, 7], [21, 8], [21, 9], [21, 10], [21, 11], [21, 12], [21, 17], [21, 18], [21, 19], [21, 20]$
$[22, 9], [22, 10], [22, 11], [22, 12], [22, 13], [22, 14], [22, 15], [22, 16], [22, 1], [22, 2], [22, 3], [22, 4]$
$[23, 13], [23, 14], [23, 15], [23, 16], [23, 17], [23, 18], [23, 19], [23, 20], [23, 5], [23, 6], [23, 7], [23, 8]$
$[24, 17], [24, 18], [24, 19], [24, 20], [24, 1], [24, 2], [24, 3], [24, 4], [24, 9], [24, 10], [24, 11], [24, 12]$
$[25, 1], [25, 2], [25, 3], [25, 4], [25, 5], [25, 6], [25, 7], [25, 8], [25, 13], [25, 14], [25, 15], [25, 16]$.
Vue une certaine symétrie du graphe, il suffira de vérifier pour deux sommets : par exemple les sommets $1$ et $21$.
Je constate que le sommet $1$ a $10$ voisins et $9$ second voisins, ainsi que les sommets de $2$ à $20$ et que le sommet $21$ a $12$ et $10$ second voisins ainsi que les sommets de $22$ à $25$.
Merci de vérifier.
Cordialement. -
Tous les sommets sont des solutions....LOL.
Voici la liste $x,d1(x),d2(x)$ :
1, 10, 11
2, 10, 11
3, 10, 11
4, 10, 11
5, 10, 11
6, 10, 11
7, 10, 11
8, 10, 11
9, 10, 11
10, 10, 11
11, 10, 11
12, 10, 11
13, 10, 11
14, 10, 11
15, 10, 11
16, 10, 11
17, 10, 11
18, 10, 11
19, 10, 11
20, 10, 11
21, 12, 12
22, 12, 12
23, 12, 12
24, 12, 12
25, 12, 12
La prochaine fois stp vérifie avant et aussi donne la liste des arcs en mode texte. J'ai perdu du temps et de la patience à convertir. -
Ca veut dire que pour chaque sommet, il y a deux second voisins que j'ai pas vus.
Je lis à partir d'un graphe schématisé.
Je vais les rechercher.
Merci. -
J'ai étudié par programmation un truc qui pourrait être intéressant en étendant une approche de babsgueye.
On considère chaque sommet $x$ d'un graphe $G_4$. On enlève respectivement :
1. Ses arcs entrants pour obtenir un graphe $G_1$
2. Ses arcs sortants pour obtenir un graphe $G_2$
3. Ses arcs entrants et sortants pour obtenir un graphe $G_3$
On regarde chaque solution dans ces trois graphes et si elle est solution dans le graphe initial $G_4$.
Je note $1$ pour être solution et $0$ pour ne pas l'être.
On obtient les $7$ cas suivants (il y en a peut-être plus mais pas encore trouvé d'autres cas de figure) :
$[0, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 1], [0, 1, 1, 0], [1, 0, 1, 0], [1, 0, 1, 1], [1, 1, 1, 1]$
On voit que $[non,non,non]$ n'implique rien sur $G_4$ puisqu'on a les deux cas de figure $[0, 0, 0, 0], [0, 0, 0, 1]$.
$[non,oui,non,oui]$ semble dire que si un sommet $s$ n'est pas solution dans $G_1,G_3$ mais l'est dans $G_2$ cela implique qu'il l'est dans $G_4$. Donc $[non,oui,non]$ semble impliquer $oui$ sur $G_4$.
$[non,oui,oui]$ semble impliquer $non$
$[oui,non,oui]$ n'implique rien
$[oui,oui,oui]$ semble impliquer $oui$
à voir...... -
On peut aussi séparer les cas. Pour le $x$ considéré et les sommets $z$ solutions ou non :
Si $z=x$, on a $2$ configurations possibles : $[0, 1, 1, 0], [1, 1, 1, 1]$
Ce qui dit que $x$ est solution si et seulement si il l'est quand on enlève ses arcs entrants et aussi la trivialité que $x$ est solution quand on enlève ses arcs sortants (les $1$ en position deux (et aussi forcément en position trois)).
Si $z\not=x$, on a (au moins) $6$ configurations : $[0, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 1, 1, 1]$
C'est à dire que : $[non,oui,non]$ pourrait impliquer $oui$....cela reste à prouver. -
Je pense que la finalité de ton raisonnement est de montrer que $G_4$ admet une solution.
Comment espères-tu t'en sortir s'il y a des cas où tu ne peux décider pour $G_4$ ? -
C'est en cours....du moins expérimentalement...après il faudra prouver.
Il s'agit de considérer plus de types d'arcs et que des configurations (après suppressions) permettent de décider $oui$. -
@serge, je propose ici une démonstration de ta conj 2, ce qui équivaut à résoudre le problème de P. Seymour. En fait, je montre que la conjecture est vraie.
Soit $G$ un graphe contenant un sommet de degré supérieur à $1$ (sinon il n'y a pas de problème, $G$ contient une solution).
Soit $s_0$ un sommet de $G$ de degé $n\geq 1$ (nombre d'arcs sortants de $s_0$).
- soit $s_0$ est solution (au sens que $\#G_2(s_0)\geq \#G_1(s_0)$), alors c'est fini.
- soit $s_0$ n'est pas solution, alors l'ensemble des second voisins de $s_0$ est de cardinal au plus $n - 1$.
Les voisins de $s_0$ ont leurs voisins dans l'ensemble $E_0$ composé des voisins et des second voisins de $s_0$. Cet ensemble $E_0$ est de cardinal au plus $n + n - 1 = 2n - 1$.
Le nombre total d'arcs possible dans cet ensemble est donc au plus $\dfrac{(2n - 2)(2n - 1)}{2} = (n - 1)(2n - 1)$.
Donc il existe au moins un voisin de $s_0$, soit $s_1$ qui a au plus $\dfrac{(n - 1)(2n - 1)}{2n - 1} = n - 1$ voisins (Parce que chaque sommet de, au moins la moitié des sommets de $E_0$, a au plus $\dfrac{(n - 1)(2n - 1)}{2n - 1} = n - 1$ voisins dans $E_0$, et que les voisins de $s_0$ représentent plus de la moitié des sommets de $E_0$).
Alors
- soit $s_1$ est solution, et c'est fini
- soit $s_1$ n'est pas solution, et alors il a au plus $n - 2$ voisins.
Les voisins de $s_1$ ont leurs voisins dans l'ensemble $E_1$ composé des voisins et des second voisins de $s_1$. Cet ensemble $E_1$ est de cardinal au plus $n - 1 + n - 2 = 2n - 3$.
Le nombre total d'arcs possible dans cet ensemble est donc au plus $\dfrac{(2n - 4)(2n - 3)}{2} = (n - 2)(2n - 3)$.
Donc pour les mèmes raisons que ci-haut, il existe au moins un voisin de $s_1$, soit $s_2$ qui a au plus $\dfrac{(n - 2)(2n - 3)}{2n - 3} = n - 2$ voisins.
Alors
- soit $s_2$ est solution, et c'est fini
- soit $s_2$ n'est pas solution, et alors il a au plus $n - 3$ voisins.
Les voisins de $s_2$ ont leurs voisins dans l'ensemble $E_2$ composé des voisins et des second voisins de $s_2$. Cet ensemble $E_2$ est de cardinal au plus $n - 2 + n - 3 = 2n - 5$...
On construit ainsi de proche en proche, une suite de sommets de degré décroissant dans le graphe $G$.
Donc si $G$ est d'ordre fini, on tombera sur une solution $s_i, 0\leq i\leq n - 1$, ou finalement sur un sommet $s_n$ qui est sans voisin, et donc solution.
Cqfd.
Cordialement -
C'est à vérifier avec précision mais l'idée est bonne.
Je poursuis la mienne :
pour chaque sommet $x$, on considère les trois graphes obtenus en :
1. enlevant les arcs sortants
2. enlevant les arcs entrants
3. enlevant les arcs sortants et les arcs entrants
Je note $1$ pour $x$ solution, $0$ pour $x$ pas solution et $2$ pour "ça ne change pas le graphe".
Les cas possibles sont : $[1, 0, 1], [1, 1, 1], [1, 2, 1], [2, 1, 1], [2, 2, 2]$
et les cas $ [1, 1, 1], [2, 1, 1], [2, 2, 2]$ sont obtenus si et seulement si $x$ est solution dans le graphe initial et il existe un tel sommet.
Voyez que :
le cas $[2,2,2]$ signifie simplement que $x$ est un sommet isolé.
le cas $[2,1,1]$ signifie que $x$ n'a pas d'arc sortant et il est solution en enlevant ses arcs entrants.
le cas $[1,1,1]$ signifie que $x$ a des arcs sortants et entrants et il devient solution dans les trois cas de retrait de ces arcs. -
Je ne vois toujours pas là où tu veux en venir avec ta méthode.serge burckel a écrit:Les cas possibles sont : [1,0,1],[1,1,1],[1,2,1],[2,1,1],[2,2,2]
Pourquoi il y a que ces seuls cas ? Et le cas [0, 0, 0] par exemple.
Sinon, je crois fermement à ma preuve. Essaie de la comprendre. -
J'ai des doutes sur ton argument de décroissance des degrés. Le degré des voisins peut être le même que celui d'un sommet.
Et sinon, il suffirait de considérer un $s_0$ initial de degré minimal et ce serait fini. -
Pourquoi pas $[0,0,0]$ ? Si on enlève les arcs sortants d'un $x$, il devient solution.
Pour ta preuve, j'avais déjà essayé une approche par dénombrement des arcs possibles entre les voisins et ceux qui donnent forcément des sommets à distance $2$. Tu as peut-être vu un truc nouveau, mais je ne vois pas pourquoi il existerait un voisin $s_1$ de degré $n-1$. On peut avoir par exemple les voisins de $s_0$ qui forment un cycle entre eux et qui ont en plus $n-1$ arcs vers l'extérieur qui donnent $n-1$ sommets à distance $2$ de $s_0$. Les voisins sont quand même tous de degré $n$. -
Tu as réfléchi à ton argument de l'existence d'un voisin $s_1$ de degré au plus $n-1$ ? Il doit être faux non ?
Tu as compris le mien avec le cycle ?
Les $n$ voisins de $s_0$ forment un cycle entre eux. Chacun a donc un voisin parmi eux. Et chacun peut ensuite avoir un arc vers chacun des $n-1$ sommets à distance $2$ de $s_0$. Les $n$ voisins sont tous de degré $n$. -
Dans mon approche, le seul cas commun entre ce qui peut décider $oui$ et $non$ est $[1,2,1]$. Pour ce genre de sommet on ne peut pas dire s'il est solution ou non dans le graphe initial. Cela correspond à des sommets qui :
1. sont solutions quand on enlève les arcs sortants (évident mais le $1$ veut dire qu'il y en a sinon ce serait un $2$)
2. n'ont pas d'arcs entrants (c'est $2$ donc les enlever ne change pas le graphe)
1. sont solutions quand on enlève les arcs entrants (aucun) et sortants (logique)
Mais alors ces sommets ont seulement des arcs qui vont vers un sous-graphe plus petit qui contient par hypothèse une solution. -
Et comment tu interprètes le cas [0, 0, 0] ?
-
Ce cas $[0,0,0]$ est juste impossible.
Pour le premier chiffre, enlever les arcs sortants :
a) soit il y en a et cela donne $1$ (le sommet devient solution évidente).
b) soit il n'y en a pas et cela donne $2$ (le graphe ne change pas)
Donc pas de $0$ comme premier chiffre. -
Excuse-moi, certains de tes posts m'avaient échappé.
Mais je ne vois toujours pas où tu veux en venir avec ton raisonnement, et surtout à quoi ça sert de parler des arcs entrants (ils n'ont aucune influence sur le sort de $x$).
C'est vrai, mon raisonnement est encore faux.
Merci. -
Justement si, l'action d'enlever les arcs entrants donne une information :
a) s'il n'y en a pas, alors le sommet est isolé ou a des arcs vers un sous-graphe qui contient une solution.
b) s'il en a, on peut les enlever et s'il devient solution alors il le sera encore.
c) s'il en a, on peut les enlever et s'il ne devient pas solution alors il ne le sera toujours pas. -
J'ai de plus en plus de mal à croire à la conjecture après mes différentes tentatives de la démontrer. Je cherche en ce moment un contre-exemple.
-
Salut.
@serge buckel, je pense que celle-là est la bonne. Un contre-exemple à la conjecture. Un graphe à $32$ sommmets notés $1, 2, \cdots, 32$ que j'appelle $G$. Ses arcs sont les suivants.
$[1, 6], [1, 7], [1, 8], [1, 9], [1, 10], [1, 11], [1, 19], [1, 25], [1, 26], [1, 27], [1, 28], [1, 29], [1, 30], [1, 31], [1, 32]$
$[2, 6], [2, 7], [2, 8], [2, 9], [2, 10], [2, 11], [2, 19], [2, 25], [2, 26], [2, 27], [2, 28], [2, 29], [2, 30], [2, 31], [2, 32]$
$[3, 6], [3, 7], [3, 8], [3, 9], [3, 10], [3, 11], [3, 19], [3, 25], [3, 26], [3, 27], [3, 28], [3, 29], [3, 30], [3, 31], [3, 32]$
$[4, 6], [4, 7], [4, 8], [4, 9], [4, 10], [4, 11], [4, 19], [4, 25], [4, 26], [4, 27], [4, 28], [4, 29], [4, 30], [4, 31], [4, 32]$
$[5, 6], [5, 7], [5, 8], [5, 9], [5, 10], [5, 11], [5, 19], [5, 25], [5, 26], [5, 27], [5, 28], [5, 29], [5, 30], [5, 31], [5, 32]$
$[6, 12], [6, 13], [6, 14], [6, 15], [6, 16], [6, 17], [6, 18]$
$[7, 12], [7, 13], [7, 14], [7, 15], [7, 16], [7, 17], [7, 18]$
$[8, 12], [8, 13], [8, 14], [8, 15], [8, 16], [8, 17], [8, 18]$
$[9, 12], [9, 13], [9, 14], [9, 15], [9, 16], [9, 17], [9, 18]$
$[10, 12], [10, 13], [10, 14], [10, 15], [10, 16], [10, 17], [10, 18]$
$[11, 12], [11, 13], [11, 14], [11, 15], [11, 16], [11, 17], [11, 18]$
$[12, 1], [12, 2], [12, 3], [12, 4], [12, 5], [12, 16], [12, 17], [12, 18]$
$[13, 1], [13, 2], [13, 3], [13, 4], [13, 5], [13, 16], [13, 17], [13, 18]$
$[14, 1], [14, 2], [14, 3], [14, 4], [14, 5], [14, 16], [14, 17], [14, 18]$
$[15, 1], [15, 2], [15, 3], [15, 4], [15, 5], [15, 16], [15, 17], [15, 18]$
$[16, 1], [16, 2], [16, 3], [16, 4], [16, 5], [16, 19], [16, 20], [16, 21], [16, 22], [16, 23], [16, 24]$
$[17, 1], [17, 2], [17, 3], [17, 4], [17, 5], [17, 19], [17, 20], [17, 21], [17, 22], [17, 23], [17, 24]$
$[18, 1], [18, 2], [18, 3], [18, 4], [18, 5], [18, 19], [18, 20], [18, 21], [18, 22], [18, 23], [18, 24]$
$[19, 6], [19, 7], [19, 8], [19, 9], [19, 10], [19, 11], [19, 12], [19, 13], [19, 14], [19, 15]$
$[20, 6], [20, 7], [20, 8], [20, 9], [20, 10], [20, 11], [20, 12], [20, 13], [20, 14], [20, 15]$
$[21, 6], [21, 7], [21, 8], [21, 9], [21, 10], [21, 11], [21, 12], [21, 13], [21, 14], [21, 15]$
$[22, 6], [22, 7], [22, 8], [22, 9], [22, 10], [22, 11], [22, 12], [22, 13], [22, 14], [22, 15]$
$[23, 6], [23, 7], [23, 8], [23, 9], [23, 10], [23, 11], [23, 12], [23, 13], [23, 14], [23, 15]$
$[24, 6], [24, 7], [24, 8], [24, 9], [24, 10], [24, 11], [24, 12], [24, 13], [24, 14], [24, 15]$
$[25, 12], [25, 13], [25, 14], [25, 15], [25, 16], [25, 17], [25, 18]$
$[26, 12], [26, 13], [26, 14], [26, 15], [26, 16], [26, 17], [26, 18]$
$[27, 12], [27, 13], [27, 14], [27, 15], [27, 16], [27, 17], [27, 18]$
$[28, 12], [28, 13], [28, 14], [28, 15], [28, 16], [28, 17], [28, 18]$
$[29, 12], [29, 13], [29, 14], [29, 15], [29, 16], [29, 17], [29, 18]$
$[30, 12], [30, 13], [30, 14], [30, 15], [30, 16], [30, 17], [30, 18]$
$[31, 12], [31, 13], [31, 14], [31, 15], [31, 16], [31, 17], [31, 18]$
$[32, 12], [32, 13], [32, 14], [32, 15], [32, 16], [32, 17], [32, 18]$
D'après mes calculs :
les sommets de $1$ à $5$ ont chacun $15$ voisins et $14$ second voisins,
les sommets de $6$ à $11$ ont chacun $7$ voisins et $6$ second voisins,
les sommets de $12$ à $15$ ont chacun $8$ voisins et $7$ second voisins,
les sommets de $16$ à $18$ ont chacun $11$ voisins et $10$ second voisins,
le sommet $19$ a $10$ voisins et $8$ second voisins,
les sommets de $20$ à $24$ ont chacun $10$ voisins et $8$ second voisins,
les sommets de $25$ à $32$ ont chacun $7$ voisins et $6$ second voisins.
Merci de vérifier.
Cordialement. -
Mais c'est quoi ces arcs multiples ?????? Tu ne peux pas avoir 7 fois l'arcs [6,12] comme dans ton exemple. Une seule fois au plus.
S'il te plait, donne la prochaine fois la liste des arcs en format texte sans les dollars.
les solutions sont : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 25, 26, 27, 28, 29, 30, 31, 32
1, 15, 7, {6, 7, 8, 9, 10, 11, 19, 25, 26, 27, 28, 29, 30, 31, 32}, {12, 13, 14, 15, 16, 17, 18}
2, 15, 7, {6, 7, 8, 9, 10, 11, 19, 25, 26, 27, 28, 29, 30, 31, 32}, {12, 13, 14, 15, 16, 17, 18}
3, 15, 7, {6, 7, 8, 9, 10, 11, 19, 25, 26, 27, 28, 29, 30, 31, 32}, {12, 13, 14, 15, 16, 17, 18}
4, 15, 7, {6, 7, 8, 9, 10, 11, 19, 25, 26, 27, 28, 29, 30, 31, 32}, {12, 13, 14, 15, 16, 17, 18}
5, 15, 7, {6, 7, 8, 9, 10, 11, 19, 25, 26, 27, 28, 29, 30, 31, 32}, {12, 13, 14, 15, 16, 17, 18}
6, 1, 8, {12}, {1, 2, 3, 4, 5, 16, 17, 18}
7, 1, 8, {12}, {1, 2, 3, 4, 5, 16, 17, 18}
8, 1, 8, {12}, {1, 2, 3, 4, 5, 16, 17, 18}
9, 1, 8, {12}, {1, 2, 3, 4, 5, 16, 17, 18}
10, 1, 8, {12}, {1, 2, 3, 4, 5, 16, 17, 18}
11, 1, 8, {12}, {1, 2, 3, 4, 5, 16, 17, 18}
12, 8, 20, {1, 2, 3, 4, 5, 16, 17, 18}, {6, 7, 8, 9, 10, 11, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32}
13, 8, 20, {1, 2, 3, 4, 5, 16, 17, 18}, {6, 7, 8, 9, 10, 11, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32}
14, 8, 20, {1, 2, 3, 4, 5, 16, 17, 18}, {6, 7, 8, 9, 10, 11, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32}
15, 8, 20, {1, 2, 3, 4, 5, 16, 17, 18}, {6, 7, 8, 9, 10, 11, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32}
16, 11, 18, {1, 2, 3, 4, 5, 19, 20, 21, 22, 23, 24}, {6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 25, 26, 27, 28, 29, 30, 31, 32}
17, 11, 18, {1, 2, 3, 4, 5, 19, 20, 21, 22, 23, 24}, {6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 25, 26, 27, 28, 29, 30, 31, 32}
18, 11, 18, {1, 2, 3, 4, 5, 19, 20, 21, 22, 23, 24}, {6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 25, 26, 27, 28, 29, 30, 31, 32}
19, 10, 8, {6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 16, 17, 18}
20, 10, 8, {6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 16, 17, 18}
21, 10, 8, {6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 16, 17, 18}
22, 10, 8, {6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 16, 17, 18}
23, 10, 8, {6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 16, 17, 18}
24, 10, 8, {6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 16, 17, 18}
25, 7, 11, {12, 13, 14, 15, 16, 17, 18}, {1, 2, 3, 4, 5, 19, 20, 21, 22, 23, 24}
26, 7, 11, {12, 13, 14, 15, 16, 17, 18}, {1, 2, 3, 4, 5, 19, 20, 21, 22, 23, 24}
27, 7, 11, {12, 13, 14, 15, 16, 17, 18}, {1, 2, 3, 4, 5, 19, 20, 21, 22, 23, 24}
28, 7, 11, {12, 13, 14, 15, 16, 17, 18}, {1, 2, 3, 4, 5, 19, 20, 21, 22, 23, 24}
29, 7, 11, {12, 13, 14, 15, 16, 17, 18}, {1, 2, 3, 4, 5, 19, 20, 21, 22, 23, 24}
30, 7, 11, {12, 13, 14, 15, 16, 17, 18}, {1, 2, 3, 4, 5, 19, 20, 21, 22, 23, 24}
31, 7, 11, {12, 13, 14, 15, 16, 17, 18}, {1, 2, 3, 4, 5, 19, 20, 21, 22, 23, 24}
32, 7, 11, {12, 13, 14, 15, 16, 17, 18}, {1, 2, 3, 4, 5, 19, 20, 21, 22, 23, 24}
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 3
3 Invités