Perbedaan Antara Grafik Langsung dan Tidak Langsung

Grafik Diarahkan vs Tidak Diarahkan

Grafik adalah struktur matematika yang terdiri dari kumpulan simpul dan tepi. Grafik mewakili satu set objek (diwakili oleh simpul) yang terhubung melalui beberapa tautan (diwakili oleh tepi). Menggunakan notasi matematika, grafik dapat direpresentasikan dengan G, di mana G = (V, E) dan V adalah himpunan simpul dan E adalah himpunan tepi. Dalam grafik yang tidak diarahkan, tidak ada arah yang terkait dengan tepi yang menghubungkan simpul. Dalam grafik terarah ada arah yang terkait dengan tepi yang menghubungkan simpul.

Grafik Tidak Terarah

Seperti disebutkan sebelumnya, grafik yang tidak diarahkan adalah grafik di mana tidak ada arah di tepi yang menghubungkan simpul dalam grafik. Gambar 1 menggambarkan grafik tidak berarah dengan set simpul V = V1, V2, V3. Kumpulan tepi pada grafik di atas dapat ditulis sebagai V = (V1, V2), (V2, V3), (V1, V3). Dapat juga dicatat bahwa tidak ada yang mencegah penulisan himpunan tepi sebagai V = (V2, V1), (V3, V2), (V3, V1) karena tepi tidak memiliki arah. Oleh karena itu ujung-ujungnya dalam grafik yang tidak terarah bukan pasangan berurutan. Ini adalah karakteristik utama dari grafik yang tidak diarahkan. Grafik yang tidak diarahkan dapat digunakan untuk mewakili hubungan simetris antara objek yang diwakili oleh simpul. Misalnya, jaringan jalan dua arah yang menghubungkan sekumpulan kota dapat direpresentasikan menggunakan grafik yang tidak diarahkan. Kota-kota dapat diwakili oleh simpul dalam grafik dan ujung-ujungnya mewakili jalan dua arah yang menghubungkan kota-kota.

Grafik yang Diarahkan

Grafik berarah adalah grafik di mana ujung-ujungnya dalam grafik yang menghubungkan simpul memiliki arah. Gambar 2 menggambarkan grafik berarah dengan set simpul V = V1, V2, V3. Kumpulan tepi pada grafik di atas dapat ditulis sebagai V = (V1, V2), (V2, V3), (V1, V3). Tepi dalam grafik tidak terarah adalah pasangan yang dipesan. Secara formal, tepi e dalam grafik terarah dapat diwakili oleh pasangan terurut e = (x, y) di mana x adalah simpul yang disebut titik asal, sumber atau titik awal dari tepi e, dan simpul y disebut terminal , mengakhiri titik simpul atau terminal. Misalnya, jaringan jalan yang menghubungkan sekumpulan kota menggunakan jalan satu arah dapat direpresentasikan menggunakan grafik yang tidak diarahkan. Kota-kota dapat diwakili oleh simpul dalam grafik dan ujung-ujungnya diarahkan mewakili jalan yang menghubungkan kota-kota dengan mempertimbangkan arah arus lalu lintas di jalan..

Apa perbedaan antara Grafik Berarah dan Grafik Tidak Berarah?

Dalam grafik terarah, sebuah tepi adalah pasangan berurutan, di mana pasangan berurutan mewakili arah tepi yang menghubungkan dua simpul. Di sisi lain, dalam grafik tidak terarah, sebuah tepi adalah pasangan yang tidak terurut, karena tidak ada arah yang terkait dengan sebuah tepi. Grafik yang tidak diarahkan dapat digunakan untuk mewakili hubungan simetris antara objek. In-degree dan out-degree dari setiap node dalam grafik yang tidak diarahkan adalah sama tetapi ini tidak benar untuk grafik yang diarahkan. Ketika menggunakan matriks untuk mewakili grafik yang tidak diarahkan, matriks selalu menjadi grafik simetris, tetapi ini tidak benar untuk grafik yang diarahkan. Grafik yang tidak diarahkan dapat dikonversi ke grafik yang diarahkan dengan mengganti setiap tepi dengan dua tepi yang diarahkan ke arah yang berlawanan. Namun, tidak mungkin untuk mengkonversi grafik berarah ke grafik tidak terarah.