Bahagian 2 Bahagian 3 Bahagian 4 Saya telah digesa untuk menulis artikel ini oleh tugas berbahaya daripada pencarian Java Multithreading, yang, bukan tanpa sedikit usikan daripada pembangun, dipanggil oleh mereka sebagai "tugas StringBuilder." Intipati keadaannya adalah bahawa satu set perkataan (dalam keadaan nama bandar diberikan, yang mengingatkan kepada permainan kata kanak-kanak) harus disusun mengikut prinsip domino, huruf terakhir perkataan n' harus sama dengan huruf pertama perkataan (n+1) go, dan diketahui bahawa semua perkataan yang diberikan (secara individu) telah dijumlahkan dalam rantai sedemikian. Jika ada kemungkinan untuk mengarang beberapa pilihan untuk rangkaian perkataan yang dikehendaki, mana-mana satu telah diterima sebagai penyelesaian. Walaupun kesederhanaan dan kejelasan keadaan yang jelas, menyelesaikan masalah adalah jauh dari mudah, dan penggunaan StringBuilder yang mahir tidak menyelamatkan keadaan. Pemaju masalah itu ternyata dipesan isomorph dari planet Linear Chaos, yang lebih daripada sekali menakutkan kadet JavaRush. Seperti yang dijangkakan, penyelesaian cetek tidak sesuai dengan pengesah, kerana sentiasa ada rantai yang memaksa algoritma naif untuk melangkau perkataan. Ia adalah perlu untuk menumpuk "tongkat" tambahan, yang, walaupun merumitkan masalah, tidak membawa penyelesaian lebih dekat dalam kes umum dan semakin menguatkan perasaan bahawa keadaan mudah harus mempunyai penyelesaian yang sama mudah. Saya terpaksa menukar taktik dan menyelam sedikit ke dalam bidang yang lebih asas. Izinkan saya membuat tempahan segera supaya saya tidak menganggap diri saya pakar dalam teori graf; topik yang akan saya sentuh hampir tidak melampaui skop menyelesaikan masalah perkataan domino, dengan pengecualian, mungkin, hanya beberapa penyelewengan yang bersifat teori. Jadi, graf. Apakah itu graf: ia ialah koleksi (set, set, senarai - apa sahaja) bucu yang disambungkan antara satu sama lain . Sambungan biasanya dipanggil tepi , bucu juga dipanggil nod atau nod. Ini ialah graf: Ini juga graf: Jika kita boleh mengatakan tentang tepi bahawa ia mempunyai arah, maka graf itu dipanggil berorientasikan : Graf dalam dua gambar pertama tidak terarah. Kita boleh katakan tentang mereka bahawa tepi (u, v) adalah sama dengan tepi (v, u), iaitu, sebagai contoh, tepi (0, 4) dan (4, 0) adalah tepi yang sama. Anak panah pada tepi graf terarah bermakna tepi (u, v) ialah laluan dari bucu u ke bucu v dan tepi (v, u) tidak wujud. Dalam gambar ketiga terdapat tepi (E, A). Tiada tepi (A, E). Mari kita lihat dengan lebih dekat lukisan terakhir. Anda boleh perhatikan bahawa bucu F tidak mempunyai tepi sama sekali, ini agak mungkin. Kami juga ambil perhatian bahawa tepi telah muncul berhampiran bucu A - gelung, dan di antara bucu B dan D terdapat dua tepi berarah berbeza. Graf terarah membenarkan artifak tersebut. Katakan graf itu menerangkan sekumpulan kenalan yang saling memberi hadiah. Kami melihat bahawa F yang tamak tidak memberikan apa-apa kepada sesiapa, B dan D bertukar hadiah (kecuali fakta bahawa setiap daripada mereka memberi hadiah kepada orang lain), dan A memberi hadiah kepada dirinya sendiri, mungkin atas kejayaan menyelesaikan masalah. masalah dari planet Linear Chaos. Ngomong-ngomong, ambil perhatian bahawa bucu graf tidak semestinya nombor atau mengandungi nombor; ia adalah bekas, i.e. mereka boleh menyimpan sebarang objek. Graf ialah perihalan sambungan. Istilah penting yang akan berguna kepada kita kemudian - bilangan tepi yang dilampirkan pada bucu (atau, seperti yang mereka katakan, kejadian kepadanya) dipanggil darjah bucu yang diberikan. Sebagai contoh, dalam gambar pertama, puncak 0 mempunyai darjah 2, 1 mempunyai darjah 4, 3 mempunyai darjah 3, puncak 0 daripada rajah kedua mempunyai darjah 1. Dalam artikel ini kita tidak akan menyelidiki pelbagai jenis graf yang berbeza, kami hanya akan menyebut bahawa terdapat juga graf berwajaran, mereka. yang mana nombor tertentu dilampirkan pada setiap tepi, yang menunjukkan "harga" laluannya. Graf yang disambungkan mempunyai beberapa subjenis, dibezakan oleh sifatnya. Contohnya, graf yang tepinya tidak membentuk kitaran di mana-mana dipanggil pokok (ia mempunyai keluarga yang menarik dengan nama hebat seperti "pokok merah-hitam," contohnya) dan digunakan secara meluas dalam pelbagai algoritma dan struktur data yang penting. Menggunakan graf untuk menyelesaikan masalah Semua ini sangat menarik, kata anda, tetapi apakah kaitan semua ini dengan membina rangkaian perkataan? Ternyata perkara yang paling langsung adalah. Mari lihat contoh ujian kami daripada syarat: { Amsterdam Melbourne New York Kyiv Vienna }. Mari tuliskan dalam sebarang susunan huruf "nodal" yang mana perkataan itu berpaut: {A, M, N, K, B} dan sambungkannya dengan perkataan. Seperti yang kita lihat, kita mempunyai graf terarah di mana nodnya adalah huruf dan bahagian tepinya ialah perkataan yang menghubungkannya. Jika kita mencari jalan untuk merentasi semua tepi dari bucu ke bucu supaya kita melawat setiap tepi sekali sahaja, masalah kita akan selesai. Mari cuba untuk mengedarkan nod dalam rajah sedikit berbeza: Sekarang kita boleh melihat dengan lebih baik bahawa graf kita ialah gelung tertutup. Kita boleh memulakan urutan dengan apa-apa perkataan, dan ia akan menjadi keputusan yang tepat. Walau bagaimanapun, keadaan masalah memberitahu kita bahawa mana-mana satu penyelesaian akan mencukupi. Mari gantikan Vena dengan Vladimir: Kami melihat dua akibat: pertama, kami terpaksa menambah bucu baharu, huruf P, dan kedua, kami melihat bahawa tidak lagi mungkin untuk menggelungkan graf kami. Mari kita ringkaskan semua perkara di atas dan perkenalkan dua istilah baharu: 1. Graf bersambung yang tepinya boleh dilalui dengan melawati setiap satu sekali sahaja dipanggil graf yang mengandungi “laluan Eulerian ” . Ciri graf sedemikian (kecuali ketiadaan bucu tanpa tepi) ialah darjah genap semua bucu kecuali dua (dan hanya dua). 2. Jika ternyata mungkin untuk kembali ke nod asal, kami mengatakan bahawa terdapat "kitaran Eulerian" dalam graf . Ciri graf sedemikian (kecuali ketiadaan bucu tanpa tepi) ialah darjah genap semua bucu. Mari bayangkan senarai bandar kami seperti ini: {Moscow Anapa Adler Rostov-on-Don Wuhan}. Mari bina graf: Dalam rajah anda boleh melihat bahawa graf ini mempunyai laluan Eulerian. Terdapat hanya dua bucu dengan darjah ganjil - ini adalah M dan L, selebihnya adalah genap: A mempunyai darjah 4, kerana gelung dikira dua kali, dan P dan Y mempunyai darjah 2. Jika kita menghasilkan algoritma yang boleh membina laluan Eulerian berdasarkan skema ini, katakan, dalam bentuk senarai {M, A, A, P, Y , L}, maka kita akan menyelesaikan masalah itu, kerana mengeluarkan perkataan dalam susunan tertentu hanya akan menjadi soal teknik. Oleh itu, penyelesaian kepada masalah perkataan domino kami adalah untuk melaksanakan algoritma untuk mencari laluan Eulerian (kitaran adalah "percuma") dalam graf terarah. Seterusnya ->
Ini juga graf: 
Jika kita boleh mengatakan tentang tepi bahawa ia mempunyai arah, maka graf itu dipanggil berorientasikan : 
Graf dalam dua gambar pertama tidak terarah. Kita boleh katakan tentang mereka bahawa tepi (u, v) adalah sama dengan tepi (v, u), iaitu, sebagai contoh, tepi (0, 4) dan (4, 0) adalah tepi yang sama. Anak panah pada tepi graf terarah bermakna tepi (u, v) ialah laluan dari bucu u ke bucu v dan tepi (v, u) tidak wujud. Dalam gambar ketiga terdapat tepi (E, A). Tiada tepi (A, E). Mari kita lihat dengan lebih dekat lukisan terakhir. Anda boleh perhatikan bahawa bucu F tidak mempunyai tepi sama sekali, ini agak mungkin. Kami juga ambil perhatian bahawa tepi telah muncul berhampiran bucu A - gelung, dan di antara bucu B dan D terdapat dua tepi berarah berbeza. Graf terarah membenarkan artifak tersebut. Katakan graf itu menerangkan sekumpulan kenalan yang saling memberi hadiah. Kami melihat bahawa F yang tamak tidak memberikan apa-apa kepada sesiapa, B dan D bertukar hadiah (kecuali fakta bahawa setiap daripada mereka memberi hadiah kepada orang lain), dan A memberi hadiah kepada dirinya sendiri, mungkin atas kejayaan menyelesaikan masalah. masalah dari planet Linear Chaos. Ngomong-ngomong, ambil perhatian bahawa bucu graf tidak semestinya nombor atau mengandungi nombor; ia adalah bekas, i.e. mereka boleh menyimpan sebarang objek. Graf ialah perihalan sambungan. Istilah penting yang akan berguna kepada kita kemudian - bilangan tepi yang dilampirkan pada bucu (atau, seperti yang mereka katakan, kejadian kepadanya) dipanggil darjah bucu yang diberikan. Sebagai contoh, dalam gambar pertama, puncak 0 mempunyai darjah 2, 1 mempunyai darjah 4, 3 mempunyai darjah 3, puncak 0 daripada rajah kedua mempunyai darjah 1. Dalam artikel ini kita tidak akan menyelidiki pelbagai jenis graf yang berbeza, kami hanya akan menyebut bahawa terdapat juga graf berwajaran, mereka. yang mana nombor tertentu dilampirkan pada setiap tepi, yang menunjukkan "harga" laluannya. Graf yang disambungkan mempunyai beberapa subjenis, dibezakan oleh sifatnya. Contohnya, graf yang tepinya tidak membentuk kitaran di mana-mana dipanggil pokok (ia mempunyai keluarga yang menarik dengan nama hebat seperti "pokok merah-hitam," contohnya) dan digunakan secara meluas dalam pelbagai algoritma dan struktur data yang penting. Menggunakan graf untuk menyelesaikan masalah Semua ini sangat menarik, kata anda, tetapi apakah kaitan semua ini dengan membina rangkaian perkataan? Ternyata perkara yang paling langsung adalah. Mari lihat contoh ujian kami daripada syarat: { Amsterdam Melbourne New York Kyiv Vienna }. Mari tuliskan dalam sebarang susunan huruf "nodal" yang mana perkataan itu berpaut: {A, M, N, K, B} 
dan sambungkannya dengan perkataan. 
Seperti yang kita lihat, kita mempunyai graf terarah di mana nodnya adalah huruf dan bahagian tepinya ialah perkataan yang menghubungkannya. Jika kita mencari jalan untuk merentasi semua tepi dari bucu ke bucu supaya kita melawat setiap tepi sekali sahaja, masalah kita akan selesai. Mari cuba untuk mengedarkan nod dalam rajah sedikit berbeza: 
Sekarang kita boleh melihat dengan lebih baik bahawa graf kita ialah gelung tertutup. Kita boleh memulakan urutan dengan apa-apa perkataan, dan ia akan menjadi keputusan yang tepat. Walau bagaimanapun, keadaan masalah memberitahu kita bahawa mana-mana satu penyelesaian akan mencukupi. Mari gantikan Vena dengan Vladimir: 
Kami melihat dua akibat: pertama, kami terpaksa menambah bucu baharu, huruf P, dan kedua, kami melihat bahawa tidak lagi mungkin untuk menggelungkan graf kami. Mari kita ringkaskan semua perkara di atas dan perkenalkan dua istilah baharu: 1. Graf bersambung yang tepinya boleh dilalui dengan melawati setiap satu sekali sahaja dipanggil graf yang mengandungi “laluan Eulerian ” . Ciri graf sedemikian (kecuali ketiadaan bucu tanpa tepi) ialah darjah genap semua bucu kecuali dua (dan hanya dua). 2. Jika ternyata mungkin untuk kembali ke nod asal, kami mengatakan bahawa terdapat "kitaran Eulerian" dalam graf . Ciri graf sedemikian (kecuali ketiadaan bucu tanpa tepi) ialah darjah genap semua bucu. Mari bayangkan senarai bandar kami seperti ini: {Moscow Anapa Adler Rostov-on-Don Wuhan}. Mari bina graf: 
Dalam rajah anda boleh melihat bahawa graf ini mempunyai laluan Eulerian. Terdapat hanya dua bucu dengan darjah ganjil - ini adalah M dan L, selebihnya adalah genap: A mempunyai darjah 4, kerana gelung dikira dua kali, dan P dan Y mempunyai darjah 2. Jika kita menghasilkan algoritma yang boleh membina laluan Eulerian berdasarkan skema ini, katakan, dalam bentuk senarai {M, A, A, P, Y , L}, maka kita akan menyelesaikan masalah itu, kerana mengeluarkan perkataan dalam susunan tertentu hanya akan menjadi soal teknik. Oleh itu, penyelesaian kepada masalah perkataan domino kami adalah untuk melaksanakan algoritma untuk mencari laluan Eulerian (kitaran adalah "percuma") dalam graf terarah. Seterusnya ->
GO TO FULL VERSION