Coloration dun graphe - Meilleur en Maths
Coloration d'un graphe 1 Activité Pour une coupe du monde de football, les équipes qualifiées sont réparties en « poule » de quatre équipes Chaque équipe rencontre une et une seule fois les trois autres Toutes les équipes de la même poule, jouent le même jour un match et un seul
Algorithmique des graphes quelques notes de cours
9 Coloration Stable de cardinal maximum 33 Si le graphe est donné par tableau de listes de successeurs, la complexité du parcours en 2 1 3 Exercices 1
Coloriage et planarite´ - Institut de Mathématiques de Toulouse
Exercice 8 (Theor´ eme` de Konig)¨ Soit G un graphe de n sommets Prouver que G admet une bicoloration si et seulement s’il ne possede pas de cycle de longueur impaire ` Exercice 9 Dans un pays, 11 villes sont reli´ees deux a deux directement soit par une autoroute soit par une` ligne de chemin de fer (qui fonctionnent dans les deux sens)
ÉLÉMENTS DE THÉORIE DES GRAPHES QUELQUES EXERCICES D
Éléments de théorie des graphes - Quelques exercices d’application (avec solutions) page 3 0,0 5,0 0,3 5,3 2,3 3,0 3,3 2,0 0,2 5,2 4,3 4,0 Etc Exercice 5 (Jeu de Fan Tan) Deux joueurs disposent de 2 ou plusieurs tas d’allumettes A tour de rôle, chaque joueur peut enlever un certain nombre d’allumettes de l’un des tas (selon la
1 VOCABULAIRE DE BASE a Graphe
COLORATION D’UN GRAPHE ET NOMBRE CHROMATIQUE a Coloration d’un graphe Définition: Colorer un graphe consiste à affecter une couleur à chacun de ses sommets de telle sorte que deux sommets adjacents ne portent pas la même couleur Remarque: La coloration d’un graphe est toujours possible
ÉLÉMENTS DE THÉORIE DES GRAPHES QUELQUES EXERCICES D APPLICATION
Bon nombre de ces exercices peuvent être à l’origine de toute une « famille » d’exercices que l’enseignant n’aura aucun mal à « générer » 1 NOTIONS DE BASE 1 1 Modélisation Exercice 1 Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et
Compilation réalisée à partir d’exercices de BAC TES
GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir d’exercices de BAC TES Exercice n° 1 Un groupe d’amis organise une randonnée dans les Alpes On a représenté par le graphe ci-dessous les sommets B, C, D, F, T, N par lesquels ils peuvent choisir de passer Une arête entre deux sommets coïncide avec l’existence d’un
[PDF] algorithme de coloration de welsh et powell
[PDF] algorithme de coloration de graphe en java
[PDF] coloration des graphes pdf
[PDF] coloration graphe terminale es
[PDF] algorithme de coloration de graphe en c
[PDF] algorithme de coloration de graphe en python
[PDF] coloriage magique avec les puissances correction
[PDF] coloriage numérique isabelle guillot
[PDF] écrire une fraction sous la forme d'un entier et d'une fraction cm2
[PDF] les fractions supérieures ? 1
[PDF] fractions inférieures supérieures ou égales ? 1
[PDF] cours cap coiffure la permanente
[PDF] cours coloration cap coiffure
[PDF] règles des couleurs en coiffure
IUT Aix-en-ProvenceAnn´ee 2014-2015
DUT Informatique TD Graphes et Langagesfeuille n5Coloriage et planarit´eExercice 1 (Animosit´e)On consid`ere un groupe d"´el`eves de 7´el`eves appel´es A, B, C, D, E, F et G. Pour un
expos´e, les´el`eves se mettent en´equipes mais il faut respecter les incompatibilit´es entre les´el`eves. Dans le ta-
faudra-t-il cr´eer au minimum?ABCDEFG
AXXX BXX CXXXX DXXXXEXXXXX
FXXXX GXXExercice 2 (Radio pirate)On d´esire implanter 7 stations radio dans 7 endroits dont les distances mutuelles
en km sont donn´ees dans le tableau ci-dessous. En sachant que deux stations interf´erent si elles se trouvent`a
moins de 100 km l"une de l"autre, quel est alors le nombre minimum de longueurs d"onde qu"il faut pr´evoir
pour´eviter toute interf´erence?A B C D E F G
A0 55 110 108 60 50 88
B0 87 142 133 98 139
C0 77 111 85 193
D0 75 114 82
E0 107 41
F0 63Exercice 3Trois maisons doiventˆetre reli´ees`a 3 usines qui leur fournissent l"eau, le gaz et l"´electricit´e; on
demande de tracer le plan du r ´eseau de telle mani`ere que les tuyaux ne se croisent pas.Exercice 4 (Graphe planaire)1.Soit G= (S,A)un graphe simple planaire avec au moins 2 arˆetes. Mon-
trer quejAj 3jSj 6. 2. Montr erque K5ne peut pasˆetre un sous graphe deG. 3. Pr ouverque si Gest un graphe simple et planaire, ayant un nombre fini de sommets, alorsGposs`ede au moins un sommet de degr´e ne d´epassant pas 5.
4.Montr erpar r
´ecurrence sur le nombre de sommets que pour un graphe simple planaire G on ac(G)6. 5.En analysant plus finement le passage de la r
´ecurrence, montrer que l"on peut avoirc(G)5.
Exercice 5Soitn>1 un entier. On consid`ere le graphe simpleGndont les sommets sont les entiers de 1`an,
les sommetsaetb´etant reli´es par une arˆete si et seulement sia+best un nombre premier. 1. D´eterminer le nombre chromatique deGn.
2. D ´eterminer les entiers n pour lesquelsGnest planaire.Exercice 6 (Graphes d"intervalles)Dans le probl`eme suivant les questions sont assez ind´ependantes. Vous
pouvez donc sauter certaines questions si vousˆetes bloqu´e.`A une famille d"intervalles ferm´esI1= [a1,b1],...,In= [an,bn]on associe ungraphe d"intervalle G= (S,A)
dont les sommetsSsont les intervalles et les arˆetesAsont les paires(Ii,Ij)telles queIi\Ij6=AE. 1. Afin d"or ganiserles oraux d"un concours, on doit af fecter `a chaque´epreuve des salles diff´erentes. Voil`a la r´epartition des horaires des diff´erents oraux sur une journ´ee :MathInfoFranc¸aisAnglaisSportPhysique
2. On note l"ordre sur les intervalles d´efini parIJsi infIinfJ. On utilise aussi la notationAdj(I) correspondant`a l"ensemble des sommets adjacent`aI. Consid´erons l"algorithme de coloriage suivant :Algorithm 1:Coloriage d"un graphe d"intervalleData:Une famille Sd"intervallesI1,...,In.
Result:Une fonction de coloriage c:S!NforI2Sdoc(I) +¥;whileil existe I2S tel que c(I) = +¥dochoisirI2Sminimal pourtel quec(I) = +¥;
c(I) minfn1 tel quen6=c(J)pour toutJ2Adj(I)g;(a)Montr erque cet algorithme termine. (b)Montr erque cet algorithme donne un coloriage.
(c) Montr erque si l"algorithme donne la couleur ka un sommet, alors ce sommet est dans une clique de taille au moins ´egal`ak. On rappelle qu"unecliqueest un ensemble de sommets tous reli´es deux`a deux par des arˆetes du graphe.
(d) Montr erque le coloriage obtenu est optimal, c"est `a dire donne le nombre chromatique du graphe d"intervalles associ´e.
(e)Quel est la comple xit
´e de cet algorithme, c"est`a dire le nombre d"´etapes interm´ediaire n´ecessaire pour traiter un graphe `ajSjsommets etjAjarˆetes. 3.Un graphe est triangul´esi tout cycle de longueur sup´erieur ou´egal`a 4 admet une corde, c"est`a dire une
arˆete reliant deux sommets non cons´ecutifs.
(a)Est ce que les graphes suivant sont triangul
´es?MSF
A IPABC D EFGFAGDCH
EB (b) Montr erque tout graphe d"intervalles est triangul´e.
4.´Etant donn´e un graphe simpleG= (S,A), lecompl´ementaired"un graphe est le grapheG= (S,A)o`u
l"ar ˆetefs1,s2g 2Asi et seulement sifs1,s2g/2A. Un grapheG= (S,A)est un graphe decomparaison s"il est possible d"orienter les ar ˆetes de telle sorte que s"il existe un arc des1verss2et un autre des2vers s3alors il existe un arc des1verss3.
(a)Est ce que le compl
´ementaire des graphes suivant sont des graphes de comparaison?MSF A IPABC D EFGFADC
EB (b) Montr erque pour tout graphe d"intervalles G, le compl´ementaireGest un graphe de comparaison.5.Par un beau matin de novembr e,le duc de Densmor eest tr ouv
´e mort suite`a l"explosion d"une pi`ece
de son chˆateau de l"ˆıle de White. Les enquˆeteurs constatent que le meurtre a´et´e commis`a l"aide d"une
bombe plac´ee avec pr´ecaution dans le labyrinthe du chˆateau. Or, avant son assassinat, le duc avait invit´e
8 femmes sur l"
ˆıle. Lorsqu"elles sont interrog´ees, elles ne peuvent se souvenir des dates pr´ecises aux-
quelles chacune est venue au ch ˆateau, mais elles se rappellent quelles autres femmes elles ont crois´ees au chˆateau pendant leur s´ejour, et chacune jure que si quiconque d"autre avait´et´e l`a en mˆeme temps
qu"elle, elle s"en serait aperc¸ue, `a moins qu"une personne ne se soit volontairement cach´ee dans le la- byrinthe. Le marin qui faisait la navette vers l" ˆıle a lui aussi oubli´e les dates, mais il atteste n"avoir transport ´e chacune que pour un seul aller retour. Les enquˆeteurs´etablissent le rapport suivant : Ann dit avoir vu Betty ,Cynthia, Emily ,Felicia et Geor gia.Betty dit avoir vu Ann, Cynthia et Helen.
Cynthia dit avoir vu Ann, Betty ,Diana, Emily et Helen.Diana dit avoir vu Cynthia et Emily .
Emily dit avoir vu Ann, Cynthia, Diana et Felicia.Felicia dit avoir vu Ann et Emily .
Geor giadit avoir vu Ann et Helen.
Helen dit avoir vu Betty ,Cynthia et Geor gia.
Qui est le principal suspect? (Indication : On suppose que l"assassin a agit seul et se soit cach´e sur l"ˆıle.
Lorsqu"on retire un suspect du graphe des rencontres, si le graphe obtenu reste un graphe qui n"est pas
un graphe d"intervalles, alors c"est que ce suspect est innocent.) 6. Montr erqu"ungrapheGestungraphed"intervallessietseulements"ilexisteune´enum´erationC1,...,Cn des cliques deG, telles que pour tout sommetv, les indicesktels quev2Cksont cons´ecutifs. 7. Montr erque si Gest un graphe triangul´e etGest un graphe de comparaison alorsGest un graphe d"intervalles.Exercice 71.Pr ouverque dans toute soir ´ee de 6 personnes, il y en a toujours trois qui se connaissent
mutuellement ou trois qui ne se connaissent pas deux `a deux. 2.Dans une soir
´ee`a laquelle participent 17 personnes, certaines sont amies, d"autres sont ennemies et certaines ne se connaissent pas. Prouver qu"il existe un groupe de trois personnes qui ont deux `a deux les mˆemes sentiments les unes envers les autres.
3. Dans un gr oupede 18 personnes, deux quelconques sont toujours amies ou ennemies. Pr ouverqu"il existe quatre de ces personnes qui ont toutes les mˆemes sentiments les unes envers les autres.
Exercice 8 (Th´eor`eme de K¨onig)SoitGun graphe densommets. Prouver queGadmet une bicoloration si et
seulement s"il ne poss `ede pas de cycle de longueur impaire.Exercice 9Dans un pays, 11 villes sont reli´ees deux`a deux directement soit par une autoroute soit par une
ligne de chemin de fer (qui fonctionnent dans les deux sens). Prouver qu"il existe forc´ement un pont sur lequel
soit une autoroute passe au-dessus d"une autre, soit une voie de chemin de fer passe au-dessus d"une autre.
IUT Aix-en-ProvenceAnn´ee 2014-2015
DUT Informatique TD Graphes et Langagesfeuille n5Coloriage et planarit´e (Solutions)Correction 1On trace le grapheGo`u les sommets correspondent aux individus et il y a une arˆete entre
deux sommets si il y"a incompatibilit ´e. Une r´epartition des´el`eves correspond`a un coloriage du graphe G.Le probl
`eme se ram`ene`a trouver le nombre chromatique du graphe suivant.ABC D E FGL"algorithme Welsh-Powell fournit un 4 coloriage ainsic(G)4 (faire tourner l"algol). Le graphe induit par
les sommetsfE,F,C,Dgest complet, il est donc n´ecessaire d"avoir 4 couleur pour colorier le grapheGd"ou
c(G)4. Ainsic(G) =4.Correction 2On trace le grapheGo`u les sommets correspondent aux stations et il y a une arˆete entre deux
sommets si les deux station sont `a une distance inf´erieure`a 100km. Une r´epartition des´el`eves correspond`a un coloriage du graphe G. Le probl `eme se ram`ene`a trouver le nombre chromatique du graphe suivant.ABC D E FG L"algorithme Welsh-Powell fournit un 4 coloriage ainsic(G)4 (faire tourner l"algol).Supposons qu"il existe un 3-coloriagec:S!N. Si on consid`ere les triangles EDG et AEG, on en d´eduit que
D et A sont de la m
ˆeme couleur. Ainsi lorsqu"on regarde le sous-graphe ABCF, les sommets A et C doiventetre de couleurs diff´erentes. Il faut donc une quatri`eme couleur pour pouvoir le colorier ce qui am`ene une
contradiction. Ainsic(G)4 et doncc(G) =4.Correction 3
Correction 41.Notons que d"apr `es la formule d"Euler, que G soit connexe ou non, on as+fa+2.PuisqueGest simple, chacune de ses faces utilise au moins 3 arˆetes. R´eciproquement, chaque arˆete
intervient sur deux faces. Ainsi, on a 3f2a. En, reportant dans la relation d"Euler, il vient 2+a s+fs+23 a. Et ainsi :a3s6. 2. Le graphe K5est un graphe connexe`as=5 sommets eta=10 arˆetes. Comme 10>356, il ne v ´erifie pas l"in´egalit´e pr´ec´edente et ne peut donc pasˆetre planaire. 3.Il suf fitde travailler sur une composante connexe. On note s1,...,snles sommets deG. Soit a le nombre
d"ar ˆetes deG. Par l"absurde : Supposons que, pour tout i, on aitd(si)6. Alors 2a=åid(si)6n et donc 3na. Puisque G est planaire, on sait quea3n6. Cela conduit`aaa6, ce qui est clairement absurde. La conclusion en d´ecoule.
4.On pr ouvele r
´esultat par r´ecurrence sur le nombre n de sommets. Pourn=1, la conclusion est´evidente (comme pourn=6 d"ailleurs).Soitn1 fix´e. On suppose que la conclusion est´etablie pour tout graphe simple planaire n"ayant pas
plus densommets. Soit alors un graphe simple planaireGden+1 sommets. G poss`ede un sommet de degr ´e au plus´egal`a 5. Soitsun tel sommet, etG0le graphe induit en supprimantset les arˆetes correspondantes. D"apr `es l"hypoth`ese de r´ecurrence, chaque composante connexe deG0est 6-colorable (bien s ˆur, on utilise les mˆemes couleurs pour chaque composante). Commesn"est pas adjacent`a plusde 5 sommets, quelles que soient les colorations choisies sur chaque composante, il restera toujours au
moins une couleur disponible pour ˆetre attribu´ee`as, et construire ainsi une 6-coloration deG. 5. Soit Gun graphe planaire simple`ansommets. On va montrer par r´ecurrence sur le nombre de sommetsquotesdbs_dbs4.pdfusesText_8