Mengidentifikasi tepi yang tidak berguna untuk jalur terpendek

Pertimbangkan grafik (masalahnya masuk akal untuk grafik langsung dan tidak langsung). Sebut matriks jarak : adalah jarak lintasan terpendek dari simpul ke simpul dalam untuk fungsi agregasi tetap tertentu (misalnya atau ). $G$ $M_G$ $G$ $M_G[i, j]$ $i$ $j$ $G$ $+$ $\max$

Saya mengatakan bahwa subgraf dari (dengan set simpul yang sama) adalah sp-setara untuk jika . Dengan kata lain, menghilangkan tepi untuk berpindah dari ke tidak mengubah panjang jalur terpendek; tepi yang dihilangkan tidak diperlukan untuk jalur terpendek. $G'$ $G$ $G$ $M_G = M_{G'}$ $G$ $G'$

Secara umum tidak ada subgraf Sp-ekuivalen tunggal dari yang minimal untuk dimasukkan. Misalnya, jika tidak diarahkan dan semua sisi memiliki bobot , setiap pohon spanning dari adalah subgraph minimal sp-ekuivalen (memang, setiap tepi dalam suatu siklus dapat dihilangkan, tetapi melepaskan pasangan simpul jelas mengubah jarak). Namun saya masih bisa menyebut edge tidak berguna jika mereka tidak dalam subgraph minimum sp-ekuivalen, diperlukan jika mereka berada di semua subgraph minimum sp-ekuivalen (yaitu, di persimpangan mereka), dan opsional jika mereka ada di beberapa dari mereka (yaitu , dalam persatuan mereka). $G$ $G$ $0$ $G$ $G$

Pertanyaan pertama saya adalah: Apakah gagasan ini memiliki nama standar?

Pertanyaan kedua saya adalah: Apa kerumitan mengklasifikasikan tepi dengan cara ini, tergantung pada apakah tidak diarahkan atau diarahkan, dan pada fungsi agregasi? $G$ $G$

(Misalnya, untuk tidak diarahkan dan untuk , subgraph minimum sp-ekuivalen mencakup pohon dengan bobot minimum, jadi setidaknya jika semua bobot tepi berbeda, klasifikasi mudah dihitung dengan menghitung pohon spanning minimum yang unik, tetapi secara umum saya tidak tahu cara kerja.) $G$ $\max$

ds.algorithms reference-request graph-algorithms shortest-path a3nm
sumber

K_{n}

$K_n$

1

$1$

K_{n}

$K_n$

G

$G$

G^{'}

$G'$

(u, v)

$(u, v)$

1 = M_{G} [u, v] < M_{G^{'}} [u, v]

$1 = M_G[u, v] < M_{G'}[u, v]$

(u, v)

$(u,v)$

u

$u$

v

$v$

u

$u$

v

$v$

max

$\max$

Anda mungkin ingin mencari "pengawet jarak"

arnab

Sasho Nikolov: Maaf, untuk grafik yang tidak diarahkan dan tidak berbobot, maksud saya adalah tepi bobot 0, bukan 1. Mengulangi ini dalam pertanyaan.

a3nm

Jika Anda mencari cara untuk menamai (atau mengkarakterisasi secara bergantian) tepi-tepi ini yang Anda sebut "tidak berguna" dan "perlu," Anda bisa menyebutnya sebagai tepi dengan sentralitas antara = 0 dan = 1, masing-masing. Setiap sisi dapat diklasifikasikan sebagai memiliki = 0, = 1 atau dalam (0,1) ukuran ketepatan waktu semua-pasangan-jalur terpendek.

Ini adalah ukuran tepi jaringan yang dipelajari dengan baik, dan ada algoritma cepat untuk memperbarui semua nilai sentralitas tepi pada penghapusan tepi (tapi saya tidak yakin tentang gangguan lainnya).

Fungsi sentralitas terintegrasi untuk sebagian besar setiap analisis jaringan yang pernah saya lihat, dan ada definisi yang berlaku untuk grafik berarah juga:

(sunting: tautan yang saya berikan pada mulanya hanya membahas sentralitas antar node, tetapi di sini adalah satu-satunya artikel wikipedia yang saya temukan yang membahas sentralitas tepi-antar: http://en.wikipedia.org/wiki/Girvan%E2%808093Newman_algorithm Namun, edge-betweenness adalah ukuran standar yang biasanya dapat ditemukan dalam paket analisis jaringan.)

JimN
sumber

Saya pikir perbedaan antara sentralitas simpul dan sentralitas tepi tidak penting karena Anda selalu dapat menambahkan node perantara ke tepi, atau menyalin node dan menambahkan satu tepi dari satu salinan ke yang lain, untuk mengurangi satu definisi ke yang lain. Ini adalah pointer yang berguna, terima kasih telah membuat saya menyadari hal ini!

a3nm

Mengidentifikasi tepi yang tidak berguna untuk jalur terpendek

Jawaban: