Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI GRAFOVI

Grafovi: Rasporediti prijatelje u dve sobe

Grafovi: Rasporediti prijatelje u dve sobe

Postod nkole » Nedelja, 05. Avgust 2018, 08:14

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.
nkole  OFFLINE
 
Postovi: 12
Zahvalio se: 4 puta
Pohvaljen: 1 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +2

Re: Grafovi: Rasporediti prijatelje u dve sobe

Postod ubavic » Nedelja, 05. Avgust 2018, 14:56

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].
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 623
Zahvalio se: 385 puta
Pohvaljen: 641 puta

Re: Grafovi: Rasporediti prijatelje u dve sobe

Postod 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.
nkole  OFFLINE
 
Postovi: 12
Zahvalio se: 4 puta
Pohvaljen: 1 puta


Povratak na GRAFOVI

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 0 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 10:13 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs