Бипартитивни граф — разлика између измена

== Примери ==

Када се моделују релације између две различите класе објеката, бипартитивни графови су често корисни и њихова примена је природна. На пример, граф фудбалера и клубова, са граном између фудбалера и клуба која означава да је фудбалер играо за тај клуб, је природан пример афилационе мреже, која је тип бипартитивног графа који се користи у анализи друштвених веза.

 

Још један пример овог типа графа кој се такође природно намеће је у пробелему оптимизације пруге(спада у област [[НП-комплетни проблеми]]), у којем је улаз распоред возова и њихових станица, а циљ је да се пронађе скуп возова да буде што мањи је могуће тако да сваки воз посети макар једну од изабраих станица. Овај проблем може да се моделује као доминантни скуп у бипартитивном графу који има чвор за сваки воз и сваку станицу и грану за сваку станицу на којој се воз зауставља.

 

 

Абстрактинији примери могу да буду:

 

Према још једној теореми која описује савшене графове, савршени графови имају забрањену карактеризацију графа која подсећа на бипартитиван граф: граф је бипартитиван ако и само ако нема непаран циклус као подграф, и граф је савршен ако и само ако нема непаран циклус или његов комплемент као индукован подграф. Бипартитивни графови, линијски графови бипартитивних графова и њигови комплементи граде четири од пет основних класа савршених графова који се користе да би се доказала горе наведена теорема.

 

=== Степен ===

 

Алтернативно овоме, слична процедура може дас епримени са методом [[претрага у ширину]] уместо претраге у дубину. Опет, сваки чвор добија супротну боју од свог родитеља у стаблу претраге. Ако је неки чвор обојен, онда постоји и грана која га спаја са претходно обојеним чвором том бојом, онда је ова грана заједно са том путањом у стаблу које настеје при примени алгоритма претраге у дубину која спаја та два краја са њиховим најнижим заједничким претком који чини циклус непарне дужине. Ако се алгоритам завши без да је пронашао циклус непарне дужине на овај начин, онда је сигурно нашао исправно бојење, и сигурно може да се закључи да је овај граф бипартитиван.

 

За графове са убацивањем n-те дужи или неког другог облика у Еуклидовој равни, могуће је да се тестира да ли је граф бипартитиван и вратити или две боје или циклус непарне дужине у<math>O(n\log n)</math>,времену, иако граф сам по себи има до <math>\Omega(n^2)</math> грана.

 

Као једноставан пример, претпоставимо да посотји скуп П људи где сви људи траже послове међу скупом Ј који предстваља скупове, тако да нису сви људи одговарајући за све послове. Ова ситуација може да се моделује као бипартитиван граф (P, J, E) где гране спајају сваког кандидата са одговарајућим послом. Савршено поклапање описује начин да се симултано задовоље сви људи које траже посао као и да су сви послови попуњени; Халова теорема брака даје карактеризацију бипартитивног графа који дозвољава савршено поклапање. Национални програм за поклапање се односи на методе поклапања да се реше сви проблеми за САД-ове студенте медицине и послове за стажисте по болницама.

 

Далмеџ-Менделсон декомпозиција је структурална декомпозиција бипартитивних графова који су корисни у налажењу максималних поклапања.

== Додатни проблеми ==

Бипартитивни графови се врло користе у модерној теорији кодовања, нарочито за декодовање шифри које се примају преко канала. Фактор графови и Танерови графови су примери овога. Танеров граф је бипартитиван граф у којем су чворови са једне стране бипартиције представљени цифрама из шифре, а чворови са друге стране су представљени комбинацијама цифри за које се претпоставља да је сума од нуле у самој шифри. Фактор граф је уско повезан са методама за пробалистичко декодовањем турнокода и ЛДПЦ.

 

У информатици, Петри мрежа је оруђе за математичко моделовање које се користи за анализу и симулацију конкурентних система. Систем је моделован као бипартитиван граф са два скупа чворова: скуп са „место“ чворовима који садрже ресурсе, и скуп „догађаја“ чворова који генеришу и/или ресурс за конзумацију. Постоје и додатне границе за чворове и гране које ограничавају понашање система. Петри мреже користе особине бипартитивних усмерених графова да би дозволили математичке доказе понашања система док такође дозвољавају лаку имплементацију симулација система.

 

У пројективној геометрији, Ливај графови су облик бипартитивних графова који се корсити да се моделују инциденције између тачака и линија у конгигурацији. Ливај графови не морају да садрже циклусе дужине четири, тако да је дужина најкраћег циклуса већа од 6, а то одговара геометријском правилу тачака и права које каже да се две праве секу у највише једној тачки и да се једна права може повући из најмање две тачке.

 

== Погледати такође ==