Apa gunanya grafik tak terbatas?

Saya baru saja membaca di Wikipedia bahasa Jerman bahwa grafik infinite adalah grafik dengan jumlah node yang tidak terbatas atau jumlah edge yang tidak terbatas. Saya hanya tahu aplikasi dan algoritma untuk grafik hingga.

Apa gunanya grafik tak terbatas?

Apa aplikasi itu? Saya tidak dapat membayangkan algoritma yang akan bekerja pada grafik tanpa batas, karena Anda tidak dapat menyimpan grafik tanpa batas. Jadi Anda tidak bisa beroperasi di sana.

Banyak masalah pencarian dalam kecerdasan buatan (seperti mencari pohon permainan dari permainan catur, atau mencari solusi untuk teka-teki seperti kubus Rubik, atau lebih umum mencari urutan tindakan yang harus dilakukan untuk mencapai beberapa tujuan yang diinginkan), di efek, algoritma pada grafik tak terbatas, meskipun jawaban yang diinginkan adalah jalur yang terbatas. Tentunya dimungkinkan untuk melakukan algoritma pada grafik tersebut, jika mereka diwakili secara implisit .

Tetapi juga benar bahwa matematika mungkin berguna bahkan jika bukan matematika dari masalah yang dapat diselesaikan dengan algoritma. Grafik tak terbatas dapat digunakan untuk memodelkan proses kelahiran dan kematian (misalnya, bagaimana aturan kami untuk pewarisan nama, dan tingkat di mana orang dilahirkan dan mati, menyebabkan distribusi nama keluarga yang tidak seragam di antara budaya manusia yang berbeda?), Untuk memberikan kerangka kerja untuk mendekati pertanyaan tentang simetri matematis (melalui grafik Cayley , yang seringkali tak terbatas), untuk menyediakan model untuk penalaran tentang sistem logika (lihat grafik Rado dan model jenuh ), dll.

$d$$d$

Di satu sisi ambang, model Ising sulit diperkirakan. Di sisi lain dari ambang, model Ising mudah diperkirakan. Kompleksitas model Ising sepanjang ambang keunikan saat ini merupakan masalah terbuka, tetapi dugaannya adalah bahwa itu bisa ditelusuri.

Yang paling baru hasil dalam pekerjaan ini adalah dengan Sly sebuah Sun. Lihat referensi mereka untuk karya terkait lainnya.

Untuk memberi Anda aplikasi tertentu yang berguna untuk memikirkan grafik tak terbatas, pertimbangkan jaringan node terdistribusi, yang masing-masing menjalankan algoritma terdistribusi yang menghasilkan dalam putaran. Dalam setiap putaran, sebuah node dapat memperbarui kondisinya dengan melakukan perhitungan lokal dan berkomunikasi dengan mengirim / menerima pesan ke / dari tetangganya. Output dari algoritma semacam itu adalah output gabungan dari semua node. Misalnya, setiap node dapat memutuskan secara lokal apakah itu bagian dari set independen.

$\Omega(\log^* n)$

Diskusi lebih lanjut tentang hal ini dapat ditemukan di sini .

grafik universal tidak terbatas & generalisasi dari grafik acak Rado yang disebutkan oleh DE. penelitian baru-baru ini di daerah tersebut dalam arah mengidentifikasi grafik universal untuk keluarga grafik F: yaitu, grafik tak terbatas milik F yang berisi semua grafik berhingga dalam F sebagai subgraf terinduksi.