La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Sujets
Informations
Publié par | Hermès - Editions Lavoisier |
Date de parution | 08 juillet 2010 |
Nombre de lectures | 18 |
EAN13 | 9782746241367 |
Langue | Français |
Poids de l'ouvrage | 12 Mo |
Informations légales : prix de location à la page 0,1200€. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.
Extrait
Partitionnement de graphe
© LAVOISIER, 2010
LAVOISIER
11, rue Lavoisier
75008 Paris
www.hermes-science.com
www.lavoisier.fr
ISBN 978-2-7462-3005-7
Le Code de la propriété intellectuelle n’autorisant, aux termes de l’article L. 122-5, d’une
part, que les "copies ou reproductions strictement réservées à l’usage privé du copiste et non
destinées à une utilisation collective" et, d’autre part, que les analyses et les courtes citations
dans un but d’exemple et d’illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l’auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce
soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du
Code de la propriété intellectuelle.
Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins
d’identification et sont des marques de leurs détenteurs respectifs.
Printed and bound in England by Antony Rowe Ltd, Chippenham, September 2010.
Partitionnement
de graphe
optimisation et applications
sous la direction de
Charles-Edmond Bichot
Patrick Siarry
Il a été tiré de cet ouvrage
35 exemplaires hors commerce réservés
aux membres du comité scientifique,
aux auteurs et à l’éditeur
numérotés de 1 à 35
Partitionnement de graphe
sous la direction de Charles-Edmond Bichot et Patrick Siarry
fait partie de la série INFORMATIQUE ET SYSTEMES D’INFORMATION
dirigée par Jean-Charles Pomerol
Directeur de collection Francis Sourd
Traités IC2, sous la direction scientifique de Bernard Dubuisson
IC2 – constitué par un ensemble de huit traités – répond au besoin de
disposer d’une somme complète des connaissances et des méthodes
nécessaires à la maîtrise des systèmes technologiques.
Conçu volontairement dans un esprit d’échange disciplinaire, IC2
représente l’état de l’art dans les domaines suivants retenus par le comité
scientifique :
Cognition et traitement de l’information
Informatique et systèmes d’information
Ingénierie pour la santé
Management et gestion des STIC
Réseaux et télécoms
Signal et Image
Systèmes automatisés
Technologies et développement durable
Chaque ouvrage décrit aussi bien les aspects fondamentaux
qu’expérimentaux. Une classification des différents articles contenus
dans chacun, une bibliographie et un index détaillé orientent le lecteur
vers ses points d’intérêt immédiats : celui-ci dispose ainsi d’un guide
pour ses réflexions ou pour ses choix.
Les savoirs, théories et méthodes rassemblés dans chaque ouvrage ont
été choisis pour leur pertinence dans l’avancée des connaissances ou pour
la qualité des résultats obtenus dans le cas d’expérimentations réelles.
Liste des auteurs
Jean-Baptiste ANGELELLI Jean-Loup GUILLAUME
IML LIP6
Aix-Marseille Universités Université Pierre et Marie Curie
Marseille Paris
Thomas AYNAUD Laura GRIGORI
LIP6 INRIA Saclay-Ile de France
Université Pierre et Marie Curie LRI
Paris Université Paris-Sud 11
Orsay
Charles-Edmond BICHOT
LIRIS Renaud LAMBIOTTE
Ecole centrale de Lyon Institute for Mathematical Sciences
Université de Lyon Imperial College London
Angleterre
Vincent BLONDEL
Department of Mathematical Sid LAMROUS
Engineering SET
Université catholique de Louvain UTBM
Belgique Belfort-Montbéliard
Alexandre CAMINADA Laurent NAJMAN
SET LIGM
UTBM ESIEE
Belfort-Montbéliard Noisy le Grand
HEVALIER AKIB Cédric C Amir N
Sandia National Laboratories LiSSi
Albuquerque Université Paris-Est Créteil
New Mexico Créteil
Etats-Unis
Mustapha OUGHDI
URAND Nicolas D SET
POM UTBM
DSNA/DTI/R&D Belfort-Montbéliard
Toulouse
François PELLEGRINI
Alain GUÉNOCHE INRIA
IML Bordeaux Sud-Ouest - LaBRI
CNRS Institut polytechnique de Bordeaux
Marseille Talence Laurence REBOUL Hugues TALBOT
Laboratoir de Mathématiques et LIGM
Applications ESIEE
Université de Poitiers Noisy le Grand
Poitiers
Patrick SIARRY
LiSSi
Université Paris-Est Créteil
Créteil
Tabledesmatières
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Charles-EdmondBICHOT, Patrick SIARRY
Chapitre1.Introductiongénéraleaupartitionnementdegraphe . . . . . . 23
Charles-EdmondBICHOT
1.1. Lepartitionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.2. Notionsmathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.3. Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4. Descriptionformelleduproblèmedupartitionnementdegraphe . . . . 31
1.5. Fonctionsobjectifspourlepartitionnementdegraphe . . . . . . . . . . 33
1.6. Lepartitionnementcontraint . . . . . . . . . . . . . . . . . . . . . . . . 35
1.7. Lepartitionnementnoncontraint . . . . . . . . . . . . . . . . . . . . . . 37
1.8. Différencesentrepartitionnementcontraintetnoncontraint . . . . . . 39
1.9. Delabissectionauk-partitionnement:labissectionrécursive . . . . . 39
1.9.1. Créerunepartitionavecpournombredepartieunepuissancede2 40
1.9.2. Créerunek-partitionenutilisantlabalancedepartitionnement . 42
1.10. NP-difficultédesproblèmesdepartitionnement . . . . . . . . . . . . . 42
1.10.1. Lecasdupartitionnementcontraint . . . . . . . . . . . . . . . . 42
1.10.2. Lecasdupartitionnementnoncontraint . . . . . . . . . . . . . . 43
1.10.2.1. NP-difficultédelacoupenormalisée . . . . . . . . . . . . . 43
1.10.2.2. NP-difficultéduratiodecoupe . . . . . . . . . . . . . . . . 44
1.11. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.12. Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
PREMIÈRE PARTIE. APPROCHE POUR LE CALCUL NUMÉRIQUE . . . . . 49
Chapitre2.Laméthodemulti-niveaux . . . . . . . . . . . . . . . . . . . . . . 51
Charles-EdmondBICHOT
2.1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.2. Principesdelaméthodemulti-niveaux . . . . . . . . . . . . . . . . . . 5210 Partitionnementdegraphe
2.3. Contractiondugraphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.3.2. Appariementd’ungraphe . . . . . . . . . . . . . . . . . . . . . . . 56
2.3.3. L’algorithmedecontractiond’Hendrickson-Leland . . . . . . . . 57
2.3.4. Algorithmedecontractiondelapluslourdearête(HEM) . . . . . 57
2.4. Partitionnementdugrapheréduit . . . . . . . . . . . . . . . . . . . . . . 59
2.4.1. Desméthodesdepartitionnementéprouvées . . . . . . . . . . . . 59
2.4.2. Lesméthodesd’expansionderégion . . . . . . . . . . . . . . . . 60
2.4.2.1. Descriptiongénérale. . . . . . . . . . . . . . . . . . . . . . . 60
2.4.2.2. GraphGrowingPartitioningalgorithm(GGP) . . . . . . . . 61
2.4.2.3. GreedyGraphGrowingPartitioningalgorithm(GGGP). . . 62
2.5. Affinageetexpansiondugraphe . . . . . . . . . . . . . . . . . . . . . . 63
2.5.1. Présentationdelaphased’affinageetd’expansiondugraphe . . . 63
2.5.2. L’algorithmedeKernighan-Lin . . . . . . . . . . . . . . . . . . . 64
2.5.2.1. Principegénéral . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.5.2.2. L’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.5.2.3. AméliorationsproposéesparB.KernighanetS.Lin. . . . . 67
2.5.2.4. Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.5.2.5. Partiesdetaillesdifférentes. . . . . . . . . . . . . . . . . . . 68
2.5.2.6. Sommetsdepoidsdifférents . . . . . . . . . . . . . . . . . . 68
2.5.2.7. Autresaméliorationsdel’algorithmedeKernighan-Lin . . . 68
2.5.3. L’implémentationdeFiduccia-Mattheyses . . . . . . . . . . . . . 69
2.5.4. Adaptationauk-partitionnementdirect . . . . . . . . . . . . . . . 71
2.5.5. GlobalKernighan-Linrefinement . . . . . . . . . . . . . . . . . . 71
2.5.6. Algorithmed’affinagedeWalshaw-Cross . . . . . . . . . . . . . . 73
2.6. Laméthodespectrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
2.6.1. Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
2.6.2. Quelquesrésultatsd’analysenumérique. . . . . . . . . . . . . . . 76
2.6.3. TrouverlesvaleurspropresdelamatriceLaplaciennedugraphe . 78
2.6.4. Borneinférieurepourlepartitionnementdegraphecontraint . . . 79
2.6.5. Méthodesspectralespourlepartitionnementcontraint . . . . . . 80
2.6.6. Méthodesspectralespourlepartitionnementnoncontraint . . . . 81
2.6.6.1. Leratiodecoupe . . . . . . . . . . . . . . . . . . . . . . . . 82
2.6.6.2. Lacoupenormalisée . . . . . . . . . . . . . . . . . . . . . . 82
2.6.7. Problèmesetaméliorations . . . . . . . . . . . . . . . . . . . . . . 82
2.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.8. Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Chapitre3.Lepartitionnementd’hypergraphe . . . . . . . . . . . . . . . . 89
Cédric CHEVALIER
3.1. Définitionsetmétriques . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.1.1. Hypergrapheetpartitionnement . . . . . . . . . . . . . . . . . . . 89Tabledesmatières 11
3.1.2. Métriquespourlepartitionnementd’hypergraphe . . . . . . . . . 91
3.2. Relationsentregraphes,hypergraphesetmatrices . . . . . . . . . . . . 91
3.3. Algorithmespourlepartitionnementd’hypergraphe . . . . . . . . . . . 93
3.3.1. Contraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.3.2. Partitionnementinitialetaffinage . . . . . . . . . . . . . . . . . . 96
3.3.3. Affinage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.4. Utilisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.4.1. Intérêtsdupartitionnementd’hypergraphe . . . . .