graphe biparti oor Russies

graphe biparti

Vertalings in die woordeboek Frans - Russies

Двудольный граф

Soortgelyke frases

graphe biparti complet
Полный двудольный граф

voorbeelde

Toutefois, pour les graphes non biparti, trouver les chemins d'augmentation pour chacune des phases est plus difficile.
Однако для недвудольных графов поиск удлиняющих путей в каждой фазе более сложен.

Les graphes planaires extérieurs possèdent des caractérisations par graphes exclus analogues à celles des graphes planaires données par les théorèmes de Kuratowski et de Wagner : un graphe est planaire extérieur si et seulement s'il ne contient pas de subdivision du graphe complet K4 ou du graphe biparti complet K2,3.
Внешнепланарные графы имеют характеризацию запрещёнными графами, аналогичную теореме Понтрягина — Куратовского и теореме Вагнера для планарных графов — граф внешнепланарен тогда и только тогда, когда он не содержит подразбиения* полного графа K4 или полного двудольного графа K2,3 .

En s'appuyant sur divers travaux antérieurs Micali et Vazirani 1980 ont montré comment implémenter chaque phase de l'algorithme en temps linéaire, ce qui finalement donne un algorithme pour le couplage dans les graphes non bipartis qui a la même borne de complexité que l'algorithme de Hopcroft-Karp pour les graphes bipartis.
Базируясь на более ранних работах, Micali & Vazirani (1980) показали, как выполнять фазу за линейное время, что привело к созданию алгоритма с той же верхней оценкой, что и у алгоритма Хопкрофта — Карпа для двудольных графов.

Le même principe a aussi été employé pour développer des algorithmes plus compliqués de couplage dans des graphes non bipartis, avec la même complexité en temps que l’algorithme de Hopcroft-Karp.
Та же идея используется в более сложных алгоритмах для поиска паросочетаний в недвудольных графах с тем же асимптотическим временем работы, как у алгоритма Хопкрофта — Карпа.

Iofinova et Ivanov ont montré en 1985 qu'il existe exactement cinq graphes semi-symétriques cubiques bipartis (bipartite cubic semisymmetric graphs) dont le groupe d'automorphisme préserve les partitions et agit primitivement sur chaque partition.
Иванов и Иофинова доказали в 1985 году существование пяти и только пяти полусимметричных кубических двудольных графов, группы автоморфизмов которых действуют примитивно на каждой доле двудольного графа.

Par exemple, l'analyse de la complexité en moyenne pour des graphes creux biparti aléatoires menée par Bast et al. 2006, améliorant des résultats antérieurs de Motwani 1994, montre qu'avec une grande probabilité, tous les couplages non optimaux ont des chemins d'augmentation de longueur logarithmique.
Например, в случае разреженного двудольного случайного графа в 2006 году было показано (улучшая предыдущий результат), что с большой вероятностью все неоптимальные паросочетания имеют увеличивающие пути логарифмической длины.

Néanmoins, si l'on assemble toutes ces conditions, le problème de savoir si les graphes planaires cubiques bipartis 3-connexes contiennent toujours un cycle hamiltonien reste ouvert (conjecture de Barnette (en)), et si c'était le cas le problème restreint à ces graphes ne pourrait pas être NP-complet.
Складывая всё вместе, остаётся открытой задача, всегда ли 3-связные 3-регулярные двудольные планарные графы должны содержать гамильтонов цикл и если должны, задача, ограниченная этими графами не будет NP-полной, см. статью «Гипотеза Барнетта».