Mengapa grafik terarah penting?

18

Kami telah membaca tentang algoritma untuk MST, konektivitas yang kuat, perutean, dll dalam grafik yang diarahkan.

Juga baru-baru ini orang telah melakukan penelitian untuk algoritma yang dinamis dan toleran kesalahan untuk grafik berarah.

Tapi saya bertanya-tanya apakah ada aplikasi praktis di mana jaringan grafik yang digarisbawahi adalah "Sutradara". Selain jejaring sosial, semua masalah yang dapat saya pikirkan seperti jaringan rel / jalan, jaringan Internet, dll. Hanya menangani grafik yang tidak diarahkan.

Sunting 1: Saya mengerti bahwa ini dapat digunakan untuk memodelkan beberapa skenario di mana tautan diarahkan tetapi saya bertanya-tanya seberapa sering skenario ini terjadi di dunia nyata, dan seberapa penting studi toleransi kesalahan untuk grafik yang diarahkan.

graphs graph-theory fault-tolerance chyle
sumber
6
Dua kelas grafik terarah paling terkenal dalam semua ilmu komputer adalah pohon dan DAG (Directed Acyclic Graph). Pohon itu digunakan dalam banyak hal (misalnya pohon keluarga, hierarki); DAG dapat melakukan versi yang lebih canggih dari itu. DAG digunakan pada dasarnya setiap kali Anda memiliki satu set entitas yang memiliki ketergantungan satu sama lain. Ketika masalah Anda memiliki komponen "waktu" atau "langkah-demi-langkah", keteraturan menunjukkan bahwa kemajuan yang tak terhindarkan. Anda melihat DAG dalam hal-hal seperti diagram alir, perangkat lunak manajemen paket dan formulir SSA-representasi menengah kompiler.
Iwillnotexist Idonotexist
2
Oke, apa pertanyaan Anda yang sebenarnya? Apakah Anda ingin tahu mengapa grafik terarah penting atau mengapa toleransi kesalahan dalam grafik terarah penting? Itu adalah dua pertanyaan yang sepenuhnya terpisah.
David Richerby
2
Contoh Anda, walaupun secara fisik "tidak diarahkan" dalam implementasi, masih sering mengarahkan grafik yang beroperasi secara logis atas mereka. Misalnya, kereta api tidak melakukan perjalanan dua arah - mereka berjalan satu arah, atau yang lain, sesuai jadwal. Katakanlah seseorang tidak menjadwalkan kereta, tetapi hanya menjadwalkan penumpang. Kemudian, orang itu tertarik pada grafik yang diarahkan, meskipun fakta arbitrer bahwa kereta api secara teoritis dapat melakukan perjalanan dengan cara apapun di atas rel.
Darren Ringer
5
chyle: Jaringan pasti bisa mendapat manfaat dari diwakili oleh grafik yang diarahkan. Sebagian besar koneksi internet rumah tangga asimetris. Tautan hulu dan hilir dapat memiliki properti yang sama sekali berbeda (bandwidth, latensi, kehilangan paket, dll.)
Alexander - Reinstate Monica
1
Saya tidak tahu tentang orang lain, tetapi silsilah keluarga saya adalah digraf. Saya bukan orang tua ibu saya.

Jawaban:

36

Mengingat bahwa grafik berarah adalah grafik di mana ujung-ujungnya memiliki arah yang terkait dengannya.

Menggunakan grafik terarah Anda dapat mewakili hubungan asimetris antara node, sedangkan dalam grafik tidak terarah kita hanya bisa mewakili hubungan simetris .

Secara praktis, menggunakan grafik terarah yang dapat Anda wakili:

  • Jaringan jalan (menggunakan grafik terarah Anda dapat mewakili arah jalan);
  • hyperlink yang menghubungkan halaman web ;
  • dependensi dalam modul perangkat lunak ;
  • hubungan mangsa-predator ;
  • otomat terbatas deterministik .

Selain contoh-contoh klasik ini, Anda dapat menggambarkan banyak skenario dunia nyata lainnya (perdagangan finansial, penjadwalan, penyakit menular, kutipan, aliran kendali, dll) yang membutuhkan hubungan teratur [1] .

darioSka
sumber
4
Jawaban yang bagus Saya pikir OP lupa bahwa ketika Anda memiliki jalan, Anda sebenarnya memiliki dua jalan (satu untuk setiap arah, biasanya paralel). Mereka dapat direpresentasikan sebagai grafik sederhana, tetapi grafik terarah menambahkan informasi penting ke model.
ecc
Saya suka ini, dan saya perhatikan bahwa jawaban ini berhati-hati untuk mengatakan halaman web hyperlink terhubung - yang mengecualikan penggunaan fungsi Kembali. ;-)
SDsolar
Untuk memasukkan komentar @ ecc dalam bahasa sehari-hari, Anda memiliki dua node yang terhubung oleh dua sisi. Setiap tepi diarahkan berlawanan dengan yang lain. Ini sering terlihat dalam diagram state deterministic. Untuk jalan-jalan, ia akan mengecil menjadi satu sisi, baik diarahkan (satu arah) atau tidak terarah.
SDsolar
4
@baik juga, di mana saya berasal (California), kami memiliki jalan satu arah
k_g
5

Grafik yang diarahkan memang ada. Seperti yang disebutkan dalam komentar, Grafik Acyclic Diarah (DAG), khususnya, sangat berguna dalam banyak tugas komputasi seperti kompilasi kode.

Juga, perlu dicatat bahwa sebagian besar algoritma grafik terarah dapat digunakan dalam case yang tidak diarahkan hanya dengan mengganti setiap edge yang tidak diarahkan dengan dua edge yang diarahkan. Ganda ini, mencoba membuat grafik yang diarahkan dari grafik yang tidak diarahkan, tidak dapat dilakukan untuk sebagian besar algoritma.

Cort Ammon - Pulihkan Monica
sumber
3

Awal dari penyortiran topologis (operasi mendasar pada grafik asiklik langsung) terletak pada jaringan ketergantungan dalam manajemen proyek, khususnya metode PERT . Kahn dan Lasser sama-sama mengutip PERT dalam makalah mereka dan mendasarkan contoh mereka di atasnya, misalnya

Jaringan PERT dari 30.000 kegiatan dapat dipesan dalam waktu kurang dari satu jam dari waktu mesin.

Penjadwalan pekerjaan online masih dilakukan dengan jenis jaringan ini; misalnya sistem ETL menjadwalkan pekerjaan untuk dijalankan hanya setelah pekerjaan yang menyediakan data input mereka berjalan.

KWillets
sumber
2

Jawaban: Dari OP saya menyimpulkan bahwa pertanyaan tersebut sebenarnya terkait dengan SDGs (Signed Directed Graphs). Jadi di sini adalah jawaban saya yang membahas grafik diarahkan dasar kemudian mengarah ke SDGs.

Grafik yang diarahkan secara luas digunakan dalam analisis pohon kesalahan dalam sistem industri. Saat Anda menghilangkan penyebab kesalahan, Anda mengikuti grafik yang diarahkan untuk menjelajahi kemungkinan lain.

Grafik yang diarahkan digunakan untuk mencegah peninjauan kembali node yang kontraproduktif yang telah dihilangkan secara efektif. Dalam diagnosis kesalahan, seringkali waktu untuk pemulihan layanan sangat penting. Dalam sistem industri yang kompleks selalu ada pohon paralel berdasarkan waktu yang dapat menyebabkan total sistem shutdown jika kesalahan tidak diperbaiki dalam berbagai batasan waktu. Bolak-balik akan lebih cenderung mengarah pada kegagalan total, yang dapat menyebabkan operasi restorasi yang jauh lebih memakan waktu (seperti tangki pengeringan dan pipa untuk memulai kembali kilang).

Ini seperti memotong cabang pohon - tidak perlu kembali ke batang ketika Anda mencoba menemukan ranting tunggal.

SDG memiliki properti tambahan dalam memberikan panduan berdasarkan probabilitas atau ambang batas untuk membantu membuat keputusan saat pohon dilintasi.

Berikut ini adalah tautan ke sebuah buku bagus tentang masalah ini, yang disebut Deteksi Kesalahan dan Diagnosis dalam Sistem Industri (halaman 224), di mana ia menjelaskan manfaat diagnosis berbasis SDG:

https://books.google.com/books?id=KFLlBwAAQBAJ&pg=PA224

SDsolar
sumber