Mengapa diameter grafik acak penting?
Saya dapat melihat diameter grafik, yang didefinisikan sebagai panjang jalur terpendek terpanjang, adalah kuantitas non-sepele dalam grafik acak misalnya grafik acak$G(n,p)$ dibentuk dengan menambahkan tepi di antaranya $n$ menunjuk secara independen dengan probabilitas $p$.
Tapi apa yang membuatnya begitu signifikan secara matematis? Hubungan apa yang dimilikinya dengan ide grafik fundamental lainnya? Selain itu, jika saya menambahkan beberapa batasan pada grafik, seperti distribusi derajat, atau batasan spasial pada simpul (yaitu grafik geometris acak), apa yang dilakukan hal ini terhadap signifikansi diameter grafik?
Jawaban
Diameter grafik penting dalam dirinya sendiri, seperti halnya bilangan kromatik atau derajat maksimumnya. Jika Anda ingin grafik Anda memodelkan jaringan, ini memberi tahu Anda jumlah maksimum 'lompatan' yang harus diambil seseorang untuk berpindah dari satu node ke node lainnya. Jika grafik Anda disematkan secara geometris sebagai, katakanlah, grafik yang setiap tepinya adalah garis lurus dengan panjang 1, maka diameter grafik (abstrak) adalah batas atas diameter grafik yang disematkan, yang dianggap sebagai bagian dari$\mathbb{R}^n$.
Membiarkan $D$ menjadi diameter grafik, $n$ pesanannya, $\Delta$ derajat maksimumnya dan $\kappa$konektivitasnya. Beberapa heuristik umum tentang bagaimana diameter berperilaku (ini adalah tren, bukan teorema):
- Jika sebuah graf memiliki diameter rendah, dan banyak simpul, maka ia harus memiliki banyak sisi, dan sisi-sisi ini harus didistribusikan dengan cara yang 'seragam' agar tidak ada dua simpul yang berjauhan.
- Jika diameter graf sangat besar dibandingkan dengan jumlah simpulnya, maka graf tersebut memiliki sisi yang lebih sedikit.
- Dalam nada yang mirip dengan titik-titik di atas, diameter dan derajat maksimum bersama-sama mengikat jumlah simpul yang dapat dimiliki sebuah grafik. Secara heuristik, Anda tidak bisa mendapatkan lebih banyak simpul dari grafik daripada jika Anda membuat pohon kedalaman$D$ yang bercabang secara kasar $\Delta-1$kali di setiap lapisan, dengan beberapa tepi ekstra untuk menutup semuanya. Mempelajari batasan ini adalah topik masalah diameter derajat .
- Sedangkan diameter dan derajat batas maksimum $n$dari atas, diameter dan konektivitas mengikatnya dari bawah. Batasnya terlihat kasar$n \geq \kappa \cdot (D-1)$.
- Diameter juga membatasi ketebalan grafik. Singkatnya, jika diameternya rendah, dan grafiknya mengandung siklus apa pun, ia harus memuat siklus yang pendek.
Akhirnya, diameter bertindak sebagai batasan kompleksitas yang bagus. Jika Anda mencoba mempelajari beberapa struktur atau fitur dalam grafik umum dan kehilangan harapan, sering kali berguna untuk mempertimbangkan apa yang terjadi pada grafik berdiameter 2 (terutama mengingat beberapa batasan lain atau kelas grafik terbatas yang menyertainya). Yang membuatnya sangat kebetulan bahwa hampir semua grafik memiliki diameter 2!