Grafik Berarah vs Tidak Berarah
Grafik adalah struktur matematika yang terdiri dari himpunan simpul dan tepi. Graf mewakili sekumpulan objek (diwakili oleh simpul) yang terhubung melalui beberapa tautan (diwakili oleh tepi). Dengan menggunakan notasi matematika, sebuah graf dapat direpresentasikan dengan G, di mana G=(V, E) dan V adalah himpunan simpul dan E adalah himpunan sisi. Pada graf tak berarah tidak ada arah yang berasosiasi dengan sisi-sisi yang menghubungkan simpul-simpul tersebut. Pada graf berarah terdapat arah yang berhubungan dengan sisi-sisi yang menghubungkan simpul-simpul tersebut.
Grafik Tak Berarah
Seperti disebutkan sebelumnya, graf tak berarah adalah graf yang tidak memiliki arah pada sisi-sisi yang menghubungkan simpul-simpul dalam graf tersebut. Gambar 1 menggambarkan graf tak berarah dengan himpunan simpul V={V1, V2, V3}. Himpunan sisi pada graf di atas dapat ditulis sebagai V={(V1, V2), (V2, V3), (V1, V3)}. Dapat juga dicatat bahwa tidak ada yang menghalangi penulisan himpunan sisi sebagai V={(V2, V1), (V3, V2), (V3, V1)} karena sisi-sisinya tidak memiliki arah. Oleh karena itu sisi-sisi pada graf tak berarah bukanlah pasangan terurut. Ini adalah karakteristik utama dari graf tak berarah. Graf tak berarah dapat digunakan untuk merepresentasikan hubungan simetris antara objek yang diwakili oleh simpul. Misalnya, jaringan jalan dua arah yang menghubungkan sekumpulan kota dapat direpresentasikan menggunakan graf tak berarah. Kota-kota dapat diwakili oleh simpul-simpul dalam grafik dan tepi-tepinya mewakili jalan dua arah yang menghubungkan kota-kota tersebut.
Grafik Berarah
Grafik berarah adalah graf yang sisi-sisinya pada graf yang menghubungkan simpul-simpulnya memiliki arah. Gambar 2 menggambarkan graf berarah dengan himpunan simpul V={V1, V2, V3}. Himpunan sisi pada graf di atas dapat ditulis sebagai V={(V1, V2), (V2, V3), (V1, V3)}. Sisi pada graf tak berarah adalah pasangan terurut. Secara formal, sisi e pada graf berarah dapat direpresentasikan dengan pasangan terurut e=(x, y) di mana x adalah titik yang disebut titik asal, sumber atau titik awal dari sisi e, dan titik y disebut terminus, titik akhir atau titik terminal. Misalnya, jaringan jalan yang menghubungkan sekumpulan kota menggunakan jalan satu arah dapat direpresentasikan menggunakan graf tak berarah. Kota-kota dapat diwakili oleh simpul-simpul dalam grafik dan tepi-tepi berarah mewakili jalan-jalan yang menghubungkan kota-kota dengan mempertimbangkan arah arus lalu lintas di jalan tersebut.
Apa perbedaan antara Grafik Berarah dan Grafik Tidak Berarah?
Dalam graf berarah, sisi adalah pasangan terurut, di mana pasangan terurut menyatakan arah sisi yang menghubungkan dua simpul. Di sisi lain, dalam graf tak berarah, sisi adalah pasangan tak beraturan, karena tidak ada arah yang terkait dengan sisi. Graf tak berarah dapat digunakan untuk merepresentasikan hubungan simetris antar objek. Derajat masuk dan derajat keluar setiap simpul pada graf tak berarah adalah sama, tetapi hal ini tidak berlaku untuk graf berarah. Saat menggunakan matriks untuk merepresentasikan graf tak berarah, matriks selalu menjadi graf simetris, tetapi hal ini tidak berlaku untuk graf berarah. Graf tak berarah dapat diubah menjadi graf berarah dengan mengganti setiap sisi dengan dua sisi berarah yang berlawanan arah. Namun, tidak mungkin mengubah graf berarah menjadi graf tak berarah.
