Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
169 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Cardinalité, graphe

Envoyé par Code_Name 
Cardinalité, graphe
il y a cinq semaines
avatar
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.



Edité 3 fois. La dernière correction date de il y a cinq semaines et a été effectuée par AD.
Re: Cardinalité, graphe
il y a cinq semaines
avatar
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_-\})$.



Edité 2 fois. La dernière correction date de il y a cinq semaines et a été effectuée par marco.
Re: Cardinalité, graphe
il y a cinq semaines
avatar
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_+\}$.
Re: Cardinalité, graphe
il y a cinq semaines
avatar
Bonjour marco, merci pour votre réponse smiling smiley
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.



Edité 2 fois. La dernière correction date de il y a cinq semaines et a été effectuée par AD.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 604, Messages: 1 497 686, Utilisateurs: 28 280.
Notre dernier utilisateur inscrit Section Paloise.


Ce forum
Discussions: 886, Messages: 7 497.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page