Graf dan Aplikasi

Banyak masalah dunia sebenar boleh diselesaikan menggunakan algoritma graf. Graf berguna dalam memodelkan dan menyelesaikan masalah dunia sebenar. Sebagai contoh, masalah untuk mencari bilangan penerbangan paling sedikit antara dua bandar boleh dimodelkan menggunakan graf, di mana bucu mewakili bandar dan tepi mewakili penerbangan antara dua bandar bersebelahan, seperti ditunjukkan dalam Rajah di bawah. Masalah mencari bilangan minimum penerbangan sambungan
antara dua bandar dikurangkan kepada mencari laluan terpendek antara dua bucu dalam graf.

Kajian masalah graf dikenali sebagai teori graf. Teori graf telah diasaskan oleh Leonhard Euler pada tahun 1736, apabila beliau memperkenalkan istilah graf untuk menyelesaikan masalah Tujuh Jambatan Königsberg yang terkenal. Bandar Königsberg, Prusia (kini Kaliningrad, Rusia), dibahagikan dengan Sungai Pregel. Terdapat dua pulau di sungai. Bandar dan pulau itu dihubungkan oleh tujuh jambatan, seperti yang ditunjukkan dalam Rajah di bawah (a). Persoalannya, bolehkah seseorang berjalan-jalan, menyeberangi setiap jambatan tepat sekali, dan kembali ke titik permulaan? Euler membuktikan bahawa ia tidak mungkin.

Untuk mewujudkan bukti, Euler mula-mula mengabstrak peta bandar Königsberg dengan menghapuskan semua jalan, menghasilkan lakaran yang ditunjukkan dalam Rajah di atas (a). Seterusnya, dia menggantikan setiap jisim darat dengan titik, dipanggil puncak atau nod, dan setiap jambatan dengan garis, dipanggil tepi, seperti yang ditunjukkan dalam Rajah di atas (b). Struktur dengan bucu dan tepi ini dipanggil graf.

Melihat graf, kami bertanya sama ada terdapat laluan bermula dari mana-mana bucu, merentasi semua tepi tepat sekali dan kembali ke bucu permulaan. Euler membuktikan bahawa untuk laluan sedemikian wujud, setiap bucu mesti mempunyai bilangan tepi genap. Oleh itu, masalah Tujuh Jambatan Königsberg tiada penyelesaian.

Masalah graf selalunya diselesaikan menggunakan algoritma. Algoritma graf mempunyai banyak aplikasi dalam pelbagai bidang, seperti dalam sains komputer, matematik, biologi, kejuruteraan, ekonomi, genetik dan sains sosial.

Terminologi Graf Asas

Graf terdiri daripada bucu dan tepi yang menghubungkan bucu. Bab ini tidak menganggap bahawa anda mempunyai pengetahuan terdahulu tentang teori graf atau matematik diskret. Kami menggunakan istilah biasa dan mudah untuk mentakrifkan graf.

Apakah itu graf? Graf ialah struktur matematik yang mewakili hubungan antara entiti dalam dunia sebenar. Sebagai contoh, graf dalam Rajah di atas mewakili penerbangan antara bandar dan graf dalam Rajah di bawah (b) mewakili jambatan antara jisim darat.

Graf terdiri daripada set bucu yang tidak kosong (juga dikenali sebagai nod atau titik) dan satu set tepi yang menyambungkan bucu. Untuk kemudahan, kami mentakrifkan graf sebagai G = (V, E), di mana V mewakili satu set bucu dan E mewakili satu set tepi. Contohnya, V dan E bagi graf dalam Rajah di bawah adalah seperti berikut:

V = {"Seattle", "San Francisco", "Los Angeles",
"Denver", "Kansas City", "Chicago", "Boston", "New York",
"Atlanta", "Miami", "Dallas", "Houston"};

E = {{"Seattle", "San Francisco"},{"Seattle", "Chicago"},
{"Seattle", "Denver"}, {"San Francisco", "Denver"},
...
};

Graf mungkin diarahkan atau tidak terarah. Dalam graf terarah, setiap tepi mempunyai arah, yang menunjukkan bahawa anda boleh bergerak dari satu bucu ke bucu yang lain melalui tepi. Anda boleh memodelkan perhubungan ibu bapa/anak menggunakan graf terarah, dengan tepi dari bucu A ke B menunjukkan bahawa A ialah induk kepada B. Rajah di bawah (a) menunjukkan graf terarah.

Dalam graf tidak terarah, anda boleh bergerak dalam kedua-dua arah antara bucu. Graf dalam Rajah di bawah tidak terarah.

Tepi mungkin ditimbang atau tidak ditimbang. Sebagai contoh, anda boleh menetapkan berat untuk setiap tepi dalam graf dalam Rajah di atas untuk menunjukkan masa penerbangan antara kedua-dua bandar.

Dua bucu dalam graf dikatakan bersebelahan jika ia disambungkan dengan tepi yang sama. Begitu juga, dua tepi dikatakan bersebelahan jika ia disambungkan pada bucu yang sama. Tepi dalam graf yang bergabung dengan dua bucu dikatakan kejadian kepada kedua-dua bucu. darjah sesuatu bucu ialah bilangan tepi yang berdekatan dengannya.

Dua bucu dipanggil jiran jika bersebelahan. Begitu juga, dua tepi dipanggil jiran jika bersebelahan.

gelung ialah tepi yang memautkan satu bucu kepada dirinya sendiri. Jika dua bucu disambungkan oleh dua atau lebih tepi, tepi ini dipanggil tepi selari. graf ringkas ialah graf yang tidak mempunyai sebarang gelung atau tepi selari. Dalam graf lengkap, setiap dua pasang bucu disambungkan, seperti ditunjukkan dalam Rajah di bawah (b).

Graf disambungkan jika wujud laluan antara mana-mana dua bucu dalam graf. A subgraf graf G ialah graf yang set bucunya ialah subset bagi G dan set tepinya ialah subset bagi G. Contohnya, graf dalam Rajah di atas (c) ialah subgraf graf dalam Rajah di atas (b).

Anggap bahawa graf bersambung dan tidak berarah. kitaran ialah laluan tertutup yang bermula dari bucu dan berakhir pada bucu yang sama. Graf bersambung ialah pokok jika ia tidak mempunyai kitaran. pokok rentang graf G ialah subgraf bersambung G dan subgraf ialah pokok yang mengandungi semua bucu dalam G.

Atas ialah kandungan terperinci Graf dan Aplikasi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!