Chemin dans un graph

Bonjour,

Soit le graphe $G(2,1)$ avec $V=2$ sommets et $E=1$ arête. Le postier chinois parcourt l’arête deux fois pour revenir à son point de départ. Donc la longueur du cycle minimal est $2$. Or $2 Card(E)-1=1$ : ta conjecture est fausse, non ?

Si le graphe n’est pas un arbre, il existe au moins une arête qui forme un cycle fermé. Quand on coupe ce cycle, le graphe devient un arbre et le cycle chinois contient $2Card(E)$ arêtes. Le plus petit cycle fermé possède trois sommets et trois arêtes. Sur une dessin, on voit qu’on peut parcourir les arêtes de ce cycle une seule fois (au lieu de deux fois dans un arbre). On a donc comme majorant $2Card(E)-3.$

Bonjour,

Arête (sic) de déconner... j’utilise un vocabulaire non spécialisé.
Quel est le plus petit graphe qui n’est pas un arbre ?
Il contient un cycle. Ouvre ce cycle pour le transformer en arbre. Et relis mon message... le plus petit cycle permet de ne passer qu’une fois sur les arêtes de ce cycle et on trouve donc une majoration.
Enfin, c’est mon idée. Je pense qu’un graphe qui n’est pas un arbre contient un cycle (une boucle) : un triangle (ou plus d’aretes). On les parcourt une seule fois et donc on majore par $2Card(E)-3.$

Bonjour,

Couper le cycle est utile pour comparer à l'arbre pour lequel on a $2Card(E).$ De plus, on se fout de l'unicité des coupes. On n'a pas cette unicité d'ailleurs.

Pour un arbre, on passe deux fois par chaque arête et donc, pour $n$ arêtes, le cycle chinois est $2 n=2 Card(E).$
Pour un graphe qui n'est pas un arbre, on a une série de cycles disjoints $c_1, c_2, ...$, chacun de longueur $n_1, n_2, ...$ avec $n_i \geq 3.$ Comme on ne passe qu'une fois par les arêtes dans ces cycles (*), on a un gain de $n_1+n_2+...$. Un gain par rapport à quoi ? Je coupe chacun de ces cycles en séparant deux arêtes du cycle. J'obtiens un graphe qui est un arbre (puisqu'on a détruit tout cycle). Son nombre d'arêtes est le même que celui du graphe original : $2 Card(E).$ Le majorant est donc $2 Card(E) - (n_1+n_2+...) \leq 2 Card(E)-3.$

Si les cycles ne sont pas disjoints et ont $m$ arêtes communes, alors on a $2 Card(E) - (n_1+n_2+... - m).$ Par exemple si on considére un carré et sa diagonale, vus comme deux cycles triangulaires.

(*) il suffit de l'écrire pour un triangle $ABC$ et de montrer qu'on peut toujours passer de $A$ à $B$ (puis de parcourir la partie du graphe attaché à $B$) et quand on revient en $B$ (**) on passe de $B$ à $C$ (puis de parcourir la partie du graphe attaché à $C$) et quand on revient en $C$ on passe de $C$ à $A$.
(**) si on n'est pas obligé de passer par $B$ c'est qu'il y a d'autres cyles, mais on cherche un majorant, donc on prend le cas le plus défavorable.