Son rapport
Contents
1. Rg est exprimable dans MS Re u v ssi Je Ri u e Ri v e De plus il existe des propri t s sur les graphes exprimables dans M S2 mais pas dans MS par exemple l appartenance Egpar Logique MSO Les formules de la logique monadique du second ordre se d finissent ainsi Les propositions atomiques sont l application de pr dicats Pour et w deux formules o et V w sont des formules Pour une formule x et X des variables du premier et second ordre d notant donc des l ments ou des parties de U Jx o et 3X 6 sont des formules Classes de graphes associ es Une formule de la logique monadique du second ordre MS ou M S2 va d finir une classe de graphes C o G S G E o on crit S si la formule est vraie dans la structure S Intuitivement C est l ensemble des graphes v rifiant la propri t 3 2 Largeur arborescente d un graphe La notion de largeur arborescente mesure la ressemblance un arbre d un graphe donn on peut voir un graphe compliqu comme une tr s simple structure d arbre paissie par des ar tes suppl mentaires Il s agit de l paisseur minimale d une d composition en arbre du graphe D composition en arbre Soit G V E un graphe Une d composition en arbre de G est un arbre X i I F o les X sont des parties de G v rifiant T Uier Xi V Vu vEe E GEI uwe X Vi2. des formules de Hintikka de la mani re suivante D he MS Z X h est satisfaisable h Hi X ssi vo MS z X h g est soit non satisfaisable soit quivalente h Premi res propri t s Deux formules de Hintikka distinctes sont incom patibles Yh ho Hi X h ho h A he false Toute formule est disjonction de formules de Hintikka vo MSi a X GI C Hi X V h hel 4 2 D composition de graphes On consid re des graphes k color s chaque sommet se voit attribuer une unique couleur parmi k sur lesquels on d finit plusieurs op rations permet tant de combiner des graphes Notation standard G V E Vi Vk o V est l ensemble des sommets de la 7 couleur et donc o les V forment une partition de V Union disjointe On colle deux graphes c te c te G eG VUV EUE V U V Recoloriage p _ Tous les sommets de couleur i prennent la couleur j pij G V E Vi Vi 0 Vj Vi U Vj ee Vn C Fusion Fusion Tous les sommets de couleur 7 sont fusionn s en un seul qui collecte toutes les ar tes En posant G Fusion G vi un sommet neuf hors de V et en assimilant pour E une ar te un l ment de V V V Vi U vi V vi et Vj i V Vj E E A V U u vi w Vi u v E U vi u Ww Vj v u E Connexion crois e n j Tous les sommets de couleur sont li s t
3. j k I Si j est sur le chemin de 7 k dans T alors X N Xk C X L paisseur d une telle d composition est maxier X 1 La largeur arborescente de G est le minimum des paisseurs de ses d com positions en arbre on remarquera que V est une d composition triviale de G d paisseur V 1 4 Notions abord es dans la d monstration du th o r me Je vais dans cette partie aborder les notions utilis es dans la preuve du th or me principal de l article que j tudie dont le th or me sur les fonctions g n ratrices de la section 2 se d duit Ceci concerne les formules de Hintikka les d compositions de graphes selon certaines op ration structurelles et le th or me de Ferferman Vaught sur les sommes disjointes de structures Je donnerai ensuite les tapes de la d monstration 4 1 Formules de Hintikka Rang de quantification Le rang de quantification d une formule logique est le nombre maximum de quantificateurs imbriqu s qu elle comporte On le d finit formellement ainsi a d signe une formule atomique ie l application d un pr dicat et et w des formules quelconques gr a 0 qr ar qr V Y max qr d ar qgr Ax qr 3X ar 1 On note MS x X l ensemble des formules de MS de rang de quanti fication au plus l dont les variables libres forment les vecteurs 7 et x Formules de Hintikka On d finit les ensembles H Z X
4. Feferman Vaught et Shelah Pour toute formule X MS z Y X il existe un nombre fini de couples de formules de Hintikka hi alz X H z X hoo G X H ij X telles que pour tout graphe G G1 G2 et interpr tation z comme ci dessus G z H e z y X si et seulement si il existe a tel que Gi 21 E hia X et Ga z2 hoali Une preuve de ce th or me vient du lien entre les formules de Hintikka et les jeux d Ehrenfeucht Fraiss les formules d crivent les positions gagnantes de ces jeux 4 4 Etapes pour d montrer le th or me sur les fonctions g n ratrices On exprime la fonction g n ratrice GF G o E est d finissable par W E formule monadique du second ordre de rang de quantification au plus k par gt Il Y E AE CE e E Le mode d emploi est ensuite le suivant Construire l ensemble des formules de Hintikka dont on aura besoin Cette tape ne fait pas appel au graphe mais uniquement Y C est une tape tr s d licate Pour toute formule monadique du second ordre de rang de quantifi cation au plus k d terminer la disjonction de formules de Hintikka quivalente M me commentaire que pr c demment Regarder dans les yeux le graphe on a besoin de sa d composition pour un graphe dont on conna t la largeur arborescente la d compo sition est trouvable honn tement Calculer r cursivement en suivant la d composition
5. tes repr sentent la relation d incidence de G On peut voir ceci comme l ajout d un sommet au milieu de chaque ar te Le plus important est qu avec la seule logique MS sur I G on obtient la puissance de MS sur G Formellement pour toute propri t d finie par une formule M S2 6 il existe une formule MS 4 telle que GHo ssi I G E WV La propri t de largeur arborescente born e est conserv e lors du passage de G I G la largeur est au plus augment e de 1 C est cet endroit qu on peut voir que largeur arborescente et MS font bon m nage quand bien m me les th or mes ne sont valables que pour MS il suffit de travailler sur le graphe d incidence pour pouvoir abaisser notre formule la puissance MS et on le fait sans effet secondaire sur notre hypoth se de largeur ar borescente born e C est je pense un argument permettant de compl ter la partie de la d monstration du gros th or me que j ai comment e on peut m me transposer la fonction de poids vers G de mani re ce que la fonc tion g n ratrice conserve la m me valeur En revanche ceci ne vaut pas pour la largeur de clique notion avec laquelle on doit alors se restreindre aux propri t s d finissables par MS1 ce qui est le revers qu on pouvait attendre de ce crit re plus faible O tout le monde se retrouve On dit d un graphe G V E qu il est k clairsem si E lt k V G est uniform ment k clairsem si tous
6. La derni re tape est polynomiale et on peut l adapter afin de construire un circuit alg brique calculant la fonction g n ratrice Le probl me ainsi restreint est donc bien dans VP Entourloupe Remarquez l admirable fa on dont on a arr t de parler ici du petit chiffre indi ant MS La preuve de l article se place dans le contexte MS et ne s inqui te pas de justifier pr cis ment ce qui permet de passer M S2 Je profiterai de la discussion de la section suivante pour proposer une solution 5 Discussion largeur arborescente largeur de clique L article tudi discute une autre valuation de la complexit d un graphe la largeur de clique qui n est pas sans liens avec la largeur arborescente Je vais dans cette derni re section pr senter cette nouvelle notion et la comparer avec la premi re avant de revenir au point flou de la section pr c dente 5 1 Largeur de clique D finition La classe des graphes de largeur de clique au plus k s obtient en utilisant les op rations pr c demment d finies d union disjointe de reco loriage et de connexion crois e partir de sommets isol s le tout dans un contexte o k couleurs sont utilis es On ne conna t pas comme pour la largeur arborescente d autre description de ces classes pour k gal 3 ou plus mais on peut quand m me remarquer que les cliques ont une largeur de clique gale 2 et les arbres 3 En effet donnons cet assemblage d o
7. Probl mes d valuation et d nombrement sur graphes Thibaut BALABONSKI 24 Novembre 2006 1 Introduction J tudie ici l article 2 C est un document dense qui fourmille de r sul tats de types tr s diff rents sur les graphes je centrerai ici mon d veloppe ment sur les aspects concernant la complexit alg brique je partirai de ses applications en prise directe avec le cours pour explorer la th orie g n rale pr sent e par les auteurs en explicitant certains des points qui font appel a des notions et r f rences exterieures de la justification de certaines petites propri t s folkloriques la d monstration du r sultat principal Les autres applications et discussions de l article seront pr sent es bri vement titre d annexes dans une derni re partie 2 Fonctions g n ratrices On va introduire une forme g n rale de fonction d nombrant les oc curences d une propri t donn e comme un chemin hamiltonien dans un graphe ou la somme des poids de ces occurences pour un graphe ar tes pond r es Une fonction g n ratrice est construite partir de plusieurs param tres Un graphe G V E n sommets Une classe de graphes close par isomorphisme On d finit alors ainsi la fonction g n ratrice associ e ces param tres d argument w GF G w S O E V E E et E C E o Q E feep w e pour tout sous ensemble E de E Q exten
8. arborescente born e alors la famille GF G est dans VP 3 Notions Cette section est consacr e la d finition des notions indispensables la compr hension du th or me la d finition de classes de graphes par des for mules logiques du second ordre et l valuation de complexit d un graphe qu est la largeur arborescente 3 1 Propri t s de graphes expressibles en logique du second ordre On s int ressera plus particuli rement la logique monadique du second ordre les variables du second ordre des relations dans le cas g n ral sont limit es l arit 1 on les assimile des ensembles dont on va voir deux variantes sur les graphes Structures On consid re un graphe G V E comme un structure rela tionnelle S G sur un univers U Logique MS U V muni d une relation Rg pour les ar tes R u v ssi u v E Logique MS U VUE muni d une relation typ e d incidence R R u e ssi 3v e u v dans le cas de graphes orient s on utilise deux relations d incidence une source et une objectif On a en plus de cela dans chaque cas un nombre fini de pr dicats unaires quivalents autant de sous ensembles de U qu on peut comprendre aussi comme des constantes du second ordre et de constantes de U La premi re remarque faire sur ces deux logiques est que la seconde est strictement plus expressive que la premi re En effet
9. ident pour la largeur de clique notamment R f rences 1 B Courcelle and J A Makowsky Fusion on relational structures and the verification of monadic second order properties Mathematical Structures in Computer Science 2002 2 B Courcelle J A Makowsky and U Rotics On the fixed paramater complexity of graph enumeration problems definable in monadic second order logic Discrete Applied Mathematics 108 23 52 2001 3 J A Makowsky and K Meer Polynomials of bounded tree width 10
10. ous les sommets de couleur j On pose toujours G n _ G et on a la d finition formelle V V Vi VJ V F EU u v u V et v Vj Largeurs Les auteurs ont prouv dans un article ult rieur 1 que les graphes de largeur arborescente au plus k taient la cl ture par union dis jointe recoloriage et fusion des graphes k 1 color s au plus k 1 sommets ce qui rendra mon d voleppement plus direct La cl ture des graphes k color s un sommet par union disjointe recolo riage et connexion crois e donne quant elle la classe des graphes de largeur de clique au plus k propri t qu on discutera dans la derni re section 4 3 Th or me de Feferman Vaught Ce th or me concerne les unions disjointes de graphes On consid re donc dans cette partie un graphe G G1 G2 sa structure associ e S G d univers U on tend la notation aux indices 1 et 2 et on parlera de MS E X plut t que de MS x X on fera correspondre dans les in terpr tations G1 et G2 Interpr tation On appelle interpr tation une fonction des variables du premier ordre dans U Soit z une interpr tation envoyant les x dans Uy et les y dans U2 On lui associe les interpr tations z1 et z2 d finies comme suit mi Xj z X 0 V xs 2 x et y z y Ainsi z est identique z except qu elle restreint l interpr tation des va riables du second ordre G Th ro me
11. p rations imm diatement exten sible pour construire une clique a 4 l ments On note i v le sommet isol de couleur i p21 m2 2 y p21 m2 2 x S pe 1 m 2 2 w 1 v 5 2 Comparaison des largeurs Largeur arborescente et largeur de clique peuvent se d finir de fa on analogue on ne s tonnera donc pas de trouver des relations entre les deux Comparaison brute On vient de voir que toute clique avait une largeur de clique au plus 2 Mais les cliques ont la largeur arborescente maximale parmi tous les graphes largeur de n pour une clique n 1 sommets Ainsi une classe de graphes de largeur de clique born e n est pas n cessairement de largeur arborescente born e En revanche un graphe de largeur arborescente k a une largeur de clique d au plus O 4 Une classe de largeur arborescente born e a une largeur de clique born e La morale de cette histoire est que la propri t de largeur de clique bor n e est plus g n rale s applique de plus nombreuses classes de graphes Appliquer ce nouveau crit re les m mes th or mes pourrait donc tre in t ressant si cela est possible Propri t s MS et MS2 Mais l une des deux classes tant plus large que l autre on peut s attendre ce que les probl mes auxquels elle s applique soient moins nombreux On d finit le graphe d incidence 7 G d un graphe G comme le graphe biparti dont les sommets sont les sommets et ar tes de G et dont les ar
12. ses sous graphes sont k clairsem s On note US k la classe des graphes k clairsem s A l int rieur de cette classe les puissances de M S4 et de M So deviennent identiques de m me qu une classe de graphe est de largeur de clique born e si et seulement si elle est de largeur arborescente born e 6 En guise de conclusion J ai dans ce rapport pr sent l article 2 en partant de ses implications en complexit alg brique Ce qu on a obtenu la fin est un couple de notions valuant la complexit d un graphe la largeur arborescente et la largeur de clique La seconde est plus g n rale car c est une hypoth se plus faible mais est galement plus d licate d emploi Notamment elle ne s articule naturel lement qu avec la logique MS qui ne quantifie que sur les sommets d un graphe alors que l autre s entend fort bien la logique MS qui elle auto rise la quantification sur les ar tes comme sur les sommets et est strictement plus expressive Cependant une fois cette distinction faite les r sultats relatifs aux deux notions se rejoignent les d nombrements souvent P difficiles et V NP complets li s des propri t s M S2 sur une classe de graphes de largeur arborescente born e ou des propri t s M S4 sur une classe de graphes de largeur de clique born e sont polynomiaux une fois qu une d composition t moignant de la largeur born e a t trouv e ce qui n est pas forc ment v
13. sion de w aux ensembles d ar tes qu on notera encore w par la suite w peut tre interpr t de plusieurs fa ons C est avant tout une fonction de pond ration de E dans un corps K Mais aussi Un sous graphe pond r de G un poids 0 quivaut une ar te in existante Une matrice carr e de dimension n x n matrice d adjacence Un ensemble de n ind termin es GF G E devient alors un poly n me plusieurs ind termin es C est sur ce dernier point de vue que nous nous arr terons qui permet de se pencher sur la complexit alg brique des fonctions g n ratrices Exemples Commen ons par citer quelques familles de fonctions VN P compl tes Kn d note le graphe complet n sommets GF Kn Ecpar O Ecpar est la classe des couplages parfaits permanent GF K Echam O Echam est la classe des n cycles hamiltonien GF Kn Ectique O Ectique est la classe des cliques GF K FA F o FA F est la classe des graphes dont toutes les composantes connexes sont isomorphes F ie l ensemble des unions disjointes de graphes isomorphes F La suite va consister en la restriction des param tres pour l obtention de fonctions g n ratrices dans V P On vise plus particuli rement le th or me suivant dont on explicitera le sens dans la section suivante Si E est d finissable dans la logique MS3 et si Gn est une famille de graphes de taille n et de largeur
Download Pdf Manuals
Related Search