Cardinalité, graphe

Code_Name
Code_Name
dans Combinatoire et Graphes
Bonjour, soit un graphe $G=(V,E)$ avec $V$ les sommets et $E$ les arêtes.
Soit $e\in E$ en notant $e_+$ et $e_-$ ses deux sommets aux extrémités.
Je cherche à connaître la cardinalité de $\{A\subset V\mid e_+\in A,\ e_-\in A^c\}$.
La réponse est $2^{|V|-2}$ mais je ne vois pas le raisonnement derrière.
Merci pour votre aide.

Réponses

  • marco
    marco
    Une partie $A$ appartient à l'ensemble dont on cherche la cardinalité ssi $e_+ \in A$ et $e_- \notin A$. Donc on peut choisir une partie $B$ quelconque incluse dans $V \setminus \{ e_+,e_-\}$ et ajouter $e_+$ à $B$ pour obtenir une partie $A$, $A=B \cup \{e_+\}$, qui vérifie la propriété. Il y a donc autant de parties $A$ que de parties $B$. Or on peut choisir $B$ dans $\mathcal{P}(V \setminus \{ e_+,e_-\})$.
  • marco
    marco
    Le cardinal est bien $2^{|V|-2}$ (à moins d'avoir le choix de permuter $e_+$ et $e_-$, dans ce cas-là, ça multiplie par deux le cardinal). On le voit en prenant un graphe à $2$ sommets $e_+$ et $e_-$ et une arête. Il n'y a alors qu'une seule partie $A$, qui est $\{e_+\}$.
  • Code_Name
    Code_Name
    Bonjour marco, merci pour votre réponse :-)
    Oui effectivement j'avais mal lu en recopiant, le $1$ venait du fait que dans ma situation, on considère $\{A\subset V\mid e_+\in A,\ e_-\in A^c\}$ et $\{A\subset V\mid e_+\in A^c,\ e_-\in A\}$ ce qui m'a [rendu] confus.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 29

AmadouDomJLTNicoLeProfPoirotSethMorleyJuniorVassilliastfjsway +20 Invités