Lemma Salaman

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

  1. V terdiri dari 6 titik yaitu 1, 2, 3, 4, 5 dan 6
  2. 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 \sum_{v\in V}der\left(v\right)=2\left|E\right|

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

About Nursatria

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 and tagged , , . Bookmark the permalink.

3 Responses to Lemma Salaman

  1. msihabudin says:

    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?

  2. msihabudin says:

    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

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s