Dalam bidang teori graf, memahami struktur dasar dari sebuah graf sangatlah penting. Salah satu parameter paling fundamental yang harus diidentifikasi adalah jumlah edge yang terdapat pada graf tersebut adalah. Edge, atau rusuk, merepresentasikan hubungan atau koneksi antar simpul (vertex) dalam graf. Mengetahui jumlah edge ini krusial untuk menghitung berbagai properti graf lainnya, seperti kepadatan (density), derajat rata-rata, dan klasifikasi graf (misalnya, apakah graf tersebut terhubung atau multigraf).
Sebuah graf $G = (V, E)$ didefinisikan oleh himpunan simpul $V$ dan himpunan edge $E$. Setiap elemen dalam $E$ adalah pasangan (atau tupel terurut) dari simpul di $V$. Untuk graf tak berarah sederhana (undirected simple graph), edge $\{u, v\}$ menunjukkan bahwa terdapat koneksi antara simpul $u$ dan simpul $v$. Tidak ada perulangan (loop) atau edge paralel (multiple edges) dalam graf sederhana.
Ketika kita diminta untuk menentukan jumlah edge yang terdapat pada graf tersebut adalah, prosesnya akan sangat bergantung pada jenis graf yang sedang kita analisis. Apakah graf tersebut diberikan dalam bentuk daftar adjasensi, matriks adjasensi, atau representasi visual?
Jika graf disajikan secara visual, cara termudah adalah menghitung setiap garis yang menghubungkan dua simpul. Jika graf disajikan dalam bentuk daftar edge, kita hanya perlu menghitung berapa banyak pasangan simpul yang terdaftar.
Matriks adjasensi $A$ adalah matriks persegi $|V| \times |V|$ di mana $A_{ij} = 1$ jika terdapat edge antara simpul $i$ dan $j$, dan 0 sebaliknya.
Untuk graf tak berarah sederhana, total jumlah edge yang terdapat pada graf tersebut adalah setengah dari jumlah total entri bernilai 1 dalam matriks tersebut. Hal ini karena setiap edge $\{u, v\}$ dihitung dua kali (sekali sebagai $A_{uv}$ dan sekali sebagai $A_{vu}$).
Teorema jabat tangan (Handshaking Lemma) adalah alat paling kuat dalam teori graf untuk menghubungkan derajat simpul dengan jumlah edge. Derajat sebuah simpul adalah jumlah edge yang terhubung dengannya.
Lemma ini menyatakan bahwa jumlah dari derajat semua simpul dalam graf tak berarah selalu sama dengan dua kali lipat dari jumlah edge. Ini adalah generalisasi dari perhitungan matriks adjasensi di atas.
Oleh karena itu, untuk menemukan jumlah edge yang terdapat pada graf tersebut adalah, kita cukup menjumlahkan semua derajat simpul dan membaginya dengan dua:
Perlu diperhatikan: Untuk graf berarah, perhitungan ini sedikit berbeda karena kita membedakan antara in-degree (derajat masuk) dan out-degree (derajat keluar). Total jumlah edge sama dengan total in-degree, yang juga sama dengan total out-degree.
Mari kita pertimbangkan sebuah contoh graf $G$ dengan 5 simpul $V = \{A, B, C, D, E\}$ dan edge sebagai berikut: $\{A, B\}, \{A, C\}, \{B, C\}, \{C, D\}, \{D, E\}$.
Menghitung secara langsung: Terdapat 5 edge.
Menggunakan Derajat Simpul:
Maka, jumlah edge yang terdapat pada graf tersebut adalah: $|E| = 10 / 2 = 5$. Hasilnya konsisten.
Gambar di atas mengilustrasikan sebuah graf contoh di mana jumlah edge yang terdapat pada graf tersebut adalah 5.
Menentukan jumlah edge yang terdapat pada graf tersebut adalah sebuah proses dasar yang memerlukan pemahaman yang jelas mengenai representasi graf. Baik melalui penghitungan langsung, analisis matriks adjasensi, maupun penerapan Handshaking Lemma, semua metode harus menghasilkan nilai yang sama untuk graf yang konsisten. Dalam konteks graf sederhana, teorema jabat tangan adalah cara paling efisien ketika derajat setiap simpul diketahui.
Ketika berhadapan dengan soal atau masalah praktis, identifikasi jenis graf (berarah/tak berarah, berbobot/tak berbobot, sederhana/multigraf) adalah langkah pertama yang krusial sebelum menerapkan formula yang tepat untuk mendapatkan $|E|$. Mengabaikan detail ini dapat menyebabkan kesalahan fatal dalam perhitungan jumlah koneksi dalam jaringan yang direpresentasikan oleh graf tersebut.