Bipartitni graf

Izvor: Hrvatska internetska enciklopedija
Skoči na:orijentacija, traži

Bipartitni graf, vrsta grafa u teoriji grafova. Za nj vrijedi [math]\displaystyle{ G = (V,E) }[/math] i za čiji se skup vrhova [math]\displaystyle{ V }[/math] može podijeliti u dva disjunktna skupa [math]\displaystyle{ A }[/math] i [math]\displaystyle{ B }[/math] sa svojstvom da svaki brid u [math]\displaystyle{ E }[/math] povezuje jedan vrh iz [math]\displaystyle{ A }[/math] i jedan vrh iz [math]\displaystyle{ B }[/math]. Kod bipartitnog grafa kromatski broj je 2. Ciklički graf se može obojati u dvije boje na samo dva načina. [1]

Izvori

  1. Prirodoslovno-matematički fakultet u Zagrebu Tomislav Bujanović: Grafovi i njihova svojstva (pristupljeno 26. svibnja 2020.)