Apakah nol diizinkan sebagai bobot tepi, dalam grafik berbobot?

Saya mencoba menulis skrip yang menghasilkan grafik acak dan saya perlu tahu apakah suatu sisi dalam grafik berbobot dapat memiliki nilai 0.

sebenarnya masuk akal bahwa 0 dapat digunakan sebagai bobot tepi, tetapi saya telah bekerja dengan grafik dalam beberapa hari terakhir dan saya belum pernah melihat contohnya.

Diizinkan oleh siapa ? Tidak ada Administrasi Grafik Pusat yang memutuskan apa yang Anda bisa dan tidak bisa lakukan. Anda dapat mendefinisikan objek dengan cara apa pun yang nyaman bagi Anda, selama Anda jelas tentang apa definisi itu. Jika ujung tanpa bobot berguna bagi Anda, maka gunakanlah; pastikan pembaca Anda tahu itu yang Anda lakukan.

Alasan mengapa Anda biasanya tidak melihat tepi nol-bobot adalah bahwa, dalam sebagian besar konteks, tepi dengan bobot nol persis sama dengan tidak adanya tepi. Misalnya, jika grafik Anda mewakili negara dan jumlah perdagangan yang dilakukan di antara mereka, keunggulan nol-bobot berarti tidak ada perdagangan, yang sama dengan tidak memiliki keunggulan sama sekali. Jika grafik Anda mewakili jarak, tepi nol-bobot akan sesuai dengan dua tempat pada jarak nol dari satu sama lain, yang berarti mereka benar-benar berada di tempat yang sama, jadi keduanya harus diwakili oleh titik yang sama. Namun, dalam konteks lain, tepi nol-berat bisa masuk akal. Misalnya, jika grafik Anda mewakili jaringan jalan dan bobot tepi mewakili jumlah lalu lintas, ada perbedaan besar antara jalan yang tidak digunakan siapa pun (tepi nol-bobot) dan tidak ada jalan sama sekali (tidak ada tepi).

Itu tergantung pada konteksnya. Secara umum ya, tepi nol dan bahkan bobot negatif mungkin diperbolehkan. Dalam beberapa kasus tertentu bobot ujung mungkin diperlukan untuk menjadi non-negatif atau benar-benar positif (misalnya, algoritma Dijkstra mengharuskan bobot menjadi non-negatif).

Seperti yang dicatat oleh jawaban lain, Anda bebas untuk mempertimbangkan (atau mengecualikan dari pertimbangan) grafik berbobot dengan tepi nol-bobot.

Yang mengatakan, dalam pengalaman saya, konvensi yang biasa di sebagian besar aplikasi grafik tertimbang adalah untuk tidak membuat perbedaan antara tepi nol-berat dan tidak adanya tepi. Salah satu alasannya adalah bahwa, biasanya, grafik berbobot muncul sebagai generalisasi multigraf , yang pada gilirannya adalah generalisasi dari grafik sederhana.

Secara khusus, multigraf adalah grafik yang (tidak seperti grafik sederhana ) memungkinkan banyak sisi antara pasangan node yang sama. Sedangkan, dalam grafik sederhana, setiap pasangan node selalu terhubung dengan 0 atau 1 tepi, sepasang node dalam multigraph dapat dihubungkan oleh 0, 1, 2, 3 atau lebih (tetapi selalu bilangan bulat non-negatif dari ) tepi.

Generalisasi multigraf untuk memungkinkan jumlah fraksional tepi antara sepasang node kemudian secara alami mengarahkan seseorang untuk mempertimbangkan grafik berbobot, dan banyak algoritma yang bekerja pada multigraf sewenang-wenang juga dapat dibuat untuk bekerja pada grafik tertimbang tersebut. Tetapi untuk algoritma seperti itu, "bobot" dari suatu tepi benar-benar menunjukkan keberagamannya . Jadi, mengingat interpretasi ini, tidak ada perbedaan yang berarti antara "no edge" dan "0 edge" antara sepasang node: keduanya berarti hal yang persis sama.

Tentu saja, "grafik berbobot" menurut definisi sebenarnya hanyalah grafik dengan angka yang terkait dengan masing-masing sisi, dan sangat mungkin untuk menafsirkan bobot sebagai sesuatu selain dari multiplisitas, dalam hal ini perbedaan antara tidak ada tepi dan bobot nol. edge mungkin memang bermakna. Tetapi mencoba menerapkan algoritma multigraf standar untuk "grafik berbobot aneh" seperti itu tidak mungkin menghasilkan hasil yang masuk akal dalam hal interpretasi alternatif (non-multiplisitas) dari bobot tepi.

Pikirkan grafik sistem jalan di Cambridge UK, catatan dibagi antara pengendara sepeda dan pengemudi mobil, demikian juga sebagian besar tepi. Melakukannya sangat mengurangi biaya pemeliharaan data.

Sekarang jika kita mendefinisikan bobot tepi sebagai waktu tempuh dalam hitungan detik, dengan bersih setiap tepian akan memiliki dua bobot, satu untuk mobil anter untuk sepeda. Beberapa bobot akan menjadi tak terbatas karena mobil tidak diizinkan pada jalur sepeda.

Sekarang perhatikan dua persimpangan jalan yang sangat dekat satu sama lain sehingga dekat mereka hanya bergerigi oleh beberapa pos yang menghentikan pengemudi mobil. (Misalnya persimpangan jalan, di mana drive mobil hanya bisa belok kiri, tetapi pengendara sepeda bisa pergi ke segala arah.) Kami kemudian mendapatkan beberapa tepi dengan bobot tak terbatas dari pengemudi mobil dan 0 berat untuk pengendara sepeda.

(Jelas grafik kemudian dapat diproses terlebih dahulu untuk membuat grafik yang lebih sederhana untuk perutean pengendara sepeda, sebelum mengerjakan rute terbaik.)

Sepertinya Anda menggunakan bobot untuk mencoba dan mewakili dua aspek grafik yang berbeda. Yang pertama adalah apakah grafik benar-benar memiliki sisi yang dapat digambarkan (ditarik), dan yang kedua adalah bobot aktualnya.

Seperti yang telah Anda perhatikan, Anda jatuh ke dalam situasi yang membingungkan jika Anda telah menggunakan 'non-nol' sebagai indikator bahwa ada tepi (dan perlu ditarik, atau terdaftar), sementara pada saat yang sama sekarang telah menemukan situasi di mana nol bobot diklasifikasikan sebagai valid.

Pada dasarnya Anda akan memerlukan cara lain untuk mewakili keberadaan tepi (dengan asumsi Anda benar-benar membutuhkannya, dan tidak bisa hanya membuat array bobot N ^ 2, tetapi kemudian Anda jatuh ke dalam perangkap karena harus memutuskan apa yang harus dilakukan tentang loop tepi belakang ...)