Grafovi: Rasporediti prijatelje u dve sobe

PostPoslato: Nedelja, 05. Avgust 2018, 08:14
od nkole
U nekoj grupi, svaki čovek ima tačno [inlmath]3[/inlmath] poznanika. Dokazati da možemo smestiti sve ljude iz te grupe u dve sobe, tako da svaki čovek ima najviše jednog poznanika u sobi u kojoj se nalazi.

[inlmath]n[/inlmath] (broj osoba) je parno pošto je graf [inlmath]3[/inlmath]-regularan, ako znači nešto.

Re: Grafovi: Rasporediti prijatelje u dve sobe

PostPoslato: Nedelja, 05. Avgust 2018, 14:56
od ubavic
Kako je graf [inlmath]3[/inlmath]-regularan, može se pravilno obojiti sa [inlmath]4[/inlmath] boje. Neka su to boje [inlmath]c_1,c_2,c_3,c_4[/inlmath]. Sada u jedan skup (u jednu sobu) stavi sve čvorove (ljude) obojene bojama [inlmath]c_1[/inlmath] i [inlmath]c_2[/inlmath], u drugi skup (drugu sobu) stavi sve čvorove (ljude) obojene bojama [inlmath]c_3[/inlmath] i [inlmath]c_4[/inlmath].

Re: Grafovi: Rasporediti prijatelje u dve sobe

PostPoslato: Utorak, 04. Septembar 2018, 18:59
od nkole
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.