Бипартитивни граф — разлика између измена
Садржај обрисан Садржај додат
м Renamed template |
, |
||
Ред 1:
[[Датотека:Simple-bipartite-graph.svg|thumb|Пример бипартитивног графа без циклуса]]
[[Датотека:Biclique_K_3_5.svg|thumb|Комплетан бипартитивни граф са m = 5 и n = 3]]
'''Бипартитивни граф''', познат и као '''''биграф''''' или '''''диграф''''' је [[граф]], у математичкој области [[теорија графова|
Два скупа '''U''' и '''V''' могу да се представе помоћу бојења графа са две боје: тако да једна боја означава све чворове из '''U''' и плава је, а сви чворови из '''V''' су представљени зеленом бојом. Тако свака грана има завршетке са различитом бојом, као што је и представљено у проблему бојења графа. Ова метода није могућа и нема смисла да се употреби за небипартитивне графове, као на пример троугао: пошто је један чвор обојен у плаво, а други у зелено, немогуће је одредити боју за трећи чвор јер у њега улазе две гране које почињу са две различите боје.
Линија 10 ⟶ 9:
== Примери ==
Када се моделују релације између две различите класе објеката, бипартитивни графови су често корисни и њихова примена је природна. На пример, граф фудбалера и клубова, са граном између фудбалера и клуба која означава да је фудбалер играо за тај клуб, је природан пример афилационе мреже, која је тип бипартитивног графа који се користи у анализи друштвених веза.<ref>{{Cite book|last1=Wasserman|first1=Stanley|last2=Faust|first2=Katherine|title=Social Network Analysis: Methods and Applications|url=http://books.google.com/books?id=CAm2DpIqRUIC&pg=PA299|date=25 November 1994|publisher=Cambridge University Press|isbn=978-0-521-38707-1|pages=299}}</ref>
Још један пример овог типа графа који се такође природно намеће је у пробелему оптимизације пруге (спада у област [[НП-комплетни проблеми]]), у којем је улаз распоред возова и њихових станица, а циљ је да се пронађе скуп возова да буде што мањи је могуће тако да сваки воз посети макар једну од изабраих станица. Овај проблем може да се моделује као доминантни скуп у бипартитивном графу који има чвор за сваки воз и сваку станицу и грану за сваку станицу на којој се воз зауставља.
Линија 38 ⟶ 36:
Још једна класа повезаних разултата се тиче савршених графова: сваки бипартитивни граф, [[комплемент]] сваког бипартитивног графа, линијски граф бипартитивног графа су савршени. Савршенство бипартитивних графова је врло једноставно да се увиди (може да се обоји са две боје, тј. њихов [[хроматски број]] је 2) али савршенство комплемента бипартитивног графа је мање тривијално и још једна је примена Конигове теореме. Ово је један од разултата који су мотивисали увођење појма савршеног графа. Исто важи и за комплементе линијског графа савршеног графа и савршенство комплемената линијских графова који се такође могу објаснити преко ове теореме тј. да сваки бипартитивни граф има боју гране коју је добила помоћу боја једнаким његовом максималном степену.
Према још једној теореми која описује савршене графове, савршени графови имају забрањену карактеризацију графа која подсећа на бипартитиван граф: граф је бипартитиван ако и само ако нема непаран циклус као подграф, и граф је савршен ако и само ако нема непаран циклус или његов комплемент као индукован подграф. Бипартитивни графови, линијски графови бипартитивних графова и њигови комплементи граде четири од пет основних класа савршених графова који се користе да би се доказала горе наведена теорема.<ref><cite class="citation" id="CITEREFChudnovskyRobertsonSeymourThomas2006">Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), [http://annals.princeton.edu/annals/2006/164-1/p02.xhtml "The strong perfect graph theorem"], ''Annals of Mathematics'' '''164''' (1): 51–229, {{doi|10.4007/annals.2006.164.51}}</cite><cite class="citation" id="CITEREFChudnovskyRobertsonSeymourThomas2006"></cite>.</ref>
=== Степен ===
Линија 60 ⟶ 57:
Могуће је тестирати и проверити да ли је граф бипартитиван, и вратити две боје (ако је граф бипартитиван) или циклус непарне дужине (ако није) у времену које се означава као [[субекспоненцијално време]], помоћу алгоритма [[претрага у дубину]]. Главна идеја да се сваком чвору дода боја која се разликује од боје родитеља у дрвету које настаје при примени претраге у дубину. Последица тога је [[разапињуће стабло]] са две боје чворова које се састоји од грана које спајају чворове до својих родитеља, али можда неће исправно обојити гране које нису [[грана стабла]]. У стаблу које је генерисано претрагом у дубину, један од два краја сваке гране која није грана стабла је предак овог другог краја и када дфс претрага открије грану која овог типа треба да провери да ли ово два чвора имају различите боје. Ако немају, онда је путања у стаблу од претка до детета, заједно са граном која је погрешно обојена циклус непарне дужине, који је враћен из алгоритма заједно са резултетом да граф није бипартитиван. Ипак, ако алгоритам заврши рад без детектовања циклуса непарне дужине овог типа, онда је свака грана правилно обојена и алгоритам враћа боје заједно са резултатом да је граф заиста бипартитиван.
Алтернативно овоме, слична процедура може да се примени са методом [[претрага у ширину]] уместо претраге у дубину. Опет, сваки чвор добија супротну боју од свог родитеља у стаблу претраге. Ако, када је неки чвор обојен, онда постоји и грана која га спаја са претходно обојеним чвором том бојом. Онда је та грана заједно са путањом у стаблу која настаје при примени алгоритма претраге у дубину која спаја та два краја са њиховим најнижим заједничким претком чини циклус непарне дужине. Ако се алгоритам заврши без да је пронашао циклус непарне дужине на овај начин, онда је сигурно нашао исправно бојење, и сигурно може да се закључи да је овај граф бипартитиван.<ref><cite class="citation" id="CITEREFKleinbergTardos2006">Kleinberg, Jon; Tardos, Éva (2006), ''Algorithm Design'', Addison Wesley. стр. 94–97</cite>.</ref>
За графове са убацивањем n-те дужи или неког другог облика у Еуклидовој равни, могуће је да се тестира да ли је граф бипартитиван и вратити или две боје или циклус непарне дужине у<math>O(n\log n)</math>, времену, иако граф сам по себи има до <math>\Omega(n^2)</math> грана.
Линија 76 ⟶ 72:
Поклапање у графу је подскуп његових грана, где ниједан пар од њих нема исти крај. Полинамијални алгоритми су познати за многе проблеме у алгоритмима за поклапање, укључујући максималан број поклапања (налажећи поклапање које користи што више грана је могуће), максималану тежину поклапања и стабилан брак. У многим случајевима, проблеми поклапања су једноставнији да се реше на бипартитивним графовима него на графовима који то нису, а многи алгоритми за поклапање као на пример [[Хопцрофт-Карп]] алгоритам за поклапање максималних кардиналности ради исправно само на бипартитивним графовима.
Као једноставан пример, претпоставимо да постоји скуп П људи где сви људи траже послове међу скупом Ј који предстваља послове, тако да нису сви људи одговарајући за све послове. Ова ситуација може да се моделује као бипартитиван граф (П, J, E) где гране спајају сваког кандидата са одговарајућим послом. Савршено поклапање описује начин да се симултано задовоље сви људи које траже посао као и да су сви послови попуњени; Халова теорема брака даје карактеризацију бипартитивног графа који дозвољава савршено поклапање. Национални програм за поклапање се односи на методе поклапања да се реше сви проблеми за САД-ове студенте медицине и послове за стажисте по болницама.<ref><cite class="citation" id="CITEREFRobinson2003">Robinson, Sara (April 2003), [http://www.siam.org/pdf/news/305.pdf "Are Medical Students Meeting Their (Best Possible) Match?"] </cite></ref>
Далмеџ-Менделсон декомпозиција је структурална декомпозиција бипартитивних графова који су корисни у налажењу максималних поклапања.
| |||