Jump to content
Sign in to follow this  
erlang

Graph Theory 1

Recommended Posts

Di sebuah ruangan terdapat finite buah orang. Diketahui bahwa untuk setiap 4 orang, terdapat setidaknya 3 orang yang saling kenal atau saling tidak kenal. Buktikan bahwa orang-orang pada ruangan tersebut dapat dipisahkan ke dua ruangan A dan B sehingga pada ruangan A semua orang saling kenal dan pada ruangan B semua orang saling tidak kenal.


Share this post


Link to post
Share on other sites

kakak admin atau moderator, tanpa suatu alasan yang jelas soal saya ter-post dua kali, tolong hapus yang ini ya (setelah saya cari-cari nampaknya member biasa tidak dapat menghapus post), terima kasih anda.


Share this post


Link to post
Share on other sites

kakak admin atau moderator, tanpa suatu alasan yang jelas soal saya ter-post dua kali, tolong hapus yang ini ya (setelah saya cari-cari nampaknya member biasa tidak dapat menghapus post), terima kasih anda.

 

untuk selanjutnya, silahkan gunakan tombol "report" yang di sebelah "quote" itu loh :)

Share this post


Link to post
Share on other sites

anyways, solusi agak berantakan


 



Lemma - syarat soal ekuivalen dengan: untuk setiap sub-graph dengan 4 vertex, ada setidaknya satu vertex yang derajatnya 0 atau 3.


Bukti singkat: misalkan tidak, maka kemungkinan derajatnya 1111, 1122, atau 2222. nanti bentuknya =, U, atau kotak; tiga-tiganya tidak memenuhi syarat.


 


Jika hanya ada 4 orang dengan mudah bisa dibuktikan.


Sekarang misalkan untuk m orang di kelompok A dan n orang di kelompok B (sehingga ada $m+n$ orang) soal benar.


Akan dibuktikan untuk $m+n+1$ orang juga memenuhi.


 


Tambahkan orang baru, sebut saja $C$.


Notasikan orang-orang di kelompok A dan B sebagai $A_1, A_2, \ldots, A_m, B_1, B_2, \ldots, B_n$.


Jika C tidak berhubungan dengan orang manapun dari kelompok B, selesai - cukup masukkan si C ke kelompok B.


Sekarang misalkan si C ini berhubungan dengan $B_1$.


Jika $m=1$ mudah: jika C berhubungan dengan $A_1$ masukkan C ke kelompok A. Jika tidak, masukkan C dan $B_1$ ke kelompok A, $A_1$ ke kelompok B.


Jika $m=2$: tinjau C, $A_1$, $A_2$, $B_1$. Menurut lemma haruslah ada yang terhubung ke semua


atau tidak terhubung ke semua $\implies$ tidak mungkin; C terhubung ke $B_1$, $A_1$ terhubung ke $A_2$.


Jika C ataupun $B_1$ terhubung ke $A_1$ dan $A_2$ maka bawa orang yang bersangkutan ke kelompok A, selesai.


Jika $A_1$ ataupun $A_2$ terhubung ke $B_1$ dan C maka bawa C dan $B_1$ ke kelompok A dan bawa $A_2$ ataupun $A_1$ (yang tidak terhubung ke tiga lainnya) ke kelompok B. Selesai.


 


Sekarang misalkan untuk $m-1$ benar, akan dibuktikan untuk $m$ benar.


Maka ada $m$ orang di kelompok A saat ini.


Tinjau C, $B_1$, $A_1$, $A_2$. Jika $A_1$ yang terhubung ke $C$ dan $B_1$ maka untuk semua sub-graph 4 vertex yang mengandung C, $B_1$, dan $A_1$ sudah memenuhi syarat soal. Namun sekarang kita bisa hilangkan $A_1$ dan lihat sebagai kasus dengan $m$ orang di kelompok A, yang sudah diasumsikan benar.


Sekarang jika C ataupun $B_1$ yang terhubung ke $A_1$ dan $A_2$:


Kita bisa WLOG misalkan C terhubung ke $A_1$ dan $A_2$. Sekarang tinjau C, $B_1$, $A_2$, $A_3$.


Jika $B_1$ yang terhubung ke $A_2$ dan $A_3$ (kita sudah anggap kalau $A_2$ atau $A_3$ yang terhubung ke C dan $B_1$, selesai), tinjau C, $B_1$, $A_1$, $A_3$.


Mau C yang terhubung ke $A_3$ ataupun $B_1$ yang terhubung ke $A_1$, pasti ada satu titik di kelompok A yang terhubung ke C dan $B_1$, yang mana kita sudah anggap soal selesai by induction.


Sekarang jika C yang terhubung ke $A_2$ dan $A_3$.


Teruskan, maka C lah yang terhubung ke semua titik di kelompok A, kecuali satu titik, sebut $A_{m+1}$. (Ini bisa dianggap seperti ini; jika ada yang terhubung ke $B_1$, lihat jalannya argumen di atas)


Maka masukkan C ke dalam kelompok A dan pindahkan $A_{m+1}$ ke kelompok B.


 


Sekarang jika C terhubung ke beberapa orang di kelompok B.


Jika C terhubung ke semua titik kecuali satu di kelompok A maka permasalahan selesai; masukkan C ke kelompok A dan jika perlu keluarkan satu orang dari kelompok A dan pindahkan ke kelompok B. Sekarang masalahnya hanya jika orang dari kelompok B lah yang terhubung ke orang-orang di kelompok A. Dengan kata lain, C tidak terhubung ke siapapun di kelompok A, yang mana permasalahan juga selesai; masukkan saja C ke kelompok B.



Maka terbukti.



 


mati panjang banget... mungkin sambil menggambar akan memudahkan, haahaha


Edited by donjar

Share this post


Link to post
Share on other sites

Jika $m=1$ mudah: jika C berhubungan dengan $A_1$ masukkan C ke kelompok A. Jika tidak, masukkan C dan $B_1$ ke kelompok A, $A_1$ ke kelompok B.

sebentar memang pasti bisa masukin $A_1$ ke kelompok B? kan bisa aja $A_1$ mengenal seseorang di kelompok B Edited by sayakalah

Share this post


Link to post
Share on other sites

sebentar memang pasti bisa masukin $A_1$ ke kelompok B? kan bisa aja $A_1$ mengenal seseorang di kelompok B

 

wah sialan, kasusnya nambah lagi dong ya :v

Share this post


Link to post
Share on other sites

Klo mau formal graph theory(biar nulis solusinya ga ambigu) kita ubah soalnya menjadi seperti ini:

 

Diberikan sebuah graph $K_n$ yang semua garis nya di warnai oleh warna biru atau warna merah, sedemikian sehingga untuk setiap $K_4$ terdapat monocolored $K_3$. Maka terdapat $K_n=K_p \cup K_q$ dimana $p+q=n$ dengan $K_p$ dan $K_q$ keduanya monocolored.


Ambil $p$ terbesar sedemikian sehingga $K_p$ adalah subgraph terbesar dari $K_n$ yang monocolored, katakanlah berwarna merah. Misalkan subgraph sisa nya adalah $K_q$ dengan $q=n-p$. Kita cukup membuktikan bahwa untuk setiap $v$ dan $w$ verteks di $K_q$ maka garis yang mengubungkan $v$ dan $w$ (notasikan $\{v, w\}$) berwarna biru.

 

Misalkan tidak demikian, yakni terdapat $v$ dan $w$ di $K_q$ sehingga $\{v,w\}$ berwarna merah.

Kita sebut sebuah segi empat dengan empat verteks $\{x, y, z, s\}$ bad jika sisi yang berseberangan punya warna sama tapi yg share common verteks warna nya beda.
[Pake gambar warna-warni lebih enak sbnrnya]
 

 

Jika terdapat paling sedikit dua verteks di $K_p$ yang terkoneksi dengan warna biru denga  $v$, ambil dua diantaranya katakan $a$ dan $b$ di $K_p$, karena $\{a,b\}$ berwarna merah maka $\{a, b, v\}$ bukan monocolored, dan karena $\{b,v\}$ biru dan $\{v, w\}$  merah maka  $\{ b, v, w\}$ bukan monocolored. Sekarang apabila $\{a, w\}$ dan $\{b, w\}$ juga merah, maka pindahkan $w$ ke dalam $K_p$ maka diperoleh monocolored $K_{p+1}$ kontradiksi dengan kemaksimalan $K_p$.

 

jadi $\{a, b, v, w\}$ tidak mempunyai monocolored $K_3$.

 

Jadi hanya ada paling banyak satu buah verteks di $K_p$ yang terkoneksi dengan warna biru ke $v$. Secara similar, hanya ada paling banyak satu verteks di $K_p$ yang terkoneksi dengan warna biru ke $w$.

Jadi ada tiga kasus (sebenarnya ada empat cuma ada dua similar)

1) Jika dari $K_p$ terdapat satu biru ke $v$ dan satu biru ke $w$, katakanlah oleh $a$ dan $b$. Maka $\{a, b, v, w\}$ tidak mempunyai multicolored $K_3$.

2) Jika dari $K_p$ terdapat satu biru ke $v$ katakanlah oleh $a$ namun tidak ada biru ke $w$. Maka pindahkan $a$ ke $K_q$ dan masukkan $v$ dan $w$ ke $K_p$, sekarang jadinya kita punya $K_{p+1}$ yang monocolored, kontradiksi dengan kemaksimalan $K_p$.

3) Jika dari $K_p$ semua garis ke $w$ dan $v$ adalah merah. Maka pindahkan $v$ dan $w$ ke $K_{p}$ sehingga kita peroleh $K_{p+2}$ yang monocolored, kontradiksi lagi.

Jadi $\{v, w\}$ tidak boleh merah, sehingga $K_q$ monocolored.

Edited by Adri

Share this post


Link to post
Share on other sites

Kita sebut sebuah segi empat dengan empat verteks $\{x, y, z, s\}$ bad jika

[Pake gambar warna-warni lebih enak sbnrnya]

Ini apa maksudnya jika apa?

 

Misalkan tidak demikian, yakni $\{v,w\}$ berwarna merah. Jika terdapat paling sedikit dua verteks di $K_p$ yang terkoneksi dengan warna biru di $v$, ambil dua diantaranya katakan $a$ dan $b$, maka $\{a, b, v, w\}$ tidak mempunyai monocolored $K_3$.

well saya gangerti part atas nya sih (yang saya quote di atas), tapi kan bisa saja $\{a,v\}$ dan $\{a,w\}$ berwarna biru, akibatnya ada $K_3$ yang monocolored? tapi entahlah mungkin ini sudah diantisipasi dengan definisi bad diatas.

 

tapi saya cukup suka dengan ide extremalnya sih bisa menghilangkan beberapa kasus annoying

Edited by sayakalah

Share this post


Link to post
Share on other sites

Ini apa maksudnya jika apa?

 

well saya gangerti part atas nya sih (yang saya quote di atas), tapi kan bisa saja $\{a,v\}$ dan $\{a,w\}$ berwarna biru, akibatnya ada $K_3$ yang monocolored? tapi entahlah mungkin ini sudah diantisipasi dengan definisi bad diatas.

 

tapi saya cukup suka dengan ide extremalnya sih bisa menghilangkan beberapa kasus annoying

 

 

Saya ngetik sambil ngerjain jdnya yg bad ujung2nya ga kepake hahaha :D intinya rectangle yg sisi sejajar nya same color itu bad.

 

 

Well klo $\{a,v\}$ biru dan $\{a,w\}$ biru krn asumsi kita $\{v,w\}$ merah maka $\{a,v,w\}$ tidak monocolored dong. Ini yg namanya bad.  Saya tambahin penjelasan nya diatas.. mgkn asumsi nya ga saya state :o

 

 

EDIT: Oh saya ngerti maksudnya kamu mgkn klo $\{a, w\}$   dan $\{b, w\}$ merah.. tp ud di fix ama extremal nya, tinggal pindahkan $w$  :D

Edited by Adri

Share this post


Link to post
Share on other sites

Wah kok graph teory sepertinya banyak peminat tp sampai hari ini gw masih nggak ngerti ngerti

Sebenarnya graph theory itu ga gt bnyk macem2 klo utk SMA.. cm mgkn ngerti istilah aja..

Contoh verteks itu titik, edge itu garis.. $K_n$ itu simple complete graph, yaitu graph dengan $n$ titik dan tiap satu titik nya terhubung tepat satu kali dengan $n-1$ titik lain (tidak dgn dia sendiri.)

Monocolored (atau harusnya saya tulis monochromatic cm ngetik nya susah klo di HP) itu artinya warna edge sama atau verteks sama

Share this post


Link to post
Share on other sites

hmm bener seharusnya, solusi saya sih gini (gatausih bener ato engga) 



jelas jika ada 2,3,4 orang maka statement di soal yang ingin dibuktikan itu benar.


misalkan jika ada $n$ orang statement benar.


akan dibuktikan untuk $n+1$ benar.


jadi ada n orang yang sudah dibagi ke dua group yang, saling kenal atau saling tidak kenal.


misalkan group yang saling kenal itu group $A$, group yang saling tidak kenal itu $B$.


pertama kita pastikan jika ada orang di group $B$ yang kenal semua orang di group A, pindahkan orang itu ke group $A$ (kalau ada banyak orang jangan dipindahkan bersamaan karena bisa saja kondisi group $A$ tidak terpenuhi), jadi kini tidak ada orang di group $B$ yang mengenal semua orang di group $A$.


orang-orang di group $A$ itu $a_1,a_2,...,a_k$, orang-orang di group $B$ itu $b_1,b_2,...,b_m$.


consider orang ke $n+1$ yang belum masuk ke group manapun, misalkan orang ini adalh $c$.


jika $c$ tidak mengenal seorangpun di group $B$, maka tinggal masukan $c$ ke group $B$.


jika $c$ mengenal setidaknya 1 orang di group $B$, w.l.o.g. $c$ mengenal $b_1$.


perhatikan ada setidaknya satu orang di group $A$ yang tidak mengenal $b_1$, w.l.o.g. $b_1$ tidak mengenal $a_1$.


consider $\{c,a_1,b_1,a_j\}$ dimana $2\le j\le k$, perhatikan ada 3 orang yang saling kenal atau saling tidak kenal.


Karena {$a_1$,$a_j$} saling kenal, dan {$c,b_1$} saling kenal, maka tidak ada 3 orang yang saling tidak kenal $\implies$ ada tiga orang yang saling kenal.


karena $\{a_1,b_1\}$ saling tidak kenal, bisa dipastikan $\{c,a_j\}$ saling kenal.


berarti $c$ mengenal $a_2,a_3,...,a_k$.


jika $c$ mengenal $a_1$ maka kita bisa masukkan $c$ ke $A$.


jika $c$ tidak mengenal $a_1$, consider 2 kasus: $a_1$ mengenal setidaknya satu orang di $B$, atau $a_1$ tidak mengenal siapapun di $B$.


kasus 1:  $a_1$ mengenal setidaknya satu orang di $B$


w.l.o.g. orang yang dikenal $a_1$ adalah $b_2$.


consider $a_1,b_1,b_2,c$ jika $a_1,c$ tidak saling kenal, mudah dilihat kalau tidak ada 3 orang yang saling kenal atau saling tidak kenal.


maka $a_1,c$ saling kenal. maka kita bisa memasukkan $c$ ke $A$.


kasus 2: $a_1$ tidak mengenal siapapun di $B$


maka kita bisa pindahkan $a_1$ ke $B$ dan $c$ ke $A$.


 


maka kita selalu bisa memisahkan  $n+1$ orang ke 2 group, satu group saling kenal dan satu group saling tidak kenal, jika kita selalu bisa memisahkan  $n$ orang ke 2 group, satu group saling kenal dan satu group saling tidak kenal.  


 induksi selesai



Edited by sayakalah

Share this post


Link to post
Share on other sites

Solusi saya menggunakan bahasa awam :p harusnya tanpa pengalaman di graph theory udah bisa ngerti

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  

×