UNIVERSITI PEDAGOGI NEGERI VLADIMIR
ABSTRAK
"TEORI GRAF"
Dilaksanakan:
Zudina T.V.
Vladimir 2001
1. Pengenalan
2. Sejarah kemunculan teori graf
3. Definisi asas teori graf
4. Teorem asas teori graf
5. Masalah aplikasi teori graf
6. Aplikasi teori graf dalam kursus matematik sekolah
7. Aplikasi teori graf dalam pelbagai bidang sains dan teknologi
8. Kemajuan terkini dalam teori graf
§1. SEJARAH PENAMPILAN TEORI GRAF.
Pengasas teori graf dianggap sebagai ahli matematik Leonhard Euler (1707-1783). Sejarah teori ini dapat dikesan melalui surat-menyurat saintis besar itu. Berikut adalah terjemahan teks Latin, yang diambil dari surat Euler kepada ahli matematik dan jurutera Itali Marinoni, dihantar dari St. Petersburg pada 13 Mac 1736 [lihat. hlm. 41-42]:
“Saya pernah ditanya masalah tentang sebuah pulau yang terletak di bandar Königsberg dan dikelilingi oleh sungai di mana tujuh jambatan dilemparkan memaklumkan bahawa tiada siapa yang saya masih belum dapat melakukan ini, tetapi tiada siapa yang telah membuktikan bahawa ini adalah mustahil, walaupun remeh, saya nampaknya patut diberi perhatian kerana geometri, mahupun algebra, mahupun seni gabungan tidak mencukupi untuk. selesaikannya... Selepas berfikir panjang, saya mendapati peraturan yang mudah, berdasarkan bukti yang benar-benar meyakinkan, dengan bantuan yang mungkin, dalam semua masalah seperti ini, untuk segera menentukan sama ada lencongan sedemikian boleh dibuat melalui mana-mana bilangan jambatan yang terletak dalam apa jua cara, atau sama ada jambatan Königsberg tidak dapat dikesan supaya ia boleh diwakili dalam rajah berikut[Rajah 1] , yang mana A menandakan pulau, dan B , C dan D - bahagian benua dipisahkan antara satu sama lain oleh dahan sungai. Tujuh jambatan ditunjukkan dengan huruf a , b , c , d , e , f , g ".
(RAJAH 1.1)
Mengenai kaedah yang ditemuinya untuk menyelesaikan masalah seperti ini, Euler menulis [lihat. hlm. 102-104]:
"Penyelesaian ini, mengikut sifatnya, nampaknya tidak mempunyai kaitan dengan matematik, dan saya tidak faham mengapa seseorang harus mengharapkan penyelesaian ini daripada seorang ahli matematik dan bukannya daripada mana-mana orang lain, kerana keputusan ini disokong oleh penaakulan sahaja, dan tidak ada perlu melibatkan diri untuk mencari penyelesaian ini, terdapat mana-mana undang-undang yang wujud dalam matematik Jadi, saya tidak tahu bagaimana ternyata soalan yang mempunyai sedikit kaitan dengan matematik lebih cenderung untuk diselesaikan oleh ahli matematik daripada yang lain.
Jadi, adakah mungkin untuk mengelilingi jambatan Königsberg dengan hanya sekali melalui setiap jambatan ini? Untuk mencari jawapannya, mari kita sambung surat Euler kepada Marinoni:
"Persoalannya ialah untuk menentukan sama ada mungkin untuk memintas semua tujuh jambatan ini, melalui setiap satu hanya sekali, atau tidak. Peraturan saya membawa kepada penyelesaian berikut untuk soalan ini. Pertama sekali, anda perlu melihat berapa banyak kawasan di sana. adalah, dipisahkan oleh air - seperti , yang tidak mempunyai peralihan lain dari satu ke yang lain kecuali melalui jambatan Dalam contoh ini, terdapat empat bahagian tersebut -. A , B , C , D . Perkara seterusnya yang perlu dibezakan ialah sama ada bilangan jambatan yang menuju ke bahagian individu ini adalah genap atau ganjil. Jadi, dalam kes kami, lima jambatan menuju ke bahagian A, dan tiga jambatan setiap satu menuju ke yang lain, iaitu Bilangan jambatan yang menuju ke bahagian individu adalah ganjil, dan ini sahaja sudah cukup untuk menyelesaikan masalah. Apabila ini telah ditentukan, kami menggunakan peraturan berikut: jika bilangan jambatan yang menuju ke setiap bahagian individu adalah genap, maka lencongan yang dipersoalkan akan dapat dilakukan, dan pada masa yang sama adalah mungkin untuk memulakan lencongan ini dari mana-mana bahagian. . Jika dua daripada nombor ini adalah ganjil, kerana hanya satu tidak boleh ganjil, maka walaupun peralihan boleh berlaku, seperti yang ditetapkan, tetapi hanya permulaan litar yang pastinya mesti diambil dari salah satu daripada dua bahagian tersebut yang membawa nombor ganjil. jambatan. Jika, akhirnya, terdapat lebih daripada dua bahagian di mana bilangan jambatan yang ganjil mendahului, maka pergerakan sedemikian pada umumnya adalah mustahil ... jika masalah lain, masalah yang lebih serius boleh dibawa ke sini, kaedah ini boleh memberi manfaat yang lebih besar dan sepatutnya jangan diabaikan." .
Rasional peraturan di atas boleh didapati dalam surat daripada L. Euler kepada rakannya Ehler bertarikh 3 April tahun yang sama. Kami akan menceritakan semula petikan surat ini di bawah.
Ahli matematik itu menulis bahawa peralihan adalah mungkin jika terdapat tidak lebih daripada dua kawasan di persimpangan sungai, yang membawa sejumlah jambatan yang ganjil. Untuk memudahkan untuk membayangkan ini, kami akan memadamkan jambatan yang telah dilalui dalam rajah. Adalah mudah untuk memeriksa bahawa jika kita mula bergerak mengikut peraturan Euler, menyeberangi satu jambatan dan memadamkannya, maka angka itu akan menunjukkan bahagian di mana sekali lagi tidak ada lebih daripada dua kawasan yang membawa bilangan jambatan yang ganjil, dan jika terdapat adalah kawasan dengan jambatan nombor ganjil yang akan kami letakkan di salah satu daripadanya. Teruskan begini, semua jambatan akan kita lalui sekali.
Kisah jambatan bandar Königsberg mempunyai kesinambungan moden. Mari kita buka, sebagai contoh, buku teks sekolah mengenai matematik yang disunting oleh N.Ya. Vilenkina untuk gred enam. Di dalamnya, pada halaman 98, di bawah tajuk membangunkan perhatian dan kecerdasan, kita akan menemui masalah yang berkaitan secara langsung dengan masalah yang pernah diselesaikan oleh Euler.
Masalah No. 569. Terdapat tujuh pulau di tasik, yang bersambung antara satu sama lain seperti yang ditunjukkan dalam Rajah 1.2. Pulau manakah yang patut dinaiki oleh bot supaya mereka boleh menyeberangi setiap jambatan dan sekali sahaja? Mengapa pengembara tidak boleh diangkut ke pulau itu? A ?
(RAJAH 1.2)
Penyelesaian. Memandangkan masalah ini serupa dengan masalah jambatan Königsberg, apabila menyelesaikannya kita juga akan menggunakan peraturan Euler. Akibatnya, kami mendapat jawapan berikut: bot mesti menghantar pelancong ke pulau itu E atau F supaya mereka boleh menyeberangi setiap jambatan sekali. Dari peraturan Euler yang sama ia mengikuti bahawa lencongan yang diperlukan adalah mustahil jika ia bermula dari pulau A .
Kesimpulannya, kami perhatikan bahawa masalah jambatan Königsberg dan masalah yang serupa, bersama-sama dengan satu set kaedah untuk kajian mereka, membentuk satu cabang matematik yang sangat penting dalam istilah praktikal, yang dipanggil teori graf. Kerja pertama pada graf adalah milik L. Euler dan muncul pada tahun 1736. Selepas itu, Koenig (1774-1833), Hamilton (1805-1865), dan ahli matematik moden C. Berge, O. Ore, A. Zykov bekerja pada graf.
§2. TEORI ASAS TEORI GRAF
Teori graf, seperti yang dinyatakan di atas, adalah disiplin matematik yang dicipta oleh usaha ahli matematik, oleh itu pembentangannya termasuk definisi ketat yang diperlukan. Jadi, mari kita teruskan ke pengenalan teratur konsep asas teori ini.
Definisi 2.01. Kira ialah himpunan bilangan mata terhingga yang dipanggil puncak graf, dan garisan berpasangan yang menghubungkan beberapa bucu ini, dipanggil tulang rusuk atau arka graf.
Definisi ini boleh dirumus secara berbeza: kira dipanggil set mata tidak kosong ( puncak) dan segmen ( tulang rusuk), kedua-dua hujungnya tergolong dalam set mata tertentu (lihat Rajah 2.1).
(RAJAH 2.1)
Dalam perkara berikut, kami akan menandakan bucu graf dengan huruf Latin A , B ,C ,D. Kadangkala graf secara keseluruhan akan dilambangkan dengan satu huruf besar.
Definisi 2.02. Bucu graf yang bukan milik mana-mana tepi dipanggil terpencil .
Definisi 2.03. Graf yang hanya terdiri daripada bucu terpencil dipanggil sifar - kira .
Jawatan: O " – graf dengan bucu yang tidak mempunyai tepi (Rajah 2.2).
(RAJAH 2.2)
Definisi 2.04. Graf di mana setiap pasangan bucu disambungkan dengan tepi dipanggil lengkap .
Jawatan: U " – graf yang terdiri daripada n bucu dan tepi yang menghubungkan semua pasangan yang mungkin bagi bucu ini. Graf sedemikian boleh diwakili sebagai n– segi tiga di mana semua pepenjuru dilukis (Rajah 2.3).
(RAJAH 2.3)
Definisi 2.05. Ijazah puncak ialah bilangan tepi yang mempunyai bucu.
Jawatan: hlm (A) – darjah puncak A . Sebagai contoh, dalam Rajah 2.1: hlm (A)=2, hlm (B)=2, hlm (C)=2, hlm (D)=1, hlm (E)=1.
Definisi 2.06. Kira, darjah semua k yang bucunya sama dipanggil homogen kira darjah k .
Rajah 2.4 dan 2.5 menunjukkan graf homogen darjah kedua dan ketiga.
(RAJAH 2.4 dan 2.5)
Definisi 2.07. Supplement diberi graf ialah graf yang terdiri daripada semua tepi dan hujungnya yang mesti ditambah pada graf asal untuk mendapatkan graf yang lengkap.
Rajah 2.6 menunjukkan graf asal G , terdiri daripada empat bucu dan tiga segmen, dan dalam Rajah 2.7 - pelengkap graf ini - graf G " .
(RAJAH 2.6 dan 2.7)
Kita lihat dalam Rajah 2.5 terdapat tulang rusuk A.C. Dan BD bersilang pada satu titik yang bukan bucu graf. Tetapi terdapat kes apabila graf tertentu perlu diwakili pada satah sedemikian rupa sehingga tepinya bersilang hanya pada bucu (isu ini akan dibincangkan secara terperinci lagi, dalam perenggan 5).
Definisi 2.08. Graf yang boleh diwakili pada satah sedemikian rupa sehingga tepinya bersilang hanya pada bucu dipanggil rata .
Sebagai contoh, Rajah 2.8 menunjukkan graf satah yang isomorfik (sama) dengan graf dalam Rajah 2.5. Walau bagaimanapun, ambil perhatian bahawa bukan setiap graf adalah satah, walaupun sebaliknya adalah benar, iaitu, mana-mana graf satah boleh diwakili dalam bentuk biasa.
(RAJAH 2.8)
Definisi 2.09. Poligon bagi graf satah yang tidak mengandungi sebarang bucu atau tepi graf dipanggil hujung .
Secara tidak formal, graf boleh dianggap sebagai satu set titik dan garis yang menghubungkan titik-titik ini, dengan atau tanpa anak panah.
Karya pertama teori graf sebagai disiplin matematik dianggap sebagai karya Euler (1736), yang menganggap masalah jambatan Köningsberg. Euler menunjukkan bahawa adalah mustahil untuk memintas tujuh jambatan bandar dan kembali ke titik permulaan dengan menyeberangi setiap jambatan tepat sekali. Teori graf menerima dorongan seterusnya hampir 100 tahun kemudian dengan perkembangan penyelidikan dalam rangkaian elektrik, kristalografi, kimia organik dan sains lain.
Tanpa menyedarinya, kami menghadapi graf sepanjang masa. Sebagai contoh, graf ialah gambar rajah laluan kereta api bawah tanah. Titik di atasnya mewakili stesen, dan garisan mewakili laluan kereta api. Dengan menyelidik keturunan kami dan menjejakinya kembali kepada nenek moyang yang jauh, kami membina apa yang dipanggil salasilah keluarga. Dan pokok ini adalah graf.
Graf berfungsi sebagai cara mudah untuk menerangkan hubungan antara objek. Kami sebelum ini telah menggunakan graf sebagai cara untuk mewakili secara visual perhubungan binari terhingga.
Tetapi graf digunakan bukan sahaja sebagai ilustrasi. Contohnya, dengan mempertimbangkan graf yang menggambarkan rangkaian jalan antara kawasan berpenduduk, anda boleh menentukan laluan dari titik A ke titik B. Jika terdapat beberapa laluan sedemikian, anda ingin memilih laluan yang optimum dalam erti kata tertentu, contohnya. paling pendek atau paling selamat. Untuk menyelesaikan masalah pemilihan, adalah perlu untuk menjalankan pengiraan tertentu pada graf. Apabila menyelesaikan masalah sedemikian, adalah mudah untuk menggunakan teknik algebra, dan konsep graf perlu diformalkan.
Kaedah teori graf digunakan secara meluas dalam matematik diskret. Tidak mustahil untuk dilakukan tanpa mereka apabila menganalisis dan mensintesis pelbagai penukar diskret: blok berfungsi komputer, pakej perisian, dll.
Pada masa ini, teori graf merangkumi banyak bahan dan sedang giat membangun. Apabila membentangkannya, kami akan mengehadkan diri kami kepada hanya sebahagian daripada hasil dan memberi penekanan utama pada penerangan dan justifikasi beberapa algoritma analisis graf yang meluas yang digunakan dalam teori bahasa formal.
Definisi asas
Graf, seperti yang telah dinyatakan dalam contoh, adalah cara untuk "memvisualisasikan" sambungan antara objek tertentu Sambungan ini boleh "diarahkan", sebagai contoh, dalam salasilah keluarga, atau "tidak berarah" (rangkaian dua hala. jalan raya). Selaras dengan ini, dalam teori graf terdapat dua jenis graf utama: terarah (atau terarah) dan tidak terarah.
Kaedah pembentangan
Setakat ini, kami telah menentukan graf terarah dan tidak terarah, menggambarkannya menggunakan lukisan. Anda boleh mentakrifkan graf sebagai sepasang set, mengikut takrifan, tetapi kaedah ini agak rumit dan agak menarik minat teori. Pembangunan pendekatan algoritma untuk menganalisis sifat graf memerlukan cara lain untuk menerangkan graf yang lebih sesuai untuk pengiraan praktikal, termasuk menggunakan komputer. Mari kita lihat tiga cara paling biasa untuk mewakili graf.
pokok
Definisi 5.5. Pokok tak berarah ialah graf tak berarah bersambung dan akiklik. Definisi 5.6. Pokok terarah ialah graf berarah bukan kontur di mana separuh darjah mana-mana bucu tidak lebih daripada 1 dan terdapat betul-betul satu bucu, dipanggil punca pokok terarah, yang separuh darjahnya ialah 0.
Pokok dengan berat terkecil
Masalah berikut dikenali dalam teori graf sebagai masalah Steiner: n mata diberikan pada satah; anda perlu menyambungkannya dengan segmen lurus sedemikian rupa sehingga jumlah panjang segmen adalah minimum.
Kaedah untuk melintasi bucu graf secara sistematik
Masalah penting dalam teori graf ialah masalah analisis global kedua-dua graf tidak terarah dan terarah. Tugas ini termasuk, sebagai contoh, tugas mencari kitaran atau kontur, mengira panjang laluan antara pasangan bucu, menyenaraikan laluan dengan sifat tertentu, dsb. Analisis graf global harus dibezakan daripada analisis tempatan, contohnya ialah masalah menentukan set pendahulu dan pengganti sesuatu bucu tetap graf terarah.
Masalah laluan dalam graf terarah berwajaran
Isomorfisme graf
Untuk graf terarah (V, E), set E lengkok boleh dianggap sebagai graf hubungan kebolehcapaian langsung binari yang ditakrifkan pada set bucu. Dalam graf tak berarah (V, E), set E tepi ialah set pasangan tak tertib. Bagi setiap pasangan tak tertib (u, v) ∈ E kita boleh andaikan bahawa bucu u dan v disambungkan oleh hubungan binari simetri p, i.e. (u, v) ∈ р dan (v, u) ∈ р.
Pengisihan topologi
Definisi 5.17. Rangkaian terarah (atau ringkasnya rangkaian) ialah graf terarah tanpa kontur*. Oleh kerana rangkaian ialah graf tanpa kontur, ia boleh ditunjukkan bahawa terdapat bucu (nod) rangkaian dengan darjah keluar sifar, serta bucu (nod) dengan darjah sifar. Yang pertama dipanggil sinki atau output rangkaian, dan yang terakhir dipanggil sumber atau input rangkaian.
Unsur-unsur siklomatik
Apabila membincangkan algoritma carian kedalaman pertama dalam graf tidak terarah, persoalan mencari kitaran asas graf telah dipertimbangkan. Dalam kes ini, kitaran asas difahamkan sebagai kitaran yang mengandungi tepat satu tepi songsang, dan surat-menyurat satu-dengan-satu telah diwujudkan antara kitaran asas dan tepi songsang timbul apabila partisi sewenang-wenangnya semua tepi graf tidak terarah ke dalam pokok (membentuk beberapa hutan tepi maksimum graf asal) dan songsang, dan dalam kes umum partition ini boleh ditentukan sepenuhnya secara bebas daripada algoritma carian kedalaman pertama. Carian mendalam-pertama hanyalah satu cara untuk melaksanakan partition sedemikian.
Teori graf ialah cabang matematik diskret yang mengkaji objek yang diwakili sebagai unsur individu (bucu) dan hubungan antara mereka (lengkok, tepi).
Teori graf berasal daripada penyelesaian masalah jambatan Königsberg pada tahun 1736 oleh ahli matematik terkenal Leonard Euler(1707-1783: dilahirkan di Switzerland, tinggal dan bekerja di Rusia).
Masalah mengenai jambatan Königsberg.
Terdapat tujuh jambatan di bandar Prusia Königsberg di Sungai Pregal. Adakah mungkin untuk mencari laluan berjalan kaki yang pergi tepat sekali di atas setiap jambatan dan bermula dan berakhir di tempat yang sama?
Graf di mana terdapat laluan yang bermula dan berakhir pada bucu yang sama dan melalui semua tepi graf tepat sekali dipanggilGraf Euler.
Urutan bucu (mungkin berulang) yang melalui laluan yang dikehendaki, seperti laluan itu sendiri, dipanggilKitaran Euler .
Masalah tiga rumah dan tiga perigi.
Terdapat tiga rumah dan tiga telaga, entah bagaimana terletak di atas kapal terbang. Lukiskan laluan dari setiap rumah ke setiap telaga supaya laluan tidak bersilang. Masalah ini telah diselesaikan (ia telah menunjukkan bahawa tiada penyelesaian) oleh Kuratovsky (1896 - 1979) pada tahun 1930.
Masalah empat warna. Membahagikan satah ke kawasan tidak bersilang dipanggil dengan kad. Kawasan peta dipanggil bersebelahan jika mereka mempunyai sempadan bersama. Tugasnya adalah untuk mewarnai peta sedemikian rupa sehingga tiada dua kawasan bersebelahan dicat dengan warna yang sama. Sejak akhir abad ke-19, hipotesis telah diketahui bahawa empat warna sudah cukup untuk ini. Hipotesis masih belum dibuktikan.
Intipati penyelesaian yang diterbitkan adalah untuk mencuba bilangan besar tetapi terhingga (kira-kira 2000) jenis contoh balas yang berpotensi kepada teorem empat warna dan menunjukkan bahawa tiada satu kes pun adalah contoh balas. Pencarian ini telah diselesaikan oleh program dalam kira-kira seribu jam operasi superkomputer.
Adalah mustahil untuk menyemak penyelesaian yang terhasil "secara manual" - skop penghitungan adalah di luar skop keupayaan manusia. Ramai ahli matematik menimbulkan persoalan: bolehkah "bukti program" sedemikian dianggap sebagai bukti yang sah? Lagipun, mungkin terdapat ralat dalam program...
Oleh itu, kita hanya boleh bergantung pada kemahiran pengaturcaraan pengarang dan percaya bahawa mereka melakukan segala-galanya dengan betul.
Definisi 7.1. Kira G= G(V, E) ialah koleksi dua set terhingga: V – dipanggil banyak bucu dan set E pasangan unsur dari V, i.e. EÍV´V, dipanggil banyak tepi, jika pasangan tidak tertib, atau banyak lengkok, jika pasangan dipesan.
Dalam kes pertama, graf G(V, E) dipanggil tidak berorientasikan, pada yang kedua - berorientasikan.
CONTOH. Graf dengan set bucu V = (a,b,c) dan set tepi E =((a, b), (b, c))
CONTOH. Graf dengan V = (a,b,c,d,e) dan E = ((a, b), (a, e), (b, e), (b, d), (b, c) , (c, d)),
Jika e=(v 1 ,v 2), еОЕ, maka mereka mengatakan bahawa tepi ialah e menyambung bucu v 1 dan v 2.
Dua bucu v 1,v 2 dipanggil bersebelahan, jika terdapat kelebihan yang menghubungkannya. Dalam keadaan ini, setiap bucu dipanggil sampingan tepi sepadan .
Dua rusuk yang berbeza bersebelahan, jika mereka mempunyai bucu sepunya. Dalam keadaan ini, setiap tepi dipanggil sampingan puncak sepadan .
Bilangan bucu graf G mari kita nyatakan v, dan bilangan tepi ialah e:
.
Perwakilan geometri graf adalah seperti berikut:
1) puncak graf ialah titik dalam ruang (di atas satah);
2) tepi graf tidak terarah – segmen;
3) lengkok graf terarah – segmen terarah.
Definisi 7.2. Jika di tepi e=(v 1 ,v 2) v 1 =v 2 berlaku, maka tepi e dipanggil gelung. Jika graf membenarkan gelung, maka ia dipanggil graf dengan gelung atau pseudograf .
Jika graf membenarkan lebih daripada satu tepi antara dua bucu, maka ia dipanggil multigraf .
Jika setiap bucu graf dan/atau tepi dilabelkan, maka graf tersebut dipanggil bertanda (atau dimuatkan ). Huruf atau integer biasanya digunakan sebagai markah.
Definisi 7.3. Graf G (V , E ) dipanggil subgraf (atau bahagian ) graf G(V,E), Jika V V, E E. Jika V = V, Itu G dipanggil merangkumi subgraf G.
Contoh 7 . 1 . Diberi graf tidak terarah.
Definisi 7.4. Graf dipanggil lengkap , Jika mana-mana dua bucunya disambungkan dengan tepi. Lengkapkan graf dengan n bucu dilambangkan dengan K n .
Kira K 2 , KEPADA 3, KEPADA 4 dan K 5 .
Definisi 7.5. Graf G=G(V, E) dipanggil dikotiledon , Jika V boleh diwakili sebagai kesatuan set terputus, katakan V=AB, jadi setiap tepi mempunyai bentuk ( v i , v j), Di mana v i A Dan v j B.
Setiap tepi menghubungkan bucu dari A ke bucu dari B, tetapi tiada dua bucu dari A atau dua bucu dari B disambungkan.
Graf bipartit dipanggil dikotiledon lengkap kira K m , n, Jika A mengandungi m puncak, B mengandungi n bucu dan untuk setiap v i A, v j B kita ada ( v i , v j)E.
Oleh itu, untuk semua orang v i A, Dan v j B terdapat tepi yang menghubungkan mereka.
K 12 K 23 K 22 K 33
Contoh 7 . 2 . Bina graf dwipartit yang lengkap K 2.4 dan graf penuh K 4 .
Graf unitn-kubus berdimensiDALAM n .
Bucu graf ialah set binari n-dimensi. Tepi menyambungkan bucu yang berbeza dalam satu koordinat.
Contoh: 
Teori graf- salah satu cabang matematik diskret yang paling meluas, digunakan secara meluas dalam menyelesaikan masalah ekonomi dan pengurusan, dalam pengaturcaraan, kimia, reka bentuk dan kajian litar elektrik, komunikasi, psikologi, psikologi, sosiologi, linguistik, dan bidang pengetahuan lain. Teori graf secara sistematik dan konsisten mengkaji sifat-sifat graf, yang boleh dikatakan terdiri daripada set titik dan set garis yang mewakili hubungan antara titik ini. Pengasas teori graf dianggap sebagai Leonhard Euler (1707-1882), yang menyelesaikan masalah jambatan Königsberg yang terkenal pada tahun 1736.
Graf dibina untuk memaparkan hubungan pada set. Biarkan, sebagai contoh, menjadi satu set A = {a1 , a 2 , ... a n)- ramai orang, dan setiap elemen akan dipaparkan sebagai titik. Sekumpulan B = {b1 , b 2 , ... b m)- banyak sambungan (garis lurus, lengkok, segmen - tidak penting lagi). Di set A hubungan perkenalan antara orang dari set ini diberikan. Membina graf daripada titik dan penghubung. Pautan akan menghubungkan pasangan orang yang mengenali antara satu sama lain. Sememangnya, bilangan kenalan sesetengah orang mungkin berbeza daripada bilangan kenalan orang lain, dan ada yang mungkin tidak mengenali sesiapa (elemen sedemikian akan menjadi mata yang tidak disambungkan kepada yang lain). Jadi kami mempunyai graf!
Apa yang pertama kali kita panggil "titik" harus dipanggil bucu graf, dan apa yang kita panggil "sambungan" harus dipanggil tepi graf.
Teori graf tidak mengambil kira sifat khusus set A Dan B. Terdapat sejumlah besar masalah khusus yang sangat berbeza, apabila menyelesaikan yang mana satu boleh melupakan sementara kandungan set tertentu dan unsur-unsurnya. Kekhususan ini tidak sama sekali menjejaskan kemajuan penyelesaian masalah, tanpa mengira kesukarannya! Sebagai contoh, apabila memutuskan sama ada ia mungkin dari satu titik a sampai ke titik e, bergerak hanya di sepanjang garis yang menghubungkan titik, tidak kira sama ada kita berurusan dengan orang, bandar, nombor, dll. Tetapi, apabila masalah itu diselesaikan, kami mendapat penyelesaian yang benar untuk mana-mana kandungan yang dimodelkan sebagai graf. Oleh itu, tidak menghairankan bahawa teori graf adalah salah satu alat yang paling popular dalam penciptaan kecerdasan buatan: lagipun, kecerdasan buatan boleh berbincang dengan teman bicara isu cinta, isu muzik atau sukan, dan isu menyelesaikan pelbagai masalah. , dan melakukan ini tanpa sebarang peralihan (penukaran) , tanpanya seseorang tidak boleh melakukannya tanpa dalam kes sedemikian.
Dan kini definisi matematik yang ketat bagi graf.
Definisi 1.Ia dipanggil graf sistem objek yang bersifat arbitrari (bucu) dan pautan (tepi) yang menghubungkan beberapa pasangan objek ini.
Definisi 2. biarlah V– (tidak kosong) set bucu, elemen v∈V- puncak. Graf G = G(V) dengan banyak bucu V terdapat keluarga pasangan tertentu dalam bentuk: e = (a, b) , Di mana a,b∈V , menunjukkan bucu yang masih bersambung. Setiap pasangan e = (a, b) - tepi graf. Sekumpulan U- banyak tepi e graf. Puncak a Dan b– titik hujung tepi e .
Graf sebagai struktur data. Penggunaan teori graf secara meluas dalam sains komputer dan teknologi maklumat adalah disebabkan oleh penambahan konsep graf sebagai struktur data kepada definisi di atas. Dalam sains komputer dan teknologi maklumat, graf ditakrifkan sebagai struktur data tak linear. Apakah itu struktur data linear dan bagaimana graf berbeza daripadanya? Struktur data linear dicirikan oleh fakta bahawa ia menghubungkan elemen melalui hubungan jenis "kejiranan mudah". Struktur data linear ialah, sebagai contoh, tatasusunan, jadual, senarai, baris gilir, tindanan, rentetan. Sebaliknya, struktur data bukan linear ialah struktur di mana elemen terletak pada tahap hierarki yang berbeza dan dibahagikan kepada tiga jenis: asal, terjana dan serupa. Jadi, graf ialah struktur data tak linear.
Perkataan graf berasal dari bahasa Yunani, daripada perkataan "Saya menulis", "Saya menerangkan". Dari awal artikel ini kita tahu apa sebenarnya yang diterangkan oleh graf: ia menerangkan perhubungan. Iaitu, mana-mana graf menerangkan hubungan. Dan sebaliknya: sebarang hubungan boleh digambarkan sebagai graf.
Konsep asas teori graf
Konsep kejadian juga perlu apabila membangunkan algoritma untuk menyelesaikan banyak masalah praktikal dengan graf. Sebagai contoh, anda boleh membiasakan diri dengan pelaksanaan perisian lintasan kedalaman-pertama bagi graf yang diwakili oleh matriks kejadian. Ideanya mudah: anda hanya boleh bergerak melalui bucu yang disambungkan dengan tepi. Dan jika beberapa nilai diberikan pada tepi ("skala", selalunya dalam bentuk nombor, graf sedemikian dipanggil berwajaran atau berlabel), maka masalah yang digunakan yang kompleks boleh diselesaikan, beberapa daripadanya disebut dalam perenggan akhir daripada pelajaran ini.
Masalah klasik teori graf dan penyelesaiannya
Salah satu contoh karya pertama yang diterbitkan mengenai teori graf dan aplikasi graf ialah karya mengenai "Masalah Jambatan Königsberg" (1736), yang dikarang oleh ahli matematik abad ke-18 yang terkenal Leonhard Euler. Masalahnya mengandungi sungai, pulau yang dihanyutkan oleh sungai ini, dan beberapa jambatan. Soalan masalah: adakah mungkin, selepas meninggalkan titik tertentu, untuk menyeberangi setiap jambatan hanya sekali dan kembali ke titik permulaan? (gambar di bawah)
Masalahnya boleh dimodelkan seperti berikut: satu titik dilampirkan pada setiap kawasan tanah, dan dua titik disambungkan dengan garisan jika dan hanya jika kawasan tanah yang sepadan disambungkan oleh jambatan (rajah di bawah, garis penghubung dilukis dalam garis putus-putus) . Oleh itu, graf dibina.
Jawapan Euler kepada soalan masalah adalah seperti berikut. Jika masalah ini mempunyai penyelesaian positif, maka dalam graf yang terhasil akan terdapat laluan tertutup yang melalui tepi dan mengandungi setiap tepi sekali sahaja. Jika laluan sedemikian wujud, maka setiap bucu mesti mempunyai nombor genap sahaja. Tetapi graf yang terhasil mempunyai bucu yang mempunyai bilangan tepi yang ganjil. Oleh itu, masalah itu tidak mempunyai penyelesaian yang positif.
Menurut tradisi yang telah ditetapkan, graf Eulerian ialah graf di mana ia boleh melintasi semua bucu dan pada masa yang sama melintasi satu tepi sekali sahaja. Di dalamnya, setiap bucu mesti mempunyai nombor genap sahaja. Masalah kesukaran sederhana pada graf Euler adalah dalam bahan "Jenis graf asas".
Pada tahun 1847, Kirchhoff membangunkan teori pokok untuk menyelesaikan sistem serentak persamaan algebra linear, membolehkan seseorang mencari nilai arus dalam setiap konduktor (arka) dan dalam setiap litar litar elektrik. Mengasingkan daripada litar elektrik dan litar yang mengandungi rintangan, kapasitor, induktansi, dan lain-lain, dia menganggap struktur gabungan yang sepadan yang mengandungi hanya bucu dan sambungan (tepi atau lengkok), dan untuk sambungan tidak perlu mengambil kira jenis elemen elektrik. mereka sepadan dengan . Oleh itu, Kirchhoff menggantikan setiap litar elektrik dengan graf yang sepadan dan menunjukkan bahawa untuk menyelesaikan sistem persamaan adalah tidak perlu untuk mempertimbangkan setiap kitaran graf litar elektrik secara berasingan.
Cayley pada tahun 1858, semasa mengusahakan masalah praktikal semata-mata dalam kimia organik, menemui kelas graf penting yang dipanggil pokok. Dia cuba menyenaraikan isomer hidrokarbon tepu, dengan bilangan atom karbon tertentu. Cayley mula-mula merumuskan masalah secara abstrak: cari bilangan semua pokok dengan hlm bucu, setiap satunya mempunyai bucu dengan darjah 1 dan 4. Dia tidak dapat menyelesaikan masalah ini dengan segera, dan dia mula mengubah perumusannya sedemikian rupa sehingga masalah penghitungan baharu dapat diselesaikan:
- pokok berakar (di mana salah satu bucu dipilih);
- semua pokok;
- pokok yang darjah puncaknya tidak melebihi 4;
- pokok yang darjah bucunya ialah 1 dan 4 (penyataan masalah daripada kimia).
Masalah graf untuk mengukuhkan konsep asas
Contoh 1. biarlah A- set nombor 1, 2, 3: A= (1, 2, 3) . Bina graf untuk memaparkan hubungan "
Penyelesaian. Jelas sekali, nombor 1, 2, 3 harus diwakili sebagai bucu graf. Kemudian setiap pasangan bucu mesti disambungkan dengan satu tepi. Menyelesaikan masalah ini, kami sampai kepada konsep asas teori graf seperti graf terarah dan tidak terarah. Graf tidak terarah ialah graf yang tepinya tidak mempunyai arah. Atau, seperti yang mereka katakan lebih kerap, susunan kedua-dua hujung tepi adalah tidak penting. Malah, graf yang dibina pada awal pelajaran ini dan mewakili hubungan perkenalan antara orang tidak memerlukan arah tepi, kerana boleh dikatakan bahawa "orang nombor 1" biasa dengan "orang nombor 2" pada tahap yang sama. sebagai "orang nombor 2" dengan "orang nombor 1". Dalam contoh semasa kami, satu nombor adalah kurang daripada yang lain, tetapi bukan sebaliknya. Oleh itu, pinggir graf yang sepadan mesti mempunyai arah yang menunjukkan nombor mana yang kurang daripada yang lain. Iaitu, susunan hujung tepi adalah penting. Graf sedemikian (dengan tepi mempunyai arah) dipanggil graf berarah atau digraf.
Jadi, dalam ramai kita A nombor 1 adalah kurang daripada nombor 2 dan nombor 3, dan nombor 2 adalah kurang daripada nombor 3. Kami memaparkan fakta ini dengan tepi yang mempunyai arah, yang ditunjukkan oleh anak panah. Kami mendapat graf berikut:
Contoh 2. biarlah A- set nombor 2, 4, 6, 14: A= (2, 4, 6, 14) . Cipta graf untuk memaparkan hubungan "boleh bahagi dengan" pada set ini.
Penyelesaian. Dalam contoh ini, beberapa tepi akan mempunyai arah, dan beberapa tidak, iaitu, kita sedang membina graf bercampur. Mari kita senaraikan hubungan pada set: 4 boleh dibahagi dengan 2, 6 boleh dibahagikan dengan 2, 14 boleh dibahagikan dengan 2, dan setiap nombor daripada set ini boleh dibahagi dengan sendirinya. Hubungan ini, iaitu, apabila nombor boleh dibahagi dengan sendirinya, akan dipaparkan dalam bentuk tepi yang menghubungkan bucu dengan dirinya. Tepi sedemikian dipanggil gelung. Dalam kes ini tidak perlu memberi arah kepada gelung. Jadi dalam contoh kami terdapat tiga tepi terarah biasa dan empat gelung. Kami mendapat graf berikut:
Contoh 3. Biarkan set yang diberikan A= (α, β, γ) dan B= (a, b, c) . Bina graf untuk memaparkan hubungan “Cartesian product of sets.”
Penyelesaian. Seperti yang diketahui dari definisi Hasil cartesan set, tiada set tertib elemen bagi set yang sama. Iaitu, dalam contoh kami, anda tidak boleh menggabungkan huruf Yunani dengan Yunani dan Latin dengan Latin. Fakta ini dipaparkan sebagai graf dwipartit, iaitu satu di mana bucu dibahagikan kepada dua bahagian supaya bucu kepunyaan bahagian yang sama tidak bersambung antara satu sama lain. Kami mendapat graf berikut:
Contoh 4. Agensi hartanah menggaji pengurus Igor, Sergey dan Peter. Objek O1, O2, O3, O4, O5, O6, O7, O8 diservis. Bina graf untuk memaparkan hubungan "Igor berfungsi dengan objek O4, O7", "Sergey bekerja dengan objek O1, O2, O3, O5, O6", "Peter bekerja dengan objek O8".
Penyelesaian. Graf yang memaparkan perhubungan ini juga akan menjadi dwipartit, kerana pengurus tidak berfungsi dengan pengurus dan objek tidak berfungsi dengan objek. Walau bagaimanapun, tidak seperti contoh sebelumnya, graf akan diarahkan. Malah, sebagai contoh, Igor berfungsi dengan objek O4, tetapi objek O4 tidak berfungsi dengan Igor. Selalunya, apabila sifat perhubungan sedemikian jelas, keperluan untuk memberi arahan kepada tepi mungkin kelihatan seperti "kebodohan matematik." Tetapi masih, dan ini mengikuti sifat matematik yang ketat, jika hubungan itu berat sebelah, maka perlu memberi arahan kepada tepi. Dalam aplikasi perhubungan, ketegasan ini membuahkan hasil, contohnya, dalam program yang direka bentuk untuk perancangan, di mana graf juga digunakan dan laluan di sepanjang bucu dan tepi mesti melalui dengan ketat dalam arah tertentu. Jadi, kami mendapat graf bipartit terarah berikut:
Dan sekali lagi kepada contoh dengan nombor.
Contoh 5. Biar satu set diberikan C = {2, 3, 5, 6, 15, 18} . Bina graf yang melaksanakan hubungan yang mentakrifkan semua pasangan nombor a Dan b daripada ramai C, di mana, apabila membahagikan elemen kedua dengan yang pertama, kita memperoleh hasil bagi yang merupakan integer lebih besar daripada 1.
Penyelesaian. Graf yang memaparkan perhubungan ini akan berorientasikan, kerana keadaan mengandungi sebutan unsur kedua dan pertama, iaitu, tepi akan diarahkan dari elemen pertama ke kedua. Dari sini jelaslah jelas unsur mana yang pertama dan mana yang kedua. Mari juga tambah beberapa istilah: tepi berorientasikan biasanya dipanggil arka. Akan ada 7 lengkok dalam graf kami: e1 = (3, 15) , e2 = (3, 18) , e3 = (5, 15) , e4 = (3, 6) , e5 = (2, 18) , e6 = (6, 18) , e7 = (2, 6) . Dalam contoh ini, tepi (arka) graf hanya diberi nombor, tetapi nombor siri bukanlah satu-satunya perkara yang boleh diberikan kepada arka. Arka juga boleh diberikan skala bermakna, sebagai contoh, kos penghantaran kargo dari satu titik ke tempat lain. Tetapi kita akan berkenalan dengan pemberat arka kemudian dan dengan lebih terperinci. Jadi, kami mendapat graf terarah berikut:
Seperti yang telah kita ketahui dari bahagian pengenalan teori, teori graf tidak mengambil kira sifat khusus set dan dengan bantuan graf yang sama adalah mungkin untuk menentukan hubungan pada set dengan kandungan yang sangat berbeza. Iaitu, kandungan ini boleh disarikan daripada semasa memodelkan tugasan. Mari kita beralih kepada contoh yang menggambarkan sifat luar biasa teori graf ini.
Contoh 6. Pada sekeping papan catur berukuran 3 X 3, dua kesatria putih dan dua kesatria hitam diletakkan seperti rajah di bawah.
Adakah mungkin untuk memindahkan kesatria ke negeri yang ditunjukkan dalam rajah berikut, tidak lupa bahawa dua keping tidak boleh berada pada petak yang sama?
Penyelesaian. Dalam graf yang dibina, pasangan bucu akan disambungkan oleh hubungan "gerak kesatria". Iaitu, satu puncak adalah yang dari mana ksatria itu pergi, dan satu lagi adalah yang mana ia tiba, dan sel perantaraan huruf "r" akan berada di luar hubungan ini. Kami mendapat graf berikut:
Namun reka bentuknya ternyata menyusahkan. Sel-sel papan catur kelihatan di dalamnya, dan banyak tepi graf bersilang. Adakah mungkin untuk abstrak dari rupa fizikal papan catur dan membayangkan hubungannya dengan lebih mudah? Ternyata ia mungkin. Dalam graf baharu, bucu jiran ialah bucu yang disambungkan oleh perhubungan "kesatria bergerak", dan bukannya jiran pada papan catur (rajah di bawah).
Sekarang mudah untuk melihat bahawa jawapan kepada persoalan masalah ini adalah negatif. Pada keadaan awal tidak ada ksatria hitam di antara dua ksatria putih, tetapi pada keadaan akhir pasti ada ksatria hitam ini. Tepi graf diletakkan supaya dua kesatria yang bersebelahan tidak boleh melompat antara satu sama lain.
Contoh 7. Masalah tentang serigala, kambing dan kubis. Di satu tebing sungai terdapat seorang lelaki (H), sebuah perahu, seekor serigala (V), seekor kambing (Kz) dan seekor kubis (Kp). Seseorang dan tidak lebih daripada satu objek yang diangkut boleh berada di dalam bot pada masa yang sama. Seseorang mesti mengangkut semua objek ke sisi lain, memerhatikan keadaan: serigala tidak boleh ditinggalkan tanpa pengawasan dengan kambing, atau kambing dengan kubis.
Penyelesaian. Dalam graf yang dibina, bucu adalah konfigurasi, dan tepi ialah hubungan "sambungan dengan satu perjalanan bot" antara konfigurasi. Konfigurasi merujuk kepada susunan objek pada bank asal dan pada bank bertentangan. Setiap konfigurasi dipaparkan sebagai ( A|B), Di mana A- objek yang terletak di pantai asal, dan B- objek yang terletak di tebing bertentangan. Oleh itu konfigurasi awal adalah - (PMCpKz| ) . Sebagai contoh, selepas mengangkut kambing ke seberang, konfigurasi akan menjadi (VKp|ChKz) . Konfigurasi akhir sentiasa ( |PMCpKz) . Sekarang kita boleh membina graf, sudah mengetahui maksud bucu dan tepi:
Mari letakkan bucu graf supaya tepi tidak bersilang, dan bucu jiran ialah bucu yang disambungkan oleh hubungan pada graf. Kemudian akan lebih mudah untuk melihat perhubungan (untuk membesarkan gambar, klik kiri padanya):
Seperti yang dapat kita lihat, terdapat dua laluan berterusan yang berbeza dari konfigurasi awal hingga yang terakhir. Oleh itu, masalah itu mempunyai dua penyelesaian yang berbeza (dan kedua-duanya betul).
Teori graf dan masalah gunaan moden yang paling penting
Berdasarkan teori graf, kaedah telah dibangunkan untuk menyelesaikan masalah gunaan di mana sistem yang sangat kompleks dimodelkan dalam bentuk graf. Dalam model ini, nod mengandungi komponen individu, dan tepi mewakili sambungan antara komponen. Lazimnya, graf berwajaran digunakan untuk memodelkan rangkaian pengangkutan, sistem beratur dan perancangan rangkaian. Kami telah membincangkannya; ini adalah graf di mana pemberat diberikan kepada lengkok.
Graf pokok digunakan, sebagai contoh, untuk membina pokok keputusan(berkhidmat untuk analisis risiko, analisis kemungkinan keuntungan dan kerugian di bawah keadaan ketidakpastian). Menggunakan teori graf, dibangunkan dan model matematik yang lain untuk menyelesaikan masalah dalam bidang mata pelajaran tertentu.
Graf dan masalah aliran
Perumusan masalah. Terdapat sistem paip air, diwakili oleh graf dalam rajah di bawah.
Setiap lengkok graf mewakili paip. Nombor di atas lengkok (skala) adalah kapasiti paip. Nod ialah tempat di mana paip disambungkan. Air mengalir melalui paip dalam satu arah sahaja. Simpul S- sumber air, nod T- stok. Ia diperlukan untuk memaksimumkan isipadu air yang mengalir dari sumber ke longkang.
Untuk menyelesaikan masalah aliran, anda boleh menggunakan kaedah Ford-Fulkerson. Idea kaedah: pencarian aliran maksimum dilakukan dalam langkah-langkah. Pada permulaan algoritma, aliran ditetapkan kepada sifar. Pada setiap langkah seterusnya, nilai aliran meningkat, yang mana laluan pelengkap dicari melalui mana aliran tambahan tiba. Langkah-langkah ini diulang selagi laluan tambahan wujud. Masalah ini telah berjaya digunakan dalam pelbagai sistem teragih: sistem bekalan kuasa, rangkaian komunikasi, sistem kereta api dan lain-lain.
Graf dan perancangan rangkaian
Dalam merancang masalah proses kompleks yang terdiri daripada banyak kerja, beberapa daripadanya dilakukan secara selari dan beberapa secara berurutan, graf berwajaran, dikenali sebagai rangkaian PERT, telah digunakan secara meluas.
PERT - Teknik Penilaian dan Semakan Program (Projek) - teknik untuk menilai dan menganalisis program (projek), yang digunakan dalam pengurusan projek.
Rangkaian PERT ialah graf terarah akiklik berwajaran di mana setiap lengkok mewakili kerja (tindakan, operasi), dan berat lengkok ialah masa yang diperlukan untuk menyelesaikannya.
Jika terdapat lengkok dalam rangkaian ( a, b) Dan ( b, c), maka kerja yang diwakili oleh lengkok ( a, b) mesti disiapkan sebelum kerja yang diwakili oleh arka ( b, c). Setiap bucu ( vi) mewakili titik dalam masa di mana semua kerja, ditakrifkan oleh lengkok yang berakhir pada puncak ( vi).
Dalam lajur seperti ini:
- satu puncak, yang tidak mempunyai pendahulu, menentukan masa mula kerja;
- satu puncak, yang tidak mempunyai pengikut, sepadan dengan saat dalam masa apabila set kerja selesai.
Laluan panjang maksimum antara bucu graf ini (dari awal hingga akhir proses kerja) dipanggil laluan kritikal. Untuk mengurangkan masa yang diperlukan untuk menyelesaikan keseluruhan kompleks kerja, adalah perlu untuk mencari kerja yang terletak pada laluan kritikal dan mengurangkan tempohnya dengan, sebagai contoh, menarik pemain tambahan, mekanisme dan teknologi baharu.
Keseluruhan blok "Teori Graf"
Teori graf ialah cabang matematik yang digunakan dalam sains komputer dan pengaturcaraan, ekonomi, logistik, dan kimia.
Apakah itu graf
Gambar rajah grafik sering digunakan untuk menerangkan struktur sistem. Unsur-unsur di dalamnya diwakili oleh bulatan, titik, segi empat sama, dsb., dan hubungan antara unsur-unsur diwakili oleh garis atau anak panah. Dalam kes ini, cara elemen digambarkan mahupun panjang atau bentuk garisan tidak penting - hanya elemen yang disambungkan yang penting. Jadi, graf ialah sepasang bentuk (A, M), di mana A ialah set bucu terhingga, dan M ialah set tepi - garis yang menghubungkan beberapa bucu.
Konsep asas teori graf
Graf atau digraf berorientasikan (lihat rajah di bawah) mempunyai tepi berorientasikan, dipanggil lengkok, dan digambarkan oleh anak panah. Lengkok boleh dilambangkan dengan sepasang bucu tertib yang disambungkan, permulaan dan penghujung.
Graf tidak terarah (lihat rajah di bawah) mempunyai tepi yang dilukis sebagai garis tanpa orientasi. Oleh itu, pasangan bucu yang disambungkan oleh tepi adalah tidak tertib. Kedua-dua bucu ini ialah hujung tepi.
Jika bucu a dan b ialah hujung tepi (atau permulaan dan penghujung lengkok) graf, maka bucu a dan b dikatakan bersampingan dengan tepi ini (arka), dan tepi (arka) juga kejadian ke bucu a dan b. Jika bucu a dan b ialah hujung tepi, maka ia (a dan b) dipanggil bersebelahan.
Selalunya, kami menganggap graf yang tepinya adalah daripada satu jenis - sama ada ia diarahkan atau tidak.
Jika tepi mempunyai permulaan dan akhir yang sama, maka ia dipanggil berbilang tepi, dan graf di mana ia hadir dipanggil multigraf.
Teori graf juga menggunakan konsep "gelung" - tepi yang keluar dan masuk ke bucu yang sama. Graf yang mempunyai gelung dipanggil pseudograf.
Yang paling biasa ialah graf tidak terarah, yang tidak mempunyai berbilang tepi dan tiada gelung. Graf sedemikian dipanggil biasa. Ia tidak mempunyai berbilang tepi, jadi kita boleh mengenal pasti tepi dan pasangan bucu yang sepadan.
Setiap bucu digraf dicirikan oleh:
- Separuh darjah hasil. Ini ialah bilangan lengkok yang keluar daripadanya.
- Separuh darjah pendekatan. Ini ialah bilangan lengkok yang memasuki puncak tertentu.
Jumlah separuh darjah kemasukan digraf, serta hasil tambah separuh darjah hasil, adalah sama dengan jumlah bilangan lengkok graf.
Dalam graf tidak terarah, setiap bucu dicirikan oleh darjah bucu. Ini ialah bilangan tepi yang bersampingan dengan bucu. Jumlah keseluruhan darjah bucu graf ialah bilangan tepi didarab dengan dua: setiap tepi akan menyumbang sumbangan yang sama dengan dua.
Puncak dengan darjah 0 dipanggil terpencil.
Bucu gantung ialah bucu dengan darjah 1.
Teori graf memanggil graf kosong yang tidak mempunyai tepi. Graf lengkap ialah graf biasa di mana mana-mana 2 bucu bersebelahan.
Graf berwajaran ialah graf yang bucu atau tepi (lengkok), atau kedua-dua bucu dan tepi (lengkok) sekali gus, diberikan nombor tertentu. Mereka dipanggil skala. Rajah kedua menunjukkan graf tidak terarah yang tepinya ditimbang.
Graf: isomorfisme
Konsep isomorfisme digunakan dalam matematik. Khususnya, teori graf mentakrifkannya seperti berikut: dua graf U dan V adalah isomorfik jika dalam graf ini terdapat bijection antara set bucunya: setiap 2 bucu dalam graf U disambungkan oleh tepi jika dan hanya jika dalam graf V yang sama disambungkan oleh bucu tepi (yang mungkin mempunyai nama yang berbeza). Rajah di bawah menunjukkan dua graf isomorfik di mana bijection yang diterangkan di atas wujud antara bucu yang berwarna dalam warna yang sama dalam kedua-dua graf pertama dan kedua.
Laluan dan kitaran
Laluan dalam graf tidak terarah atau terarah ialah jujukan tepi, di mana setiap satu seterusnya bermula pada puncak di mana yang sebelumnya berakhir. Laluan mudah ialah laluan di mana semua bucu, kecuali mungkin permulaan dan penghujung, dan tepinya berbeza. Kitaran dalam digraf ialah laluan yang titik permulaan dan penamatnya bertepatan dan termasuk sekurang-kurangnya satu tepi. Kitaran dalam graf tidak terarah ialah laluan yang mengandungi sekurang-kurangnya tiga tepi yang berbeza. Dalam rajah kedua, kitaran adalah, sebagai contoh, laluan (3, 1), (6, 3), (1, 6).
Teori graf dalam pengaturcaraan digunakan untuk membina gambar rajah graf algoritma.