Salaman
Hal yang akan sering kita lakukan ketika lebaran atau hari raya lainnya. Nah…apakah kalian tahu pada metematika tepatnya pada Teori Graph ada lemma yang namanya Lemma Salaman (Handshaking Lemma). Untuk paham tentang Lemma Salaman, kalian harus tahu apa itu Graph
Graph
Suatu Graph G terdiri dari 2 hal
- Suatu himpunan V yang anggotanya terdiri dari titik-titik (Vertices)
- Suatu himpunan E yang terdiri dari pasangan-pasangan tak berurutan titik-titik berbeda yang disebut garis (edges)
Titik u dan v dikatakan berdekatan (adjacent) jika terhubung oleh satu garis (u,v)
Contoh:
©Wikipedia
Gambar diatas mewakili Graph G (V,E) dengan
- V terdiri dari 6 titik yaitu 1, 2, 3, 4, 5 dan 6
- E terdiri dari 7 garis yaitu (6,4), (4,5), (4,3), (3,2), (5,2), (5,1), (1,2)
Derajat
Derajat dari suatu titik v adalah banayaknya garis yang terhubung pada titik v tersebut, dinotasikan der(v). Pada contoh diatas diperoleh der(1)=2, der(2)=3, der(3)=2, der(6)=1.
Karena tiap garis dihitung 2 kali dalam menghitung jumlah derajat semua titik pada suatu graph maka timbulah lemma salaman
Lemma Salaman (Handshaking Lemma): Jumlah derajat semua titik pada graph adalah dua kali banyakmya garis
ataus secara formal ditulis
Diberikan Graph G(V,E) maka
Pada contoh graph diatas, diperoelh jumlah derajat semua ttiknya adalah 2 + 3 + 2 + 3 + 3 + 1 = 14, dua kali dari banyaknya garis
Mengapa disebut Lemma Salaman?
Jika kita menganalogikan Graph sebagai sebuah pertemuan, titik sebagai orang, garis sebagai salaman orang yang satu dengan yang lain dan derajat sebagai banyaknya seseorang melakukan salaman maka lemma Salaman bisa dianalogikan sebgai berikut
Jumlah total banyaknya setiap orang melakukan salaman pada sebuah pertemuan adalah dua kali banyaknya salaman yang terjadi pada pertemuan tersebut
Bagaimana menarik bukan? Salaman, satu hal yang pasti kita lakukan ketika menghadari suatu pertemuan ternyata bisa dipandang secara matematis
Blog Matematika Pak Satria 
Saya sempat bingung, pernah baca buku, nama teoremanya sama-sama handshaking, tetapi ternyata beda.. yang satu ada di Graph, dan yang satu lagi ada pada Digraph.. .
padahal kalau di Digraph itu kan dikenal indeg = outdeg = jumlah sisi
kalau pada graph dikenal deg = 2 x jumlah sisi
apa boleh, dalam teorema berbeda dengan nama yang sama?
Ya…boleh2 aja gak ada aturan yang melarang hal tersebut
Saya sempat bingung, pernah baca buku, nama teoremanya sama-sama handshaking, tetapi ternyata beda.. yang satu ada di Graph, dan yang satu lagi ada pada Digraph.. .
padahal kalau di Digraph itu kan dikenal indeg = outdeg = jumlah sisi
kalau pada graph dikenal deg = 2 x jumlah sisi