เล็กน้อยเกี่ยวกับกราฟและคำศัพท์ - โดมิโน ส่วนที่ 1.

ส่วนที่ 2 ส่วนที่ 3 ส่วนที่ 4 ฉันได้รับแจ้งให้เขียนบทความนี้โดยงานที่เป็นอันตรายจากภารกิจ Java Multithreading ซึ่งนักพัฒนาเรียกพวกเขาว่า "งาน StringBuilder" โดยไม่ต้องล้อเล่น สาระสำคัญของอาการของเธอคือต้องจัดเรียงชุดคำ (ในเงื่อนไขที่มีการตั้งชื่อเมืองซึ่งชวนให้นึกถึงเกมคำศัพท์สำหรับเด็ก) ต้องจัดเรียงตามหลักการโดมิโน ตัวอักษรตัวสุดท้ายของคำว่า n ควร เท่ากับอักษรตัวแรกของคำ (n+1) go และเป็นที่รู้กันว่าคำที่กำหนด (ทีละคำ) ทั้งหมดถูกรวมเข้าด้วยกันเป็นลูกโซ่ หากเป็นไปได้ที่จะเขียนหลายตัวเลือกสำหรับกลุ่มคำที่ต้องการ จะถือว่าตัวเลือกใดตัวเลือกหนึ่งเป็นวิธีแก้ปัญหา แม้จะมีความเรียบง่ายและชัดเจนของเงื่อนไขที่ชัดเจน แต่การแก้ปัญหาก็ยังห่างไกลจากความง่ายและการใช้ StringBuilder อย่างเชี่ยวชาญไม่สามารถกอบกู้สถานการณ์ได้ ผู้พัฒนาปัญหานี้ได้รับคำสั่งให้ isomorphs จากดาวเคราะห์ Linear Chaos ซึ่งทำให้นักเรียนนายร้อย JavaRush หวาดกลัวมากกว่าหนึ่งครั้ง ตามที่คาดไว้ วิธีแก้ปัญหาแบบผิวเผินไม่เหมาะกับเครื่องมือตรวจสอบความถูกต้อง เนื่องจากมีห่วงโซ่ที่บังคับให้อัลกอริธึมไร้เดียงสาข้ามคำอยู่เสมอ จำเป็นต้องกอง "ไม้ค้ำยัน" เพิ่มเติมซึ่งถึงแม้จะทำให้ปัญหาซับซ้อน แต่ก็ไม่ได้นำวิธีแก้ปัญหาเข้ามาใกล้ยิ่งขึ้นในกรณีทั่วไป และทำให้ความรู้สึกแข็งแกร่งขึ้นมากขึ้นว่าเงื่อนไขที่เรียบง่ายควรมีวิธีแก้ปัญหาที่ง่ายพอ ๆ กัน ฉันต้องเปลี่ยนยุทธวิธีและดำดิ่งลงสู่พื้นที่พื้นฐานมากขึ้นเล็กน้อย ฉันขอจองไว้ก่อนว่าไม่ว่าในกรณีใดฉันก็ถือว่าตัวเองเป็นผู้เชี่ยวชาญในทฤษฎีกราฟไม่ว่าในกรณีใดหัวข้อที่ฉันจะพูดถึงนั้นแทบจะไม่เกินขอบเขตของการแก้ปัญหาคำโดมิโนยกเว้นบางทีอาจเพียงเท่านั้น การพูดนอกเรื่องสองสามประการที่มีลักษณะทางทฤษฎี ดังนั้นกราฟ กราฟคืออะไร: มันคือคอลเลกชัน (เซ็ต, เซ็ต, รายการ - อะไรก็ได้) ของจุดยอดที่เชื่อมต่อถึงกัน การเชื่อมต่อมักเรียกว่าขอบจุดยอดเรียกอีกอย่างว่าโหนดหรือโหนด นี่คือกราฟ: นี่คือกราฟด้วย: หากเราสามารถพูดเกี่ยวกับขอบที่มีทิศทางได้กราฟจะเรียกว่าเชิง : กราฟในสองภาพแรกนั้นไม่มีทิศทาง. เราสามารถพูดเกี่ยวกับพวกมันได้ว่าขอบ (u, v) เหมือนกับขอบ (v, u) นั่นคือขอบ (0, 4) และ (4, 0) เป็นขอบเดียวกัน ลูกศรบนขอบของกราฟกำหนดทิศทาง หมายความว่าขอบ (u, v) เป็นเส้นทางจากจุดยอด u ไปยังจุดยอด v และไม่มีขอบ (v, u) ในภาพที่สามมีขอบ (E, A) ไม่มีขอบ (A, E) เรามาดูภาพวาดสุดท้ายกันดีกว่า คุณจะสังเกตได้ว่าจุดยอด F ไม่มีขอบเลย ซึ่งค่อนข้างเป็นไปได้ นอกจากนี้เรายังสังเกตด้วยว่าขอบปรากฏขึ้นใกล้กับจุดยอด A - วงรอบ และระหว่างจุดยอด B และ D จะมีขอบสองด้านที่มีทิศทางต่างกัน กราฟกำกับอนุญาตให้มีสิ่งประดิษฐ์ดังกล่าว สมมติว่ากราฟอธิบายกลุ่มคนรู้จักที่ให้ของขวัญกัน เราเห็นว่า F ผู้ละโมบไม่ได้ให้อะไรใครเลย B และ D แลกของขวัญกัน (ยกเว้นว่าแต่ละคนให้ของขวัญกับคนอื่น) และ A ก็ให้ของขวัญกับตัวเองซึ่งอาจเนื่องในโอกาสที่แก้ปัญหาได้สำเร็จ ปัญหาจากดาวเคราะห์ Linear Chaos อย่างไรก็ตาม โปรดทราบว่าจุดยอดของกราฟไม่จำเป็นต้องเป็นตัวเลขหรือมีตัวเลข แต่ค่อนข้างจะเป็นคอนเทนเนอร์ เช่น พวกเขาสามารถเก็บวัตถุใด ๆ กราฟคือคำอธิบายของการเชื่อมต่อ คำสำคัญที่จะเป็นประโยชน์สำหรับเราในภายหลัง - จำนวนขอบที่ติดกับจุดยอด (หรืออย่างที่พวกเขาพูดกันว่าเกิดขึ้นกับจุดนั้น) เรียกว่าระดับของจุดสุดยอดที่กำหนด ตัวอย่างเช่น ในภาพแรก จุดยอด 0 มีระดับ 2, 1 มีระดับ 4, 3 มีระดับ 3, จุดยอด 0 ของตัวเลขที่สองมีระดับ 1 ในบทความนี้ เราจะไม่เจาะลึกความหลากหลายของกราฟประเภทต่างๆ เราจะพูดถึงเพียงว่ายังมีกราฟถ่วงน้ำหนักอยู่ด้วย ซึ่งมีการติดตัวเลขจำนวนหนึ่งไว้ที่แต่ละขอบซึ่งระบุ "ราคา" ของข้อความนั้น กราฟที่เชื่อมต่อมีประเภทย่อยหลายประเภท จำแนกตามคุณสมบัติ ตัวอย่างเช่น กราฟที่มีขอบไม่ก่อให้เกิดวงจรใดๆ เรียกว่า ต้นไม้ (มีกลุ่มที่น่าสนใจซึ่งมีชื่อที่ยอดเยี่ยม เช่น "ต้นไม้สีแดงดำ") และมีการใช้กันอย่างแพร่หลายในอัลกอริธึมและโครงสร้างข้อมูลที่สำคัญต่างๆ การใช้กราฟเพื่อแก้ปัญหา คุณว่าทั้งหมดนี้น่าสนใจมาก แต่ทั้งหมดนี้เกี่ยวอะไรกับการสร้างห่วงโซ่คำ? ปรากฎว่าสิ่งที่ตรงที่สุดคือ ลองดูตัวอย่างการทดสอบของเราจากเงื่อนไข: { อัมสเตอร์ดัม เมลเบิร์น นิวยอร์ก เคียฟ เวียนนา } ลองเขียนตามลำดับใดก็ได้ของตัวอักษร "nodal" ที่คำนั้นเกาะอยู่: {A, M, N, K, B} และเชื่อมโยงพวกมันด้วยคำต่างๆ ดังที่เราเห็น เรามีกราฟกำกับซึ่งโหนดเป็นตัวอักษร และขอบเป็นคำพูดที่เชื่อมโยงกัน หากเราพบวิธีที่จะสำรวจขอบทั้งหมดจากจุดยอดหนึ่งไปยังอีกจุดหนึ่งเพื่อที่เราจะไปถึงแต่ละขอบเพียงครั้งเดียว ปัญหาของเราก็จะได้รับการแก้ไข ลองกระจายโหนดในไดอะแกรมให้แตกต่างออกไปเล็กน้อย: ตอนนี้เราจะเห็นได้ดีขึ้นว่ากราฟของเราเป็นแบบวงปิด เราสามารถเริ่มลำดับด้วยคำใดก็ได้ และมันจะเป็นการตัดสินใจที่ถูกต้อง อย่างไรก็ตาม สภาพของปัญหาบอกเราว่าวิธีแก้ไขวิธีใดวิธีหนึ่งก็เพียงพอแล้ว แทนที่ Vena ด้วย Vladimir: เราเห็นผลลัพธ์สองประการ ประการแรก เราต้องเพิ่มจุดยอดใหม่ ตัวอักษร P และประการที่สอง เราเห็นว่าไม่สามารถวนซ้ำกราฟของเราได้อีกต่อไป เราจะสรุปทั้งหมดข้างต้นและแนะนำคำศัพท์ใหม่สองคำ: 1. กราฟที่เชื่อมต่อกันซึ่งสามารถข้ามขอบได้โดยไปที่แต่ละกราฟเพียงครั้งเดียว เรียก ว่ากราฟที่มี "เส้นทางยูเลอเรียน" คุณลักษณะของกราฟดังกล่าว (ยกเว้นกรณีที่ไม่มีจุดยอดโดยไม่มีขอบ) คือระดับเลขคู่ของจุดยอดทั้งหมด ยกเว้นสองจุด (และมีเพียงสองจุดเท่านั้น) 2. หากเป็นไปได้ที่จะ กลับไปยังโหนดเดิม เราจะบอกว่ากราฟมี"วัฏจักรยูเลอเรียน" คุณลักษณะของกราฟดังกล่าว (ยกเว้นกรณีที่ไม่มีจุดยอดโดยไม่มีขอบ) คือระดับคู่ของจุดยอดทั้งหมด ลองจินตนาการถึงรายชื่อเมืองของเราดังนี้: {มอสโก อะนาปา แอดเลอร์ รอสตอฟ-ออน-ดอน อู่ฮั่น} มาสร้างกราฟกัน: ในแผนภาพ คุณจะเห็นว่ากราฟนี้มีเส้นทางออยเลอเรียน มีเพียงสองจุดยอดที่มีดีกรีคี่ - คือ M และ L ส่วนที่เหลือเป็นคู่: A มีดีกรี 4 เพราะ การวนซ้ำจะถูกนับสองครั้ง และ P และ Y มีดีกรี 2 หากเราคิดอัลกอริธึมที่สามารถสร้างเส้นทางออยเลอเรียนตามโครงร่างนี้ พูดในรูปแบบของรายการ {M, A, A, P, Y , L} แล้วเราจะแก้ปัญหา เพราะ การแสดงคำตามลำดับที่กำหนดจะเป็นเรื่องของเทคนิคเท่านั้น ดังนั้นวิธีแก้ปัญหาคำโดมิโนของเราจึงอยู่ที่การใช้อัลกอริธึมในการค้นหาเส้นทางออยเลอเรียน (วงจรคือ "อิสระ") ในกราฟกำกับ ถัดไป ->