Cycles dans un graphe et "line graph" — Les-mathematiques.net The most powerful custom community solution in the world

Cycles dans un graphe et "line graph"

Bonjour,
Je dois montrer que si G est un cycle à n sommets avec chaque sommet de degré 2 alors son "line graph" est un cycle à n sommets et il est isomorphe à G. Je dois également préciser la bijection.

J'ai fait quelques tests avec des cycles à 3 et 4 sommets mais je ne vois pas comment généraliser et surtout comment trouver explicitement la bijection.

Merci de votre aide.

Réponses

  • Peut-être pourrais-tu nous dire ce que tu appelles "line graph" ?
  • Oui pardon j'ai employé le mot anglais il s'agit du graphe aux arêtes.
    Le graphe aux arêtes de G a pour sommets les arêtes de G et deux sommets du graphe aux arêtes sont adjacents si et seulement si ils sont incidentes à un même sommet de G.
  • D'accord, on appelle souvent ça le graphe dual de $G$. Pour simplifier les notations, je numérote $e_1, e_2, \dots, e_n$ les sommets de $G$ de sorte que les arêtes soient $a_1 = \{e_1, e_2\}, a_2 = \{e_2, e_3\}, \dots, a_n = \{e_n, e_1\}$. Que penses-tu alors de l'application $\begin{array}{ccc}G & \longrightarrow & G'\\e_j & \mapsto & a_j\end{array}$ ?
  • Merci avec les notations c'est plus clair
    L'application est la bijection
    Le sommet $e_1$ dans G devient le sommet $a_1$ dans le graphe dual de G
    Le sommet $e_2$ dans G devient le sommet $a_2$ dans le graphe dual de G
    et ainsi de suite. Est-ce bien cela ?
  • Oui, et qu'en penses-tu par rapport à ton exercice ?
  • Je pensais utiliser l'application et montrer que G et son graphe dual sont isomorphes en utilisant un résultat du cours qui dit :

    Si G=(S,A) et G'=(A,B) sont isomorphes alors il existe une application telle que :

    $\forall e_1,e_2 \in S$, on a $(e_1,e_2) \in A \iff (\phi(e_1),\phi(e_2)) \in B$
  • Rebonjour
    J'aimerais également justifier que dans un graphe dual un sommet $e=\{s_i, s_j\}$ est de degré $d(e)=d_i+d_j-2$ où $d_i$ et $d_j$ sont les degrés de $s_i$ et $s_j$ dans le graphe $G$.
    Merci de votre aide.
  • C'est presque évident par définition. Je pense que tu devrais dessiner une dizaine de petits graphes et chercher leurs graphes duals pour te faire une idée, car tu n'as pas l'air à l'aise avec la notion.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!