Sebenarnya sudah ada artikel tentang Habré tentang algoritma ini, namun tidak mencakup bukti kebenaran dan beberapa langkah dari algoritma tersebut. Saya memutuskan untuk membuat versi referensi yang lebih banyak dari artikel itu dengan analisis lengkap.
Posting ini akan berguna bagi siswa dari disiplin "Algoritma dan Teori Grafik", serta mereka yang ingin meningkatkan / menyegarkan pengetahuan mereka tentang algoritma pada grafik.
Untuk memahami algoritma Kosarayu, Anda perlu mengetahui beberapa konsep teori graf
Konsep dasar
Simpul u, v disebut terhubung kuat jika graf G berisi jalur (tidak harus berupa garis lurus) u → v Dan v → u (Kami menyatakan simpul yang terhubung kuat dengan u↔v)
Komponen yang terhubung dengan kuat adalah subgraf yang terhubung kuat secara maksimal sehubungan dengan inklusi.
Membalik grafik - mengubah arah semua sisi pada grafik ke arah sebaliknya (sisi dua arah tetap dengan sendirinya)
Membalik grafik - proses memutar tepi ke arah yang berlawanan (tepi dua arah akan tetap dengan sendirinya)
Beberapa lemma yang cukup jelas dapat dikutip:
1. Komponen yang terhubung kuat adalah himpunan simpul yang termasuk dalam himpunan siklus yang
memiliki setidaknya satu simpul yang sama
2.
3. u ↔ v v ↔ w, u ↔ v ↔ w
4.
:
(DFS), «» . «», DFS ( ).
DFS
DFS .
DFS
, : : , :
DFS
( , , )
,
:
1:
'?'
DFS ( 2 , ; , , )
, - ( ) 1
, () ( ) -- DFS -- .
2:
3:
DFS, ,
DFS
3
, :
u v ⇔ DFS
:
⇒
u v G, ( 2), , .
⇐
u v . , r .
r 3 , 1 , u v. 2 :
r . u r v r ( 2). u v ( 3)
r , v. r v , r — ( , v , r, ). ( , ), , v r 3 ( )
, 1 2 , u v
O(V+E)
, , O(V+E) . ( )
, O(V+E)
, — O(V+E)
, O(V+E) .
, .
Misalnya: memproyeksikan jaringan transportasi ke grafik. Algoritme akan membantu memeriksa jaringan transport yang baru dibuat untuk keterjangkauan setiap simpul dari setiap simpul (untuk memastikan bahwa ada jalur dari pinggiran ke tengah dan belakang).
Anda dapat menguji sistem saluran di gedung dengan algoritme; aliran arus dalam perangkat semikonduktor
Anda dapat berpikir lebih luas: kami memproyeksikan sistem peredaran darah makhluk hidup, yang diinstruksikan untuk Anda buat sebagai bagian dari proyek rekayasa genetika, di suatu tempat pada tahun 2077). Algoritma ini akan membantu untuk mengetahui apakah darah mencapai dari jantung ke organ dan punggung.