Teorema Salaman

Antara Salaman, Graf, dan Kombinasi

 

(Sumber gambar: merdeka.com)

Kerap kali ketika bertemu seseorang kita melakukan jabat tangan atau salaman bukan? Sekarang coba bayangkan di suatu ruangan anda bertemu dengan 4 sahabat dan masing-masing dari diantara kalian bersalaman. Setiap orang akan melakukan salaman sebanyak berapa kali? Dalam ruangan tersebut ada berapa kali salaman?

Mari kita hitung manual.

Misalkan, anda dan 4 sahabat anda diberi nama a, b, c, d, dan e.

Pasangan salaman yang terjadi yakni

(a,b), (a,c), (a,d), (a,e),

(b,c), (b,d), (b,e),

(c,d), (c,e),

(d,e)

Dapat diketahui bahwa setiap orang akan melakukan salaman sebanyak 4 kali dan dalam ruangan tersebut terdapat 10 kali salaman.

Lalu apakah permasalahan ini akan berhenti cukup sampai disini?

Sekarang misalkan a, b, c, d, dan e adalah vertex, sedangkan salaman adalah edge. Dapat direpresentasikan dengan sebuah graf sebagai berikut:

 

Dari graf diatas dapat diketahui:

Graf diatas merupakan graf lengkap,

Banyak vertex = 5, banyak edge = 10, derajat vertex = 4.

Perhatikan bahwa

            d(1)+d(2)+d(3)+d(4)+d(5) = 2.10

4+4+4+4+4                          = 2.10

5.4                                        = 2.10

           (untuk lebih meyakinkan cobalah mengeksplorasi dengan kasus lain)

Sehingga kita dapat menarik sebuah definisi sebagai berikut:

Jika G sebuah graf, maka:

  

Bonus:

Bentuk lain teorema salaman adalah:

Misal, n = banyak objek (misal, vertex jika pada graf)

Maka banyaknya edge dapat dinyatakan dengan kombinasi:

 

Contoh:

Suatu kompetisi diikuti oleh 20 peserta. Setiap peserta akan bertanding dengan 19 lawannya masing-masing satu kali. Akan ada berapa pertandingan dalam kompetisi tersebut?

Menggunakan Teorema Salaman

Misal, Banyak Vertex = 20, Derajat Vertex = 19.

Ditanya: E(G)=?

Jawab:

            20.19 = 2.E(G)

380    = 2.E(G)

 E(G) = 380:2 = 190

 Jadi, banyaknya seluruh pertandingan dalam kompetisi tersebut adalah 190 pertandingan.

Menggunakan Kombinasi

 

Jadi, banyaknya seluruh pertandingan dalam kompetisi tersebut adalah 190 pertandingan.

Sumber:

Yulianti, K. (2008). "Handout Mata Kuliah Teori Graf (MTF 422) JILID 1". Universitas Pendidikan Indonesia: Bandung.

https://mathcyber1997.com/soal-dan-pembahasan-keterhubungan-graf/

https://www.gatevidyalay.com/handshaking-theorem-graph-theory-theorems/