| Submission declined on 16 November 2024 by Qcne (talk). This is the English language Wikipedia; we can only accept articles written in the English language. Please provide a high-quality English language translation of your submission. Have you visited the Wikipedia home page? You can probably find a version of Wikipedia in your language.
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
|  |
Isomorphisme du graphe fractionnaires
editEn theory des graphes , un isomorphisme fractionné des Graph dont les matrices adjacentes sont notées A et B est une matrice doublement stochastique D telle que DA et BD. Si la matrice doublement stochastique est une matrice de permutation, alors elle constitue un isomorphisme de graphe. L'isomorphisme fractionné est le plus grossier de plusieurs relaxations différentes de l'isomorphisme du graphe.
Complexité en informatique
editAlors que le probleme de l'isomorphisme des graphes n'est pas connu pour etre==== Catégorie:Théorie du graphisme fractionnaire ==== decidable en temps polynomial ni peut etre NP-complete, le probleme de l'isomorphisme des graphes fractionnaire est décidé en temps polynomial par ce que c'est un cas spcial du probleme de la programmation lineaire, pour les quelles sont des solutions efficients. plus précisement la condition dans la matrice D qui doit etre doublement
Équivalence à une partition équitable la plus grossière
editDeux graphes sont également isomorphes fractionnés s'ils ont une partition commune la plus grossière. Une partition d'un graphe est une collection d'ensembles de sommets disjoints appariés dont l'union est l'ensemble de sommets du graphe. Une partition est équitable si pour une paire de sommets u et v dans le même bloc de la partition et un bloc B de la partition, u et v ont tous les deux le même nombre de voisins dans B. Un partage équitable P est plus grossier si chaque bloc dans un autre partition équitable est un sous-ensemble d'un bloc dans P. Deux partitions équitables les plus grosses P et Q sont communes s'il y a une bijection f des blocs de P à des blocs de Q tels pour les blocs B et C en P, le nombre de voisins en C de n'importe quel sommet en B est égal au nombre de voisins en f(C) de n'importe quel sommet dans f(B).
Voir aussi
editRéférences
edit- Scheinerman, Edward; Ullman, Daniel (1997). "Chapitre 6: Isomorphisme fractionnaire". Théorie du graphe fractionnaire. John Wiley et Fils. pp. 127-151. ISBN 0-471-17864-0.
- Ramana, Motakuri V.; Scheinerman, Edward R.; Ullman, Daniel (1994). "Iisomorphisme fractionnaire des graphes". Mathématiques discrètes. 132 (1-3): 247-265. doi : 10.1016/0012-365X(94)90241-0. M. MR 1297385.
- Maninska, Laura; Roberson, David E.; zmal, Robert; Severini, Simone; Varvitsiotis, Antonios (2017). "Relaxations de l'isomorphisme du graphe". Dans Chatzigiannakis, Ioannis; Indyk, Piotr; Kuhn, Fabian; Muscholl, Anca (éd.). 44e Colloque international sur l'automatisation, les langues et la programmation, ICALP 2017, 10-14 juillet, 2017, Varsovie, Pologne. LIPIcs. Vol. 80. Schloss Dagstuhl – Leibniz-zentrum pour Informatik. pp. 76:1-76:14. doi: 10.4230/LIPICS.ICALP.2017.76.