Memahami \(V=\{A,B,C,D,E\}\): Contoh Himpunan Simpul dalam Graf
Notasi
\[ V=\{A,B,C,D,E\} \]
adalah salah satu bagian paling dasar dari definisi graf. Dalam teori graf, sebuah graf biasanya ditulis sebagai
\[ G=(V,E), \]
dengan \(V\) menyatakan himpunan simpul atau vertex set, dan \(E\) menyatakan himpunan sisi atau edge set. Jadi, ketika dokumen menulis \(V=\{A,B,C,D,E\}\), artinya graf yang sedang dibicarakan memiliki lima simpul, yaitu \(A\), \(B\), \(C\), \(D\), dan \(E\). Notasi semacam ini standar dalam teori graf, sebagaimana digunakan dalam buku-buku dasar seperti Diestel dan West [Diestel 2017; West 2001].
Apa arti \(V\) dalam contoh ini?
Huruf \(V\) berasal dari kata vertices, bentuk jamak dari vertex. Dalam bahasa Indonesia, vertex biasanya diterjemahkan sebagai simpul. Simpul adalah objek dasar yang ingin kita hubungkan. Pada contoh dalam dokumen induk, simpul-simpul itu dibayangkan sebagai lima responden survei. Maka \(A\), \(B\), \(C\), \(D\), dan \(E\) dapat dibaca sebagai lima orang berbeda.
Dengan kata lain, kita dapat membayangkan:
\[ A=\text{responden pertama},\quad B=\text{responden kedua},\quad C=\text{responden ketiga}, \]
dan seterusnya. Huruf-huruf tersebut bukan angka yang harus dihitung secara aritmetis. Mereka adalah label. Label hanya berfungsi untuk membedakan satu simpul dari simpul lain.
Karena \(V\) adalah sebuah himpunan, maka urutan penulisannya tidak penting. Secara matematis,
\[ \{A,B,C,D,E\}=\{E,D,C,B,A\}. \]
Keduanya menyatakan himpunan simpul yang sama. Yang penting adalah anggota himpunannya, bukan urutan tampilnya. Ini berbeda dari daftar berurutan, misalnya antrean, di mana posisi pertama dan terakhir dapat memiliki makna.
Contoh konkret: jaringan perkenalan
Misalkan lima simpul itu benar-benar lima orang dalam sebuah kelas kecil:
\[ V=\{A,B,C,D,E\}. \]
Sekarang kita ingin mencatat siapa mengenal siapa. Untuk itu, kita perlu menambahkan himpunan sisi \(E\). Misalnya:
\[ E=\{\{A,B\},\{A,C\},\{B,D\},\{D,E\}\}. \]
Maka grafnya adalah
\[ G=(V,E), \]
dengan
\[ V=\{A,B,C,D,E\} \]
dan
\[ E=\{\{A,B\},\{A,C\},\{B,D\},\{D,E\}\}. \]
Maknanya adalah sebagai berikut. Ada sisi antara \(A\) dan \(B\), sehingga \(A\) mengenal \(B\). Ada sisi antara \(A\) dan \(C\), sehingga \(A\) mengenal \(C\). Ada sisi antara \(B\) dan \(D\), serta ada sisi antara \(D\) dan \(E\).
Karena sisi ditulis sebagai himpunan dua elemen, misalnya \(\{A,B\}\), maka sisi ini tidak berarah. Artinya, \(\{A,B\}\) sama dengan \(\{B,A\}\). Ini cocok jika relasi yang dimodelkan adalah “saling mengenal”. Jika \(A\) saling mengenal dengan \(B\), maka \(B\) juga saling mengenal dengan \(A\).
Dari contoh ini, kita dapat menggambar struktur relasinya secara mental:
\[ C - A - B - D - E. \]
Gambar ini hanya membantu intuisi. Secara matematis, grafnya ditentukan oleh \(V\) dan \(E\), bukan oleh posisi titik-titik dalam gambar.
Mengapa hanya \(V\) belum cukup untuk menentukan graf?
Bagian yang disorot hanya menyebutkan
\[ V=\{A,B,C,D,E\}. \]
Ini baru memberi tahu kita siapa saja objeknya. Namun ini belum memberi tahu kita hubungan apa saja yang ada. Untuk menentukan graf sepenuhnya, kita masih memerlukan \(E\), yaitu himpunan sisi.
Sebagai contoh, dengan himpunan simpul yang sama,
\[ V=\{A,B,C,D,E\}, \]
kita bisa membentuk banyak graf berbeda.
Graf pertama bisa saja tidak memiliki sisi sama sekali:
\[ E=\varnothing. \]
Graf seperti ini berarti lima orang ada dalam data, tetapi tidak ada hubungan yang dicatat di antara mereka. Dalam teori graf, ini sering disebut graf kosong pada himpunan simpul tersebut.
Graf kedua bisa memiliki beberapa sisi:
\[ E=\{\{A,B\},\{C,D\}\}. \]
Di sini hanya \(A\) terhubung dengan \(B\), dan \(C\) terhubung dengan \(D\). Simpul \(E\) tidak terhubung dengan siapa pun.
Graf ketiga bisa berupa graf lengkap, yaitu setiap pasangan simpul berbeda terhubung oleh sisi. Karena ada lima simpul, semua sisi yang mungkin adalah
\[ E= \{ \{A,B\},\{A,C\},\{A,D\},\{A,E\}, \{B,C\},\{B,D\},\{B,E\}, \{C,D\},\{C,E\}, \{D,E\} \}. \]
Jumlahnya ada \(10\) sisi. Secara umum, untuk graf sederhana tak berarah dengan \(n\) simpul, jumlah maksimum sisi adalah
\[ \binom{n}{2}=\frac{n(n-1)}{2}. \]
Jika \(n=5\), maka
\[ \binom{5}{2}=\frac{5\cdot 4}{2}=10. \]
Jadi, kalimat \(V=\{A,B,C,D,E\}\) hanya menetapkan bahwa ada lima simpul. Struktur graf yang sebenarnya baru terlihat setelah himpunan sisi \(E\) juga diberikan.
Contoh lain: bukan orang, tetapi variabel statistik
Karena dokumen induk membahas hubungan antara teori graf dan statistik, simpul tidak harus berupa orang. Simpul juga dapat berupa variabel. Misalnya kita memiliki lima variabel dalam suatu penelitian kesehatan:
\[ V=\{\text{Usia},\text{Tekanan Darah},\text{Kolesterol},\text{Olahraga},\text{Risiko Penyakit}\}. \]
Dalam contoh ini, setiap simpul adalah variabel statistik. Sisi dapat diberi arti tertentu, misalnya “memiliki asosiasi kuat” atau “berhubungan langsung dalam model”. Jika kita menulis
\[ E=\{ \{\text{Usia},\text{Tekanan Darah}\}, \{\text{Kolesterol},\text{Risiko Penyakit}\}, \{\text{Olahraga},\text{Risiko Penyakit}\} \}, \]
maka kita sedang menyatakan bahwa ada relasi yang dimodelkan antara pasangan-pasangan variabel tersebut. Tetapi arti tepat dari sisi harus didefinisikan dengan hati-hati. Sisi tidak otomatis berarti hubungan sebab-akibat. Sisi bisa berarti korelasi, kedekatan, interaksi, dependensi bersyarat, atau hubungan lain sesuai konteks model. Peringatan ini penting dalam analisis jaringan dan model grafis probabilistik [Lauritzen 1996; Newman 2018].
Order graf dari \(V=\{A,B,C,D,E\}\)
Salah satu informasi langsung yang bisa diperoleh dari
\[ V=\{A,B,C,D,E\} \]
adalah order graf, yaitu banyaknya simpul. Order graf ditulis sebagai
\[ |V|. \]
Karena himpunan \(V\) berisi lima anggota, maka
\[ |V|=5. \]
Tanda \(|V|\) berarti kardinalitas, yaitu jumlah elemen dalam himpunan \(V\). Jadi, graf apa pun yang memakai himpunan simpul ini memiliki order \(5\), terlepas dari apakah graf itu memiliki nol sisi, empat sisi, atau sepuluh sisi.
Sebaliknya, size graf adalah banyaknya sisi, yaitu
\[ |E|. \]
Jika kita memakai contoh sisi dari dokumen induk,
\[ E=\{\{A,B\},\{A,C\},\{B,D\},\{D,E\}\}, \]
maka
\[ |E|=4. \]
Jadi graf tersebut memiliki order \(5\) dan size \(4\).
Contoh derajat simpul
Dengan
\[ V=\{A,B,C,D,E\} \]
dan
\[ E=\{\{A,B\},\{A,C\},\{B,D\},\{D,E\}\}, \]
kita dapat menghitung derajat setiap simpul. Derajat simpul \(v\), ditulis \(\deg(v)\), adalah jumlah sisi yang bersisian dengan \(v\).
Simpul \(A\) bersisian dengan dua sisi, yaitu \(\{A,B\}\) dan \(\{A,C\}\), sehingga
\[ \deg(A)=2. \]
Simpul \(B\) bersisian dengan \(\{A,B\}\) dan \(\{B,D\}\), sehingga
\[ \deg(B)=2. \]
Simpul \(C\) hanya bersisian dengan \(\{A,C\}\), sehingga
\[ \deg(C)=1. \]
Simpul \(D\) bersisian dengan \(\{B,D\}\) dan \(\{D,E\}\), sehingga
\[ \deg(D)=2. \]
Simpul \(E\) hanya bersisian dengan \(\{D,E\}\), sehingga
\[ \deg(E)=1. \]
Maka jumlah semua derajat adalah
\[ \deg(A)+\deg(B)+\deg(C)+\deg(D)+\deg(E) = 2+2+1+2+1=8. \]
Karena jumlah sisi adalah \(|E|=4\), kita memperoleh
\[ 2|E|=2\cdot 4=8. \]
Ini cocok dengan Handshaking Lemma:
\[ \sum_{v\in V}\deg(v)=2|E|. \]
Contoh kecil ini menunjukkan mengapa penulisan \(V=\{A,B,C,D,E\}\) penting. Begitu himpunan simpul jelas, kita dapat mendefinisikan sisi, menghitung derajat, menentukan order, menentukan size, dan memeriksa identitas dasar dalam teori graf.
Inti maknanya
Jadi, bagian
bukan sekadar daftar huruf. Ia menetapkan ruang objek dari graf: ada lima simpul yang akan menjadi tempat relasi didefinisikan. Dalam contoh survei, simpul-simpul itu dapat mewakili lima responden. Dalam contoh statistik lain, simpul dapat mewakili variabel, wilayah, perusahaan, artikel ilmiah, gen, atau akun media sosial.
Namun \(V\) sendiri belum menentukan hubungan. Hubungan baru ditentukan oleh \(E\). Karena itu, dalam teori graf, kita selalu perlu bertanya dua hal: “Apa simpulnya?” dan “Apa sisinya?” Notasi \(V=\{A,B,C,D,E\}\) menjawab pertanyaan pertama secara formal dan ringkas.
References
Diestel, R. (2017). Graph Theory (5th ed.). Springer.
Lauritzen, S. L. (1996). Graphical Models. Oxford University Press.
Newman, M. E. J. (2018). Networks (2nd ed.). Oxford University Press.
West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Prentice Hall.