Cycles dans un graphe et "line graph"

cmaths12345 · May 2020

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.

Poirot · May 2020

Peut-être pourrais-tu nous dire ce que tu appelles "line graph" ?

cmaths12345 · May 2020

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.

Poirot · May 2020

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}$ ?

cmaths12345 · May 2020

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 ?

Poirot · May 2020

Oui, et qu'en penses-tu par rapport à ton exercice ?

cmaths12345 · May 2020

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$

cmaths12345 · May 2020

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.

Poirot · May 2020

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.

Cycles dans un graphe et "line graph"

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 24