Politikus berteman dengan semua orang

politikus

Para Politikus di DPR

Di dalam Teori Graph , ada satu teorema yang cukup elegan, yang menjelasakan fenomena unik yang bisa saja terjadi didalam hubungan bermasayarakat. Teorema tersebut dinamakan Teorema Pertemanan (Frienship Theorem). secara informal Teorema pertemanan menyatakan :

Dalam suatu komunitas, jika setiap 2 orang mempunyai tepat 1 teman bersama maka ada 1 orang (disebut Politikus) yang berteman dengan semua orang di komunitas tersebut.

Nah… yang saya maksud dengan berteman adalah saling mengenal. Budi dan bejo  berteman artinya Budi dan Bejo saling mengenal. Jika kita menganggap komunitas sebgai graph sedangkan orang-orang didalamnya direpresentasikan dengan titik. Lalau 2 orang berteman bisa direpresentasikan sebgai 2 titik yang berdekatan (adjacent) maka secara formal teorema pertemanan menyatakan:

Teorema Pertemanan (TP): Diberikan graph berhingga G, jika setiap 2 titik di G mempunjyai tepat 1 tetangga bersama maka terdapat 1 titik yang berdekatan dengan semua titik di G.

Perlu dicatat bahwa ada graph yang memenuhi TP, yaitu graph kincir angin (Windmill Graph) perhatikan gambar disamping, kincir angin graphdengan u adalah politikus. Bahkan Graph kincir angin adalah satu-satunya graph yang memenuhi TP.  Karena keberadaan politikus hanya dimungkinkan dengan graph Kincir angin.

Yang amat menarik ternyata TP tidak berlaku untuk graph tak-hinga, Dengan kata lain ada graph tak-hingga yang setiap pasang titiknya mempunyai 1 tetangga bersama tetapi tanpa adanya politikus. Untuk mengkontruksikan Graph tak-hingga seperti itu mudah saja. bisa kita mulai dengan 5-siklik kemudian terus tambahkan 1 tetangga bagi setiap pasang titik yang belum mempunyai  tetangga bersama

Bukti :

Ada banyak cara membuktikan TP tetapi saya akan menggunakan cara dari Paul ErdősAlfréd Rényi, and Vera T. Sós. Merekalah yang pertamakali menerbitkan TP. Akan dibuktikan dengan cara kontradiksi. Dinotasikan G graph berhingga dengan setiap pasang titiknya mempunyai 1 tetangga bersama tetapi tanpa ada politikus. Akan ditunjukkan G menimbulkan kontradiksi.

Kita akan membuktikan dengan 2 langkah:

4-siklik

4-siklik

Langkah (1): Akan dibuktian bahwa G adalah regular yaitu semua titik mempunyai derajat yang sama. Perlu diperhatikan bahwa antiseden dari TP mengakibatkan tidak ada 4-siklik di G, kita sebut saja Kondisi-C4. Pertama-tama kita akan menunjukkan bahwa setiap 2 titik yang tidak berdekatan u dan v mempunyai derajat yang sama d\left(u\right)=d\left(v\right). Andaikan d\left(u\right)=k, dengan w_{1},\ldots w_{k} adalah tetangga dari u. Berdasakan antiseden TP maka salah-satu dari w_i, sebut saja w_2 berdekatan ke v dan w_2 berdekatan dengan salah satu  w_i lainnya sebut saja w_1. Kondisi tersebut diilustrasikan dengan gambar di bawah:

graph2

Titik v dan w_1 mempunyai tetangga bersama w_2. Sedangkan v dan w_{i},\,\left(i\geq2\right) mempunyai tetangga bersama z_{i},\,\left(i\geq2\right). Berdasarkan kondisi-C4, semua z_i haruslah berbeda. Disimpulkan

d\left(u\right)\geq k=d\left(v\right), berdasarkan simetri diperoleh d\left(u\right)=d\left(v\right)=k

Untuk menyelesaikan pembuktian, dapat diamati bahwa sebarang titik yang berbeda dari w_2 tidak berdekatan dengan u maupun v dan mempunyai derajat k berdasarkan apa yang telah kita buktikan diatas. Begitupula w_2 mempunyai titik-titik tak bertetangga juga berderajat k. Itu berarti G adalah reguler-k.

Jumlahkan semua k tetangga dari dari u diperoleh k^2. Karena setiap titik (kecuali u) mempunyai 1 tetangga bersama dengan u. Telah dihitung setiap titik sebanyak sekali kecuali untuk u yang dihitung k  kali.  Jadi banyaknya titik di G4 adalah:

n=k^2-1   (i)

Langkah (2): Berdasarkan persamaan (i), diketahui nilai k haruslah lebih besar daripada 2. Karena untuk k\leq2 diperoleh  G=K_1 dan G=K_2 yang hanya merupakan graph kincir angin trivial. Selanjutnya akan dibahas Matriks adjacency A. Berdasarkan Langkah (1) Setiap baris mempunyai 1 tepat sebanyak k. Berdasafrkan anteseden TP, untuk setiap 2 baris tepat terdapat 1 kolom yang keduanya bernilai 1, sedangkan diagonal utamnya bernilai 0, diperoleh :

A^{2}=\left[\begin{array}{cccc}k & 1 & \ldots & 1\\1 & k & & 1\\\vdots & & \ddots & \vdots\\1 & \cdots & 1 & k\end{array}\right]=\left(k-1\right)I+J.

Dari ekspresi diatas diketahui bahwa A^2 mempunyai nilai eigen n+k-1=k^2 dan k-1  muncul sebanyak n-1 kali. Nilai eigen dari A^2 adalah kuadrat dari nilai eigen A yaitu k dan \pm\sqrt{k-1}. Diketahui tr\left(A\right)=0 dan penjumlahan nilai-nilai eigen A sama dengan tr\left(A\right). Jika \sqrt{k-1} muncul sebanyak r kali dan \sqrt{k-1} muncul sebanyak s kali diperoleh

k+\left(r-s\right)\sqrt{k-1}=0

Berakibat k^{2}=\left(r-s\right)^{2}\left(k-1\right) yang berarti k-1 membagi k^2. Karena k adalah bilangan bulat maka solusi yang mungkin hanyalah k=1,2. Diperoleh graph K_1 dan K_2, padalaha dari yang telah kita bahas diatas kedua graph tersebut telah dikecualikan, didapat Kontradiksi maka pembutian telah lengkap.

QED

Advertisements

About Aria Turns

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika
This entry was posted in graph theory, pembuktian and tagged , , , , . Bookmark the permalink.

One Response to Politikus berteman dengan semua orang

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s