Memperlakukan grafik yang tidak terarah sebagai subkategori dari grafik yang diarahkan

10

Secara kasar, grafik tidak terarah sangat mirip dengan grafik terarah di mana untuk setiap sisi (v, w), selalu ada sisi (w, v). Itu menunjukkan bahwa mungkin dapat diterima untuk melihat grafik yang tidak diarahkan sebagai bagian dari grafik yang diarahkan (mungkin dengan batasan tambahan bahwa penambahan / penghapusan tepi hanya dapat dilakukan dalam pasangan yang cocok).

Namun, buku teks biasanya tidak mengikuti perlakuan ini, dan lebih memilih untuk mendefinisikan grafik yang tidak diarahkan sebagai konsep yang terpisah, daripada subkategori dari grafik yang diarahkan. Apakah ada alasan untuk itu?

graphs terminology maks
sumber
2
Perhatikan bahwa ada juga "grafik campuran": grafik di mana ujung-ujungnya dapat diarahkan atau tidak. Dalam hal ini sepasang tepi terarah tidak sama dengan tepi tidak berarah antara dua node. Misalnya: pertimbangkan jalan: Anda dapat memiliki sepasang jalan satu arah antara dua titik yang berlawanan arah, atau jalan dua arah tunggal. Ini penting dalam beberapa kasus: misalnya Anda tidak ingin perangkat navigasi memberi tahu pengguna untuk melakukan putar balik antara dua jalan satu arah jika ada penghalang di tengahnya, sementara itu dimungkinkan untuk melakukannya di jalan dua arah tunggal.
Bakuriu

Jawaban:

8

Anda benar sekali; itu cara yang sangat valid untuk melihat grafik yang tidak diarahkan.

Terkadang, dalam grafik yang tidak terarah, beberapa hal menjadi lebih mudah dan lebih bersih untuk dipikirkan. Misalnya, Anda tidak perlu khawatir tentang perbedaan antara komponen yang terhubung dengan lemah vs komponen yang sangat terhubung dalam grafik yang tidak diarahkan. Algoritma untuk grafik yang tidak diarahkan kadang-kadang bisa lebih efisien atau lebih sederhana daripada jika kita menerapkan algoritma yang sesuai untuk grafik yang diarahkan.

Jadi: mungkin beberapa buku teks memilih untuk mengikuti perlakuan ini karena memungkinkan mereka memperkenalkan masalah terlebih dahulu dalam konteks (lebih mudah) grafik yang tidak terarah, dan kemudian menggeneralisasi ke kasus (lebih keras) dari grafik yang diarahkan. Itu hanya spekulasi.

DW
sumber
3

Lihat halaman ini untuk contoh masalah yang bentuk grafiknya tidak diarahkan sebenarnya lebih sulit daripada bentuk grafik yang diarahkan. Ini termasuk, misalnya, menemukan siklus negatif-berat, dan menghitung jumlah siklus Euler. Bagi saya, masalah-masalah ini tampaknya lebih sulit dalam grafik tidak terarah karena bagian dari tugas dapat dibingkai sebagai entah bagaimana memilih "arah" yang tepat untuk setiap sisi - yang tentu saja "sudah dilakukan untuk kita" ketika grafik diarahkan.

j_random_hacker
sumber
1
Oh benar Misalnya, siklus Euler ketika didefinisikan dalam bentuk grafik terarah, harus mensyaratkan bahwa "tidak lebih dari satu sisi digunakan dari setiap pasangan (v, w), (w, v)" - membuat gagasan untuk merepresentasikan grafik yang tidak diarahkan. sebagai digraf yang kurang menarik.
Maks.
0

Sulit memotivasi sesuatu yang sangat umum tiba-tiba; mungkin membuat bukti dan buku teks lebih sederhana, tetapi tidak selalu lebih mudah untuk dipahami dan diikuti secara intuitif.
Orang biasanya merasa lebih intuitif untuk mempelajari konsep sederhana dan kemudian menggeneralisasikannya ke sesuatu yang lebih abstrak, daripada mendefinisikan beberapa konsep super-umum dan abstrak dan kemudian instantiate kasus-kasus khusus. Ini mungkin salah satu dari kasus-kasus itu.

pengguna541686
sumber