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.
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.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres