Bagian 2 Bagian 3 Bagian 4 Saya diminta untuk menulis artikel ini oleh tugas berbahaya dari pencarian Java Multithreading, yang, bukannya tanpa godaan dari para pengembang, disebut oleh mereka sebagai "tugas StringBuilder." Inti dari syaratnya adalah kumpulan kata (dalam syarat diberikan nama kota yang mengingatkan pada permainan kata anak-anak) harus disusun menurut prinsip domino, huruf terakhir dari kata n' harus sama dengan huruf pertama dari kata (n+1) go, dan diketahui bahwa semua kata (satu per satu) yang diberikan dijumlahkan dalam rantai seperti itu. Jika memungkinkan untuk menyusun beberapa varian rangkaian kata yang diinginkan, salah satu dapat diterima sebagai solusi. Terlepas dari kesederhanaan dan kejelasan kondisinya, pemecahan masalah tidaklah mudah, dan penggunaan StringBuilder yang ahli tidak menyelamatkan situasi. Pengembang masalah tersebut ternyata memesan isomorf dari planet Linear Chaos, yang lebih dari sekali membuat takut taruna JavaRush. Seperti yang diharapkan, solusi dangkal tidak sesuai dengan validator, karena selalu ada rantai yang memaksa algoritma naif untuk melewatkan kata-kata. Perlu dilakukan penumpukan “kruk” tambahan yang, meskipun memperumit masalah, tidak mendekatkan solusi pada kasus umum dan semakin memperkuat perasaan bahwa kondisi sederhana seharusnya memiliki solusi yang sama sederhananya. Saya harus mengubah taktik dan menyelami bidang yang lebih mendasar. Izinkan saya segera membuat reservasi bahwa saya tidak menganggap diri saya ahli dalam teori grafik; topik yang akan saya bahas hampir tidak melampaui cakupan pemecahan masalah kata domino, dengan pengecualian, mungkin, hanya beberapa penyimpangan yang bersifat teoritis. Jadi, grafik. Apa itu graf: merupakan kumpulan (himpunan, himpunan, daftar - apa pun) dari simpul-simpul yang terhubung satu sama lain . Koneksi biasanya disebut edge , simpul juga disebut node atau node. Ini adalah graf: Ini juga merupakan graf: Jika suatu sisi dapat dikatakan mempunyai arah, maka graf tersebut disebut berorientasi : Grafik pada dua gambar pertama tidak berarah. Kita dapat mengatakan bahwa sisi (u, v) identik dengan sisi (v, u), yaitu, misalnya sisi (0, 4) dan (4, 0) adalah sisi yang sama. Tanda panah pada sisi-sisi suatu graf berarah berarti sisi (u, v) merupakan lintasan dari titik u ke titik v dan sisi (v, u) tidak ada. Pada gambar ketiga terdapat tepi (E,A). Tidak ada tepi (A, E). Mari kita lihat lebih dekat gambar terakhir. Anda dapat melihat bahwa simpul F tidak memiliki tepi sama sekali, hal ini sangat mungkin terjadi. Kami juga mencatat bahwa sebuah tepi telah muncul di dekat simpul A - sebuah lingkaran, dan antara simpul B dan D ada dua sisi yang arahnya berbeda. Grafik terarah memungkinkan artefak semacam itu. Katakanlah grafik tersebut menggambarkan sekelompok kenalan yang saling memberi hadiah. Kita melihat bahwa F yang rakus tidak memberikan apa pun kepada siapa pun, B dan D bertukar hadiah (kecuali masing-masing dari mereka memberikan hadiah kepada orang lain), dan A memberikan hadiah untuk dirinya sendiri, mungkin pada saat berhasil menyelesaikan a. masalah dari planet Linear Chaos. Perlu diketahui bahwa simpul pada graf tidak harus berupa angka atau berisi angka; melainkan merupakan wadah, yaitu mereka dapat menyimpan objek apa pun. Grafik adalah deskripsi koneksi. Istilah penting yang akan berguna bagi kita nanti - jumlah sisi yang menempel pada suatu titik (atau, seperti yang juga dikatakan, bersisian dengannya) disebut derajat dari suatu titik tertentu. Misalnya pada gambar pertama, simpul 0 berderajat 2, 1 berderajat 4, 3 berderajat 3, simpul 0 pada gambar kedua berderajat 1. Pada artikel kali ini kita tidak akan mendalami macam-macam jenis graf, kami hanya akan menyebutkan bahwa ada juga grafik berbobot, yaitu. yang di mana nomor tertentu melekat pada setiap sisinya, yang menunjukkan “harga” perjalanannya. Graf terhubung mempunyai beberapa subtipe yang dibedakan berdasarkan sifat-sifatnya. Misalnya, grafik yang ujung-ujungnya tidak membentuk siklus di mana pun disebut pohon (grafik tersebut memiliki keluarga menarik dengan nama mengagumkan seperti “pohon merah-hitam”, misalnya) dan banyak digunakan dalam berbagai algoritma dan struktur data penting. Menggunakan grafik untuk menyelesaikan suatu masalah Semua ini sangat menarik, kata Anda, tetapi apa hubungannya semua ini dengan menyusun rangkaian kata? Ternyata yang paling langsung adalah. Mari kita lihat contoh pengujian kita dari kondisi: { Amsterdam Melbourne New York Kyiv Vienna }. Mari kita tuliskan dalam urutan apa pun huruf-huruf "nodal" yang melekat pada kata-kata tersebut: {A, M, N, K, B} dan menghubungkannya dengan kata-kata. Seperti yang dapat kita lihat, kita memiliki grafik berarah yang simpul-simpulnya adalah huruf dan ujung-ujungnya adalah kata-kata, yang menghubungkannya. Jika kita menemukan cara untuk melintasi semua sisi dari titik ke titik sehingga kita mengunjungi setiap sisi hanya satu kali, masalah kita akan terpecahkan. Mari kita coba mendistribusikan node pada diagram sedikit berbeda: Sekarang kita dapat melihat dengan lebih baik bahwa grafik kita adalah loop tertutup. Kita bisa memulai urutannya dengan kata apa saja, dan itu akan menjadi keputusan yang tepat. Namun, kondisi masalahnya memberi tahu kita bahwa satu solusi saja sudah cukup. Mari kita ganti Vena dengan Vladimir: Kita melihat dua konsekuensi: pertama, kita harus menambahkan simpul baru, huruf P, dan kedua, kita melihat bahwa grafik kita tidak dapat lagi dilingkarkan. Mari kita rangkum semua hal di atas dan perkenalkan dua istilah baru: 1. Graf terhubung yang sisi-sisinya dapat dilintasi hanya dengan mengunjungi masing-masing graf satu kali saja disebut graf yang memuat “jalur Euler ” . Ciri graf seperti itu (kecuali tidak adanya simpul tanpa tepi) adalah derajat genap semua simpul kecuali dua (dan hanya dua). 2. Jika ternyata dapat kembali ke simpul semula, kita katakan bahwa terdapat “siklus Euler” pada grafik tersebut . Ciri graf seperti itu (kecuali tidak adanya simpul tanpa tepi) adalah derajat genap semua simpul. Bayangkan daftar kota kita seperti ini: {Moscow Anapa Adler Rostov-on-Don Wuhan}. Mari kita membuat grafik: Pada diagram Anda dapat melihat bahwa grafik ini memiliki jalur Euler. Hanya ada dua simpul yang berderajat ganjil yaitu M dan L, selebihnya genap: A berderajat 4, karena loop dihitung dua kali, dan P dan Y memiliki derajat 2. Jika kita menemukan algoritma yang dapat membangun rute Euler berdasarkan skema ini, katakanlah, dalam bentuk daftar {M, A, A, P, Y , L}, maka kita selesaikan masalahnya , karena mengeluarkan kata-kata dalam urutan tertentu hanya masalah teknik. Jadi, solusi untuk masalah kata domino kita adalah dengan menerapkan algoritma untuk menemukan jalur Euler (siklusnya “bebas”) dalam grafik berarah. Selanjutnya ->
Ini juga merupakan graf: 
Jika suatu sisi dapat dikatakan mempunyai arah, maka graf tersebut disebut berorientasi : 
Grafik pada dua gambar pertama tidak berarah. Kita dapat mengatakan bahwa sisi (u, v) identik dengan sisi (v, u), yaitu, misalnya sisi (0, 4) dan (4, 0) adalah sisi yang sama. Tanda panah pada sisi-sisi suatu graf berarah berarti sisi (u, v) merupakan lintasan dari titik u ke titik v dan sisi (v, u) tidak ada. Pada gambar ketiga terdapat tepi (E,A). Tidak ada tepi (A, E). Mari kita lihat lebih dekat gambar terakhir. Anda dapat melihat bahwa simpul F tidak memiliki tepi sama sekali, hal ini sangat mungkin terjadi. Kami juga mencatat bahwa sebuah tepi telah muncul di dekat simpul A - sebuah lingkaran, dan antara simpul B dan D ada dua sisi yang arahnya berbeda. Grafik terarah memungkinkan artefak semacam itu. Katakanlah grafik tersebut menggambarkan sekelompok kenalan yang saling memberi hadiah. Kita melihat bahwa F yang rakus tidak memberikan apa pun kepada siapa pun, B dan D bertukar hadiah (kecuali masing-masing dari mereka memberikan hadiah kepada orang lain), dan A memberikan hadiah untuk dirinya sendiri, mungkin pada saat berhasil menyelesaikan a. masalah dari planet Linear Chaos. Perlu diketahui bahwa simpul pada graf tidak harus berupa angka atau berisi angka; melainkan merupakan wadah, yaitu mereka dapat menyimpan objek apa pun. Grafik adalah deskripsi koneksi. Istilah penting yang akan berguna bagi kita nanti - jumlah sisi yang menempel pada suatu titik (atau, seperti yang juga dikatakan, bersisian dengannya) disebut derajat dari suatu titik tertentu. Misalnya pada gambar pertama, simpul 0 berderajat 2, 1 berderajat 4, 3 berderajat 3, simpul 0 pada gambar kedua berderajat 1. Pada artikel kali ini kita tidak akan mendalami macam-macam jenis graf, kami hanya akan menyebutkan bahwa ada juga grafik berbobot, yaitu. yang di mana nomor tertentu melekat pada setiap sisinya, yang menunjukkan “harga” perjalanannya. Graf terhubung mempunyai beberapa subtipe yang dibedakan berdasarkan sifat-sifatnya. Misalnya, grafik yang ujung-ujungnya tidak membentuk siklus di mana pun disebut pohon (grafik tersebut memiliki keluarga menarik dengan nama mengagumkan seperti “pohon merah-hitam”, misalnya) dan banyak digunakan dalam berbagai algoritma dan struktur data penting. Menggunakan grafik untuk menyelesaikan suatu masalah Semua ini sangat menarik, kata Anda, tetapi apa hubungannya semua ini dengan menyusun rangkaian kata? Ternyata yang paling langsung adalah. Mari kita lihat contoh pengujian kita dari kondisi: { Amsterdam Melbourne New York Kyiv Vienna }. Mari kita tuliskan dalam urutan apa pun huruf-huruf "nodal" yang melekat pada kata-kata tersebut: {A, M, N, K, B} 
dan menghubungkannya dengan kata-kata. 
Seperti yang dapat kita lihat, kita memiliki grafik berarah yang simpul-simpulnya adalah huruf dan ujung-ujungnya adalah kata-kata, yang menghubungkannya. Jika kita menemukan cara untuk melintasi semua sisi dari titik ke titik sehingga kita mengunjungi setiap sisi hanya satu kali, masalah kita akan terpecahkan. Mari kita coba mendistribusikan node pada diagram sedikit berbeda: 
Sekarang kita dapat melihat dengan lebih baik bahwa grafik kita adalah loop tertutup. Kita bisa memulai urutannya dengan kata apa saja, dan itu akan menjadi keputusan yang tepat. Namun, kondisi masalahnya memberi tahu kita bahwa satu solusi saja sudah cukup. Mari kita ganti Vena dengan Vladimir: 
Kita melihat dua konsekuensi: pertama, kita harus menambahkan simpul baru, huruf P, dan kedua, kita melihat bahwa grafik kita tidak dapat lagi dilingkarkan. Mari kita rangkum semua hal di atas dan perkenalkan dua istilah baru: 1. Graf terhubung yang sisi-sisinya dapat dilintasi hanya dengan mengunjungi masing-masing graf satu kali saja disebut graf yang memuat “jalur Euler ” . Ciri graf seperti itu (kecuali tidak adanya simpul tanpa tepi) adalah derajat genap semua simpul kecuali dua (dan hanya dua). 2. Jika ternyata dapat kembali ke simpul semula, kita katakan bahwa terdapat “siklus Euler” pada grafik tersebut . Ciri graf seperti itu (kecuali tidak adanya simpul tanpa tepi) adalah derajat genap semua simpul. Bayangkan daftar kota kita seperti ini: {Moscow Anapa Adler Rostov-on-Don Wuhan}. Mari kita membuat grafik: 
Pada diagram Anda dapat melihat bahwa grafik ini memiliki jalur Euler. Hanya ada dua simpul yang berderajat ganjil yaitu M dan L, selebihnya genap: A berderajat 4, karena loop dihitung dua kali, dan P dan Y memiliki derajat 2. Jika kita menemukan algoritma yang dapat membangun rute Euler berdasarkan skema ini, katakanlah, dalam bentuk daftar {M, A, A, P, Y , L}, maka kita selesaikan masalahnya , karena mengeluarkan kata-kata dalam urutan tertentu hanya masalah teknik. Jadi, solusi untuk masalah kata domino kita adalah dengan menerapkan algoritma untuk menemukan jalur Euler (siklusnya “bebas”) dalam grafik berarah. Selanjutnya ->
GO TO FULL VERSION