Maths et Délires
Des maths et des délires
 

Maths et Délires Index du Forum

 FAQFAQ   RechercherRechercher   Liste des MembresListe des Membres   Groupes d'utilisateursGroupes d'utilisateurs   S'enregistrerS'enregistrer 
 ProfilProfil   Se connecter pour vérifier ses messages privésSe connecter pour vérifier ses messages privés   ConnexionConnexion 

Connexité d'un graphe infini

 
Poster un nouveau sujet   Répondre au sujet    Maths et Délires Index du Forum -> Mathématiques taupinales et supérieures
Voir le sujet précédent :: Voir le sujet suivant  
Auteur Message
Salque
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 3271
Localisation: Salle Info 3 (ou salle Infi si je suis pressé)

MessagePosté le: 25 Avr 2008, 20:04    Sujet du message: Connexité d'un graphe infini Répondre en citant

Voici une question qui m'a été inspirée par la révision de mon cours de maths sur la connexité :

Pour un graphe fini, clairement, il n'y a qu'une définition possible de la connexité, et il s'agit en fait de la connexité par arcs.
Que se passe-t-il alors pour un graphe infini ? On peut évidemment reprendre la même définition - le graphe est connexe si tout couple de sommets est relié par un chemin fini d'arêtes - mais on obtient une notion qui s'assimile seulement à la connexité par arcs. Peut-on définir une notion plus générale, qui prend en compte aussi les "chemins infinis" et qui s'apparente donc à la connexité en général ? Le problème, c'est que je vois assez mal ce qu'est une "partie ouverte" (ou fermée) d'un graphe...
_________________
Ceci est un virus de signature. Recopiez-le dans votre signature, s'il vous plait.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 28 Avr 2008, 3:37    Sujet du message: Répondre en citant

On peut définir la réalisation topologique d'un graphe simple non-orienté [tex:9d1e48f04c]G = (V, E)[/tex:9d1e48f04c] (avec [tex:9d1e48f04c]E \subseteq V \times V \setminus \Delta[/tex:9d1e48f04c] et [tex:9d1e48f04c]\Delta = \{ (v, v), v \in V \}[/tex:9d1e48f04c] la diagonale de [tex:9d1e48f04c]V \times V[/tex:9d1e48f04c]) comme étant [tex:9d1e48f04c](X, \mathcal T, \mathval V, \mathcal E)[/tex:9d1e48f04c], avec [tex:9d1e48f04c]X[/tex:9d1e48f04c] un ensemble, [tex:9d1e48f04c]\mathcal T[/tex:9d1e48f04c] une topologie sur [tex:9d1e48f04c]X[/tex:9d1e48f04c], [tex:9d1e48f04c]\mathcal V : V \to X[/tex:9d1e48f04c] injective, et [tex:9d1e48f04c]\mathcal E : E \times I \to X[/tex:9d1e48f04c] continue (avec [tex:9d1e48f04c]I = [0, 1][/tex:9d1e48f04c] muni de sa topologie usuelle, et [tex:9d1e48f04c]E[/tex:9d1e48f04c] discret) et surjective, et vérifiant :
1) [tex:9d1e48f04c]\forall e \in E, \mathcal E \left< \{ e \} \times \partial I \right> = \mathcal V \left< e \right>[/tex:9d1e48f04c] (avec [tex:9d1e48f04c]\partial I = \{ 0, 1 \}[/tex:9d1e48f04c]),
2) [tex:9d1e48f04c]\forall e, e' \in E, \forall t, t' \in I,[/tex:9d1e48f04c][tex:9d1e48f04c]\mathcal E (e, t) = \mathcal E (e', t') \Rightarrow \{ t, t' \} \subseteq \partial I \vee (e = e' \wedge t = t')[/tex:9d1e48f04c],
3) [tex:9d1e48f04c]\forall e \in E, \forall t \in I, \forall v \in V, \mathcal V (v) = \mathcal E (e, t) \Rightarrow t \in \partial I[/tex:9d1e48f04c].

Il me semble que si on impose en plus que [tex:9d1e48f04c]\mathcal V \left< V \right<[/tex:9d1e48f04c] est une partie discrète et fermée de [tex:9d1e48f04c]X[/tex:9d1e48f04c], et qu'on définit un isomorphisme de réalisations topologiques de [tex:9d1e48f04c]G[/tex:9d1e48f04c] entre [tex:9d1e48f04c](X, \mathcal T, \mathcal V, \mathcal E)[/tex:9d1e48f04c] et [tex:9d1e48f04c](X', \mathcal T', \mathcal V', \mathcal E')[/tex:9d1e48f04c] comme étant une bijection [tex:9d1e48f04c]f : X \to X'[/tex:9d1e48f04c] qui soit un homéomorphisme pour [tex:9d1e48f04c]\mathcal T[/tex:9d1e48f04c] et [tex:9d1e48f04c]\mathcal T'[/tex:9d1e48f04c] tel que [tex:9d1e48f04c]f \circ \mathcal V = \mathcal V'[/tex:9d1e48f04c] et [tex:9d1e48f04c]f \circ \mathcal E = \mathcal E'[/tex:9d1e48f04c]), alors une réalisation topologique de [tex:9d1e48f04c]G[/tex:9d1e48f04c] est unique à isomorphisme près, et si l'on fixe [tex:9d1e48f04c](X, \mathcal T, \mathcal V, \mathcal E)[/tex:9d1e48f04c] l'une d'entre elles, et [tex:9d1e48f04c]G' = (V', E')[/tex:9d1e48f04c] un sous-graphe de [tex:9d1e48f04c]G[/tex:9d1e48f04c] (donc [tex:9d1e48f04c]V' \subseteq V[/tex:9d1e48f04c] et [tex:9d1e48f04c]E' \subseteq E \cap V' \times V'[/tex:9d1e48f04c]), alors [tex:9d1e48f04c]G'[/tex:9d1e48f04c] connexe au sens des graphes si et seulement si [tex:9d1e48f04c]\mathcal V \left< V' \right>[/tex:9d1e48f04c] est connexe (dans ce cas, il est même connexe par arcs).

Si on ne fait pas cette hypothèse, par contre, on n'a plus qu'une implication (connexité du graphe entraîne connexité topologique). Contre-exemple à la réciproque : [tex:9d1e48f04c]G = (\mathbb R, \emptyset)[/tex:9d1e48f04c] n'est certainement pas connexe en tant que graphe, mais [tex:9d1e48f04c](\mathbb R, \mathcal T_{\mathbb R}, \mathit {Id}_{\mathcal R}, \emptyset)[/tex:9d1e48f04c] (avec [tex:9d1e48f04c]\mathcal T_{\mathbb R}[/tex:9d1e48f04c] la topologie usuelle de [tex:9d1e48f04c]\mathbb R[/tex:9d1e48f04c]) est connexe et même par arcs.
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal


Dernière édition par Thibaut le 28 Avr 2008, 14:23; édité 5 fois
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
Salque
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 3271
Localisation: Salle Info 3 (ou salle Infi si je suis pressé)

MessagePosté le: 28 Avr 2008, 14:15    Sujet du message: Répondre en citant

Il me semble que le premier point parmi les propriétés que doit vérifier une réalisation topologique devrait être :
Citation:
1) [tex:760e596f50]\forall e \in E, \mathcal E \left< \{ e \} \times \partial I \right> = \mathcal V \left< e \right>[/tex:760e596f50] (avec [tex:760e596f50]\partial I = \{ 0, 1 \}[/tex:760e596f50])


Par ailleurs, je ne voudrais pas te vexer, mais ta façon de présenter les choses est assez illisible. Je veux dire, tu n'est pas en train de rédiger une copie ou un article, donc toute cette masse de beaux symboles en [tex:760e596f50]\LaTeX[/tex:760e596f50] à la Bourbaki ne fait qu'obfusquer le sens mathématique. A mon avis, ce serait beaucoup plus facile à suivre si tu avais dit, par exemple (corrige-moi si j'ai mal compris) :
"On peut définir la réalisation topologique d'un graphe, à savoir un plongement du graphe dans un espace topologique, où les sommets sont représentés par des points de l'espace, et les arêtes, par des arcs, injectifs et non sécants, qui relient ces points. Dans ce cas, si on impose que les images des sommets forment une partie discrète et fermée, la réalisation topologique d'un graphe est unique à isomorphisme près, et alors la connexité (au sens classique) du graphe, la connexité de sa réalisation topologiques et la connexité par arcs de celle-ci sont équivalentes. Par contre, si on prend une réalisation topologique quelconque, elle peut très bien être connexe sans que le graphe le soit. Contre-exemple à la réciproque : un graphe formé de tous les réels reliés par aucune arête n'est certainement pas connexe, alors que [tex:760e596f50]\mathbb R[/tex:760e596f50], qui réalise topologiquement ce graphe, l'est."

Si j'ai bien compris, donc, cette définition ne me paraît pas très satisfaisante : justement, elle ne permet pas de faire apparaître la distinction entre connexité et connexité par arcs. J'aimerais bien pouvoir dire, par exemple, que le graphe dont les sommets sont [tex:760e596f50]\mathbb N \cup \omega[/tex:760e596f50], et dont les arêtes relient chaque entier au suivant, est "connexe" (alors qu'il n'est pas "connexe par arcs", i. e. connexe avec la définition classique). Le truc, c'est qu'il faut un moyen de distinguer, par exemple, un sommet qui est "au bout" d'une chaîne infinie d'arêtes et un sommet qui est simplement "à côté". Est-ce possible de le faire d'une façon qui ait un sens ? Peut-être faut-il, dans ce cas, introduire une topologie sur l'ensemble des sommets ? Mais en fait, est-ce que ça a un intérêt d'étudier de tels graphes indépendamment de leurs réalisations topologiques ?
_________________
Ceci est un virus de signature. Recopiez-le dans votre signature, s'il vous plait.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 28 Avr 2008, 15:06    Sujet du message: Répondre en citant

Salque a écrit:
Il me semble que le premier point parmi les propriétés que doit vérifier une réalisation topologique devrait être

En effet. Corrigé, ainsi que deux autres erreurs.

Citation:
(corrige-moi si j'ai mal compris)
Non, je crois que tu as bien compris et reformulé ce que j'ai voulu dire. Il faut juste préciser ce que c'est qu'un isomorphisme de réalisations topologiques d'un graphe, parce qu'on pourrait aussi définir ça comme une bijection qui soit un homéomorphisme arête par arête et pas globalement, auquel cas deux réalisations topologiques d'un même graphe sont toujours isomorphes. Ou alors on pourrait définir ça comme une bijection qui soit un homéomorphisme arête par arête et sur l'ensemble des sommets (je me demande si c'est équivalent ou pas à la première définition, d'ailleurs).

Citation:
Si j'ai bien compris, donc, cette définition ne me paraît pas très satisfaisante : justement, elle ne permet pas de faire apparaître la distinction entre connexité et connexité par arcs. J'aimerais bien pouvoir dire, par exemple, que le graphe dont les sommets sont [tex:b989e74c27]\mathbb N \cup \omega[/tex:b989e74c27], et dont les arêtes relient chaque entier au suivant, est "connexe" (alors qu'il n'est pas "connexe par arcs", i. e. connexe avec la définition classique). Le truc, c'est qu'il faut un moyen de distinguer, par exemple, un sommet qui est "au bout" d'une chaîne infinie d'arêtes et un sommet qui est simplement "à côté". Est-ce possible de le faire d'une façon qui ait un sens ? Peut-être faut-il, dans ce cas, introduire une topologie sur l'ensemble des sommets ? Mais en fait, est-ce que ça a un intérêt d'étudier de tels graphes indépendamment de leurs réalisations topologiques ?
L'ennui, c'est que dans le graphe (qui n'est constitué que de sommets et d'arêtes), rien ne dit que [tex:b989e74c27]\omega[/tex:b989e74c27] est "au bout" de la chaîne d'arêtes est pas "à côté".
C'est dans le choix d'une réalisation topologique que tu peux exprimer ça :
Si tu réalises ton graphe en envoyant l'entier [tex:b989e74c27]n[/tex:b989e74c27] sur lui-même, l'arête entre [tex:b989e74c27]n[/tex:b989e74c27] et [tex:b989e74c27]n + 1[/tex:b989e74c27] sur le segment de [tex:b989e74c27][n, n + 1][/tex:b989e74c27], et [tex:b989e74c27]\omega[/tex:b989e74c27] sur [tex:b989e74c27]- 1[/tex:b989e74c27], alors [tex:b989e74c27]\omega[/tex:b989e74c27] est "à côté" de la chaîne, et la réalisation n'est pas connexe.
Par contre, si tu le réalises en envoyant [tex:b989e74c27]n[/tex:b989e74c27] sur [tex:b989e74c27]- \dfrac 1 n[/tex:b989e74c27], l'arête entre [tex:b989e74c27]n[/tex:b989e74c27] et [tex:b989e74c27]n + 1[/tex:b989e74c27] sur le segment [tex:b989e74c27][- \frac 1 {n + 1}, - \frac 1 n][/tex:b989e74c27] et [tex:b989e74c27]\omega[/tex:b989e74c27] sur [tex:b989e74c27]0[/tex:b989e74c27], alors [tex:b989e74c27]\omega[/tex:b989e74c27] est bien au bout de la chaîne formée par les entiers, et la réalisation est alors connexe (et même par arcs).

Par contre, il n'y a pas de réalisation qui soit connexe mais pas par arcs.
En effet, si [tex:b989e74c27](X, \mathcal T, \mathcal V, \mathcal E)[/tex:b989e74c27] en était une, alors :
Posons [tex:b989e74c27]f : \begin {matrix} \mathbb [-1, 0] & \to & X \\ 0 & \mapsto \mathcal V (\omega) \\ x & \mapsto & \mathcal E (n, t) \end {matrix}[/tex:b989e74c27] (où [tex:b989e74c27]n \in \mathbb N[/tex:b989e74c27] et [tex:b989e74c27]t \in [0, 1[[/tex:b989e74c27] tels que [tex:b989e74c27]x = - \frac 1 {n + t}[/tex:b989e74c27]) serait continue sur [tex:b989e74c27][-1, 0[[/tex:b989e74c27], mais pas en [tex:b989e74c27]0[/tex:b989e74c27] (sinon [tex:b989e74c27]X[/tex:b989e74c27] connexe par arcs).
Il vient (je zappe une étape qui m'a l'air fastidieuse) que [tex:b989e74c27]\{ \mathcal V (\omega) \}[/tex:b989e74c27] est ouvert (et bien sûr fermé) dans [tex:b989e74c27]X[/tex:b989e74c27], ce qui contredit la connexité de [tex:b989e74c27]X[/tex:b989e74c27].
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    Maths et Délires Index du Forum -> Mathématiques taupinales et supérieures Toutes les heures sont au format GMT + 2 Heures
Page 1 sur 1

 
Sauter vers:  
Vous ne pouvez pas poster de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas voter dans les sondages de ce forum


Powered by phpBB © 2001, 2005 phpBB Group
Traduction par : phpBB-fr.com