[PDF] Hamiltonicité dans une grille un jeu denfant ?

View - Download Hamiltonicité dans une grille un jeu denfant ?

Previous PDF

Next PDF

Hamiltonicit´e dans une grille, un jeu d"enfant ?

Aline ParreauRapport de Stage de License

Stage effectu´e au sein de l"´equipe CNAM-MAM du Laboratoire Leibniz sous la responsabilit´e de

Sylvain Gravier, directeur de l"´equipe

1

Parreau Aline Stage de License 2006

Table des mati`eres

Introduction3

1 Probl`eme initial 3

1.1 Enonc´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2´Elements de r´esolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.1 Simplification du probl`eme . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.2 Retour au probl`eme initial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3 Vers d"autres dimensions... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Quand le chemin devient un arbre... 9

2.1 Historique des recherches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 NP-compl´etude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3 Conditions N´ecessaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 Remarques g´en´erales sur les grilles rectangulaires . . . . . . . . . . . . . . . . . . . 11

2.4.1 Formalisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.2 Ce que deviennent les conditions n´ecessaires . . . . . . . . . . . . . . . . . . 12

2.4.3 Cas interdits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4.4 Elements de r´eduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.5 3 sommets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5.1 Conditions n´ecessaires et cas interdits . . . . . . . . . . . . . . . . . . . . . 15

2.5.2 Condition suffisante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.6 k sommets? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.7 Des id´ees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.8 Conclusion sur ce probl`eme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Maths `a modeler 18

3.1 Pr´esentation de l"´equipe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.2 La d´ecouverte de MAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.3 Ma participation ou comment vulgariser mon sujet de recherche . . . . . . . . . . . 19

3.3.1 L"applet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.3.2 Le jeu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Conclusion20

Bibliographie20

2

Parreau Aline Stage de License 2006

Introduction

L"ERT ´E Maths `a Modeler, avec laquelle j"ai effectu´e ce stage, cherche `a familiariser le public

avec la recherche actuelle en math´ematiques discr`etes, recherche `a laquelle elle participe activement.

Aussi, le but de mon stage´etait double : recherche sur un probl`eme actuel et cr´eation d"une situation

ludique pour permettre au public de chercher lui aussi sur ce sujet.

Une partie du stage, la plus importante en dur´ee, a donc ´et´e l"´etude de la question suivante :

´etant donn´ee une grille et deux points sur cette grille, peut-on relier les deux points par un chemin

hamiltonien, c"est-`a-dire qui passe une fois par toutes les cases de la grille? Apr`es avoir r´epondu

`a cette question (dite "probl`eme initial"), je me suis pench´ee sur des extensions de ce probl`eme

propos´ees par mon maˆıtre de stage : dimension plus grande, plus de points sur la grille...

Parall`element, nous avons essay´e de cr´eer une situation pour mettre le public en recherche sur

le mˆeme probl`eme. C"est en participant aux activit´es de Maths `a Modeler que j"ai pu avancer sur

ce sujet.

Le probl`eme initial est pr´esent´e dans la premi`ere partie. Dans la deuxi`eme partie, j"´etudie une

extension de ce probl`eme, c"est la partie sur laquelle j"ai le plus cherch´e et o`u j"ai apport´e le plus

de choses au niveau de la recherche. Enfin, dans la troisi`eme partie, je pr´esente l"´equipe qui m"a

accueillie, ses actions et ce que j"ai fait pour "vulgariser"mon probl`eme de recherche.

1 Probl`eme initial

J"ai commenc´e par travailler sur le probl`eme suivant, dont une r´esolution compl`ete est ´ecrite

dans [1]. Cependant, j"ai r´efl´echie seule `a ce probl`eme avant de lire l"article. Dans cette partie, j"ai

volontairement ´ecrit les ´etapes et r´esultats de ma r´eflexion sans chercher `a plus les structurer. Cela

sera utile pour imaginer comment pr´esenter le probl`eme au public. Cette partie du stage m"a pris

environ une semaine.

1.1 Enonc´e

Un peu de formalisme pour savoir de quoi nous parlons. Definition 1.SoitG∞la grille infinie, le graphe dont les sommets sont les points du plan `a

coordonn´ees enti`eres et tels que deux sommets sont voisins si leur distance arithm´etique est1.

Ungraphe de grilleest un sous graphe fini deG∞induit par les noeuds : il est enti`erement

d´ecrit par l"ensemble de ses sommets. Un graphe de grille sera rep´esent´e par un quadrillage : un

sommet correspond `a une case, deux cases sont voisines si elles ont un cˆot´e commun. Lagrille rectangulaire de taillen?mest le graphe de grille dont les sommetsu= (ux,uy) v´erifient1?ux?m,1?uy?n. Nous nous posons alors le probl`eme suivant, not´eG(A,B) : Probl`eme 1.Dans un graphe de grille G, on se donne deux sommetsAetB. Existe-t-il un

chemin hamiltonien dont les extr´emit´es sont ces deux points?Fig.1 - Peut-on relier A `a B en passant une fois par toutes les cases?

Le th´eor`eme suivant a ´ete d´emontr´e par Itai, Papadimitriou et Swarcfiter dans [1] et donne un

int´erˆet au probl`eme. 3

Parreau Aline Stage de License 2006

Th´eor`eme 1.Trouver un chemin hamiltonien dans un graphe de grille est NP-complet. On en d´eduit le corollaire suivant qui concerne plus pr´ecis´ement notre probl`eme : Corollaire 1.Savoir si G(A,B) a une solution est NP-complet D´emonstration.A partir d"un graphe de grille comportant N cases, on le copieN(N-1)2 fois et on

choisit (A,B) tous les couples de cases possibles. Si on sait r´esoudre G(A,B), on sait trouver un

chemin hamiltonien dans le graphe de grille.Dans la suite, on se retreint aux grilles rectangulaires et on cherche une condition n´ecessaire et

suffisante pour que G(A,B) ait une solution. 1.2

´Elements de r´esolution

1.2.1 Simplification du probl`eme

Suivant les conseils de mon maˆıtre de stage, j"ai commenc´e par r´esoudre un probl`eme plus

simple, not´e G(A) : Probl`eme 2.Dans une grille G, on se fixe un sommet A. Existe-t-il un chemin hamiltonien partant de A? Lemme 1.Si la grille est paire (nombre pair de cases), G(A) a toujours une solution. D´emonstration.On peut toujours construire un circuit hamiltonien dans une grille paire (voir la

figure 2). En coupant le cycle au niveau de A, on a un chemin hamiltonien partant de A.Fig.2 - Circuit hamiltonien dans une grille paire

Pour les grilles impaires (nombre impair de cases), certains sommets ne "marchent"pas. Apr`es

quelques essais, en notant quels sommets ne "marchent"pas, une coloration de la grille apparaˆıt

qui correspond `a un damier. Dor´enavant, les grilles seront colori´ees (Fig. 3) : les sommets "pairs"

(i.e. dont la somme des coordon´ees est pair) en noirs, les sommets "impairs"en blanc.Fig.3 - Coloration d"une grille

Un sommet noir n"a que des voisins blancs, et un sommet blanc n"a que des voisins noirs. Le graphe est donc biparti et lorsqu"on se prom`ene dans le graphe, on alterne les couleurs. On en d´eduit le lemme suivant : Lemme 2.Si la grille est impaire, G(A) a une solution si et seulement si A est de la couleur dominante. 4

Parreau Aline Stage de License 2006

D´emonstration.Un chemin dans une grille commen¸cant par la couleurXcomporte une case de plus de couleurXou le mˆeme nombre de cases de chaque couleur. Dans une grille impaire, il y a une case de plus dans une des couleurs, la couleur dominante. Un chemin hamiltonien a donc une case de la couleur dominante de plus, il commence et finit donc obligatoirement par la couleur dominante : il faut donc que A soit de la couleur dominante. On montre que cette condition est suffisante en raisonnant par induction sur la taille de la

grille : le r´esultat est vrai pour la grille 3×3 (les deux cas sont pr´esent´es en figure 4).(a)(b)

Fig.4 - Chemin hamiltonien dans une grille 3×3

On passe d"une grille de taille (2l+1)×(2k+1) (l?1,k >1) a une grille de taille (2l+1)×(2k-1) en enlevant un bande de largeur 2 et de longueur 2l+ 1 o`u le pointAn"est pas (c"est possible car

la grille est de largeur au moins 5). On r´esout la petite grille par induction. Un des coins du cˆot´e

frontalier n"est pasA. Pour compl´eter le chemin, on distingue alors les cas suivant si ce coin est

ou non une extr´emit´e du chemin comme illustr´e en figure 5.(a) ?(b) ?(c) (d) ?(e) (f) Fig.5 - Induction pour trouver un chemin hamiltonien sur une grille impaire

1.2.2 Retour au probl`eme initial

Chacun des deux sommets est le d´epart d"un chemin hamiltonien, ils doivent donc tous deux

v´erifier les conditions donn´ees pr´ecedement. Ainsi, pour des grilles impaires, il faut que les deux

sommets soient de la couleur dominante. Pour les grilles paires, il faut que les deux sommets soient

de couleur diff´erente car il y autant de cases de chaque couleur dans une grille paire, donc dans

un chemin hamiltonien dans une grille paire. Ainsi, un chemin hamiltonien qui commence par une couleur finit par l"autre et les deux etr´emit´es sont de couleur diff´erente. Cela nous donne une condition n´ecessaire ditecondition de coloration. Est-elle suffisante? Il y a en fait quelques configurations v´erifiant la condition de coloration mais n"ayant pas de solution, ce sont les casimpossiblesouinterdits. On rencontre les premi`eres assez vite pour des

petites grilles : il faut que la grille reste connexe quand on enl`eve un ou les deux sommets choisis

(le chemin est encore connexe quand on enl`eve ses extr´emit´es). Ainsi, si la grille est de dimension

5

Parreau Aline Stage de License 2006

1 (m= 1 oun= 1), il faut que les deux sommets soient dans des coins (Fig. 6(a)). Si la grille

contient deux lignes, il ne faut pas que les deux sommets soient sur la mˆeme colonne (sauf si ce sont des coins) (Fig. 6(b)). L"autre cas impossible (le cas F3 de [1]) est le suivant :n= 3,mest pair,Aest sur une colonne avantBet n"est pas de la mˆeme couleur que les coins gauches, et : - soitAest sur la ligne du milieu etBsur une colonne diff´erente (Fig. 6(c)). - soitAest au bord etBn"est pas sur la colonne d"apr`es (Fig. 6(d)).(a)(b)(c)(d)

Fig.6 - Cas impossibles pour le probl`eme initial

La figure 7 montre pourquoi cette situation est impossible (dans le cas o`u A n"est pas sur la

ligne du milieu). Le dessin est une coupe de la grille : les coins de gauche de la grille sont noirs.(a)

Pour remplir la

partie gauche(b) ?(c) Impossible (couleurs `a gauche)(d)

Pour remplir la

partie gauche(e) ?(f) Impossible (couleurs `a gauche)(g) ?(h)

Pour pouvoir

remplir la partie gauche (impaire) on doit ressortir par b(i) la case au dessus deAn"a que deux voisins possibles(j) ?(k) B doit ˆetre en c ou c" : impossible Fig.7 - Preuve qu"une configuration est impossible

On distingue les cas suivant la position de l"arˆete issue deA. Chaque position entraˆıne des

6

Parreau Aline Stage de License 2006

arˆetes obligatoires : soit parce qu"il faut remplir une partie o`u il n"y a pas d"extr´emit´es : il faut

donc entrer et sortir de cette partie, soit `a cause des couleurs : si on entre dans une partie impaire

par une case noire on doit ressortir par une case noire, soit parce qu"il y a un sommet qui n"a plus

que deux voisins possibles. On arrive ensuite `a des situations impossibles, g´en´eralement ´a cause

des couleurs : par exemple, on doit avoir un chemin dans une grille impaire entre une case noire et une case blanche. Toutes les configurations qui v´erifient les conditions de coloration et qui ne correspondent pas

`a l"un des cas ci-dessus sont r´esolubles. On le montre par induction en utilisant des m´ethodes

similaires `a celles de la figure 5 (elles seront d´ecrites plus pr´ecis´ement ensuite) : on r´eduit les

probl`emes en enlevant des "bandes"de largeur 2 vide et en prolongeant le chemin. Quand on ne peut enlever de telles bandes, les deux points sont alors "proches"des bords et on peut couper la

grille en deux pour avoir un point de chaque cˆot´e. On r´esoud alors chacune des nouvelles grilles en

mettant des nouveaux points au niveau de la fronti`ere. (Voir [1] pour une r´esolution compl`ete).

1.3 Vers d"autres dimensions...

Une premi`ere extension du probl`eme est d"utiliser des grilles de dimension plus grande. Nous introduisons donc des d´efinitions similaires aux pr´ec´edentes : Definition 2.Lagrille infineGd∞en dimensiondest le graphe dont les sommets sont les sommets deZdet deux sommets sont voisins s"ils sont `a une distance arithm´etique1. Ungraphe de grille de dimensiondfinieet un sous graphe deGd∞induit par les noeuds : elle est enti`erement d´ecrite par l"ensemble de ses sommets. Unbloc de dimensiondde taillen1×...×ndest un graphe de grille de dimensiondfinie isomorphe au graphe de grille dont les sommetsxv´erifient :?i?[1;d],1?xi?nd

Et on se pose la mˆeme question :

Probl`eme 3.Dans un bloc de dimensiond, on se donne deux sommets. Existe-t-il un chemin hamiltonien dont les extr´emit´es sont ces deux points? On peut colorier de la mˆeme mani`ere les blocs et on garde la mˆeme condition de coloration. Le th´eor`eme suivant r´epond `a cette question. Th´eor`eme 2.SoitGun bloc de dimensiond?3, de taillen1×...×nd, avec?i?[1;d],ni>1.

Soit deux sommetsAetBde ce bloc, alors :

- il y a un chemin hamiltonien entreAetBsi et seulement si les deux points v´erifient la condition de coloration, - si le bloc est pair, pour toute arˆetepqdu bloc, il existe un circuit hamiltonien contenant l"arˆetepq Remarque.Le deuxi`eme r´esultat se d´eduit directement du premier en prenantA=petB=q, mais il sera utile pour la preuve du th´eor`eme. D´emonstration.On raisonne par r´ecurrence sur la taille et la dimension du bloc. Etape 1 : Bloc de dimension 3 de taille2×n×m La figure 8(a) fixe les notations. On distingue les cas suivant la position des deux points. Si les deux points sont dans des coins (ils n"ont que 3 voisins) et queA1?=B1, ils ne sont pas dans le mˆeme plann×m, on construit facilement un chemin (on remplit d"abord le premier plan

m×n, puis le deuxi`eme, voir la figure 8(b). C"est possible car les grˆace aux couleurs : on change

de couleur quand on change de plan) SiA1=B1, on coupe un plan pair dans lequel il y aAmais pasBet on "d´eplace"Adans le bloc restant, pour utiliser le cas pr´ec´edent. Sinon, par exemple,An"est pas dans un coin, on "essaye"de le mettre dans un coin.A2?=

1etA2?=mouA3?= 1etA3?=n. Supposons queA2?= 1etA2?=m, alorsm >2, et on enl`eve un

cˆot´e vide (Bne peut ˆetre dans les deux cˆot´es selone2de taille 2×n. Il y a un circuit hamiltonien

dans le cˆot´e enlev´e (grille paire), un chemin hamiltonien dans le bloc entreAetB(par induction)

(ce bloc est bien de dimension 3, les couleurs sont bonnes ), on recolle dans un coin libre (voir la figure 8(c)). 7

Parreau Aline Stage de License 2006

(a) Notations(b)(c)

Fig.8 - Etape 1

Etape 2 : Les autres blocs pairs

On coupe un bloc de dimensiond-1 suivantej, tel que le bloc soit pair (soitn1×...×ndn jpair). S"il n"y a pas de point dans la tranche, par induction, il y a un chemin entreAetBdans le

bloc restant (mˆeme parit´e, mˆeme couleur et dimension>2). Dans un coin libre sur le cˆot´e coup´e,

il y a une arˆetepqdans le chemin perpendiculaire `a la direction deej(il y a deux arˆetes, et une

seule peut ˆetre dans la directionej. On projette cette arˆete dans la tranche en une arˆetep?q?, et on

construit un circuit hamiltonien dans la tranche qui contient l"arˆetep?q?. On enl`eve les deux arˆetes

pqetp?q?et on rajoutte les arˆetespp?etqq?. (Fig. 9(a)) S"il y a un seul sommetAdans la tranche, il y a un coinplibre dans cette tranche dont la couleur est compatible avec celle deA(la tranche est pair), on r´ealise un chemin entreAetp (si d=3, la tranche est de dimension 2, mais avec un coin on peut toujours faire un chemin si les couleurs sont compatibles). On projettep?sur la premi`ere tranche du bloc restant.p?est de la mˆeme couleur queA, il y a donc un chemin entrep?etB, on rajoutte l"arˆetepp?pour avoir le chemin entreAetB. (Fig. 9(b))

S"il y a deux points dans la tranche, on coupe de l"autre cˆot´e : il n"y a pas de points.(a) Pas de point dans la tranche(b) Un point dans la tranche

Fig.9 - En dimensiond...

Etape 3 : Les blocs impairs

En dimension 2, la condition de coloration est suffisante pour les grilles impaires : on s"y ram`ene donc. Dans la directione1, on enl`eve des blocs de dimensiondde taille 2×n2×...×nd. S"il n"y a

pas de points, on enl`eve le bloc en recollant dans un coin libre (de la mˆeme mani`ere qu"en figure

9(a)). S"il y a un point, on fait un chemin entre ce point et un point de la couleur minoritairep

qui est sur le cˆot´e frontalier. On projettep?sur le bloc restant et on recolle les chemins (comme

dans la figure 9(b)). S"il y a deux sommets, on coupe de l"autre cˆot´e.8

Parreau Aline Stage de License 2006

2 Quand le chemin devient un arbre...

Nous ´etendons ici le probl`eme d"une autre mani`ere en rajoutant des points et en transformant

les chemins en arbres. Cette extension a constitu´e la plus grande partie de mes recherches (environ

3 semaines du stage).

Probl`eme 4.Si maintenant on se fixe non plus deux sommets dans la grille maisksommets,

existe-t-il un arbre recouvrant la grille dont les feuilles sont exactement ces sommets?(a) Donn´ees du probl`eme

(b) Mauvaise solution(c) Bonne solution

Fig.10 - Extension du probl`eme

La figure 10(a) montre comment le probl`eme se pr´esente. La figure 10(b) n"est pas une solution :

on a bien un arbre recouvrant, mais un des sommets choisis n"est pas une feuille de l"arbre et au

contraire, une feuille de l"arbre n"est pas un sommet choisi. La figure 10(c) est une bonne solution.

2.1 Historique des recherches

J"ai d"abord cherche´e et r´esolu le cas de trois sommets. La d´emonstration a ´et´e longue et

laborieuse, car je voulais adopter la mˆeme m´ethode que pour deux sommets. Aussi, je pr´esente

seulement les grandes lignes de ma d´emonstration. J"ai cependant r´edig´e la d´emonstration compl`ete.

Ensuite, j"ai choisi de ne pas r´esoudre le cas de 4 points : une d´emonstration similaire aurait

´et´e encore plus lourde et je conjecturais que l"on pouvait r´esoudre le probl`eme pour un nombre

quelquonque de sommets. J"ai donc cherch´e des r´esultats g´en´eraux. J"ai trouv´e des conditions

n´ecessaires facilement exprimables. J"ai aussi r´esolu le probl`eme dans un cas particulier, mais je

n"ai pas r´eussi ´a r´esoudre le probl`eme g´en´eral. Parall`element, nous avons montr´e que le probl`eme

pour un graphe de grille quelconque ´etait aussi NP-complet avec plus de points. Nous pensons qu"il y a une d´emonstration plus astucieuse pour r´esoudre le probl`eme avec 3

sommets qui utilise plus le r´esultat avec deux sommets et dont le principe permettrait de r´esoudre

le probl`eme g´en´eral. Dans un soucis de clart´e, la structure de ce qui suit n"est pas celle des recherches : je montre

d"abord la NP-compl´etude du probl`eme, ensuite les remarques et propri´et´es g´en´erales sur le probl`eme.

Enfin, je traite le cas des grilles rectangulaires avec 3 sommets puisksommets, et je donne quelques id´ees que nous avons eues mais que nous n"avons pas eues le temps d"approfondir.

2.2 NP-compl´etude

On montre par induction le th´eor`eme :

Th´eor`eme 3.Le probl`eme est NP-complet pour un graphe de grille fini aveck?2sommets choisis au d´epart. 9

Parreau Aline Stage de License 2006

D´emonstration.Les probl`emes sont dans NP.

On raisonne par induction sur le nombrekde sommets choisis. Le r´esultat pourk= 2 a ´et´e vu en premi`ere partie. Pourk >2, on prend une instance du probl`eme aveck-1 sommets : un graphe de grilleG0 fini etk-1 sommets de ce graphe. On va rajouter un sommet. Soit une arˆeteuvsur le bord du graphe de grille, on lui rajoute le motif de la figure 11(a) qui comporte un nouveau sommetX, on note ce nouveau probl`emeG1.(a)(b)

Fig.11 - NP-compl´etude

Lemme 3.G1a une solution si et seulement siG0a une solution contenant l"arˆeteuv D´emonstration.S"il y a une solution au probl`emeG1,betc(voir le dessin pour les notations)

ne sont pas des sommets choisis, ils sont de degr´e 2 dans l"arbre, les arˆetesacetabdoivent donc

ˆetre dans l"arbre, ainsi queaX,aest donc de degr´e 3, c"est un noeud de l"arbre. On obtient une

solution au probl`eme initial contenant l"arˆeteuven enlevant le motif et en rajouttant l"arˆeteuv

(on a toujours un arbre, qui comportek-1 feuilles, c"est donc une solution). Inversement, une

solution au probl`eme initial contenant l"arˆeteuvdonne une solution au probl`emeG1en rempla¸cant

uvpar l"arbre de la figure 11(b).Soit ?ux=min{ax,a?G} u y=max{by,bx=ux,b?G},uest de degr´e 1 ou 2 etuvest une arˆete du bord du graphe. On distingue alors les cas : uest de degr´e 1 ou n"est pas un sommet choisi :Alors, on prendvun de ses voisins, l"arˆete uvest obligatoirement pr´esente dans une solution. On rajoute le motif et par le lemme 3 les deux probl`emes sont ´equivalents. uest de degr´e 2 et c"est un sommet choisi :Soientvetv?ses deux voisins. On copie le

probl`eme : soientG1etG?1les probl`emes o`u l"on rajoute respectivement le motif `a l"arˆeteuvet `a

l"arˆeteuv?. S"il y a une solution `aG0,uest de degr´e 1 dans l"arbre solution, son voisin estvouv?,

et l"arbre contient l"arˆeteuvou l"arˆeteuv?. Il y a donc une solution contenant l"arˆeteuvou une

solution contenant l"arˆeteuv?. Donc, d"apr`es le lemme 3,G1ouG?1a une solution. R´eciproquement, siG1ouG?1a une solution,G0a une solution. On teste doncG1, siG1n"a pas de solution, on testeG?1. La r´eduction est bien polynomiale.2.3 Conditions N´ecessaires Les conditions suivantes sont valables pour des graphes de grilles et un nombre de sommets choisis quelconques. 10

Parreau Aline Stage de License 2006

ColorationOn g´en´eralise les conditions de coloration : Definition 3.Notons?la diff´erence entre le nombre de cases de couleur majoritaire et les autres. Un probl`eme estcompatible au niveau des couleurss"il v´erifie la condition suivante. : - si? >0, il doit y avoir au moins?+1cases de la couleur majoritaire parmi les cases choisies ?+ 1cases noires parmi les cases choisies; - si?= 0, il doit y avoir une case de chaque couleur parmi les cases choisies. Lemme 4.Si un probl`eme a une solution, il est compatible au niveau des couleurs. D´emonstration.On raisonne par induction sur le nombrekde cases choisies et la taille du graphe de grille : k= 2, graphe de grille de taille quelconque. On consid`ere une solution au probl`eme. Si les

deux cases choisies sont de couleur diff´erente, le chemin hamiltonien qui les relie, donc le graphe

quotesdbs_dbs13.pdfusesText_19

[PDF] de l'année 1789 ? l'exécution du roi cm1

[PDF] graphe d'ordonnancement

[PDF] sujet algorithme bts sio corrigé

[PDF] calcul matrice booléenne

[PDF] calcul matriciel bts

[PDF] prise de note rapide tableau abréviations

[PDF] sauzay programme

[PDF] programme voltaire

[PDF] un petit paragraphe sur l'environnement

[PDF] exemple de texte argumentatif sur l'environnement

[PDF] texte sur l'environnement

[PDF] texte argumentatif sur l'environnement 4am

[PDF] protection de l'environnement définition

[PDF] graphe probabiliste calculatrice

[PDF] graphe étiqueté