Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Нема описа измене
мНема описа измене
Ред 2:
[[Датотека:Biclique_K_3_5.svg|мини|Комплетан бипартитивни граф са m = 5 и n = 3]]
 
'''Бипартитивни граф''', познат и као '''''биграф''''' или '''''диграф''''' је [[граф]], у математичкој области [[теорија графова|теорије графова]], чији се чворови могу поделити на два дисјунктивна скупа '''U '''и '''V''' (тако да се '''U''' и '''V''' могу представити као скупови које се обележавају као [[независан скуп]]) тако да свака грана (ивица) спаја чвор из '''U''' и један чвор из''' V'''. Скупови чворова '''U '''и '''V''' се често и називају партитивни скупови. Еквивалентно томе, бипартитиван граф је граф који не садржи ниједан [[циклус]] непарне дужине.
 
Два скупа '''U''' и '''V''' могу да се представе помоћу бојења графа са две боје: тако да једна боја означава све чворове из '''U''' и плава је, а сви чворови из '''V''' су представљени зеленом бојом. Тако свака грана има завршетке са различитом бојом, као што је и представљено у проблему бојења графа. Ова метода није могућа и нема смисла да се употреби за небипартитивне графове, као на пример троугао: пошто је један чвор обојен у плаво, а други у зелено, немогуће је одредити боју за трећи чвор јер у њега улазе две гране које почињу са две различите боје.
Преузето из „https://sr.wikipedia.org/wiki/Бипартитивни_граф”