Kalkulator Matriks Ketetanggaan

Tentang Kalkulator Matriks Ketetanggaan

Kalkulator Matriks Ketetanggaan adalah utilitas teori graf yang mengonversi antara tiga representasi graf kanonik — matriks ketetanggaan, daftar sisi, dan daftar ketetanggaan — dan memperkaya hasilnya dengan analisis struktural: urutan derajat, densitas graf, komponen terhubung, dan pangkat matriks. Alat ini mendeteksi secara otomatis apakah input Anda mendeskripsikan graf berarah atau tidak berarah dan merender visualisasi SVG langsung di samping setiap hasil.

Apa Itu Matriks Ketetanggaan?

Diberikan graf G = (V, E) dengan n verteks, matriks ketetanggaan-nya adalah matriks persegi n × n A yang entrinya A[i][j] bernilai 1 jika ada sisi dari verteks i ke verteks j, dan 0 jika tidak.

Untuk graf tidak berarah, matriks ketetanggaan selalu simetris: setiap sisi {u, v} berkontribusi pada A[u][v] = 1 dan A[v][u] = 1. Untuk graf berarah (digraph), matriks mungkin asimetris, mencerminkan arah dari setiap busur.

Tiga Representasi — Pilih yang Sesuai dengan Masalah Anda

Metrik Utama yang Dihitung

Urutan Derajat

Untuk graf tidak berarah, derajat dari sebuah verteks adalah jumlah sisi yang bersentuhan dengannya (dengan loop sendiri dihitung dua kali). Untuk graf berarah, setiap verteks memiliki in-degree (busur masuk) dan out-degree (busur keluar). Daftar derajat yang diurutkan adalah invarian graf klasik yang digunakan dalam pengujian isomorfisme dan teorema realisabilitas Erdős–Gallai.

Densitas Graf

Densitas mengukur seberapa "penuh" sebuah graf relatif terhadap jumlah sisi maksimum yang mungkin pada n verteks.

Densitas 0 berarti tidak ada sisi, 1 berarti graf lengkap, dan nilai di bawah 0,1 biasanya menunjukkan graf jarang di mana daftar ketetanggaan lebih efisien ruang daripada matriks.

Komponen Terhubung

Sebuah komponen terhubung adalah himpunan bagian maksimal dari verteks sehingga setiap pasangan dihubungkan oleh sebuah jalur. Untuk graf berarah, kalkulator ini melaporkan komponen terhubung lemah (mengabaikan arah panah) — himpunan bagian yang sama dengan yang Anda dapatkan dengan memperlakukan setiap busur sebagai sisi tidak berarah.

Pangkat Matriks (A², A³ ... )

Sebuah teorema fundamental dari teori graf aljabar menyatakan bahwa entri (i, j) dari A^k sama dengan jumlah langkah (walks) dengan panjang tepat k dari verteks i ke verteks j. Konsekuensinya:

• A²[i][i] sama dengan derajat verteks i (tidak berarah), karena langkah-2 dari i ke dirinya sendiri adalah "pergi ke tetangga dan kembali".
• Trace dari A³ dibagi 6 menghitung jumlah segitiga dalam graf tidak berarah.
• Apakah Aⁿ⁻¹ memiliki entri nol memberitahu Anda apakah graf tersebut terhubung.

Format Input yang Diterima

1. Daftar sisi

Satu sisi per baris atau dipisahkan koma. Pemisah apa pun ini berfungsi: A-B, A B, A,B, A->B, A--B. Gunakan -> jika Anda ingin memaksakan interpretasi berarah.

2. Daftar ketetanggaan

Satu baris per verteks, dalam bentuk verteks: tetangga1, tetangga2, .... Urutan tidak masalah; verteks yang hilang ditambahkan secara otomatis dari daftar tetangga.

3. Matriks ketetanggaan

Satu baris per baris dengan nilai 0/1 yang dipisahkan spasi atau koma. Matriks harus berbentuk persegi. Secara opsional berikan label kustom di bidang Label matriks (jika tidak, A, B, C… akan digunakan).

Cara Menggunakan Kalkulator Ini

1. Pilih format input menggunakan selektor tab: daftar sisi, daftar ketetanggaan, atau matriks ketetanggaan.
2. Tempel atau ketik graf Anda di area teks. Untuk input matriks, tambahkan label opsional di bidang Label matriks.
3. Pilih jenis graf — biarkan pada Deteksi otomatis dan kalkulator akan menyimpulkan arah dari panah (->) atau simetri matriks. Paksa ke Berarah atau Tidak Berarah jika Anda ingin mengabaikannya.
4. Klik Konversi & Analisis Graf. Halaman hasil menunjukkan matriks ketetanggaan, perenderan SVG interaktif, dua representasi teks lainnya, statistik derajat, komponen terhubung, dan matriks jumlah langkah A² dan A³ saat graf cukup kecil.
5. Arahkan kursor ke baris matriks atau simpul graf untuk menyalakan baris/kolom yang cocok dan sisi yang bersentuhan — bukti visual instan bahwa setiap format mengkodekan informasi yang sama.

Contoh Pengerjaan

Pertimbangkan graf tidak berarah pada verteks {A, B, C, D} dengan sisi AB, BC, CA, CD. Matriks ketetanggaannya adalah:

Fakta utama yang diturunkan kalkulator:

• Simetris? Ya — mengonfirmasi tidak berarah.
• Urutan derajat: (3, 2, 2, 1) — verteks C adalah pusat (hub).
• Densitas: 2·4 / (4·3) = 0.667 — graf yang cukup padat.
• Terhubung? Ya, komponen tunggal.
• Segitiga: tepat satu (A–B–C), sebagaimana dikonfirmasi oleh tr(A³) = 6.

Aplikasi Umum

• Analisis jaringan sosial — graf pertemanan / pengikut, sentralitas.
• Graf web & sitasi — PageRank dan HITS bekerja langsung pada A dan A^T.
• Perutean & jaringan — jalur terpendek, min-cut, max-flow.
• Kimia — graf molekuler dengan atom sebagai verteks, ikatan sebagai sisi.
• Penjadwalan & resolusi dependensi — graf asiklik berarah (DAG) dalam sistem build.
• Rantai Markov — matriks stokastik baris yang diturunkan dari graf mengkodekan probabilitas transisi.

Pertanyaan yang Sering Diajukan

Apa itu matriks ketetanggaan?

Matriks ketetanggaan adalah matriks persegi n × n yang digunakan untuk merepresentasikan graf berhingga. Setiap sel A[i][j] bernilai 1 jika ada sisi dari verteks i ke verteks j, dan 0 jika tidak. Untuk graf tidak berarah, matriksnya simetris, sehingga A[i][j] = A[j][i]. Matriks memudahkan pemeriksaan apakah dua verteks terhubung dalam waktu konstan, dan pangkat matriks mengkodekan jumlah langkah di antara verteks.

Bagaimana cara mengetahui apakah sebuah graf berarah dari matriks ketetanggaannya?

Jika matriks ketetanggaan simetris, yang berarti A[i][j] sama dengan A[j][i] untuk setiap pasangan indeks, maka graf tersebut tidak berarah. Jika ada setidaknya satu pasangan di mana A[i][j] berbeda dari A[j][i], maka graf tersebut berarah. Kalkulator ini melakukan pemeriksaan simetri secara otomatis saat Anda memilih opsi Deteksi otomatis.

Apa yang direpresentasikan oleh pangkat ke-k dari matriks ketetanggaan?

Entri (i, j) dari A^k menghitung jumlah langkah (walks) dengan panjang tepat k dari verteks i ke verteks j. Misalnya, A²[i][j] adalah jumlah jalur 2-langkah, yang sama dengan jumlah tetangga bersama antara i dan j pada graf tidak berarah. Properti ini digunakan dalam algoritma untuk penghitungan segitiga, keterjangkauan, dan komputasi gaya PageRank.

Apa itu densitas graf?

Densitas graf adalah rasio jumlah sisi yang ada terhadap jumlah sisi maksimum yang mungkin. Untuk graf sederhana tidak berarah dengan n verteks, densitas = 2m / (n(n-1)). Untuk graf berarah, densitas = m / (n(n-1)). Densitas yang mendekati 0 berarti graf jarang; densitas 1 berarti graf lengkap.

Apa perbedaan matriks ketetanggaan dengan daftar ketetanggaan?

Matriks ketetanggaan menyimpan konektivitas untuk setiap pasangan verteks menggunakan n² bit, membuat pencarian tetangga O(1) tetapi penggunaan memori O(n²). Daftar ketetanggaan hanya menyimpan tetangga sebenarnya dari setiap verteks, memberikan memori O(n + m), yang jauh lebih kecil untuk graf jarang, tetapi pencarian tetangga memerlukan pemindaian linear. Matriks lebih baik untuk graf padat dan operasi aljabar matriks; daftar lebih baik untuk graf jarang dan algoritma penelusuran seperti BFS/DFS.

Apakah alat ini dapat menangani graf berbobot?

Kalkulator saat ini berfokus pada matriks ketetanggaan tidak berbobot dengan entri 0/1. Jika Anda menempelkan matriks dengan bobot numerik non-nol, setiap sel non-nol diperlakukan sebagai 1 untuk analisis struktural. Untuk komputasi graf berbobot seperti jalur terpendek, pertimbangkan alat graf berbobot khusus.

Bacaan Lebih Lanjut

• Adjacency matrix — Wikipedia
• Degree sequence — Wikipedia
• Graph density — Wikipedia
• Connected components — Wikipedia