Inscription / Connexion Nouveau Sujet
Dénombrement. nombre chromatique d'un graphe
Bonjour j'ai un grand problème à résoudre et je cherche les réponses aux questions mais je bloque dès le début. Voici le problème:
Dans tout le problème, on appellera paire tout ensemble de cardinal 2.
On appellera graphe tout couple (S,A) où S est un sous-ensemble fini non vide
de 
et A un ensemble de paires d'éléments de S.
Etant donné un graphe G = (S,A), les éléments de S seront appelés les sommets
du graphe G et les éléments de A les arêtes du graphe G.
Pour tout graphe G, l'ensemble des sommets de G sera noté SG ou simplement
S s'il n'y a pas d'ambiguïté ; de même l'ensemble des arêtes de G sera noté AG ou
simplement A s'il n'y a pas d'ambiguïté. On notera nG, ou simplement n s'il n'y a
pas d'ambiguïté, le nombre de sommets du graphe.
Dans tout le problème, on considère, à titre d'exemples, les quatres graphes
particuliers définis de la façon suivante : pour k
{1, 2, 3, 4}, Gk = (Sk,Ak) où :
• Sk = {1, 2, 3, 4, 5},
• A1 = {{1, 2}, {2, 3}, {3, 1}, {3, 4}, {4, 5}},
• A2 = {{4, 2}, {2, 3}, {3, 1}, {3, 4}, {4, 5}},
• A3 = {{1, 2}, {2, 3}, {3, 5}, {3, 4}, {4, 5}},
• A4 = {{1, 3}, {1, 4}, {1, 5}, {3, 5}}
1. Une représentation d'un graphe G consiste à associer à chaque sommet de G
un point du plan et à tracer le segment défini par deux de ces points si et
seulement si les sommets auxquels sont associés ces points forment une arête
de G. Les points représentants les sommets du graphe doivent être choisis de
telle sorte que les segments représentant deux arêtes distinctes quelconques
ne puissent se rencontrer en plus d'un point.
Par exemple, le graphe G = (S,A) où :
S = {2, 5, 6, 11} et A = {{2, 5}, {6, 5}, {2, 6}, {2, 11}}
peut être représenté par la figure :
(une certaine figure)
Représenter les graphes Gk pour k[[1,4]]].
Dans la mesure du possible, on évitera les reprsentations dans lesquelles deux
segments se coupent en un point ne représentant pas un sommet du graphe.
2. On dira que deux graphes G = (S,A) et G' = (S',A') sont isomorphes si et
seulement si il existe une bijection 
: S 
S' telle que :
x,yS, {x,y} A 
{(x),(y)}A'
(Une telle bijection est appelé un isomorphisme de G sur G').
(a) Prouver que les graphes G1 et G3 sont isomorphes.
(b) Pour tout graphe G = (S,A) et tout sommet sS de ce graphe, on note 
G(s) (ou simplement (s) s'il n'y a pas d'ambiguïté) le nombre
d'arêtes du graphes auxquelles s appartient, et on note VG(s) (ou simplement
V (s) s'il n'y a pas d'ambiguïté) l'ensemble :
V (s) = {tS, {s, t} A}.
i. Vérifier que, pour tout graphe G = (S,A) et tout sommet s S de ce graphe, on a :
(s) = Card(V(s)).
ii. Montrer que si G = (S,A) et G' = (S',A') sont deux graphes isomorphes,
la propriété suivante est nécessairement vérifiée :
sS, G'((s))=G(s)
où désigne un isomorphisme entre G et G'.
(c) Les graphes G1 et G2 sont-ils isomorphes ?
Dans toute la suite du problème, pour tout p* et tout graphe G,
- on appelle "p-coloriage" de G toute application 
:S[[1,p]],
- on appelle "bon p-coloriage" de G tout p-coloriage de G tel que :
s,tS, {s,t}A
(s)
(t)
- on note B(p,G) l'ensemble des bons p-coloriages de G.
De plus, pour tout graphe G on note fG l'application de * dans définie par :
p*, fG(p)=Card(B(p,G))
et on note E(G) l'ensemble défini par :
E(G) = {p*, fG(p)0}.
3. Soit G un graphe.
(a) Montrer que nG E(G).
(b) Prouver que :
p*, pE(G)p+1E(G)
(c) En déduire l'existence d'un unique entier 
G * tel que :
E(G) = {p*, p
G}.
Le nombre G est appelé nombre chromatique de G.
J'ai réussi à tracer les courbes de la 1ere question mais ensuite je suis totalement bloquée quelqu'un peut-il m'aider svp? merci
Salut,
1. Ce ne sont pas vraiment des courbes mais des graphes. Dans le plan, ça doit ressembler à une ensemble fini de points et un ensemble fini de segments reliant ces points.
2. a) As-tu compris la définition d'isomorphisme ? Les dessins devraient t'aider pour cette question.
b) i) c'est élémentaire : il suffit de recopier les définitions
ii) idem
c) découle directement de b)
à partir du 3) ça devient intéressant et délicat.
Remarque :
1) si tu veux que des gens lisent tes énoncés je te conseille vivement d'élaguer et de poser les questions une par une. La plupart des gens savent très bien ce qu'est un graphe ici, ce n'est pas la peine de redonner de définition.
2) Pose des questions précises si tu veux de l'aide ! Pas du genre "aidez moi à résoudre tout mon devoir"
bonjour, oui dsl je sais mais j'ai préféré tout mettre d'un coup pour pouvoir voir plus clairement (enfin pour moi c'est plus clair comme ça)
oui pour les dessins c'est bon j'ai réussi à les tracer mais pour la question suivante en fait j'ai quelques problèmes avec la notion de bijection et j'ai vraiment du mal à démontrer des choses comme ça.
pouvez vous m'aider à y voir plus clair svp? merci déja^^
La définition d'une bijection n'est pas compliquée. Il faut retenir les deux versions suivantes :
1) Une application f : A -> B est une bijection si il existe une application g : B -> A telle que gof =idA et fog = id_B.
2) Une application f : A -> B est une bijection si chaque élément de b admet un unique antécédant.
Il faut être à l'aise avec les deux définitions et savoir passer de l'une à l'autre.
Dans le cadre d'un graphe, on cherche une application entre les ensembles des sommets f :S1 -> S2 qui envoit les arête sur les arrêtes, i.e. {f(s1),f(S2)} est une arête si {s1,s2} en est une. On dit que c'est un isomorphisme si f est une bijection sur les sommets et sur les arêtes.
Remarque que si on ne regarde pas les chiffres sur les sommets on voit bien que G1 est le même graphe que G3. C'est simplement ça que tu dois démontrer.
euh oui d'accord enfin c'est pas vraiment clair encore pour moi la 1ere definition de la bijection.. mais enfait je ne vois pas comment on peut défnir une fonction comme ça?
Se donner un isomorphisme entre deux graphes revient à voir quelle est la bonne renumérotation à faire pour obtenir le deuxième graphe.
Ici, on cherche , on voit par exemple qu'il faut que :
f(5) = 1
f(4) = 2
...
Après tu vérifies que ça correspond bien à la définition.
Il faut vraiment voir f comme une renumérotation.
ok donc j'ai renuméroter tout ça mais donc enfait je peux poser une fonction qui va de G1 dans G2 qui vérifie toutes ces numérotations? et comment je fais pour vérifier si elles verifient les définitions?
Ce que tu dis n'est pas clair. Que veux dire "vérifier une numérotation" ?
Qu'as-tu trouvé comme fonction f : G1 -> G2 ?
euh j'ai défini la fonction
f:G1G2 tel que:
f(5)=1
f(4)=2
f(3)=3
f(1)=5
f(2)=4
mais est-ce que je peux définir cette fonction comme ça?
j'ai vérifié ce qui est demandé pour la question i. mais pour la question ii. je ne vois pas comment faire =s
Annuler
connectez vous
algèbre en post-bac