Bab 5: Jalan, Jejak, Lintasan, Siklus, dan Keterhubungan
Pada bab-bab sebelumnya, kita telah membangun graf sebagai objek yang terdiri dari simpul dan sisi, lalu mempelajari derajat serta cara merepresentasikan graf di komputer. Sekarang kita mulai bertanya tentang gerak di dalam graf.
Jika simpul mewakili individu, variabel, lokasi, artikel, gen, atau institusi, maka sisi mewakili hubungan langsung. Tetapi dalam banyak analisis statistik, hubungan tidak langsung sama pentingnya dengan hubungan langsung. Dua peneliti mungkin tidak pernah menulis artikel bersama, tetapi terhubung melalui rantai kolaborasi. Dua variabel mungkin tidak berinteraksi langsung dalam model, tetapi dapat berada dalam rantai dependensi. Dua akun dalam jaringan sosial mungkin tidak berteman, tetapi informasi dapat mengalir dari satu ke yang lain melalui beberapa perantara.
Untuk membahas hal-hal seperti itu, kita membutuhkan bahasa tentang urutan simpul dan sisi: walk, trail, path, cycle, keterhubungan, dan jarak graf. Terminologi ini merupakan fondasi standar dalam teori graf dan menjadi dasar bagi algoritma traversal seperti BFS dan DFS pada bab berikutnya (Diestel, 2017; West, 2001).
Dalam bab ini, kita terutama bekerja dengan graf tak berarah sederhana, kecuali jika disebutkan lain. Jadi, graf kita berbentuk
\[ G=(V,E), \]
dengan \(V\) himpunan simpul tak kosong dan \(E\) himpunan sisi, di mana setiap sisi adalah pasangan tak berurutan \(\{u,v\}\) dengan \(u\neq v\).
5.1 Intuisi dasar: bergerak dari simpul ke simpul
Misalkan kita mempunyai graf
\[ V=\{A,B,C,D,E,F\} \]
dan
\[ E=\{\{A,B\},\{B,C\},\{C,D\},\{D,B\},\{D,E\},\{E,F\}\}. \]
Secara visual, kita dapat membayangkan hubungan berikut:
- \(A\) terhubung ke \(B\);
- \(B\) terhubung ke \(C\) dan \(D\);
- \(C\) terhubung ke \(D\);
- \(D\) terhubung ke \(E\);
- \(E\) terhubung ke \(F\).
Dari \(A\), kita dapat bergerak ke \(B\), lalu ke \(C\), lalu ke \(D\), lalu ke \(E\), lalu ke \(F\). Urutan simpul
\[ A,B,C,D,E,F \]
menggambarkan cara berpindah melalui sisi-sisi graf.
Namun ada banyak variasi. Kita juga dapat bergerak
\[ A,B,D,C,B,D,E. \]
Urutan ini sah sebagai perjalanan dalam graf karena setiap pasangan simpul berturutan memang bertetangga. Tetapi perjalanan ini mengulang simpul \(B\) dan \(D\), serta menggunakan sisi \(\{B,D\}\) lebih dari sekali.
Di sinilah perbedaan antara walk, trail, dan path menjadi penting.
5.2 Walk: perjalanan paling umum dalam graf
Istilah paling umum adalah walk. Dalam bahasa Indonesia, kita dapat menyebutnya jalan, tetapi karena istilah “jalan” juga sering dipakai secara umum, kita akan tetap menuliskan istilah Inggrisnya di awal: walk.
Sebuah walk dalam graf tak berarah adalah urutan bergantian simpul dan sisi
\[ v_0,e_1,v_1,e_2,v_2,\dots,e_k,v_k, \]
dengan setiap sisi \(e_i\) menghubungkan \(v_{i-1}\) dan \(v_i\). Artinya,
\[ e_i=\{v_{i-1},v_i\} \]
untuk setiap \(i=1,\dots,k\).
Jika grafnya sederhana, sisi antara dua simpul paling banyak satu, sehingga walk sering cukup ditulis sebagai urutan simpul
\[ v_0,v_1,\dots,v_k, \]
dengan syarat setiap pasangan berturutan \(v_{i-1}\) dan \(v_i\) bertetangga.
Bilangan \(k\), yaitu banyak sisi yang dilewati, disebut panjang walk.
Contoh 5.1
Pada graf dengan sisi
\[ E=\{\{A,B\},\{B,C\},\{C,D\},\{D,B\},\{D,E\},\{E,F\}\}, \]
urutan
\[ A,B,C,D,E,F \]
adalah walk dari \(A\) ke \(F\) dengan panjang \(5\), karena melewati lima sisi:
\[ \{A,B\},\{B,C\},\{C,D\},\{D,E\},\{E,F\}. \]
Urutan
\[ A,B,D,C,B,D,E \]
juga merupakan walk. Panjangnya \(6\). Walk ini mengulang simpul \(B\) dan \(D\), dan mengulang sisi \(\{B,D\}\).
Perhatikan bahwa walk boleh mengulang simpul dan boleh mengulang sisi. Karena itu walk adalah konsep paling longgar.
5.3 Walk tertutup
Sebuah walk disebut tertutup jika simpul awal sama dengan simpul akhir. Dengan notasi
\[ v_0,v_1,\dots,v_k, \]
walk tersebut tertutup jika
\[ v_0=v_k. \]
Contoh 5.2
Dalam graf yang sama, urutan
\[ B,C,D,B \]
adalah walk tertutup dengan panjang \(3\), karena:
- \(B\) bertetangga dengan \(C\);
- \(C\) bertetangga dengan \(D\);
- \(D\) bertetangga dengan \(B\);
- simpul awal dan akhir sama, yaitu \(B\).
Walk tertutup penting karena ia menangkap gagasan “kembali ke titik awal”. Nanti, gagasan ini akan diperketat menjadi siklus, yaitu walk tertutup yang tidak mengulang simpul selain titik awal/akhir.
Dalam konteks statistik jaringan, walk tertutup dapat muncul ketika kita menghitung pola hubungan berulang. Misalnya, dalam jaringan sosial, walk tertutup pendek dapat mengindikasikan struktur kelompok kecil atau pola pertemanan timbal-balik secara tidak langsung. Analisis semacam ini berkaitan dengan ringkasan struktur jaringan seperti clustering dan motif, yang dibahas lebih lanjut dalam teori jaringan modern (Newman, 2010).
5.4 Trail: walk tanpa mengulang sisi
Walk terlalu umum untuk beberapa keperluan. Kadang kita ingin perjalanan yang tidak memakai sisi yang sama lebih dari sekali. Inilah yang disebut trail.
Sebuah trail adalah walk yang tidak mengulang sisi.
Trail boleh mengulang simpul, tetapi tidak boleh mengulang sisi.
Contoh 5.3
Pada graf
\[ E=\{\{A,B\},\{B,C\},\{C,D\},\{D,B\},\{D,E\},\{E,F\}\}, \]
urutan
\[ A,B,C,D,B \]
adalah trail, karena sisi yang dilewati adalah
\[ \{A,B\},\{B,C\},\{C,D\},\{B,D\}, \]
dan semuanya berbeda.
Namun urutan
\[ A,B,D,C,B,D,E \]
bukan trail, karena sisi \(\{B,D\}\) dipakai dua kali: sekali dari \(B\) ke \(D\), dan sekali dari \(B\) ke \(D\) lagi setelah melewati \(C\).
Trail menjadi penting dalam masalah seperti jalur Euler, yaitu masalah melewati setiap sisi tepat satu kali. Masalah Euler adalah salah satu asal historis teori graf, berawal dari masalah jembatan Königsberg yang dianalisis oleh Euler pada abad ke-18; pembahasan modernnya menjadi bagian standar teori graf (Diestel, 2017; West, 2001).
5.5 Path atau lintasan: walk tanpa mengulang simpul
Konsep berikutnya lebih ketat lagi. Sebuah path, dalam bahasa Indonesia sering disebut lintasan, adalah walk yang tidak mengulang simpul.
Dalam graf sederhana, path dapat ditulis sebagai
\[ v_0,v_1,\dots,v_k, \]
dengan semua simpul
\[ v_0,v_1,\dots,v_k \]
berbeda, dan setiap pasangan berturutan bertetangga.
Karena path tidak mengulang simpul, maka path juga tidak mengulang sisi. Jadi:
\[ \text{setiap path adalah trail, tetapi tidak setiap trail adalah path.} \]
Contoh 5.4
Urutan
\[ A,B,D,E,F \]
adalah path dari \(A\) ke \(F\). Semua simpulnya berbeda, dan setiap pasangan berturutan dihubungkan oleh sisi.
Urutan
\[ A,B,C,D,B \]
bukan path, karena simpul \(B\) muncul dua kali. Namun urutan itu masih merupakan trail, karena tidak ada sisi yang dipakai dua kali.
Mengapa path penting?
Path adalah model formal untuk hubungan tidak langsung tanpa pengulangan simpul. Jika ada path dari \(u\) ke \(v\), maka \(u\) dan \(v\) berada dalam bagian graf yang sama secara struktural. Dalam jaringan sosial, path dapat merepresentasikan rantai perkenalan. Dalam jaringan transportasi, path dapat merepresentasikan rute tanpa mengunjungi lokasi yang sama dua kali. Dalam model dependensi, path dapat menunjukkan bahwa dua variabel berada dalam rantai hubungan.
Untuk analisis statistik, path membantu kita membedakan antara hubungan langsung dan hubungan melalui perantara. Dua simpul mungkin tidak adjacent, tetapi tetap terhubung oleh path yang pendek. Hal ini menjadi dasar banyak ukuran jaringan, termasuk jarak, diameter, centrality, dan struktur komunitas (Newman, 2010).
5.6 Hubungan antara walk dan path
Ada fakta dasar yang sangat penting:
Jika ada walk dari simpul \(u\) ke simpul \(v\), maka ada path dari \(u\) ke \(v\).
Fakta ini tampak intuitif: jika sebuah perjalanan mengulang simpul, kita dapat membuang bagian yang berputar-putar. Mari kita buktikan secara hati-hati.
Proposisi 5.1
Jika terdapat walk dari \(u\) ke \(v\) dalam graf \(G\), maka terdapat path dari \(u\) ke \(v\).
Bukti
Ambil sebuah walk dari \(u\) ke \(v\):
\[ v_0,v_1,\dots,v_k, \]
dengan \(v_0=u\) dan \(v_k=v\).
Jika semua simpul dalam urutan ini berbeda, maka walk tersebut sudah merupakan path.
Jika tidak, ada simpul yang muncul lebih dari sekali. Misalkan
\[ v_i=v_j \]
untuk suatu \(i<j\). Maka bagian
\[ v_i,v_{i+1},\dots,v_j \]
adalah bagian walk yang mulai dan berakhir di simpul yang sama. Bagian ini dapat dihapus, sehingga kita memperoleh urutan baru
\[ v_0,\dots,v_i,v_{j+1},\dots,v_k. \]
Urutan baru ini masih merupakan walk dari \(u\) ke \(v\), karena \(v_i=v_j\), dan sebelumnya ada sisi dari \(v_j\) ke \(v_{j+1}\). Jadi setelah penghapusan, langkah dari \(v_i\) ke \(v_{j+1}\) tetap sah.
Setiap kali ada pengulangan simpul, kita hapus bagian tertutup seperti ini. Karena panjang walk berkurang setiap kali penghapusan dilakukan, proses ini pasti berhenti. Ketika berhenti, tidak ada simpul yang berulang. Maka walk yang tersisa adalah path dari \(u\) ke \(v\).
\[ \blacksquare \]
Proposisi ini adalah contoh awal dari argumen reduksi: kita mulai dari objek yang mungkin tidak sederhana, lalu menyederhanakannya tanpa kehilangan sifat utama yang diinginkan.
5.7 Cycle atau siklus
Sebuah cycle, dalam bahasa Indonesia siklus, adalah walk tertutup yang tidak mengulang simpul selain simpul awal/akhir.
Untuk graf sederhana, sebuah cycle biasanya ditulis sebagai
\[ v_0,v_1,\dots,v_{k-1},v_0, \]
dengan
\[ k\geq 3, \]
semua simpul
\[ v_0,v_1,\dots,v_{k-1} \]
berbeda, dan setiap pasangan berturutan bertetangga, termasuk \(v_{k-1}\) dengan \(v_0\).
Panjang cycle adalah banyak sisinya, yaitu \(k\).
Contoh 5.5
Pada graf kita, urutan
\[ B,C,D,B \]
adalah cycle dengan panjang \(3\). Simpul \(B,C,D\) semuanya berbeda, lalu kita kembali ke \(B\).
Cycle panjang \(3\) disebut juga segitiga. Dalam jaringan sosial, banyaknya segitiga sering dipakai untuk mengukur kecenderungan “teman dari teman juga menjadi teman”, meskipun interpretasi statistiknya harus hati-hati karena bergantung pada mekanisme pembentukan data dan bias sampling (Newman, 2010).
Contoh 5.6
Jika kita memiliki graf dengan sisi
\[ \{A,B\},\{B,C\},\{C,D\},\{D,A\}, \]
maka
\[ A,B,C,D,A \]
adalah cycle panjang \(4\).
Graf yang tidak memiliki cycle disebut asiklik. Pada bab berikutnya tentang pohon, kita akan melihat bahwa pohon adalah graf terhubung yang asiklik. Jadi siklus adalah salah satu batas penting antara graf yang memiliki struktur seperti jaringan umum dan graf yang memiliki struktur seperti hierarki.
5.8 Keterhubungan antara dua simpul
Sekarang kita beralih dari perjalanan individual ke struktur global graf.
Dua simpul \(u\) dan \(v\) disebut terhubung jika terdapat path dari \(u\) ke \(v\).
Untuk \(u=v\), kita menganggap \(u\) terhubung dengan dirinya sendiri melalui path panjang \(0\). Path panjang \(0\) hanya berisi satu simpul:
\[ u. \]
Definisi ini penting agar keterhubungan memiliki sifat matematis yang rapi.
Contoh 5.7
Misalkan
\[ V=\{A,B,C,D,E,F,G,H\} \]
dan
\[ E=\{\{A,B\},\{B,C\},\{C,D\},\{E,F\},\{F,G\}\}. \]
Maka:
- \(A\) terhubung dengan \(D\), karena ada path
\[ A,B,C,D. \]
- \(E\) terhubung dengan \(G\), karena ada path
\[ E,F,G. \]
-
\(A\) tidak terhubung dengan \(E\), karena tidak ada path dari bagian \(\{A,B,C,D\}\) ke bagian \(\{E,F,G\}\).
-
\(H\) hanya terhubung dengan dirinya sendiri, karena \(H\) adalah simpul terisolasi.
Simpul terisolasi adalah simpul berderajat \(0\). Ia tidak memiliki sisi yang bersisian dengannya.
5.9 Keterhubungan sebagai relasi ekuivalensi
Keterhubungan bukan hanya istilah intuitif. Ia memiliki struktur matematis yang kuat. Pada graf tak berarah, relasi “terhubung dengan” adalah relasi ekuivalensi pada himpunan simpul.
Sebuah relasi disebut relasi ekuivalensi jika memenuhi tiga sifat:
- Refleksif: setiap objek berelasi dengan dirinya sendiri.
- Simetris: jika \(u\) berelasi dengan \(v\), maka \(v\) berelasi dengan \(u\).
- Transitif: jika \(u\) berelasi dengan \(v\), dan \(v\) berelasi dengan \(w\), maka \(u\) berelasi dengan \(w\).
Mari kita lihat untuk keterhubungan.
Proposisi 5.2
Pada graf tak berarah \(G\), relasi “terhubung dengan” adalah relasi ekuivalensi pada \(V\).
Bukti
Refleksif. Untuk setiap simpul \(u\), ada path panjang \(0\) dari \(u\) ke \(u\). Jadi \(u\) terhubung dengan dirinya sendiri.
Simetris. Jika \(u\) terhubung dengan \(v\), maka ada path
\[ u=v_0,v_1,\dots,v_k=v. \]
Karena graf tak berarah, setiap sisi dapat dilewati dua arah. Maka urutan terbalik
\[ v=v_k,v_{k-1},\dots,v_0=u \]
adalah path dari \(v\) ke \(u\). Jadi \(v\) terhubung dengan \(u\).
Transitif. Jika \(u\) terhubung dengan \(v\), ada path dari \(u\) ke \(v\). Jika \(v\) terhubung dengan \(w\), ada path dari \(v\) ke \(w\). Dengan menggabungkan kedua path, kita memperoleh walk dari \(u\) ke \(w\). Berdasarkan Proposisi 5.1, dari walk tersebut terdapat path dari \(u\) ke \(w\). Jadi \(u\) terhubung dengan \(w\).
Ketiga sifat terpenuhi, sehingga keterhubungan adalah relasi ekuivalensi.
\[ \blacksquare \]
Konsekuensi penting dari relasi ekuivalensi adalah bahwa himpunan simpul dapat dipartisi menjadi kelas-kelas yang saling terpisah. Dalam graf, kelas-kelas ini disebut komponen terhubung.
5.10 Komponen terhubung
Sebuah komponen terhubung adalah subgraf terhubung yang maksimal.
Kata “maksimal” perlu dipahami dengan hati-hati. Maksimal bukan berarti memiliki jumlah simpul terbesar dibandingkan semua komponen lain. Maksimal berarti tidak dapat diperluas lagi dengan menambahkan simpul lain dari graf sambil tetap mempertahankan keterhubungan.
Dengan kata lain, komponen terhubung adalah kumpulan simpul yang semuanya saling terhubung satu sama lain, dan tidak ada simpul di luar kumpulan itu yang terhubung dengan simpul di dalamnya.
Contoh 5.8
Untuk graf dengan
\[ V=\{A,B,C,D,E,F,G,H\} \]
dan
\[ E=\{\{A,B\},\{B,C\},\{C,D\},\{E,F\},\{F,G\}\}, \]
komponen terhubungnya adalah:
\[ \{A,B,C,D\}, \]
\[ \{E,F,G\}, \]
dan
\[ \{H\}. \]
Simpul \(H\) membentuk komponen sendiri karena ia tidak terhubung dengan simpul lain.
Dalam analisis data jaringan, komponen terhubung sering menjadi langkah eksplorasi awal. Misalnya, jika jaringan kolaborasi memiliki banyak komponen kecil, maka tidak semua peneliti berada dalam ekosistem kolaborasi yang sama. Jika ada satu komponen yang sangat besar, maka sebagian besar simpul berada dalam struktur yang dapat dijangkau satu sama lain melalui rantai kolaborasi. Fenomena komponen besar dan struktur keterhubungan adalah tema utama dalam studi jaringan empiris dan graf acak (Newman, 2010).
5.11 Graf terhubung
Sebuah graf tak berarah disebut terhubung jika setiap pasangan simpulnya terhubung oleh path.
Secara formal, graf \(G=(V,E)\) terhubung jika untuk semua \(u,v\in V\), terdapat path dari \(u\) ke \(v\).
Jika graf hanya memiliki satu simpul dan tidak ada sisi, graf tersebut tetap dianggap terhubung. Alasannya, satu-satunya pasangan simpul yang perlu diperiksa adalah simpul itu dengan dirinya sendiri, dan ia terhubung melalui path panjang \(0\).
Contoh 5.9
Graf dengan
\[ V=\{A,B,C,D\} \]
dan
\[ E=\{\{A,B\},\{B,C\},\{C,D\}\} \]
adalah graf terhubung. Meskipun \(A\) tidak adjacent dengan \(D\), ada path
\[ A,B,C,D. \]
Sebaliknya, graf dengan
\[ V=\{A,B,C,D\} \]
dan
\[ E=\{\{A,B\},\{C,D\}\} \]
tidak terhubung, karena tidak ada path dari \(A\) ke \(C\).
Keterhubungan dan data statistik
Ketika graf dibangun dari data, keterhubungan dapat memiliki makna substantif. Dalam jaringan komunikasi, graf tidak terhubung berarti ada kelompok yang tidak dapat saling mencapai melalui rantai komunikasi yang diamati. Dalam jaringan dependensi variabel, komponen terpisah dapat menunjukkan bahwa model terbagi menjadi beberapa bagian yang tidak berinteraksi langsung maupun tidak langsung. Dalam jaringan spasial, komponen terpisah dapat menandakan pulau, wilayah terisolasi, atau kesalahan pencatatan konektivitas.
Namun interpretasi tersebut selalu bergantung pada cara graf dibangun. Jika sisi dibuat berdasarkan ambang korelasi, misalnya, maka komponen terpisah dapat berubah ketika ambang diubah. Jadi, keterhubungan adalah sifat graf, tetapi makna statistiknya bergantung pada prosedur konstruksi graf.
5.12 Jarak graf
Setelah kita tahu bahwa dua simpul dapat terhubung oleh path, pertanyaan berikutnya adalah: seberapa jauh mereka?
Dalam graf tak berbobot, jarak graf antara dua simpul \(u\) dan \(v\), ditulis
\[ d(u,v), \]
adalah panjang path terpendek dari \(u\) ke \(v\).
Jika tidak ada path dari \(u\) ke \(v\), maka jaraknya tidak hingga atau tidak terdefinisi, bergantung pada konvensi. Dalam buku ini, untuk graf tak terhubung, kita akan menggunakan konvensi:
\[ d(u,v)=\infty \]
jika \(u\) dan \(v\) berada dalam komponen berbeda.
Untuk graf terhubung, semua jarak antar pasangan simpul bernilai hingga.
Contoh 5.10
Misalkan graf memiliki sisi
\[ E=\{\{A,B\},\{B,C\},\{C,D\},\{D,E\},\{B,E\}\}. \]
Kita ingin menghitung \(d(A,E)\).
Ada path
\[ A,B,E \]
dengan panjang \(2\). Ada juga path
\[ A,B,C,D,E \]
dengan panjang \(4\). Karena path terpendek memiliki panjang \(2\), maka
\[ d(A,E)=2. \]
Jarak graf menghitung banyak langkah sisi, bukan jarak geometris biasa. Jika simpul adalah kota dan sisi adalah jalan, maka \(d(u,v)\) dalam graf tak berbobot menghitung jumlah ruas jalan minimum, bukan kilometer. Jika kita ingin menghitung kilometer, waktu tempuh, biaya, atau risiko, kita membutuhkan graf berbobot, yang akan dibahas dalam Bab 9.
5.13 Geodesik: lintasan terpendek
Sebuah geodesik antara simpul \(u\) dan \(v\) adalah path dari \(u\) ke \(v\) yang panjangnya sama dengan \(d(u,v)\). Dengan kata lain, geodesik adalah lintasan terpendek.
Istilah geodesik berasal dari geometri, tetapi dalam teori graf ia berarti path terpendek menurut jumlah sisi atau menurut bobot, tergantung jenis graf. Untuk saat ini, dalam graf tak berbobot, panjang geodesik adalah banyak sisi.
Contoh 5.11
Pada graf dengan sisi
\[ E=\{\{A,B\},\{B,C\},\{C,D\},\{D,E\},\{B,E\}\}, \]
path
\[ A,B,E \]
adalah geodesik dari \(A\) ke \(E\), karena panjangnya \(2\), dan tidak ada path dari \(A\) ke \(E\) dengan panjang lebih kecil.
Path
\[ A,B,C,D,E \]
bukan geodesik dari \(A\) ke \(E\), karena panjangnya \(4\), sedangkan jarak sebenarnya adalah \(2\).
Geodesik tidak harus tunggal
Dua simpul dapat memiliki lebih dari satu geodesik.
Misalkan
\[ V=\{A,B,C,D\} \]
dan
\[ E=\{\{A,B\},\{B,D\},\{A,C\},\{C,D\}\}. \]
Maka dari \(A\) ke \(D\), ada dua geodesik:
\[ A,B,D \]
dan
\[ A,C,D. \]
Keduanya memiliki panjang \(2\), sehingga keduanya sama-sama lintasan terpendek.
Dalam jaringan, banyaknya geodesik dapat memengaruhi interpretasi aliran informasi. Jika hanya ada satu geodesik antara dua simpul, maka jalur tersebut menjadi semacam penghubung kritis. Jika ada banyak geodesik, struktur jaringan memiliki alternatif rute yang lebih kaya.
5.14 Sifat dasar jarak graf
Pada graf terhubung, jarak graf memiliki sifat seperti metrik. Sebuah metrik adalah fungsi jarak yang memenuhi aturan dasar: tidak negatif, nol hanya untuk titik yang sama, simetris, dan memenuhi ketaksamaan segitiga.
Untuk graf tak berarah terhubung, jarak graf \(d\) memenuhi:
- Nonnegatif:
\[ d(u,v)\geq 0. \]
- Identitas:
\[ d(u,v)=0 \iff u=v. \]
- Simetri:
\[ d(u,v)=d(v,u). \]
- Ketaksamaan segitiga:
\[ d(u,w)\leq d(u,v)+d(v,w). \]
Sifat-sifat ini standar dalam pembahasan jarak graf dan menjadi dasar banyak ukuran jaringan berbasis jarak (West, 2001; Newman, 2010).
Mengapa ketaksamaan segitiga benar?
Jika path terpendek dari \(u\) ke \(v\) memiliki panjang \(d(u,v)\), dan path terpendek dari \(v\) ke \(w\) memiliki panjang \(d(v,w)\), maka dengan menggabungkan keduanya kita memperoleh walk dari \(u\) ke \(w\) dengan panjang
\[ d(u,v)+d(v,w). \]
Path terpendek dari \(u\) ke \(w\) tidak mungkin lebih panjang daripada walk ini setelah disederhanakan menjadi path. Maka
\[ d(u,w)\leq d(u,v)+d(v,w). \]
Ini adalah alasan graf terhubung dapat dipandang sebagai ruang diskret dengan konsep jarak yang sah.
5.15 Eksentrisitas simpul
Setelah jarak antar pasangan simpul didefinisikan, kita dapat meringkas posisi sebuah simpul relatif terhadap seluruh graf.
Untuk graf terhubung, eksentrisitas simpul \(v\), ditulis
\[ \operatorname{ecc}(v), \]
adalah jarak maksimum dari \(v\) ke simpul lain:
\[ \operatorname{ecc}(v)=\max_{u\in V} d(v,u). \]
Dengan kata lain, eksentrisitas \(v\) adalah seberapa jauh simpul terjauh dari \(v\).
Contoh 5.12
Ambil graf path sederhana dengan lima simpul:
\[ A-B-C-D-E. \]
Jarak dari \(A\) ke simpul lain adalah:
\[ d(A,A)=0,\quad d(A,B)=1,\quad d(A,C)=2,\quad d(A,D)=3,\quad d(A,E)=4. \]
Maka
\[ \operatorname{ecc}(A)=4. \]
Untuk simpul \(C\):
\[ d(C,A)=2,\quad d(C,B)=1,\quad d(C,C)=0,\quad d(C,D)=1,\quad d(C,E)=2. \]
Maka
\[ \operatorname{ecc}(C)=2. \]
Simpul \(C\) lebih “tengah” daripada \(A\), karena simpul terjauh dari \(C\) hanya berjarak \(2\), sedangkan simpul terjauh dari \(A\) berjarak \(4\).
Eksentrisitas memberi cara formal untuk membicarakan posisi pusat dan pinggir dalam graf.
5.16 Diameter graf
Untuk graf terhubung, diameter graf \(G\), ditulis
\[ \operatorname{diam}(G), \]
adalah eksentrisitas maksimum di antara semua simpul:
\[ \operatorname{diam}(G)=\max_{v\in V}\operatorname{ecc}(v). \]
Karena eksentrisitas adalah jarak ke simpul terjauh dari suatu simpul, diameter adalah jarak terbesar di antara semua pasangan simpul:
\[ \operatorname{diam}(G)=\max_{u,v\in V} d(u,v). \]
Contoh 5.13
Untuk graf
\[ A-B-C-D-E, \]
jarak terbesar adalah dari \(A\) ke \(E\), yaitu \(4\). Maka
\[ \operatorname{diam}(G)=4. \]
Diameter mengukur rentang terpanjang dalam graf. Dalam jaringan komunikasi, diameter memberi batas terburuk jumlah langkah minimum yang diperlukan untuk menghubungkan dua simpul mana pun dalam komponen yang sama. Dalam praktik jaringan besar, diameter kadang sulit diestimasi secara tepat jika data sangat besar atau tidak lengkap, sehingga analisis jaringan sering juga menggunakan ringkasan lain seperti rata-rata panjang lintasan atau distribusi jarak (Newman, 2010).
5.17 Radius graf dan pusat graf
Jika diameter melihat kasus terjauh secara global, radius melihat simpul terbaik dari sudut pandang jarak maksimum.
Untuk graf terhubung, radius graf \(G\), ditulis
\[ \operatorname{rad}(G), \]
adalah eksentrisitas minimum di antara semua simpul:
\[ \operatorname{rad}(G)=\min_{v\in V}\operatorname{ecc}(v). \]
Simpul yang memiliki eksentrisitas sama dengan radius disebut pusat graf atau center.
Secara formal, himpunan pusat graf adalah
\[ C(G)=\{v\in V:\operatorname{ecc}(v)=\operatorname{rad}(G)\}. \]
Contoh 5.14
Untuk graf path
\[ A-B-C-D-E, \]
eksentrisitasnya adalah:
\[ \operatorname{ecc}(A)=4, \]
\[ \operatorname{ecc}(B)=3, \]
\[ \operatorname{ecc}(C)=2, \]
\[ \operatorname{ecc}(D)=3, \]
\[ \operatorname{ecc}(E)=4. \]
Maka
\[ \operatorname{rad}(G)=2, \]
dan pusat graf adalah
\[ C(G)=\{C\}. \]
Contoh 5.15
Untuk graf path dengan empat simpul
\[ A-B-C-D, \]
eksentrisitasnya adalah:
\[ \operatorname{ecc}(A)=3, \]
\[ \operatorname{ecc}(B)=2, \]
\[ \operatorname{ecc}(C)=2, \]
\[ \operatorname{ecc}(D)=3. \]
Maka
\[ \operatorname{rad}(G)=2, \]
dan pusat graf adalah
\[ C(G)=\{B,C\}. \]
Jadi pusat graf tidak harus tunggal.
Dalam pemodelan jaringan, konsep pusat berdasarkan jarak ini berkaitan dengan gagasan bahwa simpul pusat dapat mencapai semua simpul lain dengan jarak maksimum yang relatif kecil. Namun ini berbeda dari derajat tinggi. Simpul dapat memiliki derajat kecil tetapi tetap berada di posisi struktural tengah, dan simpul dapat memiliki derajat tinggi tetapi berada di bagian pinggir jaringan.
5.18 Hubungan antara radius dan diameter
Ada hubungan dasar antara radius dan diameter:
\[ \operatorname{rad}(G)\leq \operatorname{diam}(G)\leq 2\operatorname{rad}(G) \]
untuk setiap graf terhubung \(G\).
Mari kita buktikan.
Proposisi 5.3
Jika \(G\) adalah graf terhubung, maka
\[ \operatorname{rad}(G)\leq \operatorname{diam}(G)\leq 2\operatorname{rad}(G). \]
Bukti
Karena radius adalah minimum eksentrisitas dan diameter adalah maksimum eksentrisitas, jelas bahwa
\[ \operatorname{rad}(G)\leq \operatorname{diam}(G). \]
Sekarang kita buktikan bagian kedua. Ambil sebuah simpul pusat \(c\), sehingga
\[ \operatorname{ecc}(c)=\operatorname{rad}(G). \]
Untuk sembarang dua simpul \(u,v\in V\), berdasarkan ketaksamaan segitiga,
\[ d(u,v)\leq d(u,c)+d(c,v). \]
Karena eksentrisitas \(c\) adalah jarak maksimum dari \(c\) ke simpul mana pun, kita punya
\[ d(u,c)\leq \operatorname{ecc}(c)=\operatorname{rad}(G) \]
dan
\[ d(c,v)\leq \operatorname{ecc}(c)=\operatorname{rad}(G). \]
Maka
\[ d(u,v)\leq 2\operatorname{rad}(G). \]
Karena ini berlaku untuk semua pasangan \(u,v\), maka jarak maksimum di antara semua pasangan juga memenuhi
\[ \operatorname{diam}(G)\leq 2\operatorname{rad}(G). \]
Jadi,
\[ \operatorname{rad}(G)\leq \operatorname{diam}(G)\leq 2\operatorname{rad}(G). \]
\[ \blacksquare \]
Hasil ini sederhana tetapi berguna. Ia menunjukkan bahwa radius dan diameter tidak dapat berbeda secara sembarang besar: diameter paling banyak dua kali radius.
5.19 Graf tak terhubung: bagaimana memperlakukan jarak?
Banyak graf data tidak terhubung. Karena itu kita perlu berhati-hati ketika memakai ukuran berbasis jarak.
Jika \(u\) dan \(v\) berada dalam komponen berbeda, maka tidak ada path dari \(u\) ke \(v\). Dalam konvensi buku ini,
\[ d(u,v)=\infty. \]
Akibatnya, diameter graf tak terhubung juga dapat dianggap tak hingga jika dihitung atas semua pasangan simpul. Namun dalam analisis data, orang sering menggunakan salah satu dari beberapa pendekatan berikut:
- Menghitung diameter hanya pada komponen terbesar.
- Menghitung jarak hanya untuk pasangan simpul yang saling terhubung.
- Melaporkan jumlah dan ukuran komponen sebelum menghitung ukuran berbasis jarak.
- Menggunakan ukuran alternatif yang dapat menangani ketakterhubungan.
Tidak ada satu pilihan yang selalu benar. Pilihan harus sesuai dengan pertanyaan statistik.
Contoh 5.16
Misalkan graf memiliki dua komponen:
\[ A-B-C \]
dan
\[ D-E. \]
Maka
\[ d(A,C)=2, \]
tetapi
\[ d(A,D)=\infty \]
karena tidak ada path dari \(A\) ke \(D\).
Jika kita melaporkan diameter seluruh graf dengan konvensi tak hingga, maka diameter graf adalah \(\infty\). Jika kita melaporkan diameter komponen terbesar \(\{A,B,C\}\), maka diameternya adalah \(2\).
Kedua laporan tersebut dapat benar, tetapi menjawab pertanyaan yang berbeda. Laporan pertama mengatakan bahwa graf secara keseluruhan tidak saling terjangkau. Laporan kedua mengatakan bahwa di dalam komponen terbesar, jarak maksimum adalah \(2\).
5.20 Keterhubungan dan representasi komputasi
Pada Bab 4, kita mempelajari matriks ketetanggaan dan daftar ketetanggaan. Konsep walk, path, dan keterhubungan dapat dibaca dari kedua representasi tersebut.
Jika kita memakai daftar ketetanggaan, maka dari sebuah simpul kita dapat melihat semua langkah satu sisi yang mungkin. Misalnya:
A: B
B: A, C, D
C: B, D
D: B, C, E
E: D, F
F: E
Dari daftar ini, kita dapat menelusuri graf:
- dari \(A\), kita dapat pergi ke \(B\);
- dari \(B\), kita dapat pergi ke \(C\) atau \(D\);
- dari \(D\), kita dapat pergi ke \(E\);
- dari \(E\), kita dapat pergi ke \(F\).
Dengan demikian kita menemukan path
\[ A,B,D,E,F. \]
Untuk graf besar, kita tidak ingin mencari path secara manual. Bab berikutnya akan memperkenalkan dua algoritma traversal dasar:
- Breadth-first search atau BFS;
- Depth-first search atau DFS.
BFS sangat penting untuk menghitung jarak terpendek dalam graf tak berbobot, sedangkan DFS sangat berguna untuk eksplorasi struktur, deteksi siklus, dan komponen terhubung. Keduanya adalah algoritma fundamental dalam ilmu komputer dan teori graf komputasional (Cormen et al., 2009).
5.21 Interpretasi statistik: aliran, dependensi, dan struktur jaringan
Konsep dalam bab ini bukan hanya kosakata matematika. Ia adalah bahasa untuk membaca struktur data yang direpresentasikan sebagai graf.