Bipartite graphs

Tema ovog završnog rada su bipartitni grafovi. U prvom dijelu rada opisujemo osnovne pojmove iz teorije grafova koji su nam potrebni da bi razumjeli pojam bipartitnog grafa. Zatim, slijedi poglavlje o prepoznavanju bipartitnih grafova, u kojem su prikazani određeni tipovi bipartitnih grafova i njihova matrična karakterizacija. Iskazat ćemo neke teoreme, korolare te propozicije koje nam pobliže objašnjavaju svojstva bipartitnih grafova. U četvrtom poglavlju navodimo metrička svojstva bipartitnih grafova. Neki od bitnijih pojmova su radijus, dijametar i centar bipartitnog grafa. U zadnjem dijelu rada, obradit ćemo sparivanja na bipartitnim grafovima. Definirat ćemo osnovne pojmove bitne za sparivanje grafova te iskazati i dokazati Hallov teorem, kao i Teorem o braku. Za kraj, opisat ćemo mađarski algoritam, koji nam pomaže pronaći savršeno sparivanje u bipartitnom grafu s jednakobrojnim dijelovima particije, te odrediti postoji li takvo sparivanje uopće.