Graphe et dimension

Paul Crion

Bonjour,
j'ai lu un jour un problème justifiant que certains graphes ne peuvent pas être planaires, existe-t-il d'autres théorème reliant graphe et dimension ? Par exemple, est-il possible de trouver des théorème sur les graphes qui ne pourraient pas être résolus en dimension 3 ? Si cette question est stupide pourriez vous m'expliquer simplement pourquoi?

Jer anonyme

Tout graphe se plonge dans $\R^3$. En effet, dès que l'on a une représentation raisonnable dans le plan, avec un nombre fini de croisements, il suffit de «soulever» un des brins pour supprimer le croisement et obtenir un plongement dans l'espace.

Une question de même nature mais plus compliquée, c'est : quelle est la «plus petite surface» dans laquelle on peut plonger un graphe ? Le contre-exemple $K_{3,3}$ (on prend trois usines (gaz, électricité et téléphone) et trois maisons et on relie chaque usine à chaque maison) n'est pas planaire mais il se plonge dans un tore (on parle de «graphe toroïdal»). Et inversement : étant donné une surface, comment caractériser les graphes qui ne peuvent pas se plonger dans cette surface ? Pour un tore, la réponse semble encore inconnue (voir par ex. sur la wikipedia le théorème de Robertson et Seymour).

Mais je ne sais pas si cela répond à la question.

Réf. : wikipedia ou Culture math.

christophe c

Le theoreme de Robertson et Seymour dit que tout ensemble E de graphes finis, stable par mineurs, a la propriete suivante:

il existe un ensemble FINI F tel que tout graphe fini G, G dans E ssi aucun elt de F nest un mineur de G

un mineur dun graphe G s obtient par applications successives de l operation consistant a:

1) retirer une arete OU

2) retirer un sommet (et les aretes adjacentes a lui) OU

3) contracter deux sommets relies en un seul

Pour E:=le plan on peut prendre F={K5; K3.3}

Seirios

La question de savoir quel est le plus petit entier $g$ tel qu'un graphe $\Gamma$ peut être tracé sur la surface (compact, orientable, sans bord) de genre $g$ est très délicate, et il existe encore des questions ouvertes sur le sujet. Il y a quelques paragraphes dédiés à ce problème dans History of Topology édité par James.

Paul Crion

Bonjour,
merci pour la réponse.
Je me demande si on considère un espace discret, je veux dire si le codage des sommets du graphe et les relations se font sur un espace euclidien de dimension n mais avec des coordonnées entières , peut-on trouver une limite pour le nombre de connexions possibles ? Je me dit intuitivement, si on veut que tous les points du graphe soient interconnectés et que deux connexions ne se croisent pas, il doit y avoir à un moment saturation de l'espace...non ?
Pour $\R^3$, je pense que le problème ne se pose en effet, mais dans le cas discret, n'y a-t-il pas une ralation entre nombre de points et dimension ?

Paul Crion

Bonjour,
le " genre" $g$ signifie la dimension de la "surface" ?
Si oui, alors le livre History of Topology édité par James est-il accessible sur internet ?
Cordialement,
Paul.

Meu

Genre d'une surface

Paul Crion

Merci, donc le genre classe les surfaces, mais souvenirs se réactivent, il n'y a donc rien sur des graphes "représentés" dans des espaces discrets de dimensions autres que 2... ma question doit être une non question, mais je n'arrive pas m'en convaincre...je me dis que tous les graphes concrets (réseau de routes ou autres) sont en dimension 3, mais je me dis aussi que la densité de ces graphes doit avoir une limite, les routes, on ne peut pas les croiser à l'infini, il doit exister une relation entre la "taille" des arêtes et le nombre de connexions possibles, j'ai lu un truc du genre chez Delahaye...bon, tout ceci n'est pas trop mathématique, quoique, si je cherche un modèle discret représentant un graphe, ce n'est peut être pas une question stupide...c'est peut être plutôt un problème d'informatique, mais les mathématiques et l'informatique ont des liens étroits...si quelqu'un a des pistes... je suis preneur.

Jer anonyme

Qu'est-ce qu'un espace discret ? Qu'est-ce que la dimension d'un espace discret ? Qu'est-ce qu'une "représentation" d'un graphe dans un espace discret ?

(Les réponses précédentes parlaient de plongement d'un graphe dans une surface ou dans l'espace réel, ce qui qu'on peut considérer comme l'antithèse d'un espace discret.)

Paul Crion

Bonjour,
un espace discret signifie ici un espace du genre $\N^3$, la dimension est celle de l'espace vectoriel $\N^3$...enfin je ne sais pas si on peut parler d'espace vectoriel comme je suppose que je reste en coordonnées entières, je ne peux pas prendre le corps $\R$ pour les scalaires, est ce que genre de structure a un nom ?
Une représentation serait l'adressage des noeuds du graphe avec des coordonnées entières et les connexions par des parcours sur le maillage à coordonnées entières.

Je me pose ces questions à partir du jeu de la vie de Conway, je veux juste savoir si avec un modèle de ce genre, on peut avoir une relation entre dimension(par exemple 3 pour $\N^3$) et "saturation" des connexions possibles. Il doit bien y avoir des recherches dans ce domaine puisque les réseaux informatiques reposent là dessus...mais je ne suis pas fichu de trouver des informations sur le net...de plus je débute en théorie des graphes alors je patauge un peu sur les définitions...désolé.

Jer anonyme

D'accord, je comprends un peu. Il y a en effet une évidence : si on met une arête entre deux points de $\N^3$ lorsqu'une seule de leurs coordonnées diffère d'au plus 1 (phrase mal construite), il n'y a que 6 voisins. Du coup, presque aucun graphe ne pourra être plongé. Remarque qui n'avance pas à grand-chose...

Paul Crion

Oui, d'accord mais si je suppose que les noeuds peuvent occuper un groupement de "cellules" et que les connexions elles sont les plus "petites" possibles, exemple "épaisseur" une cellule et longueur quelconque alors le problème est déjà plus "tordu", bon il y a beaucoup de guillemets, en gros j'aimerai savoir s'il existe des personnes ayant déjà entendu parler de travaux de ce genre... en mathématiques, informatique, physique...ça ressemble à un texte que j'avais lu il y a quelques années sur une sorte de géométrie "discrète"....problème de mémoire, impossible de retrouver des textes sur le sujet...

Maeglin

Un panorama sur la théorie des graphes : http://testard.frederic.pagesperso-orange.fr/mathematiques/coursGraphes/index.htm
L'optimisation dans la théorie de graphes : http://liris.cnrs.fr/csolnon/polyGraphes.pdf