Adjacent: Pengertian, Sifat, dan Contoh dalam Teori Graf

Adjacent adalah istilah dalam teori graf yang berarti bertetangga. Dua buah simpul (vertex) pada sebuah graf disebut adjacent jika keduanya dihubungkan oleh sebuah sisi (edge). Dua buah sisi juga disebut adjacent, atau bertetangga, jika keduanya terhubung pada simpul yang sama.

Kedudukan adjacent dalam definisi graf

Dictionary of Algorithms and Data Structures terbitan National Institute of Standards and Technology (NIST) mendefinisikan graf sebagai himpunan butir yang dihubungkan oleh sisi. Setiap butir disebut simpul atau node. Secara formal, graf adalah himpunan simpul beserta satu relasi biner antarsimpul, dan relasi itulah yang disebut ketetanggaan (adjacency).

Kamus yang sama memberi perumpamaan peta jalan. Kota-kota berperan sebagai simpul, sedangkan jalan dari satu kota ke kota lain berperan sebagai sisi. Dua kota yang disambungkan langsung oleh sebuah ruas jalan adalah dua simpul yang adjacent.

Sifat relasi adjacent

NIST mencatat bahwa relasi adjacent bersifat simetris, tetapi tidak harus refleksif atau transitif. Simetris berarti jika simpul pertama bertetangga dengan simpul kedua, simpul kedua juga bertetangga dengan simpul pertama. Sifat itu berlaku pada graf tak-berarah, yang relasi ketetanggaannya memang simetris.

Tidak transitif berarti dua simpul yang sama-sama bertetangga dengan simpul ketiga belum tentu bertetangga satu sama lain. Adapun pada graf yang tidak mengizinkan gelung diri (self-loop), relasi ketetanggaan bersifat irefleksif, sehingga sebuah simpul tidak bertetangga dengan dirinya sendiri.

Adjacent pada graf berarah dan derajat simpul

Pada graf berarah, setiap sisi merupakan pasangan terurut simpul, sehingga sisi hanya dapat diikuti dari satu simpul ke simpul lain. NIST mengibaratkannya sebagai lingkungan dengan jalan satu arah, yang petanya harus menunjukkan arah perjalanan yang diizinkan di setiap ruas.

Konsep ini juga berkaitan dengan derajat (degree). Derajat sebuah simpul adalah banyaknya sisi yang terhubung ke simpul tersebut, sedangkan derajat sebuah graf adalah derajat terbesar di antara semua simpulnya.

Cara komputer menyimpan ketetanggaan

Ada dua bentuk penyimpanan yang dicatat NIST. Matriks ketetanggaan (adjacency matrix) menyajikan graf berarah dengan n simpul sebagai matriks berukuran n kali n. Isian pada baris i kolom j bernilai 1 jika ada sisi dari simpul i ke simpul j, dan bernilai 0 jika tidak ada.

Bentuk kedua adalah daftar ketetanggaan (adjacency list), yaitu larik berisi n daftar simpul. Daftar ke-i memuat simpul j jika ada sisi dari simpul i ke simpul j. Menurut NIST, daftar ketetanggaan lebih ringkas untuk matriks yang jarang terisi.

Graf berbobot dapat disimpan dengan cara serupa. Pada matriks, bobot sisi dipakai sebagai nilai isian, sedangkan pada daftar, yang disimpan adalah pasangan simpul dan bobotnya.

Istilah terkait

Pemahaman tentang adjacent bertumpu pada beberapa entri lain di Kamus Telematika, yaitu graph sebagai struktur induknya, vertex dan sisi sebagai unsur pembentuknya, serta graf tak-berarah dan graf berarah sebagai dua jenis graf yang menentukan sifat ketetanggaan.

Rujukan

Sumber: Istilah-istilah dalam Bidang Teknologi, Telekomunikasi dan Informasi. Paul E. Black (ed.), Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, entri “adjacent” (2004), “graph”, “directed graph”, “degree” (2006), “adjacency-matrix representation” (2023), dan “adjacency-list representation” (2021).