Panjang rata-rata jalur st (sederhana) dalam grafik berarah

11

Mengingat fakta bahwa pencacahan jalur - t adalah masalah # P-complete, mungkinkah ada metode yang efisien yang menghitung (atau setidaknya perkiraan) panjang rata-rata jalur s - t tanpa menyebutkannya? Bagaimana jika jalur diizinkan untuk mengunjungi kembali simpul?stst

Hasil yang relevan pada grafik khusus juga dapat membantu.

liuyu
sumber
1
Jika jalur diizinkan untuk meninjau kembali simpul, maka jalur yang tidak sederhana menyiratkan bahwa tidak ada panjang rata-rata, karena panjangnya cenderung tak terhingga. s-t
Shaull
@ Samull, Anda benar. Saya sedang memikirkan waktu memukul jalan acak dari ke t . Tetapi panjang rata - rata memang cenderung tak terbatas tanpa kendala lebih lanjut. st
liuyu
ini tampaknya sangat maju, rekomendasikan bermigrasi ke cstheory
vzn
Jika saya mengerti benar, pertanyaan ini mungkin menarik bagi Anda untuk grafik khusus.
Juho
1
Sepertinya ini mungkin terkait dengan aliran jaringan maks? juga perhatikan untuk grafik dunia kecil dan berbagai grafik lainnya dengan beberapa simetri, itu akan cenderung menuju panjang jalur rata - rata . algoritma yang cukup alami mungkin untuk secara acak mengambil sampel jalur - t dan melihat standar deviasi hasil. st
vzn

Jawaban:

3

menghitung / memperkirakan / memperkirakan panjang jalur rata - rata telah dipelajari untuk beberapa model grafik acak termasuk model Erdos-Renyi dan jaringan bebas skala Barabasi-Albert, dan juga grafik dunia kecil Strogatz yang mungkin cocok sebagai perkiraan untuk grafik Anda. [akan lebih baik jika Anda dapat mempersempit / merinci beberapa sifat / karakteristik grafik yang Anda pelajari.]

vzn
sumber
ststst