Sadržaj:
Definicija - Što znači Bipartite Graph?
Dvopartični graf je graf u kojem se skup vrhova grafova može podijeliti u dva neovisna skupa, a ne mogu se nalaziti dva vertika u istom skupu. Drugim riječima, dvopartitni grafovi mogu se smatrati jednakim dvama obojivim grafovima. Bipartitni grafovi se uglavnom koriste u modeliranju odnosa, posebno između dvije cjelovite zasebne klase objekta.
Bipartitni graf poznat je i kao bigraf.
Tehopedija objašnjava Bipartite Graph
Dvostrani graf ima dvije skupove vrhova, na primjer A i B, s mogućnošću da kada se povuče neki rub, veza bi trebala biti u mogućnosti da se poveže između bilo koje verzije u A s bilo kojom vrhom u B. Ako graf ne sadrži nijednu neparni ciklus (broj vrhova u grafu je neparan), tada je njegov spektar simetričan. Kromatski broj, koji je minimalni broj boja potreban za obojenje vrhova bez susjednih vrhova koji dijele iste boje, u slučaju dvostranog grafa mora biti manji ili jednak dva. Sve vrste acikličnih grafova (grafovi koji nemaju ciklusa grafa) primjeri su bipartitnih grafova. Ciklički graf smatra se dvostranim ako su svi uključeni ciklusi jednolike dužine. Prema Koningovom teoremu obojenja linija, svi bipartitni grafovi su grafovi 1. klase.
Bipartitni grafovi se široko koriste u modernoj teoriji kodiranja osim što se koriste u modeliranju odnosa.
