Les cheminements dans un graphe

Bonsoir,

Lisez attentivement ces définitions svp:

1-une chaine est une suite de sommets reliés par des arêtes (arcs), tel que deux sommets successifs ont une arête (arc) commune.

2-une chaine est dite simple si on passe une seule fois par ses arêtes (arcs).

3-un chemin est une suite de sommets reliés successivement par des arcs orientés dans le même sens.

4-un chemin est dit simple si on passe une seule fois par ses arcs.

5-un cycle est une chaine simple dont les deux extrémités coïncident (sont confondues).

6-un circuit est un chemin dont les deux extrémités coïncident (sont confondues).

7-une chaine est dite élémentaire si on passe une seule fois par ses sommets(même chose pour un cycle élémentaire,un chemin élémentaire et un circuit élémentaire).

Y a-t-il des critiques sur ses définitions?

Merci d'avance.

Bonsoir,

Je reformule ma question:

Est ce que vous trouvez que ces définitions sont justes?

Merci d'avance.;)

http://rperrot.developpez.com/articl...page=Page_1#LI

Et

http://algo.developpez.com/faq/?page=graphes

Bonsoir,

Tout d'abord merci Romuald pour les liens.

Concernant le premier lien(que j'ai pas lu avant de poster):
http://algo.developpez.com/faq/?page=graphes

Dans la partie Qu'est-ce qu'un chemin/chaîne ?, l'auteur Florent Humbert nous fait remarquer que dans la littérature sur les graphes, on utilise parfois seulement le terme chemin pour parler à la fois des chemins et des chaînes.
Justement parce que avant d'avoir ouvert cette discussion j'ai lu plusieurs articles, et le fait qu'on utilise parfois seulement le terme chemin pour parler à la fois des chemins et des chaînes ma embrouillée:roll:.

Dans la partie Qu'est-ce qu'un cycle/circuit ?, l'auteur Florent Humbert explique que Le terme cycle est utilisé pour les graphes non orientés et le terme circuit est utilisé pour les graphes orientés mais disposent de définitions proches.
Là je suis d'accord:ccool:.

Par contre je suis pas d'accord avec lui quand il dit qu'un cycle (resp. un circuit) est un chemin (resp. une chaîne) admettant le même sommet comme sommet de départ et comme sommet d'arrivée.
Normalement il devait écrire:un cycle (resp. un circuit) est une chaîne (resp. un chemin) admettant le même sommet comme sommet de départ et comme sommet d'arrivée.
Ai-je tort?:aie:

Concernant le deuxième lien (que j'ai lu avant de poster) :
http://rperrot.developpez.com/articl...page=Page_1#LI

Dans la partie Chaînes - Chemin - Circuit - Cycle, tu explique qu'on appelle chaîne simple, une chaîne qui n'est composée que de sommets différents et un chemin simple tout chemin qui ne passe pas deux fois par le même sommet.
je suis pas d'accord avec toi:aie:. j'ai lu dans pas mal d'articles qu'une chaine est dite simple si on passe une seule fois par ses arêtes (arcs).et un chemin est dit simple si on passe une seule fois par ses arcs. Que penses-tu de cette version?:?

Tu explique qu'un circuit est un chemin fermé simple. On entend par chemin fermé un chemin dont le sommet initial est aussi le sommet final.
Je suis pas d'accord:aie:.j'ai lu dans pas mal d'articles qu'un circuit est un chemin dont les deux extrémités coïncident (sont confondues).Pourquoi tu rajoute "simple"? Entre chemin fermé et chemin fermé simple, il y a une différence quand même, tu trouve pas?.:?

Tu explique qu'on appelle cycle une chaîne fermée. C'est donc un circuit pour les graphes non orientés.
là je suis d'accord avec toi:ccool:, malgré que j'ai lu dans un livre qu'un cycle est une chaine simple dont les deux extrémités coïncident (sont confondues).Je comprends pas pourquoi l'auteur a rajouté "simple"? Entre chaine fermée et chaine fermée simple, il y a une différence quand même, tu trouve pas?.:?

Tu explique qu'un cycle est dit élémentaire si la chaîne sur laquelle il est basé est simple (hormis le sommet de départ et d'arrivé, cela va de soit.).
Désolée, mais je suis pas d'accord:aie:.
j'ai lu dans pas mal d'articles qu'une chaine est dite élémentaire si on passe une seule fois par ses sommets(même chose pour un cycle élémentaire,un chemin élémentaire et un circuit élémentaire).Il y a une différence entre ces notions: "simple" et "élémentaire".Tu n'est pas d'accord avec moi?:?

Merci d'avance.

Citation:

---

Par contre je suis pas d'accord avec lui quand il dit qu'un cycle (resp. un circuit) est un chemin (resp. une chaîne) admettant le même sommet comme sommet de départ et comme sommet d'arrivée.
Normalement il devait écrire:un cycle (resp. un circuit) est une chaîne (resp. un chemin) admettant le même sommet comme sommet de départ et comme sommet d'arrivée.
Ai-je tort?

---

Il y a peut-être une coquille, à vérifier.

Citation:

---

Dans la partie Chaînes - Chemin - Circuit - Cycle, tu explique qu'on appelle chaîne simple, une chaîne qui n'est composée que de sommets différents et un chemin simple tout chemin qui ne passe pas deux fois par le même sommet.
je suis pas d'accord avec toi. j'ai lu dans pas mal d'articles qu'une chaine est dite simple si on passe une seule fois par ses arêtes (arcs).et un chemin est dit simple si on passe une seule fois par ses arcs. Que penses-tu de cette version?

---

Je pense qu'on ne parle pas forcément de la même chose. Tu parles de chaîne/chemin eulériens et ma définition est sur les chaînes/chemins hamiltoniens. Donc a priori on a tous les deux raison.

Citation:

---

Tu explique qu'un circuit est un chemin fermé simple. On entend par chemin fermé un chemin dont le sommet initial est aussi le sommet final.
Je suis pas d'accord.j'ai lu dans pas mal d'articles qu'un circuit est un chemin dont les deux extrémités coïncident (sont confondues).Pourquoi tu rajoute "simple"? Entre chemin fermé et chemin fermé simple, il y a une différence quand même, tu trouve pas?.

---

C'est une coquille, dans mes notes papiers, il n'y apparaît pas.

Citation:

---

Tu explique qu'un cycle est dit élémentaire si la chaîne sur laquelle il est basé est simple (hormis le sommet de départ et d'arrivé, cela va de soit.).
Désolée, mais je suis pas d'accord.
j'ai lu dans pas mal d'articles qu'une chaine est dite élémentaire si on passe une seule fois par ses sommets(même chose pour un cycle élémentaire,un chemin élémentaire et un circuit élémentaire).Il y a une différence entre ces notions: "simple" et "élémentaire".Tu n'est pas d'accord avec moi?

---

A vrai dire, je ne vois pas la différence.

Je dis ceci :
"On appelle chaîne simple, une chaîne qui n'est composée que de sommets différents"

Tu dis celà :
"une chaine est dite élémentaire si on passe une seule fois par ses sommets"

Si les sommets sont différents, c'est qu'on y est passé qu'une seule fois, non ? Je ne vois pas où est le problème.

Au passage, je pense que tu t'attache très fortement aux termes des définitions des graphes. Or il me semble avoir dit qu'elles étaient sujettes à interprétation. Suivant les habitudes (certains pros ne travaillent que sur des graphes simples, donc toutes leurs dèfs sont faîtes avec ces propositions). Chaque corps de métier et chaque domaine va avoir ses propres définitions. Sous le même terme et suivant les personnes les définitions changent.

Bonsoir,

Citation:

---

Il y a peut-être une coquille, à vérifier.

---

Ça ne doit être que ça.

Citation:

---

Je pense qu'on ne parle pas forcément de la même chose. Tu parles de chaîne/chemin eulériens et ma définition est sur les chaînes/chemins hamiltoniens. Donc a priori on a tous les deux raison.

---

Non, c'est pas ça du tout.:aie:
Je parle de chaîne/chemin simple(on passe une seule fois par ses arêtes (arcs)).
Et toi aussi tu parles de chaîne/chemin simple(on passe pas deux fois par le même sommet).
Et pour ce qui est chaîne/chemin eulérien, chaîne/chemin hamiltonien,c'est autre chose:
Chaîne/chemin eulérien(on passe une seule fois par chaque arc(arête) du graphe.
Chaîne/chemin hamiltonien(on passe une seule fois par chaque sommet du graphe.

Citation:

---

C'est une coquille, dans mes notes papiers, il n'y apparaît pas.

---

Très bien. Je te pardonne.:mouarf:

Citation:

---

A vrai dire, je ne vois pas la différence.

Je dis ceci :
"On appelle chaîne simple, une chaîne qui n'est composée que de sommets différents"

Tu dis cela :
"une chaine est dite élémentaire si on passe une seule fois par ses sommets"

Si les sommets sont différents, c'est qu'on y est passé qu'une seule fois, non ? Je ne vois pas où est le problème.

---

Tu ne vois pas où est le problème parce que pour toi simple ou élémentaire c'est la même chose. Ce qui n'est pas le cas pour moi(chaine élémentaire si on passe une seule fois par ses sommets. Chaîne simple on passe une seule fois par ses arêtes).
Est-ce une coquille?:mrgreen:

Citation:

---

Au passage, je pense que tu t'attache très fortement aux termes des définitions des graphes. Or il me semble avoir dit qu'elles étaient sujettes à interprétation. Suivant les habitudes (certains pros ne travaillent que sur des graphes simples, donc toutes leurs dèfs sont faîtes avec ces propositions). Chaque corps de métier et chaque domaine va avoir ses propres définitions. Sous le même terme et suivant les personnes les définitions changent.

---

Il n'y a que ça (cette interprétation) qui peut arrêter cette discussion.
Je dis que c'est possible...

Merci Romuald.;)

Citation:

---

Envoyé par nounadevelop

1-une chaine est une suite de sommets reliés par des arêtes (arcs), tel que deux sommets successifs ont une arête (arc) commune.

2-une chaine est dite simple si on passe une seule fois par ses arêtes (arcs).

3-un chemin est une suite de sommets reliés successivement par des arcs orientés dans le même sens.

4-un chemin est dit simple si on passe une seule fois par ses arcs.

5-un cycle est une chaine simple dont les deux extrémités coïncident (sont confondues).

6-un circuit est un chemin dont les deux extrémités coïncident (sont confondues).

7-une chaine est dite élémentaire si on passe une seule fois par ses sommets(même chose pour un cycle élémentaire,un chemin élémentaire et un circuit élémentaire).

---

Je ne connaissais pas ces définitions "francaise".

Les définitions anglaises ne font pas la difference entre chaine et chemin : on parle de "path" que ce soit dans un "directed" ou "undirected graph". On ne fait pas non plus la différence entre "sommets distincts" (élémentaire) et "arc distincts" (simple) : on parle de "simple" dans les deux cas.

Citation:

---

Très bien. Je te pardonne.

---

Il faut savoir que cet article n'est pas publié officiellement, il n'a donc pas subi de relecture très attentive.

Citation:

---

Je parle de chaîne/chemin simple(on passe une seule fois par ses arêtes (arcs)).
Et toi aussi tu parles de chaîne/chemin simple(on passe pas deux fois par le même sommet).
Et pour ce qui est chaîne/chemin eulérien, chaîne/chemin hamiltonien,c'est autre chose:
Chaîne/chemin eulérien(on passe une seule fois par chaque arc(arête) du graphe.
Chaîne/chemin hamiltonien(on passe une seule fois par chaque sommet du graphe.

---

A te relire, je ne saisi toujours pas la différence, ce que tu considères comme simple, c'est un chemin eulérien, et ce que je considère comme simple, c'est un chemin hamiltonien. Il n'y a pas à ma connaissance de terminologie commune, uniforme, normalisée concernant le terme simple. Lorsque j'ai écris ces lignes, ce qui m'intéressait, c'était les parcours relatifs à des sommets donc mes definitions portaient sur ces parcours là.

Et puis ça ne reste qu'une définition relative à cet article, comme toute définition elle a une portée, un contexte (cet article), comme je l'ai dit, il n'y a pas d'entente entre les disciplines sur les définitions. Il m'est arrivé de discuter à la fois avec des Mathématiciens, des informaticiens et des télécommunicants (je fais la différence entre telécom et informatique) et à chaque fois avant d'aller plus loin dans les discussion, nous nous sommes mis d'accord sur des conventions. Il faudra que tu acceptes que chacun puisse avoir raison, qui plus est dans le domaine des graphes.

Bonjour,

Merci pseudocode d'avoir répondu.

Citation:

---

Je ne connaissais pas ces définitions "francaise".

---

Donc pour toi comme pour romuald, la théorie des graphes=Domaine des réalités subjectives.

Citation:

---

Les définitions anglaises ne font pas la différence entre chaine et chemin : on parle de "path" que ce soit dans un "directed" ou "undirected graph". On ne fait pas non plus la différence entre "sommets distincts" (élémentaire) et "arc distincts" (simple) : on parle de "simple" dans les deux cas.

---

Donc pour toi la notion de chemin/chaine élémentaire n'existe pas?

Citation:

---

Il faut savoir que cet article n'est pas publié officiellement, il n'a donc pas subi de relecture très attentive.

---

Ça arrive.j'ai passé des moments de frustration:roll:, mais c'est pardonné.
ça a r r i v e.

Citation:

---

A te relire, je ne saisi toujours pas la différence, ce que tu considères comme simple, c'est un chemin eulérien, et ce que je considère comme simple, c'est un chemin hamiltonien. Il n'y a pas à ma connaissance de terminologie commune, uniforme, normalisée concernant le terme simple. Lorsque j'ai écris ces lignes, ce qui m'intéressait, c'était les parcours relatifs à des sommets donc mes definitions portaient sur ces parcours là.

---

Romuald,tu veux pas dire quand même que pour toi simple=hamiltonien?8O
Et toi pseudocode, tu est d'accord?:aie:

Merci d'avance.;)

Citation:

---

Romuald,tu veux pas dire quand même que pour toi simple=hamiltonien?

---

Non, j'ai du mal m'exprimer. Faisons-fi de mots comme hamiltonien et eulérien (j'ai l'impression qu'ils t'embêtent). Tes définitions sont relatives aux arcs, les miennes le sont vis à vis des sommets, voilà, point barre !

Citation:

---

Donc pour toi comme pour romuald, la théorie des graphes=Domaine des réalités subjectives.

---

Il ne faudrait pas pousser trop loin l'extrapolation. Le domaine reste objectif du moment qu'on a fixé les définitions des termes. (ça n'est qu'une question de convention).

Citation:

---

Envoyé par nounadevelop

Donc pour toi comme pour romuald, la théorie des graphes=Domaine des réalités subjectives.[

---

Oui, c'est le principe meme de poser une "définition". Tant que les définition sont claires et cohérentes, c'est bon.

Citation:

---

Donc pour toi la notion de chemin/chaine élémentaire n'existe pas?

---

Si, ca existe mais je ne mets pas 2 mots séparés suivant que je parle d'unicité des sommets, ou d'unicité des arêtes.

Citation:

---

Romuald,tu veux pas dire quand même que pour toi simple=hamiltonien?8O
Et toi pseudocode, tu est d'accord?:aie:

---

Non. Hamiltonien et Eulerien parlent de chemin/circuit qui utilisent la TOTALITE des sommets/arêtes. Alors qu'un chemin/circuit "simple" n'est pas obligé de passer par TOUS les sommets/arêtes.

Citation:

---

Non, j'ai du mal m'exprimer.

---

Ouf!

Citation:

---

Faisons-fi de mots comme hamiltonien et eulérien (j'ai l'impression qu'ils t'embêtent).

---

Non, c'est une fausse impression. J'ai juste besoin de rendre les choses plus claires.

Citation:

---

Si, ca existe mais je ne mets pas 2 mots séparés suivant que je parle d'unicité des sommets, ou d'unicité des arêtes.

---

Conclusion: simple=élémentaire=unicité des sommets, ou unicité des arêtes. Ai-je bien saisi?

Citation:

---

Non. Hamiltonien et Eulerien parlent de chemin/circuit qui utilisent la TOTALITE des sommets/arêtes. Alors qu'un chemin/circuit "simple" n'est pas obligé de passer par TOUS les sommets/arêtes.

---

Ouf! je suis soulagée.:ccool:
Et toi Romuald ça te va? "cette convention".

Merci d'avance.;)

Citation:

---

Et toi Romuald ça te va?

---

Que cherches-tu exactement ? Par eulérien et Hamiltonien, je faisais référence au type d'objet (arête/sommet) sur lequel s'applique la définition.

Citation:

---

Par eulérien et Hamiltonien, je faisais référence au type d'objet (arête/sommet) sur lequel s'applique la définition.

---

Ah! tu faisais référence...
C'est parfait.:ccool:

Merci Romuald et Pseudocode.;)