Cardinalité, graphe — Les-mathematiques.net The most powerful custom community solution in the world

Cardinalité, graphe

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

  • 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_-\})$.
  • 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_+\}$.
  • 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.
Success message!