Pada pelajaran pertama, memperkenalkan konsep grafik, kami menganggap sebagai contoh kompetisi tim olahraga. Kami. menghubungkan dua tim, katakanlah A dan C, dengan edge AC jika tim-tim ini sudah saling bermain. Namun, grafik seperti itu tidak menjawab satu pertanyaan yang sangat penting: siapa sebenarnya yang memenangkan permainan?
Kekurangan ini dapat dengan mudah dihilangkan. Jika tim A menang melawan C, kami setuju untuk memasang panah di tepi AC, diarahkan dari A ke C. Misalkan kita tahu hasil dari semua permainan yang sudah dimainkan, dan tambahkan ke grafik gbr. 1 panah yang sesuai; Biarkan hasil ini dalam grafik yang ditunjukkan pada Gambar. 58.

Gambar 58.

Grafik ini menunjukkan bahwa Tim A mengalahkan C, Tim F kalah dari A, dan Tim B memenangkan semua pertandingan melawan C, E, F, dll.

Tepian grafiknya disebut berorientasi, jika satu simpul dianggap awal tulang rusuk, Dan lainnya - akhir.
Graf yang semua sisinya berorientasi disebut orientasimenghitung.
Titik yang sama dari graf berarah dapat berfungsi sebagai awal untuk beberapa sisi dan akhir untuk yang lain. Dengan demikian, dua derajat bagian atas dibedakan: gelar keluar dan gelar masuk.
Gelar keluar simpul A dari graf berarah adalah jumlah sisi yang keluar dari A (notasi: d+(A)).
Derajat masuk simpul A dari graf berarah adalah banyaknya entri dalam TETAPI tepi (simbol: d-(A)).
Bagaimana jika sebuah pertandingan berakhir seri? Kita dapat mencerminkan hasil seri pada grafik dengan membiarkan sisi-sisi yang bersesuaian tidak berarah. Dengan melakukan itu, kita mendapatkan apa yang disebut smjumlah shanny, yang memiliki tepi berarah dan tak berarah.
Lintasan dalam graf berarah G dari A1 ke An adalah barisan sisi yang berorientasi<А1; А2>, <А2; А3>, ..., <Аn-1; Аn>, sehingga ujung setiap edge sebelumnya bertepatan dengan awal edge berikutnya dan tidak ada edge yang muncul lebih dari satu kali.

Beras. 59
Jika pada graf berarah G terdapat lintasan dari TETAPI ke B, lalu kembali dari PADA ke TETAPI mungkin tidak (Gbr. 59).
Jika ada lintasan berarah dari A ke B, maka B dikatakan mencapaiibu dari
Di kolom G pada gambar 38 B dapat dicapai
dari A, A tidak dapat dijangkau dari B.
cara yang mudah Graf berarah adalah lintasan yang tidak terdapat simpul lebih dari satu kali. jalan tertutup dalam graf berarah disebut siklus berarah.
jauh adalah jumlah tepi di jalan ini.
Jarak dari A ke B pada graf berarah adalah panjang lintasan terpendek dari A ke B. Jika tidak ada lintasan dari A ke B, maka jarak A ke B disebut tak hingga dan dinotasikan?. Jarak dari A ke B dilambangkan dengan S (AB). Untuk grafik pada Gambar 38
S (AB) \u003d 1, S (CB) - 2, S (BC) \u003d ?.
Soal 9.1.
Di kota resor tepi laut, setelah ditetapkannya lalu lintas satu arah, ternyata jumlah jalan yang dapat Anda masuki setiap persimpangan sama dengan jumlah jalan yang dapat Anda tinggalkan. Buktikan bahwa mungkin untuk mengusulkan rute patroli yang dimulai dan berakhir di tempat yang sama dan melewati setiap bagian jalan tepat satu kali.
Keputusan.
Mari kita buat digraf G yang mendefinisikan pergerakan di kota.
Digraf disebut terhubung, jika mungkin untuk berpindah dari salah satu simpulnya ke simpul lainnya di sepanjang busur tanpa memperhitungkan orientasinya. Digraf terhubung disebut Euler, jika memiliki siklus Euler.
Teorema 12. Digraf terhubung adalah Euler jika dan hanya jika untuk setiap simpulnyavpersamaand- (v) = d+ (v) .
Teorema dibuktikan dengan cara yang persis sama dengan teorema pada Soal 4.2.
Dari kondisi masalah ini, untuk simpul-simpul dari graf G yang dibangun, persamaan d-(v) = d+(v) dipenuhi. Oleh karena itu, graf Euler G, dan siklus Euler akan menentukan rute patroli yang diinginkan.
Soal 9.2.
Sejumlah titik yang terbatas ditandai pada bidang. Beberapa pasang titik adalah awal dan akhir vektor, dan jumlah vektor yang masuk ke sembarang titik sama dengan jumlah vektor yang keluar darinya. Cari jumlah vektor.
Keputusan.
Titik-titik bidang bersama-sama dengan vektor-vektor membentuk digraf G. Siklus digraf, yang semua titiknya berbeda, disebut kontur.
Teorema 13. Digraf terhubungGEuler jika dan hanya jikaGadalah penyatuan kontur yang berpasangan tidak memiliki tepi yang sama.
Bukti. Kebutuhan Misalkan G adalah digraf Euler. Pertimbangkan sembarang simpul u1. Biarkan simpul u1 sepanjang busur (u1, u2) Hal ini dapat dilakukan, karena digraf G terhubung. Karena d-(u2) = d+(u2), simpul u2 dapat dibiarkan sepanjang busur (u2, u3) . Digraf G memiliki jumlah simpul yang berhingga, jadi kita berakhir di beberapa simpul w di mana kita berada sebelumnya. Bagian dari rantai yang berawal dan berakhir di w adalah jalur C1. Hapus busur kontur C1 dari digraf G . Pada digraf G1 yang dihasilkan (mungkin terputus), derajat masuk dan keluar dari simpul-simpul milik C telah berkurang satu, derajat masuk dan keluar dari simpul-simpul yang tersisa tidak berubah. Oleh karena itu, untuk sembarang simpul v dari digraf C1, persamaan d-(v) = d+(v) akan berlaku. Oleh karena itu, dalam digraf G1, kita dapat memilih kontur C 2 dll.
Kecukupan dibuktikan dengan menggabungkan kontur ke dalam siklus Euler (lihat bukti teorema dalam masalah 4.2).
Teorema telah terbukti. Mungkin digraf G yang mendefinisikan vektor-vektor dalam masalah kita tidak terhubung. Menerapkan teorema terbukti untuk setiap bagian terhubung dari digraf, kami memperoleh partisi vektor ke dalam kontur. Jumlah vektor yang termasuk dalam satu kontur sama dengan nol. Oleh karena itu, jumlah semua vektor sama dengan nol.

Sebelum Anda mulai mempelajari algoritme secara langsung, Anda harus memiliki pengetahuan dasar tentang grafik itu sendiri, untuk memahami bagaimana grafik itu direpresentasikan di komputer. Di sini, semua aspek teori graf tidak akan dijelaskan secara rinci (ini tidak diperlukan), tetapi hanya itu, ketidaktahuan yang akan secara signifikan memperumit asimilasi bidang pemrograman ini.

Beberapa contoh akan memberikan sedikit gambaran dangkal tentang grafik. Jadi grafik tipikal adalah peta kereta bawah tanah atau rute lain. Secara khusus, seorang programmer akrab dengan jaringan komputer, yang juga merupakan grafik. Hal yang umum di sini adalah adanya titik-titik yang dihubungkan oleh garis. Jadi dalam jaringan komputer, titik adalah server yang terpisah, dan garis adalah jenis sinyal listrik yang berbeda. Di kereta bawah tanah, yang pertama adalah stasiun, yang kedua adalah terowongan yang diletakkan di antara mereka. Dalam teori graf, titik disebut puncak (simpul), dan garis Tulang iga (busur). Dengan demikian, grafik adalah kumpulan dari vertex yang dihubungkan oleh edge.

Matematika beroperasi tidak dengan isi sesuatu, tetapi dengan strukturnya, mengabstraksikannya dari segala sesuatu yang diberikan secara keseluruhan. Dengan hanya menggunakan teknik ini, kita dapat menyimpulkan tentang beberapa objek seperti tentang grafik. Dan karena teori graf adalah bagian dari matematika, maka untuk itu sama sekali tidak masalah apa, pada prinsipnya, sebuah objek; satu-satunya hal yang penting adalah apakah itu grafik, yaitu, apakah ia memiliki properti yang diperlukan untuk grafik. Oleh karena itu, sebelum memberikan contoh, kami memilih objek yang sedang dipertimbangkan hanya apa, menurut pendapat kami, akan memungkinkan kami untuk menunjukkan analogi, kami mencari kesamaan.

Mari kita kembali ke jaringan komputer. Ini memiliki topologi tertentu, dan dapat digambarkan secara kondisional sebagai sejumlah komputer dan jalur yang menghubungkannya. Gambar di bawah menunjukkan topologi meshed penuh sebagai contoh.

Ini pada dasarnya grafik. Lima komputer adalah simpul, dan koneksi (jalur pensinyalan) di antara mereka adalah tepi. Mengganti komputer dengan simpul, kami mendapatkan objek matematika - grafik yang memiliki 10 tepi dan 5 simpul. Anda dapat memberi nomor simpul secara sewenang-wenang, dan tidak harus seperti yang dilakukan pada gambar. Perlu dicatat bahwa dalam contoh ini tidak ada loop yang digunakan, yaitu tepi yang meninggalkan simpul dan segera memasukinya, tetapi loop dapat terjadi dalam masalah.

Berikut adalah beberapa notasi penting yang digunakan dalam teori graf:

• G=(V, E), di sini G adalah graf, V adalah simpulnya, dan E adalah rusuk;
• |V| – urutan (jumlah simpul);
• |E| – ukuran graf (jumlah sisi).

Dalam kasus kami (Gbr. 1) |V|=5, |E|=10;

Jika ada simpul lain yang dapat diakses dari sembarang simpul, maka graf tersebut disebut tidak berorientasi grafik terhubung (Gbr. 1). Jika graf terhubung, tetapi kondisi ini tidak terpenuhi, maka graf seperti itu disebut berorientasi atau digraf (Gbr. 2).

Graf berarah dan tidak berarah memiliki pengertian derajat suatu simpul. Derajat Verteks adalah jumlah sisi yang menghubungkannya dengan simpul lainnya. Jumlah semua derajat suatu graf sama dengan dua kali jumlah semua sisinya. Untuk Gambar 2, jumlah semua kekuatan adalah 20.

Dalam digraf, tidak seperti graf tak berarah, adalah mungkin untuk berpindah dari titik h ke titik s tanpa titik perantara, hanya ketika sebuah tepi meninggalkan h dan masuk ke s, tetapi tidak sebaliknya.

Graf berarah memiliki notasi sebagai berikut:

G=(V, A), di mana V adalah simpul, A adalah tepi berarah.

Jenis grafik ketiga - Campuran grafik (Gbr. 3). Mereka memiliki tepi terarah dan non-arah. Secara formal, grafik campuran ditulis sebagai berikut: G=(V, E, A), di mana setiap huruf dalam tanda kurung juga menunjukkan apa yang sebelumnya dikaitkan dengannya.

Pada grafik pada Gambar 3, beberapa busur berarah [(e, a), (e, c), (a, b), (c, a), (d, b)], yang lain tidak berarah [( e, d), (e, b), (d, c)…].

Dua atau lebih grafik pada pandangan pertama mungkin tampak berbeda dalam strukturnya, yang muncul karena representasi yang berbeda. Tapi tidak selalu demikian. Mari kita ambil dua grafik (Gbr. 4).

Mereka setara satu sama lain, karena tanpa mengubah struktur satu grafik, Anda dapat membangun yang lain. Grafik seperti ini disebut isomorfis, yaitu, memiliki properti bahwa setiap simpul dengan jumlah tepi tertentu dalam satu grafik memiliki simpul yang identik di yang lain. Gambar 4 menunjukkan dua grafik isomorfik.

Ketika setiap sisi dari suatu graf diberi suatu nilai, yang disebut bobot dari sisi tersebut, maka graf tersebut tergantung. Dalam tugas yang berbeda, berbagai jenis pengukuran dapat bertindak sebagai bobot, misalnya, panjang, harga rute, dll. Dalam representasi grafis dari grafik, nilai bobot biasanya ditunjukkan di sebelah tepi.

Di salah satu grafik yang telah kami pertimbangkan, dimungkinkan untuk memilih jalur dan, terlebih lagi, lebih dari satu. Jalan adalah urutan simpul, yang masing-masing terhubung ke yang berikutnya melalui tepi. Jika simpul pertama dan terakhir bertepatan, maka jalur seperti itu disebut siklus. Panjang suatu lintasan ditentukan oleh banyaknya rusuk yang menyusunnya. Misalnya, pada Gambar 4.a, lintasannya adalah barisan [(e), (a), (b), (c)]. Lintasan ini adalah subgraf, karena definisi yang terakhir berlaku untuknya, yaitu: graf G'=(V', E') adalah subgraf dari graf G=(V, E) hanya jika V' dan E' milik V, E .

Jenis graf dapat ditentukan dengan prinsip umum konstruksinya (misalnya, graf bipartit dan graf Euler), atau dapat bergantung pada sifat-sifat simpul atau sisi tertentu (misalnya, graf berarah dan tidak berarah, graf biasa ).

Graf berarah dan tidak berarah

link(urutan kedua ujung suatu graf tidak penting) disebut tidak berorientasi .

Graf yang semua sisinya busur(Orde kedua ujung suatu graf signifikan) disebut grafik berarah atau digraf .

Grafik tak berarah dapat disajikan dalam bentuk grafik terarah , jika masing-masing tautannya digantikan oleh dua busur yang berlawanan arah.

Graf berlingkar, graf campuran, graf kosong, multigraf, graf biasa, graf lengkap

Jika grafik mengandung loop, maka keadaan ini ditetapkan secara khusus dengan menambahkan kata "dengan perulangan" pada ciri utama graf, misalnya, "digraf dengan perulangan". Jika graf tidak mengandung loop, maka ditambahkan kata "tanpa loop".

Campuran disebut graf yang memiliki sisi paling sedikit dua dari tiga varietas yang disebutkan (tautan, busur, loop).

Graf yang hanya terdiri dari puncak telanjang, disebut kosong .

Multigraf disebut graf yang pasangan simpulnya dapat dihubungkan oleh lebih dari satu sisi, yaitu mengandung banyak sisi, tetapi tanpa loop.

Graf tanpa busur (yaitu, tidak berarah), tanpa loop dan banyak sisi disebut biasa . Grafik biasa ditunjukkan pada gambar di bawah ini.

Graf yang bertipe tertentu disebut menyelesaikan , jika berisi semua sisi yang mungkin untuk tipe ini (dengan himpunan simpul yang sama). Jadi, dalam graf biasa lengkap, setiap pasangan simpul yang berbeda dihubungkan oleh tepat satu tautan (gambar di bawah).

grafik bipartit

Graf tersebut disebut bipartit , jika himpunan simpulnya dapat dibagi menjadi dua himpunan bagian sehingga tidak ada sisi yang menghubungkan simpul dari himpunan bagian yang sama.

Contoh 1 Membangun penuh grafik bipartit.

Graf bipartit lengkap terdiri dari dua himpunan simpul dan semua kemungkinan link yang menghubungkan simpul satu himpunan dengan simpul himpunan lain (gambar di bawah).

grafik euler

Kami sudah menyentuh masalah tentang jembatan Königsberg. Solusi negatif Euler untuk masalah ini menghasilkan karya pertama yang diterbitkan tentang teori graf. Masalah traversal jembatan dapat digeneralisasi dan masalah teori graf berikut dapat diperoleh: apakah mungkin untuk menemukan sebuah siklus dalam graf tertentu yang berisi semua simpul dan semua tepi? Graf yang memungkinkan hal ini disebut graf Euler.

Jadi, grafik Euler disebut graf di mana dimungkinkan untuk mengitari semua simpul dan pada saat yang sama melalui satu sisi hanya sekali. Di dalamnya, setiap simpul hanya boleh memiliki jumlah rusuk yang genap.

Contoh 2 Apakah graf lengkap dengan bilangan yang sama? n tepi di mana setiap simpul adalah insiden, grafik Euler? Jelaskan jawabannya. Berikan contoh.

Menjawab. Jika sebuah n adalah bilangan ganjil, maka setiap simpulnya datang n-1 tulang rusuk. Dalam hal ini graf yang diberikan adalah graf Euler. Contoh grafik tersebut ditunjukkan di bawah ini.

Grafik reguler

grafik biasa adalah graf terhubung yang semua simpulnya berderajat sama k. Dengan demikian, gambar misalnya 2 menunjukkan contoh graf beraturan, yang disebut dengan derajat simpulnya graf beraturan 4 dan graf beraturan 2 atau graf beraturan derajat ke-4 dan ke-2.

Jumlah simpul pada graf beraturan k-gelar tidak boleh kurang k+1. Graf beraturan berderajat ganjil hanya dapat memiliki jumlah simpul genap.

Contoh 3 Buatlah graf beraturan dengan siklus terpendek yang panjangnya 4.

Keputusan. Kami berpendapat sebagai berikut: agar panjang siklus memenuhi kondisi yang diberikan, diperlukan jumlah simpul dari grafik menjadi kelipatan empat. Jika jumlah simpul adalah empat, maka akan diperoleh grafik yang ditunjukkan pada gambar di bawah ini. Beraturan, tetapi siklus terpendeknya memiliki panjang 3.

Tambah jumlah simpul menjadi delapan (bilangan berikutnya adalah kelipatan empat). Kami menghubungkan simpul dengan tepi sehingga derajat simpul sama dengan tiga. Kami mendapatkan grafik berikut yang memenuhi kondisi masalah.

grafik hamilton

Graf Hamilton disebut graf yang memuat siklus Hamilton. siklus Hamilton disebut siklus sederhana yang melalui semua simpul dari graf yang ditinjau. Jadi, secara sederhana, graf Hamilton adalah graf yang semua simpulnya dapat dilalui dan setiap simpul hanya diulang satu kali selama lintasan tersebut. Contoh graf Hamilton adalah pada gambar di bawah ini.

Contoh 4 Diberikan graf bipartit di mana n- jumlah simpul dari himpunan A, sebuah m- jumlah simpul dari himpunan B. Dalam hal manakah graf tersebut merupakan graf Euler, dan dalam hal manakah graf tersebut merupakan graf Hamilton?

Dalam bab-bab sebelumnya, kami menyajikan beberapa hasil utama dari teori graf tak berarah. Namun, grafik tidak berarah tidak cukup untuk menggambarkan beberapa situasi. Misalnya, saat mewakili peta lalu lintas dengan grafik yang tepinya sesuai dengan jalan, orientasi harus ditetapkan ke tepi untuk menunjukkan arah pergerakan yang diizinkan. Contoh lain adalah program komputer yang dimodelkan oleh grafik yang ujung-ujungnya mewakili aliran kontrol dari satu set instruksi ke yang lain. Dalam representasi program ini, tepi juga harus diberi orientasi untuk menunjukkan arah aliran kontrol. Contoh lain dari sistem fisik yang membutuhkan grafik berarah untuk mewakili adalah sirkuit listrik. Aplikasi graf berarah dan algoritme terkait dibahas dalam Bab. 11-15.

Bab ini menyajikan hasil utama dari teori graf berarah. Pertanyaan terkait keberadaan rantai Euler berorientasi dan siklus Hamilton dibahas. Pohon berorientasi dan hubungannya dengan rantai Euler berorientasi juga dipertimbangkan.

5.1. Definisi dan konsep dasar

Mari kita mulai dengan memperkenalkan beberapa definisi dan konsep dasar yang terkait dengan graf berarah.

Graf berarah terdiri dari dua himpunan: himpunan berhingga V, yang elemen-elemennya disebut simpul, dan himpunan berhingga E, yang elemen-elemennya disebut tepi atau busur. Setiap busur diasosiasikan dengan sepasang simpul terurut.

Simbol digunakan untuk menunjuk simpul, dan simbol digunakan untuk menunjuk busur. Jika , maka disebut simpul akhir, di mana - simpul awal, - simpul akhir . Semua busur yang memiliki pasangan simpul awal dan simpul akhir yang sama disebut paralel. Suatu busur disebut loop jika simpul datangnya adalah simpul awal dan simpul akhirnya.

Dalam representasi grafis dari graf berarah, simpul diwakili oleh titik atau lingkaran, dan tepi (busur) diwakili oleh segmen.

garis yang menghubungkan titik atau lingkaran yang mewakili titik akhirnya. Selain itu, busur diberi orientasi, ditunjukkan oleh panah yang menunjuk dari titik awal ke titik akhir.

Misalnya, jika sedemikian rupa sehingga graf berarah dapat direpresentasikan oleh gbr. 5.1. Dalam grafik ini - busur paralel, dan - loop.

Beras. 5.1. Grafik Berorientasi.

Busur dikatakan bersinggungan dengan simpul ujungnya. Simpul disebut bertetangga jika simpul tersebut terminal untuk satu busur. Jika busur memiliki simpul terminal yang sama, maka mereka disebut berdekatan.

Sebuah busur disebut keluar dari titik awal dan memasuki titik akhir. Sebuah simpul dikatakan terisolasi jika tidak memiliki busur insiden.

Derajat suatu simpul adalah jumlah busur yang datang padanya. Derajat masuk suatu simpul adalah banyaknya busur yang masuk ke V] dan derajat keluar adalah banyaknya busur yang keluar. Simbol dan b" menunjukkan derajat keluar dan derajat masuk minimum dari graf berarah. Demikian pula, simbol masing-masing menunjukkan derajat keluar dan derajat masuk maksimum.

Himpunan setiap simpul didefinisikan sebagai berikut: . Misalnya, dalam grafik pada Gambar. 5.1.

Perhatikan bahwa loop meningkatkan setengah derajat dari masuk dan keluar dari simpul ini. Pernyataan berikut adalah konsekuensi dari fakta bahwa setiap busur bertambah 1 jumlah setengah derajat dari input dan output dari grafik berarah.

Teorema 5.1. Dalam graf berarah dengan busur

Jumlah derajat masuk = Jumlah derajat keluar = m.

Subgraf dan subgraf yang dihasilkan dari graf berarah didefinisikan dengan cara yang sama seperti dalam kasus graf tak berarah (Bag. 1.2).

Graf tak-berarah yang dihasilkan dari penghilangan orientasi dari busur-busur dari graf berarah G disebut graf tak-berarah pokok G dan dilambangkan dengan .

Lintasan berarah dari graf berarah adalah barisan berhingga dari simpul-simpulnya

Apa yang dimaksud dengan busur dari graf G. Rute seperti itu biasanya disebut rute berarah, dan titik awal adalah titik akhir dari rute, dan semua titik lainnya adalah internal. Titik awal dan akhir dari jalur berarah disebut titik akhir. Perhatikan bahwa busur, dan karenanya simpul, dapat muncul lebih dari sekali dalam jalur berarah.

Suatu rute yang berorientasi dikatakan terbuka jika simpul-simpul ujungnya berbeda, jika tidak maka disebut tertutup.

Lintasan berorientasi disebut lintasan berorientasi jika semua busurnya berbeda. Jalur berorientasi terbuka jika titik akhirnya berbeda, jika tidak maka akan tertutup.

Lintasan berorientasi terbuka disebut lintasan berorientasi jika semua simpulnya berbeda.

Rantai berorientasi tertutup disebut siklus atau kontur berorientasi jika simpulnya, kecuali simpul terminal, berbeda.

Graf berarah dikatakan asiklik atau tak berkontur jika tidak memiliki kontur. Sebagai contoh, graf berarah pada Gambar 1 adalah asiklik. 5.2.

Beras. 5.2. Graf berarah asiklik.

Beras. 5.3. Graf berarah terhubung kuat.

Barisan simpul-simpul pada graf berarah G disebut lintasan di G jika merupakan lintasan pada graf tak-berarah di bawahnya.Misalnya barisan pada graf pada Gambar. 5.2 adalah rute, tetapi tidak berorientasi.

Rantai, jalur, dan siklus dari graf berarah didefinisikan dengan cara yang sama.

Graf berarah dikatakan terhubung jika graf tak berarah di bawahnya terhubung.

Subgraf dari graf berarah G disebut komponen dari graf G jika merupakan komponen dari graf tersebut

Titik-titik dari graf berarah G dikatakan terhubung kuat jika ada jalur berarah dari dan kembali ke G. Jika terhubung kuat dengan maka, jelas terhubung kuat dengan . Setiap simpul terhubung kuat dengan dirinya sendiri.

Jika sebuah simpul terhubung kuat dengan sebuah simpul, maka, seperti yang mudah dilihat, simpul tersebut terhubung kuat dengan simpul tersebut.Oleh karena itu, dalam hal ini, cukup dikatakan bahwa simpul terhubung kuat.

Graf berarah dikatakan terhubung kuat jika semua simpulnya terhubung kuat. Misalnya, grafik pada Gambar. 5.3.

Subgraf terhubung kuat maksimal dari graf berarah G disebut komponen terhubung kuat dari G. Jika graf berarah terhubung kuat, maka ia memiliki satu komponen terhubung kuat, yaitu dirinya sendiri.

Pertimbangkan grafik berarah. Sangat mudah untuk melihat bahwa setiap simpulnya memiliki tepat satu komponen terhubung kuat dari graf G. Oleh karena itu, himpunan titik dari komponen yang terhubung kuat membentuk partisi dari himpunan titik Y dari graf

Beras. 5.4. Grafik dan kondensasinya.

Misalnya, grafik berarah pada Gambar. 5.4, ​​a memiliki tiga komponen yang terhubung kuat dengan himpunan titik dan membentuk partisi dari himpunan titik dari graf berarah.

Menariknya, graf berarah mungkin berisi busur yang tidak termasuk dalam komponen graf yang terhubung kuat. Misalnya, tidak ada komponen yang terhubung kuat termasuk busur dalam grafik pada Gambar. 5.4, ​​sebuah.

Jadi, meskipun properti "terhubung kuat" memerlukan pemisahan himpunan simpul dari graf, itu mungkin tidak menghasilkan pemisahan himpunan busur.

Persatuan, perpotongan, penjumlahan mod 2, dan operasi lain pada graf berarah didefinisikan dengan cara yang persis sama seperti pada kasus graf tak berarah (Bag. 1.5).

Grafik yang dihasilkan dari kontraksi semua busur komponen terhubung kuat dari grafik berarah G disebut grafik ringkas dari grafik G. Kondensasi grafik yang ditunjukkan pada gambar. 5.4, ​​a, ditunjukkan pada gambar. 5.4b.

Titik-titik dari graf bersesuaian dengan komponen-komponen yang terhubung kuat dari graf G dan disebut citra komponen yang diringkas.

Rangking dan bilangan siklomatik dari graf berarah sama dengan graf tak berarah yang bersesuaian. Artinya, jika suatu graf berarah G memiliki busur, simpul, dan komponen, maka rank dan bilangan siklomatik dari graf G diberikan oleh

Kami sekarang mendefinisikan graf berarah minimal terhubung dan mempelajari beberapa propertinya.

Graf berarah G dikatakan terhubung minimal jika terhubung kuat, dan menghilangkan busur apa pun menghilangkan sifat terhubung kuatnya.

Beras. 5.5. Grafik berarah minimal terhubung.

Terhubung minimal adalah, misalnya, grafik yang ditunjukkan pada Gambar. 5.5.

Jelas, grafik terhubung minimal tidak dapat memiliki busur dan loop paralel.

Kita tahu bahwa graf tak berarah terhubung minimal jika dan hanya jika graf tersebut adalah pohon (Keluaran 2.13). Berdasarkan Teorema 2.5, sebuah pohon memiliki setidaknya dua simpul berderajat 1. Oleh karena itu, graf tak berarah terhubung minimal memiliki setidaknya dua simpul berderajat 1.

Mari kita buat hasil yang serupa untuk grafik berarah. Derajat setiap simpul dari graf berarah terhubung kuat harus minimal 2, karena setiap simpul harus memiliki busur keluar dan masuk. Dalam teorema berikut, kami membuktikan bahwa graf berarah terhubung minimal memiliki setidaknya dua simpul berderajat 2.

Sisi adalah pasangan terurut dari simpul. Graf yang menunjukkan arah setiap sisinya disebut berorientasi.

Jelas aplikasi untuk turnamen. Misalnya, panah bergerak dari tim yang kalah ke tim yang menang, sehingga grafik yang diarahkan tidak hanya menunjukkan siapa yang bermain dengan siapa, tetapi siapa yang menang.

Dimungkinkan juga untuk mendefinisikan urutan atau hubungan preferensi dengan grafik berarah.

Sebagai contoh, dalam grafik algoritma simpul dari grafik sesuai operasi yang dilakukan, dan busur (tepi berorientasi) sesuai dengan ketergantungan data(yaitu input apa yang diperlukan untuk melakukan operasi).

Misalnya, dalam evaluasi sampel yang kompleks (dalam geologi, misalnya), arah tepi menunjukkan preferensi. Sistem preferensi normal seharusnya tidak memiliki siklus.

Tanya Natasha

sehingga Anda selalu dapat membuat pilihan, jika tidak, Anda perlu mempertimbangkan kembali sistem preferensi.

SATU ARAH.

Peta jalan dengan arah perjalanan memberikan contoh khusus grafik berarah. Untuk menangani jalan dua arah, alih-alih satu jalan (atau alih-alih satu tepi tidak berarah), kami memperkenalkan dua tepi berarah yang menghubungkan simpul yang sama dan memiliki arah yang berlawanan.

Pertanyaannya adalah, dalam kondisi apa jalan-jalan kota dapat diorientasikan sedemikian rupa sehingga seseorang dapat berkendara dari titik mana pun ke titik lain tanpa melanggar aturan lalu lintas di sepanjang jalan tersebut.

Dalam bahasa teori graf, dirumuskan sebagai berikut: dalam kondisi apa sisi-sisi graf G dapat diorientasikan sehingga untuk setiap pasangan simpulnya ada jalur berorientasi yang menghubungkannya?

Jelas bahwa setiap grafik seperti itu harus terhubung, tetapi ini tidak cukup.

Tepi E = (A, B) akan disebut tepi penghubung, atau genting tanah jika itu adalah satu-satunya jalan dari A ke B (atau sebaliknya).

Tepi penghubung membagi semua simpul graf menjadi dua himpunan: simpul yang dapat dicapai dari A tanpa melewati tepi E, dan simpul yang dapat dicapai dari B tanpa melewati E. Graf dalam hal ini terdiri dari dua bagian G 1 dan G 2 dihubungkan hanya oleh tepi E (Gbr. a dan a+1).

Di peta kota, tulang rusuk penghubung adalah satu-satunya jalan raya yang menghubungkan bagian kota yang terpisah. Jelas bahwa jika lalu lintas satu arah dibuat di jalan raya seperti itu, maka tidak akan ada jalan dari satu bagian kota ke bagian kota lainnya.

Jika sisi E i = (A i , B i) tidak menghubungkan, maka ada jalur lain yang menghubungkan A i dan B i dan tidak melalui E i . Oleh karena itu, tepi seperti itu akan disebut tepi siklik.

gbr.2 Menghubungkan gbr. 2+1 Final (menghubungkan) Gambar 2+2 Siklus

tulang rusuk

Teorema 1 Jika sebuah G- graf terhubung, maka selalu mungkin untuk mengorientasikan sisi siklik dari G , membiarkan tepi penghubung tidak berarah sehingga setiap pasangan simpul dalam graf ini dapat dihubungkan dengan jalur berarah.

Untuk rencana kota, pernyataan ini dapat dirumuskan sebagai berikut: jika lalu lintas dua arah hanya tersisa di jembatan (asalkan jembatan ini adalah satu-satunya jembatan yang melintasi sungai) dan di jalan buntu, maka di semua jalan lainnya lalu lintas satu arah dapat dibangun sedemikian rupa sehingga transportasi menyediakan komunikasi ke seluruh bagian kota.

Kita dapat membuktikan teorema ini dengan menunjukkan cara untuk mengarahkan grafik dengan benar. Ayo pilih di G tepi sewenang-wenang E \u003d (A, B) . Jika sebuah E - tepi penghubung, itu akan tetap dua sisi, dan kemudian dimungkinkan untuk pergi dari TETAPI ke PADA dan kembali (Gbr. 2+3).

gbr.2+3 gbr. 2+4

Jika sebuah E adalah tepi siklik, maka itu termasuk dalam beberapa siklus DENGAN, di mana Anda dapat mengatur orientasi siklik (gbr.2+4).

Misalkan kita telah mengorientasikan beberapa bagian H menghitung G, sehingga dari sembarang titik pada graf H Anda dapat pergi ke simpul lainnya sesuai dengan aturan lalu lintas satu arah. Sejak grafik G terhubung, maka H cocok dengan seluruh grafik g, atau ada tepi E \u003d (A, B), yang bukan milik H , tetapi salah satu simpulnya, katakan TETAPI , milik H .

Jika sebuah E - tulang rusuk penghubung AB , maka akan tetap dua sisi. Kemudian untuk sembarang simpul X menghitung H seseorang dapat menemukan rantai yang berorientasi R menghubungkan X dengan A , yang berarti (melalui tepi E ) , dan dengan PADA . Kembali dari atas PADA di tepi E kamu bisa pergi ke TETAPI , dan kemudian - sepanjang rantai orientasi Z - dari TETAPI ke X (Gambar a+5). Melampirkan E ke H , kita akan mendapatkan sebagian besar grafik G dengan sifat-sifat yang dibutuhkan. Jika tepi E \u003d (A, B) adalah siklik, itu milik beberapa siklus Dengan . Kami mengatur arah untuk Dengan dari TETAPI sebelum PADA dan selanjutnya Dengan ke puncak pertama D dari Dengan dimiliki oleh H (Gbr. a+6).

Nasi. a+5 gambar. a+6

Mari tambahkan semua tepi ini ke H . Biarlah X - simpul sewenang-wenang dari H , sebuah Pada - simpul apa saja Dengan ; seseorang dapat menemukan rantai yang berorientasi R , dimiliki H dan menghubungkan X dengan TETAPI dan kemudian bersama Dengan pergi ke atas Pada dari Dengan . Kembali dari Pada kamu bisa jalan-jalan Dengan ke atas D , dan darinya - milik H rantai berorientasi Z - dari D ke X . Oleh karena itu, grafik berarah diperoleh dengan menambahkan H tepi siklus yang ditentukan Dengan , juga memenuhi kondisi yang diperlukan. Melanjutkan proses ini, kami akhirnya mengarahkan grafik asli dengan cara yang diperlukan G .

Derajat verteks.

Untuk graf berarah, pada setiap simpul terdapat bilangan p(A) dari sisi keluar dan bilangan p*(A) dari sisi masuk. Jumlah seluruh rusuknya adalah:

N \u003d p (A 1) + p (A 2) + ... + p (A n) \u003d p * (A 1) + p * (A 2) + ... + p * (A n)

Ada berbagai jenis graf yang derajat simpulnya memiliki beberapa sifat khusus. Hitungannya disebut homogen, jika derajat semua simpulnya sama dengan bilangan yang sama r: untuk setiap simpul A:

p(A) = p * (A) = r

Sebuah latihan

Buatlah graf berarah homogen dengan derajat r = 2 dengan n = 2,6,7,8 simpul.

HUBUNGAN.

Hubungan dan Grafik.

Setiap sistem matematika berhubungan dengan sekumpulan objek atau elemen. (Tanda: aljabar, geometri)

Untuk membangun teori matematika, kita tidak hanya membutuhkan elemen-elemen ini sendiri, tetapi juga hubungan diantara mereka. (Contoh: untuk bilangan a > b; dalam geometri - persamaan segitiga, // garis; dalam teori himpunan - persamaan dan penyertaan himpunan.)

Semua hubungan ini menyangkut dua objek, sehingga mereka disebut hubungan biner, atau sederhananya hubungan, ada jenis hubungan lain, misalnya hubungan ternary berkaitan dengan tiga objek. (Misalnya, titik A terletak di antara titik B dan C).

Mari kita perkenalkan definisi umum dari relasi biner R: аR - berhubungan dengan R ke a.

Misalnya, relasi a > b berarti b termasuk dalam himpunan semua bilangan yang kurang dari a

Faktanya, setiap graf berarah G mendefinisikan beberapa relasi dalam himpunan simpulnya. Rasio ini dapat ditulis sebagai: аGв. Artinya graf tersebut memiliki sisi berarah dari a ke b.

Kondisi khusus.

Misalkan suatu relasi R diberikan. Jika suatu elemen a berada dalam relasi R dengan dirinya sendiri, maka elemen tersebut berkorespondensi dengan loop pada graf

Relasi R yang memenuhi syarat R untuk setiap, disebut reflektif.

Jika kondisi aRv tidak terpenuhi untuk setiap elemen, maka R disebut sikap anti refleksif.Dalam hal ini, tidak ada simpul dari grafik yang memiliki loop.

Untuk setiap relasi R, dapat didefinisikan rasio terbalik R*, dengan asumsi bahwa аR * jika dan hanya jika аR.

Dari definisi relasi invers tersebut dapat diketahui bahwa jika graf G yang bersesuaian dengan R memiliki rusuk (a, b), maka graf G* yang bersesuaian dengan R* harus memiliki rusuk (c, a). Dengan kata lain, graf G* invers terhadap G, yaitu. graf dengan sisi yang sama dengan G, tetapi berorientasi berlawanan.

Hubungan tersebut disebut simetris, jika dari аR mengikuti а.

Sebuah hubungan simetris sesuai dengan grafik dengan tepi tak berarah; sebaliknya, graf dengan sisi tak berarah mendefinisikan beberapa relasi simetris.

Hubungan tersebut disebut antisimetris, jika mengikuti dari аR itu pasti tidak berlaku di Rа. Graf relasi antisimetri tidak memiliki sisi yang tidak berarah atau berorientasi berlawanan yang menghubungkan pasangan simpul yang sama; selain itu, tidak ada loop pada mereka, mis. hubungan ini anti-reflektif.

Perbandingan secara transitif, jika mengikuti dari dua kondisi aRb dan bRc bahwa aRc.

Grafik relasi transitif memiliki sifat karakteristik sebagai berikut: untuk setiap pasangan sisi (a, b), (b, c) ada penutupan tepian. Dengan menerapkan sifat ini secara berulang, kita simpulkan bahwa jika graf ini memiliki lintasan berarah dari titik X ke titik Y, maka terdapat pula sisi berarah (x, y).

Asumsikan terdapat graf G dengan sisi berarah yang tidak transitif. Dalam semua kasus, graf berarah G dapat dibuat transitif dengan menambahkan sisi-sisi berarah ke graf tersebut hingga suatu penutupan dipasang untuk setiap pasangan sisi-sisi berurutannya. Grafik baru G m yang diperoleh disebut penutupan transitif Hitung G

Hubungan kesetaraan.

Relasi ekivalensi, biasanya dilambangkan dengan ~ , memiliki tiga sifat berikut:

satu). Refleksivitas: a ~ a;

2). Simetri: dari a ~ ke z ke ~ a;

3). Transitivitas: dari a ~ ke dan ke ~ c a ~ c.

Faktanya, relasi ekivalensi adalah generalisasi dari properti kesetaraan.

Relasi ekivalensi memperkenalkan partisi ke dalam himpunan simpul kelas ekuivalensi terputus-putus.

Misalkan B i adalah himpunan simpul dari graf ekivalensi G yang ekuivalen dengan simpul i. Kemudian semua simpul milik B i dihubungkan oleh tepi, yaitu. Dalam i - graf lengkap G i . Pada setiap simpul dari graf seperti itu terdapat sebuah loop Graf G terbagi menjadi himpunan komponen terhubung G i .

Urutan sebagian.

Sikap pesanan sebagian adalah (pada contoh himpunan):

satu). Refleksivitas: A A

2). Transitivitas: jika A B dan B C A C

3). Identitas: jika A B dan B Az A = B

Hubungan Inklusi Ketat -

satu). Anti-refleksivitas: A A tidak pernah terjadi;

2). Transitivitas: jika A B dan B C, maka A C

Hubungan pemesanan(dalam arti sempit) disebut pengaturan ketat, a > b, yang selain kondisi sebelumnya, juga berlaku:

kondisi kelengkapan. Untuk setiap dua elemen yang tidak bertepatan di dan a, salah satu dari dua relasi a>b atau b>a selalu terpenuhi.

Biasanya, graf terurut sebagian digambarkan dalam bentuk terurut. Karena untuk sembarang tepi (a, b) dan (b, c) ada tepi penutup (a, c), itu dapat dihilangkan.

GRAFIK DATAR.

Syarat graf planar.

Hitung Kuratovsky K 3.3

Grafik masalah tentang tiga rumah dan tiga sumur

Hitung Kuratovsky K 5

Kedua grafik ini TIDAK FLAT!

Ekstensi grafik- simpul baru ditempatkan di beberapa tepi, jadi tepi ini

menjadi rantai dasar yang terdiri dari beberapa tepi.

Operasi terbalik, di mana simpul yang memisahkan dihapus dari rantai dasar, disebut kompresi grafik.

Teorema Kuratovsky

Agar suatu graf menjadi datar, perlu dan cukup bahwa graf tersebut tidak mengandung graf dalam dirinya sendiri yang dapat dikompresi menjadi graf K 3.3 atau graf K 5.

rumus Euler

Kami akan mempertimbangkan grafik planar yang terbentuk di pesawat jaringan poligonal. ini berarti bahwa tepi-tepi dari graf bidang G membentuk suatu himpunan poligon yang saling berdekatan, membagi bidang tersebut menjadi daerah-daerah poligonal.

Ini mengikuti dari definisi graf poligonal bahwa mereka terhubung. Kami juga mensyaratkan bahwa tidak ada poligon yang terletak di dalam poligon lain. Tepi batas masing-masing poligon tersebut membentuk siklus, kadang-kadang disebut siklus minimum. Bagian bidang yang dilingkupi poligon disebut wajah grafik. Grafik juga memiliki siklus maksimum C 1, mengelilingi seluruh grafik dengan semua wajahnya. Kami akan mempertimbangkan bagian dari pesawat yang terletak di luar C 1, juga sebagai wajah grafik dengan batas C 1 - tak berujung wajah F .

Dilambangkan dengan

jumlah vertex, edge dan face poligon ruang..

teorema Euler

c - p + r = 2

Bukti: Rumusnya jelas untuk poligon dengan n sisi. Memang, n simpul dan n tepi, serta dua wajah F 1 F

Kami menambahkan wajah baru ke graf dengan r wajah dengan menggambar sepanjang wajah F beberapa rantai elementer yang menghubungkan dua simpul dari graf maksimal G. Jika busur ini memiliki r sisi, maka kita harus menambahkan r - 1 simpul baru dan satu simpul baru wajah. Tapi kemudian

c' - p' + r' = (c + r - 1) - (p + r) + (r + 1) = c - p + r (= 2!)

dengan hipotesis induksi.

Representasi matriks.

1. Matriks insiden A.

sebuah). Untuk graf tak berarah matriks insiden adalah matriks yang baris-barisnya bersesuaian dengan titik-titik dan kolom-kolomnya bersesuaian dengan sisi-sisi. Elemen matriks sama dengan 1 jika simpulnya bersinggungan dengan rusuk. Jika tidak, elemen matriks mengambil nilai 0.

b). Untuk graf berarah, elemen dari matriks kejadian adalah +1 ketika titik yang datang ke busur adalah titik awal dari busur (yaitu, busur berasal dari titik ini). Elemennya adalah -1 ketika busur memasuki sebuah titik. Jika titik tersebut tidak bersinggungan dengan busur, maka elemen matriksnya adalah 0.

2. Matriks siklus C.

sebuah). Untuk graf tak berarah, baris-baris matriks siklus bersesuaian dengan siklus-siklus sederhana dari graf tersebut, dan kolom-kolom bersesuaian dengan sisi-sisinya. Elemen matriks a ij =1 jika siklus i mengandung sisi e j . Jika tidak, a ij = 0.

b). Untuk graf berarah a ij =1, -1 atau 0, tergantung apakah orientasi siklus C i dan busur e j sama atau berlawanan, atau siklus ini tidak memuat busur e j sama sekali.

3. Matriks ketetanggaan simpul (atau hanya matriks ketetanggaan) V adalah matriks yang baris dan kolomnya bersesuaian dengan simpul, dan elemen matriks a ij dalam kasus graf tak berarah sama dengan jumlah rusuk yang menghubungkan simpul i dan j . Untuk graf berarah, elemen a ij sama dengan jumlah rusuk yang berarah dari titik i ke titik j.

Teorema Onovye terkait dengan representasi matriks grafik.

1) Rank (jumlah maksimum kolom bebas linier) dari matriks kejadian A dari graf terhubung (berarah dan tidak berarah) dengan n simpul sama dengan (n-1).

2). Rank dari matriks siklus C dari graf terhubung dengan m sisi dan n titik adalah (m-n+1).

Contoh penggunaan matriks ketetanggaan.

Pemetaan berikut menunjukkan bahwa graf G 1 dan G 2 isomorfik

Dalam matriks ketetanggaan, baris dan kolom dipermutasi secara bersamaan, yang dapat dilakukan dengan menggunakan transformasi kesamaan dan matriks permutasi.

A 2 \u003d PA 1 P", di mana

P = , atau p ij =d p(i),j (simbol Krocker)

dan P" adalah matriks yang ditransposisikan.

Menemukan matriks P bisa jadi rumit.

Isomorfisme G 1 dan G 2 berarti A 1 dan A 2 memiliki nilai eigen yang sama. Namun, kondisi ini tidak cukup (contoh di bawah).