Perbezaan Antara Graf Diarahkan Dan Tidak Diarahkan

2024 Pengarang: Mildred Bawerman | [email protected]. Diubah suai terakhir: 2023-12-16 08:40

Graf Diarahkan vs Tidak Diarahkan

Grafik adalah struktur matematik yang terdiri daripada set bucu dan tepi. Grafik mewakili sekumpulan objek (diwakili oleh bucu) yang dihubungkan melalui beberapa pautan (diwakili oleh tepi). Dengan menggunakan notasi matematik, grafik dapat diwakili oleh G, di mana G = (V, E) dan V adalah himpunan bucu dan E adalah set tepi. Dalam grafik yang tidak diarahkan tidak ada arah yang berkaitan dengan tepi yang menghubungkan bucu. Dalam graf yang diarahkan terdapat arah yang berkaitan dengan tepi yang menghubungkan bucu.

Graf Tidak Terarah

Seperti yang disebutkan sebelumnya, grafik yang tidak diarahkan adalah grafik di mana tidak ada arah di tepi yang menghubungkan bucu dalam grafik. Gambar 1 menggambarkan graf yang tidak diarahkan dengan set bucu V = {V1, V2, V3}. Set tepi pada grafik di atas boleh ditulis sebagai V = {(V1, V2), (V2, V3), (V1, V3)}. Juga dapat diperhatikan bahawa tidak ada yang mencegah menulis set tepi sebagai V = {(V2, V1), (V3, V2), (V3, V1)} kerana tepi tidak mempunyai arah. Oleh itu tepi dalam graf yang tidak diarahkan tidak berpasangan. Ini adalah ciri utama graf yang tidak diarahkan. Grafik tidak terarah dapat digunakan untuk mewakili hubungan simetri antara objek yang diwakili oleh bucu. Contohnya, rangkaian jalan dua arah yang menghubungkan sekumpulan bandar dapat diwakili menggunakan grafik yang tidak diarahkan. Bandar-bandar dapat diwakili oleh bucu-bucu dalam grafik dan pinggirnya mewakili jalan dua arah yang menghubungkan bandar-bandar.

Graf Terarah

Graf terarah adalah graf di mana tepi dalam grafik yang menghubungkan bucu mempunyai arah. Rajah 2 menggambarkan graf yang diarahkan dengan set bucu V = {V1, V2, V3}. Set tepi pada grafik di atas boleh ditulis sebagai V = {(V1, V2), (V2, V3), (V1, V3)}. Tepi dalam graf yang tidak diarahkan adalah pasangan yang disusun. Secara formal, tepi e dalam grafik yang diarahkan dapat diwakili oleh pasangan yang disusun e = (x, y) di mana x adalah bucu yang disebut asal, sumber atau titik awal tepi e, dan bucu y disebut sebagai ujung, menamatkan titik puncak atau titik terminal. Sebagai contoh, rangkaian jalan raya yang menghubungkan sekumpulan bandar menggunakan jalan sehala dapat diwakili menggunakan grafik yang tidak diarahkan. Bandar-bandar dapat diwakili oleh bucu-bucu dalam grafik dan tepi yang diarahkan mewakili jalan-jalan yang menghubungkan bandar-bandar dengan mempertimbangkan arah lalu lintas yang mengalir di jalan.

Apakah perbezaan antara Graf Terarah dan Graf Tidak Terarah?

Dalam graf terarah tepi adalah pasangan tertib, di mana pasangan tertib mewakili arah tepi yang menghubungkan dua bucu. Sebaliknya, dalam grafik yang tidak diarahkan, tepi adalah pasangan yang tidak tersusun, kerana tidak ada arah yang terkait dengan tepi. Grafik tidak terarah dapat digunakan untuk mewakili hubungan simetri antara objek. Tahap dalam dan luar darjah setiap nod dalam graf yang tidak diarahkan adalah sama tetapi ini tidak berlaku untuk graf yang diarahkan. Apabila menggunakan matriks untuk mewakili graf yang tidak diarahkan, matriks selalu menjadi graf simetri, tetapi ini tidak berlaku untuk graf yang diarahkan. Graf yang tidak diarahkan dapat ditukar menjadi graf yang diarahkan dengan menggantikan setiap tepi dengan dua tepi yang diarahkan ke arah yang bertentangan. Walau bagaimanapun, tidak mungkin untuk menukar graf yang diarahkan ke grafik yang tidak diarahkan.