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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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.
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 ?
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$
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.