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

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

Hasil yang relevan pada grafik khusus juga dapat membantu.

algorithms complexity-theory graphs approximation enumeration liuyu
sumber

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

$s-t$

Shaull

@ Samull, Anda benar. Saya sedang memikirkan waktu memukul jalan acak dari

. Tetapi panjang rata - rata memang cenderung tak terbatas tanpa kendala lebih lanjut.

s

$s$

t

$t$

liuyu

ini tampaknya sangat maju, rekomendasikan bermigrasi ke cstheory

vzn

Jika saya mengerti benar, pertanyaan ini mungkin menarik bagi Anda untuk grafik khusus.

Juho

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

dan melihat standar deviasi hasil.

s

$s$

t

$t$

vzn

Jawaban: