Бипартитивни граф — разлика између измена
Садржај обрисан Садржај додат
м Разне исправке |
Нема описа измене |
||
Ред 5:
Два скупа '''U''' и '''V''' маго да се представе помоћу бојења графа са две боје: тако да једна боја означава све чворове из '''U''' и плава је, а сви чворови из '''V''' су представљени зеленом бојом. Тако свака грана има завршетке са различитом бојом, као што је и представљено у проблему бојења графа. Ова метода није могућа и нема смисла да се употреби за небипартитивне графове, као на пример троугао: пошто је један чвор обојен у плаво, а други у зелено, немогуће је одредити боју за трећи чвор јер у њега улазе две гране које почињу са две различите боје.
Често се користи и ознака '''G = (U, V, E)''' да се означи бипартитивни граф који има два дисјунктна скупа чворова '''U''' и '''V''', и '''Е''' који означава гране графа. Ако бипартитиван граф није повезан, онда може да има више од једног пара дисјунктних скупова. У том слулају, ова нотација ('''G = (U, V, E)''') је врло од помоћи при навођењу конкретног пара скупова који може да буде од користи. Ако '''|U| = |V|''' (број чворова у U је једнак броју чворова у V, U и V имају исту [[
== Примери ==
Када се моделују релације између две различите класе објеката, бипартитивни графови су често корисни и њихова примена је природна. На пример, граф фудбалера и клубова, са граном између фудбалера и клуба која означава да је фудбалер играо за тај клуб, је природан пример афилационе мреже, која је тип бипартитивног графа који се користи у анализи друштвених веза.
<ref>
Још један пример овог типа графа кој се такође природно намеће је у пробелему оптимизације пруге(спада у област [[НП-комплетни проблеми]]), у којем је улаз распоред возова и њихових станица, а циљ је да се пронађе скуп возова да буде што мањи је могуће тако да сваки воз посети макар једну од изабраих станица. Овај проблем може да се моделује као доминантни скуп у бипартитивном графу који има чвор за сваки воз и сваку станицу и грану за сваку станицу на којој се воз зауставља.
Ред 86:
У информатици, Петри мрежа је оруђе за математичко моделовање које се користи за анализу и симулацију конкурентних система. Систем је моделован као бипартитиван граф са два скупа чворова: скуп са „место“ чворовима који садрже ресурсе, и скуп „догађаја“ чворова који генеришу и/или ресурс за конзумацију. Постоје и додатне границе за чворове и гране које ограничавају понашање система. Петри мреже користе особине бипартитивних усмерених графова да би дозволили математичке доказе понашања система док такође дозвољавају лаку имплементацију симулација система.
<ref>
У пројективној геометрији, Ливај графови су облик бипартитивних графова који се корсити да се моделују инциденције између тачака и линија у конгигурацији. Ливај графови не морају да садрже циклусе дужине четири, тако да је дужина најкраћег циклуса већа од 6, а то одговара геометријском правилу тачака и права које каже да се две праве секу у највише једној тачки и да се једна права може повући из најмање две тачке.
<ref>
== Погледати такође ==
Ред 97:
== Референце ==
{{reflist|colwidth = 30em}}
== Литература ==
[[Категорија:Фамилије графова]]
| |||