od nkole » Utorak, 04. Septembar 2018, 18:59
Evo kako otprilike može da se uradi drugačije.
Postavimo zadatak ovako: Dokazati da se čvorovi grafa mogu podeliti u dve grupe tako da svaki čvor u svojoj grupi ima manje suseda nego u drugoj grupi. To se poklapa sa onim što se traži u zadatku, tj. da ima [inlmath]0[/inlmath] suseda u svojoj i [inlmath]3[/inlmath] u drugoj ili [inlmath]1[/inlmath] suseda u svojoj i [inlmath]2[/inlmath] u drugoj.
Podelimo nasumično čvorove u grupe. Neka [inlmath]u[/inlmath] u svojoj grupi ima [inlmath]x[/inlmath], a u drugoj [inlmath]y[/inlmath] suseda i neka je [inlmath]A[/inlmath] broj grana između grupa. Ako prebacimo [inlmath]u[/inlmath] u drugu grupu, novi broj grana između grupa je [inlmath]A'=A+(x-y)[/inlmath]. Ako je [inlmath]x>y[/inlmath], onda [inlmath]A'>A[/inlmath], tj. broj grana između grupa se povećava.
Svaki čvor [inlmath]u[/inlmath] prebacimo u drugu grupu ako u svojoj grupi ima više suseda nego u drugoj. Tada će on u svojoj novoj grupi imati manje grana nego u staroj grupi. Ovaj algoritam se završava u konačno mnogo koraka jer se svakim prebacivanjem broj grana imeđu grupa povećava za bar [inlmath]1[/inlmath], a ne može se povećavati u beskonačnost jer je broj grana konačan.
Ima i potpitanje da li važi ako svako ima tačno [inlmath]4[/inlmath] poznanika. [inlmath]K_5[/inlmath] je kontraprimer.