Algoritme komponen yang terhubung dengan kuat untuk grafik berarah

Saya telah membaca tentang algoritma untuk menemukan komponen yang sangat terhubung dalam grafik yang diarahkan $G=(V,E)$. Ini mempertimbangkan dua DFS mencari dan langkah kedua adalah transposing grafik asli .$G^T$

Algoritma adalah sebagai berikut:

1. Jalankan DFS pada (mulai dari titik awal yang berubah-ubah), catat waktu penyelesaian dari semua simpul.$G$
2. Hitung transposnya,
3. Jalankan DFS pada , mulai dari titik dengan waktu penyelesaian terakhir, membentuk pohon yang berakar pada titik tersebut. Setelah pohon selesai, lanjutkan ke vertex yang belum dikunjungi dengan waktu penyelesaian terbaru berikutnya dan bentuk pohon lain menggunakan DFS dan ulangi sampai semua simpul dalam dikunjungi.$G^T$$G^T$
4. Keluarkan simpul di setiap pohon yang dibentuk oleh DFS kedua sebagai komponen yang terhubung sangat kuat.

Pertanyaanku adalah :

1. Apa intuisi di balik langkah tengah ini menghitung transpos?

Transposing matriks adjecency $A$ tidak

$\qquad A[i,j] = 1 \iff A^T[j,i] = 1$.

Dalam hal grafik, itu artinya

$\qquad u \to_G v \iff v \to_{G^T} u$.

Dengan kata lain, transposing membalikkan arah semua tepi. Catat itu$G^T$ memiliki komponen kuat yang sama dengan $G$.

Algoritma yang Anda lihat adalah algoritma Kosaraju . Berhati-hatilah dengan gagasan Anda tentang "waktu penyelesaian": ini bukan waktu simpul dikunjungi, tetapi ketika pencarian telah melintasi subgraf yang dapat dijangkau darinya. Wikipedia mengusulkan untuk menggunakan tumpukan untuk mengelola ini, yang menurut saya adalah ide yang bagus.

Mengapa itu benar untuk digunakan $G^T$, secara intuitif? Menganggap$x$ adalah simpul pertama dari komponen kuatnya yang dikunjungi oleh DFS.

• DFS menyala $G$ melintasi seluruh komponen kuat dari $x$ setelah mencapai $x$, ditambah beberapa lainnya melalui tepi yang meninggalkan komponen.
• Karena kami menggunakan urutan tumpukan untuk mengingat urutan node, $x$ juga merupakan simpul pertama dari komponen kuatnya yang dikunjungi (sebagai simpul awal, datar) pada fase kedua.
• Sejak $G$ dan $G^T$ memiliki komponen kuat yang sama, semua node dalam komponen kuat $x$ dikunjungi saat mencari $G^T$ dari $x$. Tepi tersebut meninggalkan komponen pada titik fase pertama ke arah yang salah$G^T$dan karenanya tidak diikuti. Semua tepi meninggalkan komponen$x$ di $G^T$ telah dihapus karena urutan tumpukan.

Pemahaman saya:

Saat Anda menjalankan DFS pada grafik DAG apa pun yang melacak waktu penyelesaian, satu - satunya hal yang dapat Anda jamin adalah bahwa simpul wastafel tidak akan pernah mendapatkan waktu penyelesaian tertinggi [1] . Tetapi pada saat yang sama, waktu penyelesaian terendah dapat muncul di komponen grafik mana pun . Oleh karena itu, itu membuat waktu penyelesaian terendah menjadi tidak berguna.

Pada dasarnya, fakta [1] tidak berguna dalam grafik asli juga, tetapi sangat berguna dalam grafik yang ditransformasikan . Saat Anda pindah, pernyataan ini mengarah ke yang berikut:

Dalam grafik transposisi, node yang tenggelam dalam grafik non-transposisi akan selalu mendapatkan waktu penyelesaian tertinggi .