Kegiatan dalam pergaulan sehari-hari, apabila kita perhatikan, pelajari, dan maknai, dapat memperkaya pengetahuan dan wawasan kita. Termasuk suatu kegiatan sederhana, yaitu bersalaman. Coba kita perhatikan dua orang yang bersalaman. Masing-masing orang itu mengulurkan 1 buah tangan, sehingga terjadi dua uluran tangan. Dua uluran tangan ini menghasilkan satu buah atau satu kali jabat-tangan. Jadi, banyaknya jabat-tangan adalah setengahnya dari banyaknya uluran tangan. Hal sesederhana ini, apabila kita kembangkan, akan memberikan hasil-hasil yang tidak kita bayangkan sebelumnya.
Sekarang, perhatikan contoh berikut. Dalam suatu acara ulang tahun, terdapat 20 orang tamu undangan yang tidak saling mengenal. Untuk acara yang lebih akrab, si empunya hajat ingin setiap tamu undangan untuk berjabat tangan dan saling berkenalan dengan 19 tamu lainnya. Dengan demikian, ada berapa buah jabat-tangan yang terjadi dalam acara itu? Dalam contoh ini, setiap orang mengulurkan tangan sebanyak 19 kali sehingga secara keseluruhan terdapat 20.19 = 380 kali uluran tangan. Karena banyaknya jabat-tangan adalah setengahnya dari banyaknya uluran tangan, dapat kita simpulkan bahwa banyaknya jabat-tangan yang terjadi adalah 380/2 = 190 buah. Secara umum, apabila terdapat n orang tamu dan setiap tamu bersalaman dengan (n-1) orang tamu lainnya, maka akan terjadi n(n-1) buah uluran tangan, sehingga banyaknya jabat-tangan yang terjadi adalah n(n-1)/2.
Kita tentunya tahu bahwa suatu segitiga tidak memiliki diagonal. Suatu segiempat memiliki dua buah diagonal. Dengan menggambarkan suatu segilima, kita bisa tahu bahwa segilima memiliki 5 buah diagonal. Namun kita akan kerepotan apabila harus menjawab ada berapa diagonal yang dimiliki oleh suatu segi-100? Ternyata dengan mempelajari jabat-tangan kita dapat menjawab pertanyaan ini. Dalam suatu segibanyak/poligon, setiap titik sudut merupakan titik persekutuan dari dua sisi. Sebagai contoh, dalam segiempat ABCD (lihat gambar di bawah ini), titik A merupakan titik persekutuan antara sisi AB dan AD. Titik B merupakan titik persekutuan antara AB dan BC, dan seterusnya.
Segiempat tersebut dapat juga dipandang sebagai suatu graf G(V,E), dengan V = {A, B, C, D} dan E = {(A,B), (B,C), (C,D), (D,A)}. Demikian juga suatu segi-n dapat dipandang sebagai suatu graf Gn(Vn,En) dengan Vn = {v1, v2, v3, …, vn} dan En = {(v1,v2), (v2,v3), (v3,v4), …, (vn-1,vn), (vn,v1)}. Suatu diagonal dalam segi-n tersebut menghubungkan suatu verteks vi ∊ Vn ke suatu verteks lain vj ∊ Vn dengan ketentuan (vi,vj) ∉ En. Dengan kata lain, suatu diagonal menghubungkan suatu verteks dengan verteks lain yang tidak adjacent dengannya. Perhatikan bahwa setiap verteks v* pada graf tersebut memiliki sebanyak (n – 3) verteks lain v*1, v*2, …, v*n-3 yang tidak adjacent dengannya, sehingga dari v* dapat dibuat (n-3) buah diagonal. Dengan menganggap v*, v*1, v*2, …, v*n-3 adalah sekumpulan orang, v* berjabat-tangan dengan (n-3) orang lain sehingga v* melakukan (n-3) kali uluran tangan. Karena dalam graf tersebut terdapat n buah verteks, maka secara keseluruhan terjadi n(n-3) uluran tangan. Sebagaimana diuraikan di awal tulisan ini, banyaknya jabat-tangan adalah setengahnya dari banyaknya uluran tangan sehingga banyaknya jabat-tangan yang terjadi adalah n(n-3)/2, yang sekaligus merupakan banyaknya diagonal pada segi-n tersebut. Jadi, dapat kita simpulkan bahwa “banyaknya diagonal suatu segi-n adalah n(n-3)/2”. Dengan demikian, banyaknya diagonal dari suatu segi-100 adalah 100.(100-3)/2 = 100.97/2 = 4850.
Dalam teori graf sendiri terdapat suatu Lemma yang disebut dengan “Lemma Jabat-tangan” yang menyatakan bahwa banyaknya tepi (edge) dari suatu graf adalah setengah dari jumlah derajat semua verteks pada graf tersebut. Jadi, apabila G(V,E) adalah suatu graf dengan V = {v1, v2, …, vn} dan d(vi) adalah derajat verteks vi ∊ V, maka banyaknya tepi (edge) dalam graf tersebut adalah:
SETETES ILMU DALAM JABAT TANGAN
Kegiatan dalam pergaulan sehari-hari, apabila kita perhatikan, pelajari, dan maknai, dapat memperkaya pengetahuan dan wawasan kita. Termasuk suatu kegiatan sederhana, yaitu bersalaman. Coba kita perhatikan dua orang yang bersalaman. Masing-masing orang itu mengulurkan 1 buah tangan, sehingga terjadi dua uluran tangan. Dua uluran tangan ini menghasilkan satu buah atau satu kali jabat-tangan. Jadi, banyaknya jabat-tangan adalah setengahnya dari banyaknya uluran tangan. Hal sesederhana ini, apabila kita kembangkan, akan memberikan hasil-hasil yang tidak kita bayangkan sebelumnya.
Sekarang, perhatikan contoh berikut. Dalam suatu acara ulang tahun, terdapat 20 orang tamu undangan yang tidak saling mengenal. Untuk acara yang lebih akrab, si empunya hajat ingin setiap tamu undangan untuk berjabat tangan dan saling berkenalan dengan 19 tamu lainnya. Dengan demikian, ada berapa buah jabat-tangan yang terjadi dalam acara itu? Dalam contoh ini, setiap orang mengulurkan tangan sebanyak 19 kali sehingga secara keseluruhan terdapat 20.19 = 380 kali uluran tangan. Karena banyaknya jabat-tangan adalah setengahnya dari banyaknya uluran tangan, dapat kita simpulkan bahwa banyaknya jabat-tangan yang terjadi adalah 380/2 = 190 buah. Secara umum, apabila terdapat n orang tamu dan setiap tamu bersalaman dengan (n-1) orang tamu lainnya, maka akan terjadi n(n-1) buah uluran tangan, sehingga banyaknya jabat-tangan yang terjadi adalah n(n-1)/2.
Kita tentunya tahu bahwa suatu segitiga tidak memiliki diagonal. Suatu segiempat memiliki dua buah diagonal. Dengan menggambarkan suatu segilima, kita bisa tahu bahwa segilima memiliki 5 buah diagonal. Namun kita akan kerepotan apabila harus menjawab ada berapa diagonal yang dimiliki oleh suatu segi-100? Ternyata dengan mempelajari jabat-tangan kita dapat menjawab pertanyaan ini. Dalam suatu segibanyak/poligon, setiap titik sudut merupakan titik persekutuan dari dua sisi. Sebagai contoh, dalam segiempat ABCD (lihat gambar di bawah ini), titik A merupakan titik persekutuan antara sisi AB dan AD. Titik B merupakan titik persekutuan antara AB dan BC, dan seterusnya.
Segiempat tersebut dapat juga dipandang sebagai suatu graf G(V,E), dengan V = {A, B, C, D} dan E = {(A,B), (B,C), (C,D), (D,A)}. Demikian juga suatu segi-n dapat dipandang sebagai suatu graf Gn(Vn,En) dengan Vn = {v1, v2, v3, …, vn} dan En = {(v1,v2), (v2,v3), (v3,v4), …, (vn-1,vn), (vn,v1)}. Suatu diagonal dalam segi-n tersebut menghubungkan suatu verteks vi ∊ Vn ke suatu verteks lain vj ∊ Vn dengan ketentuan (vi,vj) ∉ En. Dengan kata lain, suatu diagonal menghubungkan suatu verteks dengan verteks lain yang tidak adjacent dengannya. Perhatikan bahwa setiap verteks v* pada graf tersebut memiliki sebanyak (n – 3) verteks lain v*1, v*2, …, v*n-3 yang tidak adjacent dengannya, sehingga dari v* dapat dibuat (n-3) buah diagonal. Dengan menganggap v*, v*1, v*2, …, v*n-3 adalah sekumpulan orang, v* berjabat-tangan dengan (n-3) orang lain sehingga v* melakukan (n-3) kali uluran tangan. Karena dalam graf tersebut terdapat n buah verteks, maka secara keseluruhan terjadi n(n-3) uluran tangan. Sebagaimana diuraikan di awal tulisan ini, banyaknya jabat-tangan adalah setengahnya dari banyaknya uluran tangan sehingga banyaknya jabat-tangan yang terjadi adalah n(n-3)/2, yang sekaligus merupakan banyaknya diagonal pada segi-n tersebut. Jadi, dapat kita simpulkan bahwa “banyaknya diagonal suatu segi-n adalah n(n-3)/2”. Dengan demikian, banyaknya diagonal dari suatu segi-100 adalah 100.(100-3)/2 = 100.97/2 = 4850.
Dalam teori graf sendiri terdapat suatu Lemma yang disebut dengan “Lemma Jabat-tangan” yang menyatakan bahwa banyaknya tepi (edge) dari suatu graf adalah setengah dari jumlah derajat semua verteks pada graf tersebut. Jadi, apabila G(V,E) adalah suatu graf dengan V = {v1, v2, …, vn} dan d(vi) adalah derajat verteks vi ∊ V, maka banyaknya tepi (edge) dalam graf tersebut adalah:
[pmath]delim{|}{E}{|}=sum{i=1}{n}{d(v_{i})}[/pmath]
Materi lain yang berkenaan dengan teori graf atau penerapannya dapat diunduh pada tautan berikut: graf Euler
Bagikan ini:
Most visitors also read :
BERKENALAN DENGAN NILAI DAN VEKTOR EIGEN
DEKOMPOSISI NILAI SINGULAR (SINGULAR VALUE DECOMPOSITION)
MATRIKS AKAR KUADRAT
SOAL DAN PEMBAHASAN ANALISIS KOMPONEN UTAMA