Галлай-Эдмондстың ыдырауы - Gallai–Edmonds decomposition
Жылы графтар теориясы, Галлай-Эдмондстың ыдырауы - бұл графиктің шыңдарының белгілі бір қасиеттерді қанағаттандыратын ішкі жиындарға бөлінуі. Бұл жалпылау Дульмагж - Мендельсонның ыдырауы екі жақты графикадан жалпы графикке дейін.[1]
Мұны тәуелсіз түрде дәлелдеді Тибор Галлай және Джек Эдмондс.
Мұны пайдаланып табуға болады гүлдену алгоритмі.
Галлай-Эдмондстың ыдырау теоремасын көп қырлы сәйкестікке дейін кеңейту Катарзина Палучтың «Сыйымды сыйымдылық-максималды сәйкестіктерінде» келтірілген.[2]
Әдебиеттер тізімі
- ^ Сабо, Яцинта; Лебль, Мартин; Джаната, Марек (2005 ж. 14 ақпан). «Эдмондс-Галлайдың ыдырауы к-Дананы орау мәселесі «. Комбинаториканың электронды журналы. 12. дои:10.37236/1905. S2CID 11992200.
- ^ Палуч, Катарзына (2013 ж. 22 мамыр). Сыйымдылығы бойынша дәрежелік-максималды сәйкестіктер. Алгоритмдер және күрделілік. Информатика пәнінен дәрістер. 7878. Шпрингер, Берлин, Гейдельберг. 324–335 бб. дои:10.1007/978-3-642-38233-8_27. ISBN 978-3-642-38232-1.
 | Бұл математикаға қатысты мақала а бұта. Сіз Уикипедияға көмектесе аласыз оны кеңейту. |