MATEMANIJA

Imam zadatak da odredim broj grana u bipartitivnom grafu [inlmath]K_{2,n}[/inlmath].
Je l postoji formula iz teorije kako se odredjuje maksimalan broj grana ili bih trebao da zakljucim po nekoj logici?

U bipartitivnom grafu imaš dva disjunktna podskupa čvorova. Iz čvora koji pripada jednom od ta dva podskupa mogu ići grane samo ka čvorovima iz drugog podskupa. To jest, ne može postojati grana koja povezuje dva čvora unutar istog podskupa.

To znači, ako bismo posmatrali opštiji slučaj od tvog, [inlmath]K_{m,n}[/inlmath] (u tvom slučaju je [inlmath]m=2[/inlmath]), imali bismo dva disjunktna podskupa čvorova tog grafa, pri čemu je u prvom podskupu [inlmath]m[/inlmath], a u drugom [inlmath]n[/inlmath] čvorova. Iz prvog od tih [inlmath]m[/inlmath] čvorova prvog podskupa možemo povući najviše [inlmath]n[/inlmath] grana, budući da toliko ima čvorova u drugom podskupu. Iz drugog od tih [inlmath]m[/inlmath] čvorova možemo takođe povući najviše [inlmath]n[/inlmath] grana. Itd. do [inlmath]m[/inlmath]-tog čvora – i iz [inlmath]m[/inlmath]-tog čvora možemo takođe povući najviše [inlmath]n[/inlmath] grana. Pa, prema tome, koliko najviše grana možemo povući grana unutar tog grafa?

Ako sam dobro razumeo, mozemo povuci [inlmath]m\cdot n[/inlmath] grana?

Upravo tako.