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

== Примери ==

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

 

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

 

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

 

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

 

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

 

== Литература ==

 

[[Категорија:Фамилије графова]]