Преглед садржаја:
Дефиниција - Шта значи Бипартите граф?
Двопартитни граф је графикон у којем скуп врхова графа може бити подељен у два независна скупа, а ниједна два вертика у истом скупу нису суседна. Другим речима, двопартитни графови могу се сматрати једнаким двема обојивим графовима. Бипартитни графови се углавном користе у моделирању односа, посебно између две читаве одвојене класе објекта.
Бипартитни граф познат је и као биграф.
Техопедиа објашњава Бипартите Грапх
Двопартитни граф има два скупа врхова, на пример А и Б, с могућношћу да када се повуче ивица, веза треба да буде у могућности да се повеже између било које верзије у А с било којом врхом у Б. Ако граф не садржи ниједан непарни циклус (број врхова на графу је непаран), тада је његов спектар симетричан. Хроматски број, који је минимални број боја потребан за обојење врхова без суседних врхова који деле исте боје, у случају двопартитног графа мора да буде мањи или једнак две. Све врсте ацикличних графова (графови који немају циклуса графа) су примери двопартитних графова. Циклички граф сматра се двостраним ако су сви укључени циклуси једнолике дужине. Према Конинговој теореми о бојању линија, сви бипартитни графови су графови 1. класе.
Бипартитни графови се широко користе у савременој теорији кодирања осим што се користе у моделирању односа.
