Graf Berarah lwn Tidak Berarah
Graf ialah struktur matematik yang terdiri daripada set bucu dan tepi. Graf mewakili satu set objek (diwakili oleh bucu) yang disambungkan melalui beberapa pautan (diwakili oleh tepi). Menggunakan tatatanda matematik, graf boleh diwakili oleh G, di mana G=(V, E) dan V ialah set bucu dan E ialah set tepi. Dalam graf tidak terarah tiada arah yang dikaitkan dengan tepi yang menghubungkan bucu. Dalam graf terarah terdapat arah yang dikaitkan dengan tepi yang menyambungkan bucu.
Graf Tidak Arah
Seperti yang dinyatakan sebelum ini, graf tidak berarah ialah graf yang tiada arah di bahagian tepi yang menghubungkan bucu dalam graf. Rajah 1 menggambarkan graf tidak berarah dengan set bucu V={V1, V2, V3}. Set tepi dalam graf di atas boleh ditulis sebagai V={(V1, V2), (V2, V3), (V1, V3)}. Ia juga boleh diperhatikan bahawa tiada apa-apa yang menghalang menulis set tepi sebagai V={(V2, V1), (V3, V2), (V3, V1)} kerana tepi tidak mempunyai arah. Oleh itu, tepi dalam graf tidak terarah bukanlah pasangan tertib. Ini adalah ciri utama graf tidak terarah. Graf tidak terarah boleh digunakan untuk mewakili hubungan simetri antara objek yang diwakili oleh bucu. Sebagai contoh, rangkaian jalan dua hala yang menghubungkan set bandar boleh diwakili menggunakan graf tidak berarah. Bandar boleh diwakili oleh bucu dalam graf dan tepi mewakili jalan dua hala yang menghubungkan bandar.
Graf Berarah
Graf terarah ialah graf di mana tepi dalam graf yang menghubungkan bucu mempunyai arah. Rajah 2 menggambarkan graf berarah dengan set bucu V={V1, V2, V3}. Set tepi dalam graf di atas boleh ditulis sebagai V={(V1, V2), (V2, V3), (V1, V3)}. Tepi dalam graf tidak terarah ialah pasangan tertib. Secara formal, tepi e dalam graf berarah boleh diwakili oleh pasangan tertib e=(x, y) di mana x ialah bucu yang dipanggil asalan, punca atau titik awal tepi e, dan bucu y dipanggil tamat., puncak penamat atau titik terminal. Contohnya, rangkaian jalan raya yang menghubungkan set bandar menggunakan jalan sehala boleh diwakili menggunakan graf tidak berarah. Bandar boleh diwakili oleh bucu dalam graf dan tepi terarah mewakili jalan yang menghubungkan bandar dengan mengambil kira arah aliran lalu lintas di jalan raya.
Apakah perbezaan antara Graf Berarah dan Graf Tidak Berarah?
Dalam graf terarah, tepi ialah pasangan tertib, di mana pasangan tertib mewakili arah tepi yang memautkan dua bucu. Sebaliknya, dalam graf tidak berarah, tepi ialah pasangan tidak tertib, kerana tiada arah yang dikaitkan dengan tepi. Graf tidak terarah boleh digunakan untuk mewakili hubungan simetri antara objek. Darjah dalam dan darjah keluar setiap nod dalam graf tidak terarah adalah sama tetapi ini tidak benar untuk graf terarah. Apabila menggunakan matriks untuk mewakili graf tidak terarah, matriks sentiasa menjadi graf simetri, tetapi ini tidak benar untuk graf terarah. Graf tidak terarah boleh ditukar kepada graf terarah dengan menggantikan setiap tepi dengan dua tepi terarah menuju ke arah bertentangan. Walau bagaimanapun, anda tidak boleh menukar graf terarah kepada graf tidak terarah.
