Jump to content
Sign in to follow this  
Louiscahyadi

Dalam Suatu Pesta

Recommended Posts

Dalam suatu pesta, setiap orang  mengenal sedikitnya 3 orang lain. Buktikan terdapat $n$ orang diantaranya dengan $n$ genap dan $n \geq 4$ dapat duduk di suatu meja bundar sehingga setiap orang mengenal kedua orang di sebelahnya. 


Share this post


Link to post
Share on other sites

Dalam "bahasa graph":


Diberikan sebuah graph dengan $k\ge 4$ vertex, dan degree setiap vertex lebih dari sama dengan 3. Buktikan terdapat cycle dengan genap buah vertex.


Share this post


Link to post
Share on other sites

Dalam pesta itu ada permainan yang sangat asik



dipilih satu orang random (orang 1)


terus pilih orang yang kenal dia untuk berdiri di belakangnya (orang 2)


pilih orang yang kenal orang dua yang belom baris untuk berdiri dibelakang orang 2 (ini orang 3)


dan selama bisa, pilih orang k+1 untuk berdiri di belakang orang k jika masih ada orang yang kenal orang k tapi belum ikut baris


terus tinggal liat barisan ini deh nanti ada cycle evennya (loh kenapa)



asik sekali kan (saya dulu pernah main permainan ini loh)


Share this post


Link to post
Share on other sites


Klaim: Pasti ada cycle.


Bukti: Ambil aja terus rentetan orang-orangnya. Kan setiap orang kenalannya tiga, ntar juga pasti balik dan membentuk cycle.


 


Misalkan cycle ini ganjil. Kalau di orang-orang di cycle tersebut, ada 2 orang ga berdekatan yang kenalan, ntar cyclenya jadi kebagi, satu ganjil satu genap.


Contoh: cycle 1 - 2 - 3 - 4 - 5 - 6 - 7 - 1


Misalnya 1 kenal 5. Ntar kebagi jadi 1 - 2 - 3 - 4 - 5 - 1 dan 5 - 6 - 7 - 1 - 5. Kan ada yang ganjil dan yang genap tuh. Berarti ada deh yang genap.


 


Kalau nggak ada, berarti setiap orang punya kenalannya masing-masing. Berarti setiap orang itu bisa dibuat kelompok kenalan gitu: kelompok 1 isinya orang 1 dan kenalannya, kelompok 2 isinya 2 dan kenalannya dst... Nanti kenalannya juga punya kenalan, cabang lagi...


Kalau ada orang di kelompok a yang kenal orang di kelompok b yang bukan orang utama (di cycle utama) (which is inevitable karena banyaknya orang finite), berarti ada cycle yang nempel ke cycle utama tuh (kayak naftalen lol). either cycle barunya genap, atau ganjil --> cycle besar yang gabungin keduanya genap. hore selesai.



Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

×