Louiscahyadi 17 Report post Posted July 19, 2015 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
erlang 44 Report post Posted July 21, 2015 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
erlang 44 Report post Posted July 23, 2015 Dalam pesta itu ada permainan yang sangat asikdipilih 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 baristerus 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
donjar 40 Report post Posted November 3, 2015 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 - 1Misalnya 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