Разложение Галлаи – Эдмондса - Gallai–Edmonds decomposition
В теория графов, то Разложение Галлаи – Эдмондса является разбиением вершин графа на подмножества, удовлетворяющие определенным свойствам. Это обобщение Разложение Дульмаджа – Мендельсона от двудольных графов к общим графам.[1]
Это было независимо доказано Тибор Галлай и Джек Эдмондс.
Его можно найти с помощью алгоритм цветения.
Распространение теоремы о разложении Галлаи – Эдмондса на многореберные паросочетания дано в книге Катаржины Палуч «Емкостные ранговые максимальные паросочетания».[2]
Рекомендации
- ^ Сабо, Яцинт; Лёбль, Мартин; Джаната, Марек (14 февраля 2005 г.). "Разложение Эдмондса – Галлая для k-Проблема с упаковкой ". Электронный журнал комбинаторики. 12. Дои:10.37236/1905. S2CID 11992200.
- ^ Палуч, Катажина (22 мая 2013 г.). Максимальные ранговые соответствия. Алгоритмы и сложность. Конспект лекций по информатике. 7878. Шпрингер, Берлин, Гейдельберг. С. 324–335. Дои:10.1007/978-3-642-38233-8_27. ISBN 978-3-642-38232-1.
 | Эта статья по математике заглушка. Вы можете помочь Википедии расширяя это. |