Utilisateur:SacréHubert/Brouillon
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bipartite dimension » (voir la liste des auteurs).
Dans le domaine mathématique de la théorie des graphes et de l'optimisation combinatoire, la dimension bipartie d'un graphe G = (V, E) est le nombre minimum de sous-graphes bipartis complets nécessaires pour toutes les arêtes de E. Un ensemble de sous-graphes de G bipartis complets est appelé une couverture de G par sous-graphes bipartis complets. La dimension bipartie de G est souvent notée d(G).
Exemple[modifier | modifier le code]
Voici un exemple de couverture sous-graphes bipartis complets:
-
Un graphe biparti
-
... et une couverture par quatre sous-graphes
-
Le sous-graphe biparti complet rouge
-
Le sous-graphe biparti complet bleu
-
Le sous-graphe biparti complet vert
-
Le sous-graphe biparti complet noir
Dimension bipartie[modifier | modifier le code]
La dimension bipartie d'un graphe complet est .
La dimension bipartie d'un graphe couronne à 2n sommets est , où:
La dimension bipartie d'un graphe grille de taille est si est pair et pour deux entiers et , avec ; sinon[2].
La dimension bipartie de certains graphes a déjà été déterminé: par exemple, pour le chemin , ; pour le cycle , [3].
Calculer la dimension bipartie[modifier | modifier le code]
Le calcul de la dimension bipartie d'un graphe G donné est un problème d'optimisation (en). Le problème de décision associé à la dimension bipartie peut être formulé ainsi:
- Entrée: Un graphe et un entier positif .
- Sortie: Oui, si il existe une couverture de G par sous-graphes bipartis complets de cardinal inférieur à
Ce problème est appelé problème GT18 dans le livre de Garey et Johnson[4] sur les problèmes NP-complets, et est une reformulation d'un autre problème sur les familles d'ensembles finis, le problème Set Basis nommé SP7.
Il a été prouvé que le problème GT18 est NP-complet[5], et ce même pour les graphe biparti. Il reste NP-dur si l'on se restreint aux graphes dont la dimension bipartie est au pire en , avec n la taille de l'instance[6].
De plus, si P ≠ NP, ce problème ne peut être approximé finement: même pour les graphes bipartis, pour tout , le ratio d'approximation est borné par [7]. Cependant, on peut montrer grâce à de la kernelisation que ce problème est FPT[8]. Ainsi, pour un graphe biparti à n sommets donné, on peut décider en , avec si sa dimension bipartie est inférieure ou égal à [9].
Applications[modifier | modifier le code]
Le calcul de la dimension biparti d'un graphe peut être utile dans différents contextes. Dans des systèmes informatiques, différents utilisateurs peuvent avoir accès à différentes ressources. Dans un système à Contrôle d'accès à base de rôles, un rôle donne les droits accès à certaines ressources. Un utilisateur peut avoir plusieurs rôles, et doit avoir accès à toutes les ressources liées à chacun de ses rôles. De plus, plueiseurs utilisateurs peuvent avoir le même rôle. Le role mining problem consiste à trouver le nombre minimum de rôles, tels que chaque utilisateur a accès à des ressources spécifiques. L'ensemble des utilisateurs, combiné avec l'ensemble des ressources, forme un graphe biparti dont les arêtes sont les permissions. Tout sous-graphes bipartis complets est un rôle potentiel, et la solution du role mining problem est justement une couverture par sous-graphes bipartis complets minimale[10].
Un scénario similaire se rencontre en sécurité des systèmes d'information, plus précisément en sécurité de télédiffusion. Dans ce cas-là, plusieurs messages doivent être envoyés à certains ensembles de destinataires, via un moyen de communication non sécurisé. Chaque message doit être codé à partir d'une clé connue uniquement des destinataires. Chacun d'entre eux peut avoir plusieurs clés, et chaque clés peut être possédée par plusieurs destinataires. L'optimum key generation problem consiste à trouver un nombre minimal de clé pour que chaque transmissions soit sécurisé. Ce problème peut être modélisé par un graphe biparti, dont la couverture par sous-graphes bipartis complets minimale correspond à une solution du problème[11].
Voir aussi[modifier | modifier le code]
- Liste de problèmes NP-complets
- Couverture par sous-graphes bipartis complets
- Intersection number (graph theory) (en)
Réferences[modifier | modifier le code]
- → N'hésitez pas à publier sur le brouillon un texte inachevé et à le modifier autant que vous le souhaitez.
- → Pour enregistrer vos modifications au brouillon, il est nécessaire de cliquer sur le bouton bleu : « Publier les modifications ». Il n'y a pas d'enregistrement automatique.
Si votre but est de publier un nouvel article, votre brouillon doit respecter les points suivants :
- Respectez le droit d'auteur en créant un texte spécialement pour Wikipédia en français (pas de copier-coller venu d'ailleurs).
- Indiquez les éléments démontrant la notoriété du sujet (aide).
- Liez chaque fait présenté à une source de qualité (quelles sources – comment les insérer).
- Utilisez un ton neutre, qui ne soit ni orienté ni publicitaire (aide).
- Veillez également à structurer votre article, de manière à ce qu'il soit conforme aux autres pages de l'encyclopédie (structurer – mettre en page).
- → Si ces points sont respectés, pour transformer votre brouillon en article, utilisez le bouton « publier le brouillon » en haut à droite. Votre brouillon sera alors transféré dans l'espace encyclopédique.
- « MR: Matches for: MR=657202 », sur mathscinet.ams.org (consulté le )
- (en) Krystal Guo, Tony Huynh et Marco Macchia, « The Biclique Covering Number of Grids », The Electronic Journal of Combinatorics, , P4.27–P4.27 (ISSN 1077-8926, DOI 10.37236/8316, lire en ligne, consulté le )
- (en) « Bipartite dimensions and bipartite degrees of graphs », Discrete Mathematics, vol. 160, nos 1-3, , p. 127–148 (ISSN 0012-365X, DOI 10.1016/0012-365X(95)00154-O, lire en ligne, consulté le )
- (en) « Computers and Intractability », dans Wikipedia, (lire en ligne)
- (en) « Contentment in graph theory: Covering graphs with cliques », Indagationes Mathematicae (Proceedings), vol. 80, no 5, , p. 406–424 (ISSN 1385-7258, DOI 10.1016/1385-7258(77)90055-5, lire en ligne, consulté le )
- (en) Lee-Ad J. Gottlieb, John E. Savage et Arkady Yerukhimovich, « Efficient Data Storage in Large Nanoarrays », Theory of Computing Systems, vol. 38, no 4, , p. 503–536 (ISSN 1433-0490, DOI 10.1007/s00224-004-1196-9, lire en ligne, consulté le )
- (en) Hermann Gruber et Markus Holzer, « Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP », Developments in Language Theory, Springer, lecture Notes in Computer Science, , p. 205–216 (ISBN 978-3-540-73208-2, DOI 10.1007/978-3-540-73208-2_21, lire en ligne, consulté le )
- R. G. Downey, Parameterized complexity, Springer, (ISBN 0-387-94883-X et 978-0-387-94883-6, OCLC 37004493, lire en ligne)
- (en) Igor Nor, Danny Hermelin, Sylvain Charlat et Jan Engelstadter, « Mod/Resc Parsimony Inference », Combinatorial Pattern Matching, Springer, lecture Notes in Computer Science, , p. 202–213 (ISBN 978-3-642-13509-5, DOI 10.1007/978-3-642-13509-5_19, lire en ligne, consulté le )
- Ene, Alina; Horne, William G.; Milosavljevic, Nikola; Rao, Prasad; Schreiber, Robert; Tarjan, Robert Endre (2008), "Fast exact and heuristic methods for role minimization problems", in Ray, Indrakshi; Li, Ninghui (eds.), 13th ACM Symposium on Access Control Models and Technologies (SACMAT 2008), ACM, pp. 1–10
- Shu, Guoqiang; Lee, David; Yannakakis, Mihalis (2006), "A note on broadcast encryption key management with applications to large scale emergency alert systems.", 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), IEEE