Kazalo:
Opredelitev - Kaj pomeni grafikon Bipartite?
Dvostranski graf je graf, v katerem lahko niz vertik grafov razdelimo v dva neodvisna niza, nobena dva točka grafov znotraj istega niza pa nista sosednja. Z drugimi besedami, dvopartitni grafi se lahko štejejo za enaka dvema barvnima grafoma. Bipartitni grafi se večinoma uporabljajo pri modeliranju odnosov, zlasti med dvema celotnima ločenima razredoma predmetov.
Dvostranski graf je znan tudi kot bigraf.
Tehopedija razlaga Bipartite Graph
Dvostranski graf ima dva niza vozlišč, na primer A in B, z možnostjo, da mora biti pri risanju roba povezava med katero koli točko v A na katero koli točko v B. Če graf ne vsebuje nobenega neparni cikel (število vrstic v grafu je liho), potem je njegov spekter simetričen. Kromatsko število, ki je najmanjše število barv, potrebnih za barvanje tock, brez sosednjih tock, ki imajo iste barve, mora biti v primeru dvopartitnega grafa manjša ali enaka dvema. Vse vrste acikličnih grafov (grafov, ki nimajo ciklov grafov) so primeri dvostranskih grafov. Ciklični graf velja za dvostranski, če so vsi vključeni cikli enakomerne dolžine. Glede na Koningov linijski teorem o barvanju so vsi dvostranski grafi grafi 1. razreda.
Bipartitni grafi se v sodobni teoriji kodiranja pogosto uporabljajo, razen da se uporabljajo pri modeliranju razmerij.
