Кіріспе
Екі жақты графты ерекше қасиетімен бөлу
Графтар теориясында, Дулмедж-Мендельсон ыдырауы – екі жақты графтың төбелерін қосалқы жиымдарға бөлу, мұнда екі іргелес төбе егер және тек қана олар графтың толық сәйкестігінде бір-бірімен жұптасқан болса, бірдей қосалқы жиымға тиесілі болады. Ол 1958 жылы жариялаған А. Л. Дулмедж және Натан Мендельсонның есімімен аталады. Кез келген графқа жалпылау Эдмондс-Галлай ыдырауы, Блосс алгоритмін қолдану арқылы жүзеге асырылады.
In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958. A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.
Құрылыс
Дулмадж-Мендельшон ыдырауын келесідей құрастыруға болады. (авторлығы кімге тиесілі екені белгісіз, ол бұл ойды кімге жатқызады). G екі жақты граф болсын, M – G графындағы ең үлкен дәрежелі сәйкестік, ал V0 – M сәйкестігіне кірмейтін G графының төбелерінің жиыны ("бос төбелер"). Онда G үш бөлікке бөлінеді: E – жұп төбелер – V0-дан M ауыспалы жолы арқылы қол жетімді төбелер. O – тақ төбелер – V0-дан M тақ ұзындығындағы ауыспалы жол арқылы қол жетімді төбелер. U – қол жетпес төбелер – V0-дан M ауыспалы жолы арқылы қол жетпес төбелер. Мысалы сол жақта көрсетілген. Қалың сызықтар M сәйкестігінің жиектері. Жұқа сызықтар G графының қалған жиектері. Қызыл нүктелер V0 жиынының төбелері. V0 төбелері E жиынына кіретінін ескеріңіз, себебі оларға V0-дан 0 ұзындығындағы жолмен жетуге болады. Осы ыдырау негізінде G графының жиектерін олардың соңғы төбелеріне қарай алты бөлікке бөлуге болады: E U, E E, O O, O U, E O, U U. Бұл ыдыраудың келесідей қасиеттері бар: Алайда, бұл түсінік график гомоморфизміндегі өзектен және төмен дәрежелі төбелерді жою арқылы құрылатын k-өзектен ерекшеленеді.
E the even vertices the vertices reachable from V0 by an M alternating path of even length. O the odd vertices the vertices reachable from V0 by an M alternating path of odd length. U the unreachable vertices the vertices unreachable from V0 by an M alternating path. An illustration is shown on the left. The bold lines are the edges of M. The weak lines are other edges of G. The red dots are the vertices of V0. Note that V0 is contained in E, since it is reachable from V0 by a path of length 0. Based on this decomposition, the edges in G can be partitioned into six parts according to their endpoints: E U, E E, O O, O U, E O, U U. This decomposition has the following properties: However, this concept should be distinguished from the core in the sense of graph homomorphisms, and from the k core formed by the removal of low degree vertices.
Қолданбалар
Бұл жіктеу шекті элементтер талдауында торларды бөлуге, сондай-ақ сызықтық емес теңдеулер жүйелерінде берілген, жеткіліксіз және артық анықталған теңдеулерді анықтауға қолданылды. Бұл, сонымен қатар, ранг бойынша максималды сәйкестендіру алгоритмі үшін де пайдаланылды.
Асимметриялық нұсқа
Бұл жерде екі жақты графиктің тағы бір түрлі ажыратылуы бар, ол асимметриялық – ол графтың бір жағындағы төбелерді екінші жағындағы төбелерден ажыратады. Оны салмақталмаған екі жақты графтарда максималды кардиналдылықта қызғанусыз сәйкестікті, ал салмақталған екі жақты графтарда минималды құнмен максималды кардиналдылықтағы сәйкестікті табу үшін қолдануға болады.