Бипартитивни граф — разлика између измена
Садржај обрисан Садржај додат
м Dodavanje datuma u šablone za održavanje i/ili sredjivanje referenci |
м Поправљене везе: степен → Степен (теорија графова) |
||
Ред 6:
Два скупа '''U''' и '''V''' могу да се представе помоћу бојења графа са две боје: тако да једна боја означава све чворове из '''U''' и плава је, а сви чворови из '''V''' су представљени зеленом бојом. Тако свака грана има завршетке са различитом бојом, као што је и представљено у проблему бојења графа. Ова метода није могућа и нема смисла да се употреби за небипартитивне графове, као на пример троугао: пошто је један чвор обојен у плаво, а други у зелено, немогуће је одредити боју за трећи чвор јер у њега улазе две гране које почињу са две различите боје.
Често се користи и ознака '''G = (U, V, E)''' да се означи бипартитивни граф који има два дисјунктна скупа чворова '''U''' и '''V''', и '''Е''' који означава гране графа. Ако бипартитиван граф није повезан, онда може да има више од једног пара дисјунктних скупова. У том слулају, ова нотација ('''G = (U, V, E)''') је врло од помоћи при навођењу конкретног пара скупова који може да буде од користи. Ако '''|U| = |V|''' (број чворова у U је једнак броју чворова у V, U и V имају исту [[кардиналност]]), онда се G назива и балансиран бипартитиван граф. Ако су сви чворови са исте стране имају исти [[Степен (теорија графова)|степен]], онда се G назива бирегуларан граф.
== Примери ==
|