théorème des 4 couleurs

[invite10a6d253]

tout ça me fait penser qu'aux boeufs aussi on donne des médailles dans les foires agricoles, quand ils ont un gros derrière

Merci, tu m'as fait rire aux éclats.
-----

[invite10a6d253]

Attention ... je vais vous lacher ma solution

c'est un processus en 4 temps :

vous coloriez un nuage de points qui ne sont pas relies par des aretes par la couleur 1
dans les points qui restent (il en reste 3/4 vu qu'il reste 3 couleurs ) on fait pareil avec la couleur 2
on traite toujours des points qui ne sont pas relies par une arete.
la il reste la moitie des points. On itere une fois le processus.
Voila il ne reste plus qu'a mettre la couleur 4 aux points qui restent, donc 1 quart des points logiquement vu qu'on a consomme le reste.

Voila ca marche tres bien sur un triangle et deux triangles colles.

Et voila le travail. Vous en pensez koi ?

Wouaaah. Mais pourquoi n'y avions-nous pas pensé plus tôt ?...

[invite9c9b9968]

dans les points qui restent (il en reste 3/4 vu qu'il reste 3 couleurs )

Salut,

Faute de logique. Si on reprenait le début avec l'idée de faire un coloriage à 5 couleurs, tu aurais dit à ce stade "il en reste 4/5 vu qu'il reste 4 couleurs". Alors 4/5 ou 3/4 ?

[invite455504f8]

Wouaaah. Mais pourquoi n'y avions-nous pas pensé plus tôt ?...

oui il me semble que ça correspond un peu à la méthode suivante:
1) se munir de 4 crayons de couleurs (différentes ! attention!)
2) colorier la carte de façon à ce que deux zones contigües n'aient pas la même couleur

et voilà!!!

[invite455504f8]

au fait à propos du sujet d'hier sur les bases de Hamel, j'ai un exemplaire numérique du bouquin cité par edpiste: Strange functions in real analysis.
obtenu par des voies inavouables mais bon.....

[GuYem]

Je crois que je ne comprends rien à ce fil ...

[invite455504f8]

désolé j'ai posté un message qui n'avait rien à voir.....le sujet est bien la "nouvelle" deémonstration du théorème des 4 couleurs par jahlucine

[inviteeb9ddbba]

Salut,

Faute de logique. Si on reprenait le début avec l'idée de faire un coloriage à 5 couleurs, tu aurais dit à ce stade "il en reste 4/5 vu qu'il reste 4 couleurs". Alors 4/5 ou 3/4 ?

Eh bien c'est tout a fait juste mais alors je suis en train de me dire que ca marche aussi pour 3 couleurs. Donc tous les graphes planaires sont 3 coloriables aussi en fait. C'est encore plus puissant que je pensais au depart.

pas forcement planaire le graphe vu que j utilise pas cette hypothese.

[inviteeb9ddbba]

plus serieusement

Est ce que quelqu'un aurait un lien vers une page sur la conjecture de Tait infirmee par tutte. Dans un article je lis que cette conjecture aurait implique le theoreme des 4 couleurs. Quelqu un pourrait m'expliquer pourquoi ?

[invite986312212]

pas forcement planaire le graphe vu que j utilise pas cette hypothese.

mauvais signe...
as-tu entendu parler des graphes de Kuratowski ?

[invite455504f8]

j'aimerais contribuer moi aussi: je viens de découvrir que l'on pouvait entièrement colorier un graphe avec une seule couleur!

[inviteeb9ddbba]

j'aimerais contribuer moi aussi: je viens de découvrir que l'on pouvait entièrement colorier un graphe avec une seule couleur!

Ah non objection

c'est pas sur

regarde par exemple si t as un crayon de couleur de 6 cm par exemple. Tu peux pas colorier disons 2000 - 2500points. Surtout si les points sont gros. donc il existe eps tel que taille a colorier > capacite du crayon .

Si tu fais tendre vers l'infini t'obtiens une contradiction

[inviteeb9ddbba]

bon j'ai fini par trouver toutes les informations que je cherchais sur le web.

Je vous remercie de vos idees. Je vais deposer ma demo lundi matin et je pourrai vous en faire part des mardi.

d'ici la je propose une tournee des paris .
Qui prend les paris que ma demo est bonne ou pas ?

[invite455504f8]

mince je suis refais
j'abandonne les maths et repars vers la philathélie

[invitec053041c]

[invite10a6d253]

d'ici la je propose une tournee des paris .
Qui prend les paris que ma demo est bonne ou pas ?

Bonjour, la mégalo...

[invite9c9b9968]

Eh bien c'est tout a fait juste mais alors je suis en train de me dire que ca marche aussi pour 3 couleurs. Donc tous les graphes planaires sont 3 coloriables aussi en fait. C'est encore plus puissant que je pensais au depart.

pas forcement planaire le graphe vu que j utilise pas cette hypothese.

Dommage, le coloriage à trois couleurs est impossible, cela a été démontré en 1940 par Danilo Blanuša en proposant un graphe dont chaque sommet est l'extrémité d'exactement trois arêtes.

[invite986312212]

Dommage, le coloriage à trois couleurs est impossible, cela a été démontré en 1940 par Danilo Blanuša en proposant un graphe dont chaque sommet est l'extrémité d'exactement trois arêtes.

oui, ce graphe n'est autre que , le graphe complet à 4 sommets, qui est planaire.

[inviteeb9ddbba]

bonjour

Je proposerais de partir de :

Coloriage de graphe hamiltonien planaire complet => coloriage de tout graphe planaire.

puis de developper l'etude des graphes hamiltoniens :

le graphe hamiltonien divise de plan en 2 parties. Il est facile de voir qu'en considerant les aretes constituant le cycle hamiltonien + les aretes contenues dans un demi plan on obtient exactement 1 coloriage en 3 couleurs (aux permutations pres donc *6 dans l absolu) et de maniere generale
k(k-1)(k-2)^(n-3) pour k couleurs.

On part de l'unique coloriage en 3 couleurs qui satisfasse un des demi-plan.

un algorithme pour inserer convenablement la 4eme couleur permet de conclure. (Je developperai l'algorithme si des personnes sont interessees)

Mais pensez vous que le debut du raisonnement est correct ?

[inviteeb9ddbba]

je precise que coloriage de graphe hamiltonien planaire => coloriage de tout graphe planaire est vraie uniquement pour k>=4 en vertu du theoreme de tutte :

"tout graphe 4 connexe est hamiltonien"

[inviteaf1870ed]

Just one for the road : Quel était le prénom de Tutte ?

[inviteeb9ddbba]

tututte je crois

[inviteaf1870ed]

Non, son prénom était Cosi, car il était belge

[invite7553e94d]

Je vais deposer ma demo lundi matin et je pourrai vous en faire part des mardi.

Alors alros ?

[inviteeb9ddbba]

lol

ben le debut de la demo est quelques posts plus haut. J'attends des critiques

[invite986312212]

je ne comprends pas pourquoi il suffit de considérer des graphes hamiltoniens. Autrement, qu'un circuit hamiltonien sépare le plan en deux parties, c'est vrai, que le graphe constitué du circuit plus les arêtes de l'une des deux parties soit 3-colorable, ça me semble vrai, bien que je ne voie pas bien comment le démontrer. Le point difficile, c'est l'algorithme pour créer une 4-coloration à partir des deux 3-colorations. C'est dommage qu'il n'existe pas d'injection de {1,2,3}x{1,2,3} dans {1,2,3,4}

[inviteeb9ddbba]

pour les circuits hamiltoniens ca vient du fait que les graphes a considerer sont 4 connexes , car s ils ne le sont pas la jonction entre eux se fait par 3 points, il suffit de relier les 3 points entre eux dans chacun des sous graphes pour pouvoir refaire la jonction. (apres permutation des couleurs d'un cote si c'est necessaire)

le coloriage d'un demi plan en 3 couleurs se demontre en considerant une distribution maximale d'aretes (n-3 aretes d'un cote du plan sans compter les aretes du circuit hamiltonien) et en constatant qu'on obtient une sorte d'arbre binaire. Si l arbre est complet son coloriage mene a une seule solution en 3 couleurs.

(En gros on part d'un triangle et on colorie de proche en proche)

Merci enfin pour cette premiere reponse ....

[invite986312212]

merci,
pour la 3-coloration, il y a une preuve ici:
http://theory.lcs.mit.edu/~indyk/6.8...douts/lec4.pdf

[inviteeb9ddbba]

merci pour le lien.

Mais je m'etonne vraiment de ne voir nulle part developper l'etude du coloriage des graphes hamiltoniens sur le web. Tout ce qu'on lit sur le web parle de la methode de kempe et de ses reduction. Pourtant que la methode des graphes hamiltoniens aboutisse ou pas elle devrait etre le lieu de developpements combinatoires interessants et devrait au moins servir pour les calculs probabilistes et les enumerations de graphe.

Merci de me faire passer d'autres liens sur le coloriage des graphes hamiltoniens si vous en trouvez

[inviteeb9ddbba]

ceci dit je note qu avec plus de 900 lectures ce fil tient le haut du pave

et on file vers les 1000 si ca continue