Perbedaan antara grafik terarah dan tidak terarah

Grafik terarah vs tidak terarah

Grafik adalah struktur matematika yang terdiri dari set simpul dan tepi. Grafik mewakili satu set objek (diwakili oleh simpul) yang terhubung melalui beberapa tautan (diwakili oleh tepi). Menggunakan notasi matematika, grafik dapat diwakili oleh 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 yang tidak diarahkan dengan set simpul v = v1, v2, v3. Set tepi dalam grafik di atas dapat ditulis sebagai v = (v1, v2), (v2, v3), (v1, v3). Dapat juga dicatat bahwa tidak ada yang mencegah penulisan set tepi sebagai v = (v2, v1), (v3, v2), (v3, v1) ​​karena ujungnya tidak memiliki arah. Oleh karena itu tepi dalam grafik yang tidak diarahkan tidak dipesan pasangan. 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 satu set kota dapat diwakili menggunakan grafik yang tidak diarahkan. Kota -kota dapat diwakili oleh simpul dalam grafik dan tepi mewakili jalan dua arah yang menghubungkan kota -kota.

Grafik terarah

Grafik terarah adalah grafik di mana tepi dalam grafik yang menghubungkan simpul memiliki arah. Gambar 2 menggambarkan grafik terarah dengan set simpul v = v1, v2, v3. Set tepi dalam grafik di atas dapat ditulis sebagai v = (v1, v2), (v2, v3), (v1, v3). Tepi dalam grafik yang tidak diarahkan dipesan pasangan. Secara formal, tepi E dalam grafik terarah dapat diwakili oleh pasangan yang dipesan E = (x, y) di mana x adalah titik yang disebut asal, sumber atau titik awal tepi E, dan simpul Y disebut terminal , mengakhiri titik titik atau terminal. Misalnya, jaringan jalan yang menghubungkan satu set kota menggunakan jalan satu arah dapat diwakili menggunakan grafik yang tidak diarahkan. Kota -kota dapat diwakili oleh simpul dalam grafik dan tepi terarah mewakili jalan yang menghubungkan kota -kota mempertimbangkan arah yang mengalir di jalan di jalan.

Apa perbedaan antara grafik terarah dan grafik yang tidak diarahkan?

Dalam grafik terarah, tepi adalah pasangan yang dipesan, di mana pasangan yang dipesan mewakili arah tepi yang menghubungkan kedua simpul. Di sisi lain, dalam grafik yang tidak diarahkan, tepi adalah pasangan yang tidak berurutan, karena tidak ada arah yang terkait dengan tepi. Grafik yang tidak diarahkan dapat digunakan untuk mewakili hubungan simetris antar objek. Dalam derajat dan keluar derajat setiap node dalam grafik yang tidak diarahkan adalah sama tetapi ini tidak berlaku untuk grafik yang diarahkan. Saat menggunakan matriks untuk mewakili grafik yang tidak diarahkan, matriks selalu menjadi grafik simetris, tetapi ini tidak berlaku untuk grafik yang diarahkan. Grafik yang tidak diarahkan dapat dikonversi ke grafik terarah dengan mengganti setiap tepi dengan dua tepi terarah ke arah yang berlawanan. Namun, tidak mungkin untuk mengonversi grafik yang diarahkan ke grafik yang tidak diarahkan.