Perbedaan Antara Grafik Berarah Dan Tidak Terarah

2024 Pengarang: Mildred Bawerman | [email protected]. Terakhir diubah: 2023-12-16 08:39

Grafik Berarah vs Tidak Terarah

Grafik adalah struktur matematika yang terdiri dari kumpulan simpul dan tepi. Grafik mewakili sekumpulan objek (diwakili oleh simpul) yang terhubung melalui beberapa tautan (diwakili oleh tepi). Dengan menggunakan notasi matematika, sebuah graf dapat direpresentasikan oleh G, di mana G = (V, E) dan V adalah himpunan simpul dan E adalah himpunan tepi. Dalam graf tidak berarah tidak ada arah yang diasosiasikan dengan tepi yang menghubungkan simpul. Dalam graf berarah ada arah yang berasosiasi dengan tepi yang menghubungkan simpul.

Grafik Tidak Berarah

Seperti yang telah disebutkan sebelumnya, graf tak berarah adalah graf yang tidak memiliki arah tepi yang menghubungkan simpul pada graf tersebut. Gambar 1 menggambarkan grafik tidak berarah dengan kumpulan simpul V = {V1, V2, V3}. Kumpulan edge 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, tepi dalam grafik yang tidak berarah tidak berpasangan. Ini adalah ciri utama dari graf tidak berarah. Grafik tidak berarah dapat digunakan untuk merepresentasikan hubungan simetris antar objek yang diwakili oleh simpul. Misalnya, jaringan jalan raya dua arah yang menghubungkan sekumpulan kota dapat direpresentasikan menggunakan grafik tidak berarah. Kota-kota dapat diwakili oleh simpul-simpul pada grafik dan ujung-ujungnya mewakili jalan dua arah yang menghubungkan kota-kota.

Grafik Berarah

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

Apa perbedaan antara Grafik Berarah dan Grafik Tidak Terarah?

Dalam grafik berarah, sisi adalah pasangan berurutan, di mana pasangan berurutan mewakili arah tepi yang menghubungkan dua simpul. Di sisi lain, dalam graf tak berarah, sebuah sisi adalah pasangan tak beraturan, karena tidak ada arah yang diasosiasikan dengan sebuah sisi. Grafik tidak berarah dapat digunakan untuk merepresentasikan hubungan simetris antar objek. Derajat masuk dan keluar tiap simpul pada graf tak berarah sama tetapi ini tidak berlaku untuk graf berarah. Saat menggunakan matriks untuk merepresentasikan graf tak berarah, matriks selalu menjadi graf simetris, tetapi ini tidak berlaku untuk graf berarah. Grafik tidak berarah dapat diubah menjadi grafik berarah dengan mengganti setiap sisi dengan dua sisi berarah yang berlawanan arah. Namun, tidak mungkin untuk mengubah grafik berarah menjadi grafik tidak berarah.