Екі бөлікке бөлінетін графтар

Кіріспе

Граф теориясының математикалық саласында екі бөлікті граф (немесе биграф) – төбелері екі бөлек және тәуелсіз жиынға бөлінетін граф, яғни әр қабырғасы жиынның біреуінен екіншісіне жалғанады. Төбелер жиындары графтың бөліктері деп аталады. Балама түсіндіру бойынша, екі бөлікті граф – тақ ұзындықтағы циклдары жоқ граф. Екі жиынды графты екі түспен бояу ретінде қарастыруға болады: егер бір жиынның барлық түйіндерін көк, ал екінші жиынның барлық түйіндерін қызыл түспен бояса, әр қабырғаның екі ұшы әртүрлі түстерде болады, бұл графты бояу есебінде қажетті жағдай. Керісінше, үшбұрыш сияқты екі бөлікті емес графтар үшін мұндай бояу мүмкін емес: бір түйін көк, екіншісі қызыл түспен боялғаннан кейін, үшбұрыштың үшінші төбесі екі түстің де төбелерімен байланысады, оған ешқандай түс тағайындауға мүмкіндік бермейді. Екі бөлікті графты оның бөліктері арқылы белгілеу қабылданған, мұнда графтың қабырғаларын білдіреді. Егер екі бөлікті граф байланыссыз болса, онда оның бірнеше екі бөлігі болуы мүмкін; мұндай жағдайда, белгіленуі нақты қолданбада маңызды болатын нақты екі бөлікті көрсетуге көмектеседі. Егер , яғни екі жиынның саны тең болса, онда граф теңгерімді екі бөлікті граф деп аталады. Егер екі бөліктің бір жағындағы барлық төбелердің дәрежесі бірдей болса, онда граф біртекті деп аталады.

Кениг теоремасы және кемелді графиктер

Екі жақты графтарда ең төменгі нүктелік қаптаманың мөлшері ең жоғары сәйкестіктің мөлшеріне тең; бұл Кёниг теоремасы. Бұл теореманың баламалы және эквивалентті түрі – ең үлкен тәуелсіз жиынның мөлшері плюс ең жоғары сәйкестіктің мөлшері, графтың төбелерінің санына тең. Оқшауланған төбелері жоқ кез келген граф үшін, ең төменгі жиектің қаптамасының мөлшері және ең жоғары сәйкестіктің мөлшері, төбелердің санына тең. Бұл теңдікті Кёниг теоремасымен біріктіргенде, екі жақты графтарда ең төменгі жиек қаптамасының мөлшері ең үлкен тәуелсіз жиынның мөлшеріне тең, ал ең төменгі жиек қаптамасының мөлшері плюс ең төменгі нүктелік қаптаманың мөлшері, төбелердің санына тең деген қорытындыға келеміз. Тағы бір қатысты нәтижелер толыққанды графтарға қатысты: әрбір екі жақты граф, әрбір екі жақты графтың толықтығы, әрбір екі жақты графтың желілік графы және әрбір екі жақты графтың желілік графының толықтығы – бәрі де толыққанды. Екі жақты графтардың толықтығын көру оңай (олардың хроматикалық саны екі және олардың ең үлкен клика мөлшері де екі), бірақ екі жақты графтардың толықтығының толықтығын анықтау қиынырақ, және бұл Кёниг теоремасының тағы бір түрі. Бұл толыққанды графтардың бастапқы анықтамасын тудырған нәтижелердің бірі болды. Толыққанды графтардың желілік графтарының толықтығы – бұл Кёниг теоремасының тағы бір түрі, ал желілік графтардың толықтығы – бұл Кёнигтің бұрынғы теоремасының түрі, яғни әрбір екі жақты графты оның ең жоғары дәрежесіне тең түстер санымен бояуға болады. Күшті толыққанды граф теоремасына сәйкес, толыққанды графтар екі жақты графтарға ұқсас, тыйым салынған граф сипаттамасына ие: граф екі жақты болады, егер және тек қана оның ішінде тақ цикл болмаса, ал граф толыққанды болады, егер және тек қана оның ішінде тақ цикл немесе оның толықтығы болмаса. Екі жақты графтар, екі жақты графтардың желілік графтары және олардың толықтығы, күшті толыққанды граф теоремасының дәлелінде қолданылатын толыққанды графтардың бес негізгі класының төртеуін құрайды. Осыдан екі жақты графтың кез келген ішкі графы да екі жақты болады, өйткені ол тақ циклды ала алмайды.

In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching; this is Kőnig's theorem. An alternative and equivalent form of this theorem is that the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices. In any graph without isolated vertices the size of the minimum edge cover plus the size of a maximum matching equals the number of vertices. Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices. Another class of related results concerns perfect graphs: every bipartite graph, the complement of every bipartite graph, the line graph of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (their chromatic number is two and their maximum clique size is also two) but perfection of the complements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. This was one of the results that motivated the initial definition of perfect graphs. Perfection of the complements of line graphs of perfect graphs is yet another restatement of Kőnig's theorem, and perfection of the line graphs themselves is a restatement of an earlier theorem of Kőnig, that every bipartite graph has an edge coloring using a number of colors equal to its maximum degree. According to the strong perfect graph theorem, the perfect graphs have a forbidden graph characterization resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its complement as an induced subgraph. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem. It follows that any subgraph of a bipartite graph is also bipartite because it cannot gain an odd cycle.

Степені

Вершина үшін іргелес төбелердің саны – бұл төбе дәрежесі деп аталады және осылай белгіленеді. Екі бөлікті граф үшін дәрежелердің қосындысы туралы формула былай гласит:

Екі бөлікті графтың дәрежелік тізбегі – екі бөліктің дәрежелерін қамтитын екі тізімнің жұбы болып табылады және . Мысалы, толық екі бөлікті граф K3,5-тің дәрежелік тізбегі . Изоморфты екі бөлікті графтардың дәрежелік тізбегі бірдей болады. Дегенмен, дәрежелік тізбек, әдетте, екі бөлікті графты бірегей түрде анықтамайды; кейбір жағдайларда, изоморфты емес екі бөлікті графтардың дәрежелік тізбегі бірдей болуы мүмкін. Екі бөлікті іске асыру мәселесі – берілген екі табиғи сандар тізіміне сәйкес келетін дәрежелік тізбегі бар қарапайым екі бөлікті графты табу мәселесі. (Бастапқы нөлдерді ескермеуге болады, себебі оларды диграфқа оқшауланған төбелердің тиісті санын қосу арқылы оңай жүзеге асыруға болады.)

Гиперграфтар мен бағытталған графиктерге қатынасы

Бипартитті графиктің қос тікелейлік матрицасы – (0,1) өлшемі бар матрица, онда әрбір жанасқан төбе жұбы үшін 1, ал жанаспаған төбелер үшін 0 болады. Қос тікелейлік матрицаларын бипартитті графиктер, гиперграфиктер және бағытталған графиктер арасындағы эквиваленттіліктерді сипаттау үшін қолдануға болады. Гиперграф – бағытсыз график сияқты, төбелері мен жиектері бар, бірақ жиектері дәл екі нүктеге ие болудың орнына төбелердің кез келген жиынтығынан тұруы мүмкін комбинаторлық құрылым. Гиперграфты модельдеу үшін бипартитті графикті пайдалануға болады, онда U – гиперграфтың төбелерінің жиынтығы, V – гипержиектердің жиынтығы, ал E – гиперграфтың төбесі v-ден гиперграфтың жиегі e-ге дейінгі жиекті қамтиды, егер v жиек e-нің соңғы нүктелерінің бірі болса. Осы сәйкестік бойынша, бипартитті графиктердің қос тікелейлік матрицалары сәйкес гиперграфтардың инциденттік матрицалары болып табылады. Бипартитті графиктер мен гиперграфиктер арасындағы осы сәйкестіктің ерекше жағдайы ретінде, кез келген көпжиекті графикті (бірдей екі төбе арасында екі немесе одан көп жиек болуы мүмкін) кейбір гипержиектерінің бірдей төбелер жиынтығы бар гиперграф ретінде қарастыруға болады және бірнеше тікелей жақындықтары жоқ, ал екі бөліктің бір жағындағы төбелердің бәрі екінші дәрежеде болатын бипартитті графикпен бейнелеуге болады. Іргелес матрицалардың ұқсас қайта түсіндірілуі бағытталған графиктерді (белгіленген төбелердің берілген санында, өзіндік циклдерге рұқсат берумен) және теңгерілген бипартитті графиктерді, екі бөліктің әр жағындағы төбелердің саны бірдей болатын, бір-бірге сәйкестікті көрсету үшін қолданылуы мүмкін. Мысалы, n төбесі бар бағытталған графиктің іргелес матрицасы кез келген (0,1) өлшемі бар матрица болуы мүмкін, содан кейін оны екі бөліктен тұратын графиктің екі жағындағы n төбесі бар іргелес матрицасы ретінде қайта түсіндіруге болады. Бұл құрылымда бипартитті график – бағытталған графиктің бипартитті екі жақты жамылғысы.

Екі жақтылықты тексеру

Графтың екібөлікті екенін тексеруге және тереңдікке бірінші іздеуді пайдаланып, екі түсті бояуды (егер екібөлікті болса) немесе тақ циклді (болмаса) сызықтық уақытта қайтаруға болады. Басты идея – тереңдікке бірінші іздеу орманрындағы әр төбеге ата-анасының түсінен өзгеше түс тағайындау, түстерді тереңдікке бірінші іздеу орманының алдын ала жүріс тәртібімен беру. Бұл міндетті түрде төбелерді ата-аналарына жалғастыратын қабырғалардан тұратын орманға екі түсті бояуды қамтамасыз етеді, бірақ орманға жатпайтын кейбір қабырғаларды дұрыс боямауы мүмкін. Тереңдікке бірінші іздеу орманында орманға жатпайтын әр қабырғаның екі ұшының бірі екінші ұшының ата-бабасы болып табылады, және тереңдікке бірінші іздеу осы типтегі қабырғаны тапқанда, осы екі төбенің әртүрлі түстерде екенін тексеруі керек. Егер олар бірдей болса, онда ата-бабадан ұрпаққа дейінгі орман жолы, қате боялған қабырғамен бірге, тақ цикл құрайды, ол алгоритмнен граф екібөлікті емес деген нәтижемен бірге қайтарылады. Дегенмен, егер алгоритм осы типтегі тақ циклді таба алмай аяқталса, онда барлық қабырға дұрыс боялған болуы керек, және алгоритм бояуды граф екібөлікті деген нәтижемен бірге қайтарады. Балама ретінде, тереңдікке бірінші іздеудің орнына ендікке бірінші іздеуді пайдаланып ұқсас процедураны қолдануға болады. Тағы да, әр түйінге іздеу орнындағы ата-анасынан кері түс беріледі, ендік бірінші тәртіппен. Егер түйін боялғанда, оған бұрын боялған және сол түсті түйінге жалғасқан қабырға болса, онда бұл қабырға ендікке бірінші іздеу орманындағы жолдармен бірге оның екі ұшын және олардың ең төменгі ортақ ата-бабасын байланыстыратын тақ цикл құрайды. Егер алгоритм осылайша тақ циклді таба алмай аяқталса, онда ол дұрыс бояуды тапқан болуы керек және граф екібөлікті деген қорытындыға сенімді түрде келе алады. Эвклид жазықтығындағы түзу кесінділерінің немесе басқа қарапайым пішіндердің қиылысу графтары үшін, графтың өзіне дейін қабырғалар болса да, графтың екібөлікті екенін тексеруге және екі түсті бояуды немесе тақ циклді уақытта қайтаруға болады.

It is possible to test whether a graph is bipartite, and to return either a two coloring (if it is bipartite) or an odd cycle (if it is not) in linear time, using depth first search. The main idea is to assign to each vertex the color that differs from the color of its parent in the depth first search forest, assigning colors in a preorder traversal of the depth first search forest. This will necessarily provide a two coloring of the spanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non forest edges. In a depth first search forest, one of the two endpoints of every non forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite. Alternatively, a similar procedure may be used with breadth first search in place of depth first search. Again, each node is given the opposite color to its parent in the search forest, in breadth first order. If, when a vertex is colored, there exists an edge connecting it to a previously colored vertex with the same color, then this edge together with the paths in the breadth first search forest connecting its two endpoints to their lowest common ancestor forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite. For the intersection graphs of line segments or other simple shapes in the Euclidean plane, it is possible to test whether the graph is bipartite and return either a two coloring or an odd cycle in time , even though the graph itself may have up to edges.

Қисық циклдің көлденең

Тақ циклдің көлденеңі – бұл NP-толық алгоритмдік мәселе, граф G = (V, E) және сан k берілгенде, G-ден k төбе шығару арқылы алынған граф екібөлікті бола ма деген сұраққа жауап береді. Мәселе тұрақты параметрлі шешімді, яғни алгоритмінің орындалу уақытын графтың өлшемі k-ның үлкен функциясымен көбейтілген полиномдық функциямен шектеуге болады. Тақ циклдің көлденеңі деген атау графтың екібөлікті болуы үшін онда тақ циклдар болмауы керек екендігімен байланысты. Сондықтан, екібөлікті граф алу үшін графтан төбелерді жою үшін "барлық тақ циклдарды жою" немесе тақ циклдің көлденең жиынын табу қажет. Мысалда, графтың әрбір тақ циклында көк (ең төменгі) төбелер бар, сондықтан оларды жою барлық тақ циклдарды жояды және екібөлікті графты қалдырады. Қабырғалардың екібөлікті болу мәселесі – графты екібөлікті ету үшін мүмкіндігінше аз қабырғаларды жоюдың алгоритмдік мәселесі және графты өзгерту алгоритміндегі маңызды мәселе. Бұл мәселе де тұрақты параметрлі шешімді және k – жойылатын қабырғалардың саны, ал m – кіріс графтың қабырғаларының саны болғанда белгілі бір уақытта шешіледі.

Сәйкестікті анықтау

Графиктегі сәйкестік – оның қабырғаларының жиынтығының бір бөлігі, олардың ешқайсысы да ортақ нүктеге ие емес. Көптеген сәйкестіктерге қатысты алгоритмдік есептерді шешу үшін полиномиалдық уақыт алгоритмдері белгілі, соның ішінде максималды сәйкестік (мүмкіндігінше көп қабырғаны пайдаланатын сәйкестікті табу), максималды салмақты сәйкестік және тұрақты үйлену. Көп жағдайларда сәйкестік мәселелерін екі бөлікті графиктерде шешу, екі бөлікті емес графиктерге қарағанда оңайырақ, және Хопкрофт-Карп алгоритмі сияқты көптеген сәйкестік алгоритмдері екі бөлікті кірістерде ғана дұрыс жұмыс істейді. Мысалы, адамдар тобы жұмыс орындарының ішінде жұмыс іздеп жүр дейік, бірақ барлық адамдар барлық жұмысқа жарамды емес. Бұл жағдайды екі бөлікті график ретінде модельдеуге болады, онда әр жұмыс іздеуші әр қолайлы жұмыспен байланыстырылған қабырға арқылы көрсетіледі. Кемел сәйкестік – барлық жұмыс іздеушілерді бірден қанағаттандырып, барлық жұмыс орындарын толтырудың тәсілін сипаттайды; Холлдың үйлену теоремасы кемел сәйкестіктерге мүмкіндік беретін екі бөлікті графиктердің сипаттамасын ұсынады. Ұлттық резиденттік сәйкестендіру бағдарламасы АҚШ-тың медицина студенттері мен ауруханалардағы тұру орындары үшін осы мәселені шешу үшін график сәйкестігі әдістерін қолданады. Дулмадж-Мендельсонның жіктелуі – екі бөлікті графиктердің құрылымдық жіктелуі, ол максималды сәйкестіктерді табуда пайдалы.

Қосымша өтінімдер

Бипартит графиктері қазіргі заманғы кодтау теориясында, әсіресе арнадан алынған кодты сөздерді декодтау үшін кеңінен қолданылады. Факторлық графиктер мен Таннер графиктері осыған мысалдар. Таннер графигі – екі бөліктен тұратын график, онда екі бөліктің бірінші жағындағы төбелер кодты сөздің цифрларын, ал екінші жағындағы төбелер кодты сөзде қатесіз нөлге тең болуы тиіс цифрлардың комбинацияларын көрсетеді. Факторлық график – LDPC және турбо кодтарының ықтималдық декодтауын қолдануға арналған, оған жақын сенім желісі. Компьютер ғылымында Петри желісі – бір мезгілдегі жүйелерді талдау және модельдеуде қолданылатын математикалық модельдеу құралы. Жүйе екі жиынтығы бар екіжақты бағытталған график ретінде модельделеді: ресурстарды қамтитын "орналасқан жерлер" жиынтығы және ресурстарды жасайтын және/немесе тұтынатын "оқиғалар" жиынтығы. Жүйенің мінез-құлқына шектеулер қоятын төбелер мен қабырғаларда қосымша шектеулер бар. Петри желілері екіжақты бағытталған графиктердің қасиеттерін және басқа да қасиеттерді пайдаланады, бұл жүйелердің мінез-құлқын математикалық тұрғыдан дәлелдеуге, сонымен қатар жүйенің модельдеуін оңай жүзеге асыруға мүмкіндік береді. Проективтік геометрияда Леви графигі – конфигурациядағы нүктелер мен түзулер арасындағы байланыстарды модельдеу үшін қолданылатын бипартит графигінің бір түрі. Нүктелер мен түзулердің геометриялық қасиеттеріне сәйкес, әр екі түзу ең көп дегенде бір нүктеде қиылысады және әр екі нүкте бір түзумен байланыстырылады, Леви графиктерінде ұзындығы төртке тең циклдар болмайды, сондықтан олардың айналымы алты немесе одан да көп болуы керек.