พื้นฐานของทฤษฎีกราฟ ประวัติความเป็นมาและพัฒนาการ กราฟคืออะไร กราฟ: คำจำกัดความ - History.NES ประวัติทฤษฎีกราฟ
ทฤษฎีกราฟค้นหาการประยุกต์ใช้งาน เช่น ในระบบสารสนเทศทางภูมิศาสตร์ (GIS) บ้าน โครงสร้าง บล็อก ฯลฯ ที่มีอยู่หรือที่ออกแบบใหม่จะถือเป็นจุดยอด ส่วนถนน โครงข่ายสาธารณูปโภค สายไฟ ฯลฯ ที่เชื่อมต่อกันจะถือเป็นจุดยอด การใช้การคำนวณต่างๆ ที่ดำเนินการกับกราฟดังกล่าว ช่วยให้สามารถค้นหาเส้นทางเลี่ยงที่สั้นที่สุดหรือร้านขายของชำที่ใกล้ที่สุด หรือวางแผนเส้นทางที่เหมาะสมที่สุดได้
ทฤษฎีกราฟประกอบด้วยปัญหาที่ยังไม่ได้รับการแก้ไขจำนวนมากและสมมติฐานที่ยังไม่ได้รับการพิสูจน์
ประวัติความเป็นมาของทฤษฎีกราฟ
Leonard Euler ถือเป็นผู้ก่อตั้งทฤษฎีกราฟ ในปี ค.ศ. 1736 เขาได้กำหนดและเสนอวิธีแก้ปัญหาของสะพานทั้งเจ็ดแห่งเคอนิกสแบร์กในจดหมายฉบับหนึ่งของเขา ซึ่งต่อมาได้กลายเป็นหนึ่งในปัญหาคลาสสิกของทฤษฎีกราฟ คำว่า "กราฟ" ได้รับการบัญญัติขึ้นครั้งแรกโดยซิลเวสเตอร์ เจมส์ โจเซฟ ในปี พ.ศ. 2421 ในบทความของเขาในวารสาร Nature [ ] .
ศัพท์เฉพาะทางทฤษฎีกราฟ
การประยุกต์ทฤษฎีกราฟ
ดูสิ่งนี้ด้วย
หมายเหตุ
วรรณกรรม
- ดิสเทล อาร์.ทฤษฎีกราฟทรานส์ จากอังกฤษ - โนโวซีบีสค์: สำนักพิมพ์ของสถาบันคณิตศาสตร์, 2545 - 336 หน้า ไอ 5-86134-101-X.
- ดีสเทล อาร์.ทฤษฎีกราฟ ฉบับอิเล็กทรอนิกส์ - NY: Springer-Verlag, 2005. - หน้า 422.
- บาซาเกอร์ อาร์., ซาตี ที.กราฟและเครือข่ายจำกัด อ.: Nauka, 1974. 368c.
- Belov V.V., Vorobiev E.M., Shatalov V.E.ทฤษฎีกราฟ - ม.: สูงกว่า. โรงเรียน พ.ศ. 2519 - หน้า 392
- เบิร์ก เค.ทฤษฎีกราฟและการประยุกต์ อ.: อิลลินอยส์ 2505 320c
- Emelichev V. A. , Melnikov O. I. , Sarvanov V. I. , Tyshkevich R. I.บรรยายเรื่องทฤษฎีกราฟ อ.: Nauka, 1990. 384 หน้า (แก้ไข 2, แก้ไข M.: URSS, 2009. 392 p.)
Leonard Euler ถือเป็นผู้ก่อตั้งทฤษฎีกราฟ ในปี ค.ศ. 1736 เขาได้กำหนดและเสนอวิธีแก้ปัญหาของสะพานเคอนิกส์แบร์กทั้งเจ็ดแห่งในจดหมายฉบับหนึ่งของเขา ซึ่งต่อมาได้กลายเป็นหนึ่งในปัญหาคลาสสิกของทฤษฎีกราฟ
ปัญหาแรกในทฤษฎีกราฟเกี่ยวข้องกับการแก้ปัญหาและปริศนาทางคณิตศาสตร์ด้านสันทนาการ นี่เป็นการเล่าข้อความที่ตัดตอนมาจากจดหมายของออยเลอร์ลงวันที่ 13 มีนาคม พ.ศ. 2279 ว่า “ฉันได้รับปัญหาเกี่ยวกับเกาะที่ตั้งอยู่ในเมืองเคอนิกสเบิร์ก และล้อมรอบด้วยแม่น้ำที่มีสะพาน 7 แห่งพาดผ่าน คำถามก็คือว่ามีใครสามารถเดินอ้อมสะพานไปเรื่อยๆ โดยผ่านสะพานแต่ละสะพานได้เพียงครั้งเดียวหรือไม่ แล้วฉันก็ได้รับแจ้งว่ายังไม่มีใครสามารถทำได้ แต่ไม่มีใครพิสูจน์ได้ว่าเป็นไปไม่ได้ อย่างไรก็ตาม คำถามนี้แม้จะเป็นเรื่องเล็กน้อย แต่ดูเหมือนว่าคุ้มค่าแก่ความสนใจ เนื่องจากทั้งเรขาคณิต พีชคณิต หรือศิลปะเชิงผสมผสานก็ไม่เพียงพอที่จะแก้ปัญหาได้ หลังจากการไตร่ตรองอย่างถี่ถ้วนแล้ว ฉันพบกฎง่าย ๆ บนพื้นฐานของข้อพิสูจน์ที่น่าเชื่อถืออย่างสมบูรณ์ ด้วยความช่วยเหลือซึ่งเป็นไปได้ในทุกปัญหาประเภทนี้ เพื่อตัดสินทันทีว่าทางเบี่ยงดังกล่าวสามารถทำได้ด้วยจำนวนเท่าใดก็ได้และจำนวนเท่าใดก็ได้ สะพานตั้งอยู่แต่อย่างใด” สะพานเคอนิกส์แบร์กสามารถแสดงเป็นแผนผังได้ดังนี้:
กฎของออยเลอร์:
1. ในกราฟที่ไม่มีจุดยอดเป็นองศาคี่ จะมีการเคลื่อนที่ของขอบทั้งหมด (และแต่ละขอบจะเคลื่อนที่เพียงครั้งเดียว) โดยเริ่มต้นที่จุดยอดใดๆ ของกราฟ
2. ในกราฟที่มีจุดยอดสองจุดและมีองศาคี่เพียงสองจุด จะมีการเคลื่อนที่ที่เริ่มต้นที่จุดยอดที่มีระดับคี่และสิ้นสุดที่อีกจุดหนึ่ง
3. ในกราฟที่มีจุดยอดที่มีองศาคี่มากกว่าสองจุด จะไม่มีการเคลื่อนที่ดังกล่าว
มีปัญหาอีกประเภทหนึ่งที่เกี่ยวข้องกับการเดินทางไปตามกราฟ เรากำลังพูดถึงปัญหาที่จำเป็นต้องค้นหาเส้นทางที่ผ่านจุดยอดทั้งหมดและไม่เกินหนึ่งครั้งผ่านแต่ละจุด วัฏจักรที่ผ่านแต่ละจุดยอดเพียงครั้งเดียวเรียกว่าเส้นแฮมิลตัน (ตามชื่อวิลเลียม โรวัน แฮมิลตัน นักคณิตศาสตร์ชาวไอริชผู้โด่งดังแห่งศตวรรษที่ผ่านมา ซึ่งเป็นคนแรกที่ศึกษาเส้นดังกล่าว) น่าเสียดายที่ยังไม่พบเกณฑ์ทั่วไปที่สามารถตัดสินได้ว่ากราฟที่กำหนดเป็นกราฟแฮมิลตันหรือไม่ และหากเป็นเช่นนั้น ให้ค้นหาเส้นแฮมิลตันทั้งหมดในกราฟนั้น
สร้างขึ้นในช่วงกลางศตวรรษที่ 19 ปัญหาสี่สีก็ดูเหมือนเป็นปัญหาที่น่าสนุกเช่นกัน แต่ความพยายามที่จะแก้ไขได้นำไปสู่การศึกษากราฟบางส่วนที่มีความสำคัญทั้งทางทฤษฎีและประยุกต์ ปัญหาสี่สีมีการกำหนดไว้ดังนี้: “พื้นที่ของแผนที่แบนใดๆ สามารถระบายสีด้วยสี่สีเพื่อให้พื้นที่สองแห่งที่อยู่ติดกันมีสีต่างกันได้หรือไม่” สมมติฐานที่ว่าคำตอบคือการยืนยันได้รับการกำหนดขึ้นในช่วงกลางศตวรรษที่ 19 ในปีพ.ศ. 2433 มีการพิสูจน์ข้อความที่อ่อนแอกว่า กล่าวคือ แผนที่เรียบๆ สามารถระบายสีได้ห้าสี ด้วยการเชื่อมโยงแผนที่ระนาบใดๆ กับกราฟระนาบคู่ของมัน เราจะได้สูตรของปัญหาที่เทียบเท่ากันในรูปของกราฟ: จริงหรือไม่ที่เลขโครมาติกของกราฟระนาบใดๆ น้อยกว่าหรือเท่ากับสี่ ความพยายามหลายครั้งในการแก้ปัญหามีอิทธิพลต่อการพัฒนาทฤษฎีกราฟจำนวนหนึ่ง ในปี พ.ศ. 2519 มีการประกาศวิธีแก้ปัญหาเชิงบวกสำหรับปัญหาโดยใช้คอมพิวเตอร์
ปัญหาทอพอโลยีเก่าอีกปัญหาหนึ่งที่ต่อต้านการแก้ปัญหามาเป็นเวลานานและหลอกหลอนจิตใจของผู้ชื่นชอบปริศนา เรียกว่า “ปัญหาไฟฟ้า ก๊าซ และน้ำประปา” ในปี 1917 Henry E. Dudeney ได้ให้สูตรนี้แก่ผลิตภัณฑ์นี้ จะต้องติดตั้งแก๊ส ไฟฟ้า และน้ำ ในแต่ละหลังทั้งสามหลังตามภาพ
ทฤษฎีกราฟ 1
ประวัติความเป็นมาของทฤษฎีกราฟ 1
กฎของออยเลอร์ 1
วรรณกรรม
1. ทฤษฎีกราฟ Belov มอสโก "วิทยาศาสตร์" 1968.
2. เทคโนโลยีการสอนและสารสนเทศใหม่ E.S. Polat , มอสโก, "อคาเดเมีย" 1999
3. Kuznetsov O.P., Adelson-Velsky G.M. คณิตศาสตร์ไม่ต่อเนื่องสำหรับวิศวกร – อ.: Energoatomizdat, 1988.
4. Cook D., Baze G. คณิตศาสตร์คอมพิวเตอร์. – อ.: วิทยาศาสตร์, 1990.
5. Nefedov V.N., Osipova V.A. หลักสูตรคณิตศาสตร์แบบไม่ต่อเนื่อง – อ.: สำนักพิมพ์ เอ็ม เอ ไอ, 1992.
6. ทฤษฎีกราฟแร่ทุม – อ.: วิทยาศาสตร์, 1980.
7. อิสมากิลอฟ อาร์.เอส., คาลินคิน เอ.วี. สื่อการสอนภาคปฏิบัติในหลักสูตร: คณิตศาสตร์แบบไม่ต่อเนื่อง
ผู้ก่อตั้งทฤษฎีกราฟคือนักคณิตศาสตร์ เลออนฮาร์ด ออยเลอร์ (1707-1783) ประวัติความเป็นมาของทฤษฎีนี้สามารถสืบย้อนได้จากจดหมายโต้ตอบของนักวิทยาศาสตร์ผู้ยิ่งใหญ่คนนี้ นี่คือคำแปลของข้อความภาษาละติน ซึ่งนำมาจากจดหมายของออยเลอร์ถึงนักคณิตศาสตร์และวิศวกรชาวอิตาลี มาริโนนี ซึ่งส่งจากเซนต์ปีเตอร์สเบิร์กเมื่อวันที่ 13 มีนาคม ค.ศ. 1736 [ดู หน้า 41-42]:
“ครั้งหนึ่งผมเคยถูกถามถึงปัญหาเกี่ยวกับเกาะแห่งหนึ่งที่ตั้งอยู่ในเมืองเคอนิกส์แบร์กและล้อมรอบด้วยแม่น้ำซึ่งมีสะพานถึง 7 แห่งถูกโยนทิ้งไป คำถามก็คือ มีใครสามารถเดินไปรอบๆ เกาะเหล่านั้นได้อย่างต่อเนื่อง โดยผ่านแต่ละสะพานเพียงครั้งเดียว แล้วผมก็ แจ้งว่ายังไม่มีใครสามารถทำเช่นนี้ได้ แต่ก็ไม่มีใครพิสูจน์ได้ว่าเป็นไปไม่ได้ อย่างไรก็ตาม สำหรับฉันคำถามนี้แม้จะดูเล็กน้อยแต่ก็คุ้มค่าที่จะให้ความสนใจในแง่ที่ว่าทั้งเรขาคณิต พีชคณิต หรือศิลปะเชิงผสมผสานนั้นไม่คู่ควร ก็เพียงพอที่จะแก้ไขได้... หลังจากครุ่นคิดอยู่นานก็พบกฎง่ายๆ โดยมีหลักฐานที่น่าเชื่อถืออย่างสมบูรณ์ ซึ่งช่วยระบุปัญหาประเภทนี้ได้ทันทีว่าทางอ้อมดังกล่าวสามารถทำได้ด้วยวิธีใดก็ตาม จำนวนสะพานที่ตั้ง แต่อย่างใด ดังรูปต่อไปนี้[รูปที่ 1] โดยที่ A หมายถึงเกาะ และ B, C และ D - ส่วนหนึ่งของทวีปแยกจากกันด้วยกิ่งก้านของแม่น้ำ สะพานทั้งเจ็ดมีป้ายกำกับว่า a, b, c, d, e, f, g"
(รูปที่ 1.1)
เกี่ยวกับวิธีการที่เขาค้นพบในการแก้ปัญหาประเภทนี้ ออยเลอร์เขียนไว้ [ดู หน้า 102-104]:
“โดยธรรมชาติแล้ววิธีแก้ปัญหานี้ดูเหมือนจะไม่ค่อยเกี่ยวข้องกับคณิตศาสตร์เลย และฉันก็ไม่เข้าใจว่าทำไมเราจึงควรคาดหวังคำตอบนี้จากนักคณิตศาสตร์มากกว่าจากบุคคลอื่น เพราะการตัดสินใจนี้ได้รับการสนับสนุนจากการใช้เหตุผลเพียงอย่างเดียว และไม่มี จำเป็นต้องเกี่ยวข้องกับการหาวิธีแก้ปัญหานี้ ไม่ว่าจะเป็นกฎใดๆ ก็ตามที่มีอยู่ในคณิตศาสตร์ ดังนั้น ฉันไม่รู้ว่าคำถามที่เกี่ยวข้องกับคณิตศาสตร์น้อยมากมีแนวโน้มที่จะแก้โดยนักคณิตศาสตร์มากกว่าคำถามอื่นๆ"
เป็นไปได้ไหมที่จะเดินทางรอบสะพานเคอนิกส์แบร์กโดยผ่านสะพานแต่ละแห่งเพียงครั้งเดียว หากต้องการค้นหาคำตอบ เรามาเขียนจดหมายของออยเลอร์ถึงมาริโนนีต่อ:
0 "คำถามคือต้องพิจารณาว่าเป็นไปได้หรือไม่ที่จะข้ามสะพานทั้งเจ็ดแห่งนี้ โดยผ่านแต่ละสะพานเพียงครั้งเดียวหรือไม่ กฎของฉันนำไปสู่วิธีแก้ปัญหาต่อไปนี้ ก่อนอื่นคุณต้องดูว่ามีกี่สะพาน ส่วนต่างๆ มีน้ำคั่น - ส่วนที่ไม่มีทางเดินอื่นจากที่หนึ่งไปยังอีกที่หนึ่งยกเว้นผ่านสะพาน ในตัวอย่างนี้ มีสี่ส่วนดังกล่าว - A, B, C, D ต่อไป คุณต้องแยกแยะว่าจำนวน สะพานที่นำไปสู่แต่ละส่วนเหล่านี้เป็นเลขคู่หรือคี่ ดังนั้น ในกรณีของเรา สะพานห้าแห่งนำไปสู่ส่วน A และสะพานสามแห่งไปยังส่วนอื่นๆ ที่เหลือ กล่าวคือ จำนวนสะพานที่นำไปสู่แต่ละส่วนนั้นเป็นเลขคี่ และเพียงอย่างเดียวก็เพียงพอที่จะแก้ได้ ปัญหา. เมื่อพิจารณาแล้ว เราจะใช้กฎต่อไปนี้: หากจำนวนสะพานที่นำไปสู่แต่ละส่วนที่แยกจากกันเป็นจำนวนเท่ากัน ทางเบี่ยงนั้นก็จะเป็นไปได้ และในขณะเดียวกันก็เป็นไปได้ที่จะเริ่มทางเบี่ยงนี้จาก มาตราใด ๆ ถ้าเป็นเลขคี่เพราะมีเพียงอันเดียวเท่านั้นที่จะเป็นคี่ไม่ได้แล้วถึงแม้การเปลี่ยนผ่านจะเสร็จสิ้นตามที่กำหนดไว้ แต่ต้องเอาเฉพาะจุดเริ่มต้นของทางอ้อมจากหนึ่งในสองส่วนนั้นอย่างแน่นอนซึ่งมีเลขคี่ สะพานนำไปสู่ ในที่สุด หากมีมากกว่าสองส่วนที่สะพานจำนวนคี่พาไป การเคลื่อนไหวดังกล่าวก็เป็นไปไม่ได้โดยทั่วไป ... หากสามารถนำปัญหาอื่น ๆ ที่ร้ายแรงกว่ามาที่นี่ได้ วิธีนี้อาจมีประโยชน์มากกว่าและควร อย่าละเลย" .
เหตุผลสำหรับกฎข้างต้นสามารถพบได้ในจดหมายจากแอล. ออยเลอร์ถึงเอห์เลอร์เพื่อนของเขา ลงวันที่ 3 เมษายนของปีเดียวกัน เราจะเล่าข้อความที่ตัดตอนมาจากจดหมายฉบับนี้อีกครั้งด้านล่าง
นักคณิตศาสตร์เขียนว่าการเปลี่ยนแปลงเกิดขึ้นได้หากมีบริเวณทางแยกแม่น้ำไม่เกินสองแห่ง ซึ่งมีสะพานเป็นจำนวนคี่ เพื่อให้ง่ายต่อการจินตนาการ เราจะลบสะพานที่สำรวจไปแล้วในภาพออก ง่ายที่จะตรวจสอบว่าถ้าเราเริ่มเคลื่อนที่ตามกฎของออยเลอร์ ข้ามสะพานหนึ่งแล้วลบออก รูปนั้นจะแสดงส่วนที่อีกครั้งว่ามีพื้นที่ไม่เกินสองพื้นที่ซึ่งมีสะพานเป็นเลขคี่พาไป และถ้ามี เป็นพื้นที่ที่มีสะพานเลขคี่เราจะอยู่ในหนึ่งในนั้น เดินหน้าต่อไปแบบนี้เราจะข้ามสะพานทั้งหมดครั้งเดียว
เรื่องราวของสะพานแห่งเมือง Königsberg มีความต่อเนื่องที่ทันสมัย ยกตัวอย่างหนังสือเรียนวิชาคณิตศาสตร์ที่แก้ไขโดย N.Ya Vilenkina สำหรับชั้นประถมศึกษาปีที่ 6 ในนั้น ในหน้า 98 ภายใต้หัวข้อการพัฒนาความใส่ใจและความฉลาด เราจะพบปัญหาที่เกี่ยวข้องโดยตรงกับปัญหาที่ออยเลอร์เคยแก้ไข
ปัญหาหมายเลข 569. ทะเลสาบมีเกาะอยู่ทั้งหมด 7 เกาะ ซึ่งเชื่อมต่อถึงกันดังแสดงในรูปที่ 1.2 เรือลำไหนควรพานักท่องเที่ยวไปข้ามสะพานแต่ละแห่งได้เพียงครั้งเดียว? เหตุใดนักท่องเที่ยวจึงไม่สามารถขนส่งไปยังเกาะได้? ก?
สารละลาย.เนื่องจากปัญหานี้คล้ายกับปัญหาของสะพานเคอนิกสเบิร์ก เมื่อทำการแก้ไข เราจะใช้กฎของออยเลอร์ด้วย เราจึงได้คำตอบดังนี้ เรือต้องส่งนักท่องเที่ยวไปที่เกาะ อีหรือ เอฟเพื่อจะได้ข้ามสะพานแต่ละแห่งได้ครั้งหนึ่ง จากกฎออยเลอร์เดียวกัน เป็นไปตามที่ว่าทางเบี่ยงที่จำเป็นนั้นเป็นไปไม่ได้หากเริ่มจากเกาะ ก.
โดยสรุป เราสังเกตว่าปัญหาของสะพานเคอนิกสเบิร์กและปัญหาที่คล้ายกัน พร้อมด้วยชุดวิธีการศึกษา ถือเป็นสาขาวิชาคณิตศาสตร์ที่สำคัญมากในแง่ปฏิบัติ เรียกว่าทฤษฎีกราฟ งานกราฟชิ้นแรกเป็นของ L. Euler และปรากฏในปี 1736 ต่อจากนั้น Koenig (1774-1833), Hamilton (1805-1865) และนักคณิตศาสตร์สมัยใหม่ C. Berge, O. Ore, A. Zykov ทำงานในกราฟ
ทฤษฎีกราฟ- หนึ่งในสาขาวิชาคณิตศาสตร์แยกที่กว้างขวางที่สุด ซึ่งใช้กันอย่างแพร่หลายในการแก้ปัญหาเศรษฐศาสตร์และการจัดการ ในการเขียนโปรแกรม เคมี การออกแบบและการศึกษาวงจรไฟฟ้า การสื่อสาร จิตวิทยา จิตวิทยา สังคมวิทยา ภาษาศาสตร์ และสาขาความรู้อื่น ๆ ทฤษฎีกราฟศึกษาคุณสมบัติของกราฟอย่างเป็นระบบและสม่ำเสมอซึ่งอาจกล่าวได้ว่าประกอบด้วยเซตของจุดและเซตของเส้นที่แสดงถึงการเชื่อมต่อระหว่างจุดเหล่านี้ ผู้ก่อตั้งทฤษฎีกราฟคือ Leonhard Euler (1707-1882) ซึ่งเป็นผู้แก้ไขปัญหาสะพานเคอนิกส์เบิร์กที่โด่งดังในขณะนั้นในปี 1736
กราฟถูกสร้างขึ้นเพื่อแสดงความสัมพันธ์ระหว่างฉาก สมมุติว่าเป็นเซต ก = {ก1 , ก 2 , ... กน)- คนจำนวนมาก และแต่ละองค์ประกอบจะแสดงเป็นจุด พวงของ บี = {ข1 , ข 2 , ... ขม)- การเชื่อมต่อมากมาย (เส้นตรง ส่วนโค้ง ส่วนต่างๆ - มันยังไม่สำคัญ) ในชุด กเป็นการมอบความสัมพันธ์ของคนรู้จักระหว่างคนจากชุดนี้ การสร้างกราฟจากจุดและจุดเชื่อมต่อ ลิงค์จะเชื่อมโยงคู่รักที่รู้จักกัน โดยธรรมชาติแล้วจำนวนคนรู้จักของบางคนอาจแตกต่างจากจำนวนคนรู้จักของคนอื่นๆ และบางคนก็อาจไม่รู้จักใครเลย (องค์ประกอบดังกล่าวจะเป็นจุดที่ไม่เชื่อมโยงกับบุคคลอื่น) เราก็จะได้กราฟ!
สิ่งที่เราเรียกว่า "จุด" ในตอนแรกควรเรียกว่าจุดยอดของกราฟ และสิ่งที่เราเรียกว่า "การเชื่อมต่อ" ควรเรียกว่าขอบของกราฟ
ทฤษฎีกราฟไม่ได้คำนึงถึงลักษณะเฉพาะของเซต กและ บี. มีปัญหาเฉพาะที่แตกต่างกันจำนวนมากจำนวนมากเมื่อทำการแก้ไขซึ่งใคร ๆ ก็สามารถลืมเกี่ยวกับเนื้อหาเฉพาะของชุดและองค์ประกอบได้ชั่วคราว ความเฉพาะเจาะจงนี้ไม่ส่งผลกระทบใด ๆ ต่อความคืบหน้าของการแก้ปัญหาไม่ว่าปัญหาจะเป็นอย่างไร! เช่น เมื่อตัดสินใจว่าเป็นไปได้จากจุดใดจุดหนึ่งหรือไม่ กไปถึงจุด จเคลื่อนไปตามเส้นเชื่อมจุดเท่านั้นไม่สำคัญว่าเราจะติดต่อกับคน เมือง ตัวเลข ฯลฯ แต่เมื่อปัญหาได้รับการแก้ไข เราจะได้คำตอบที่เป็นจริงสำหรับเนื้อหาใดๆ ที่ถูกจำลองเป็นกราฟ ดังนั้นจึงไม่น่าแปลกใจที่ทฤษฎีกราฟเป็นหนึ่งในเครื่องมือที่ได้รับความนิยมมากที่สุดในการสร้างปัญญาประดิษฐ์ เพราะท้ายที่สุดแล้ว ปัญญาประดิษฐ์สามารถพูดคุยกับคู่สนทนาในประเด็นความรัก ปัญหาด้านดนตรีหรือกีฬา และประเด็นในการแก้ปัญหาต่างๆ และทำสิ่งนี้โดยไม่มีการเปลี่ยนแปลงใด ๆ (การสลับ) โดยที่บุคคลไม่สามารถทำได้หากไม่มีในกรณีเช่นนี้
และตอนนี้คำจำกัดความทางคณิตศาสตร์ที่เข้มงวดของกราฟ
คำจำกัดความ 1.มันเรียกว่ากราฟระบบของวัตถุที่มีลักษณะตามอำเภอใจ (จุดยอด) และลิงก์ (ขอบ) ที่เชื่อมต่อวัตถุเหล่านี้บางคู่
คำจำกัดความ 2อนุญาต วี– (ไม่ว่าง) ชุดจุดยอด องค์ประกอบ โวลต์∈วี- ยอดเขา กราฟ ช = ช(วี) มีจุดยอดมากมาย วีมีบางตระกูลของคู่แบบฟอร์ม: จ = (ก, ข) , ที่ไหน ก,ข∈วี เพื่อระบุว่าจุดยอดใดยังคงเชื่อมต่ออยู่ แต่ละคู่ จ = (ก, ข) - ขอบของกราฟ พวงของ ยู- ขอบมากมาย จกราฟ. ยอดเขา กและ ข– จุดสิ้นสุดของขอบ จ .
กราฟเป็นโครงสร้างข้อมูลการใช้ทฤษฎีกราฟอย่างแพร่หลายในวิทยาการคอมพิวเตอร์และเทคโนโลยีสารสนเทศเกิดจากการเพิ่มแนวคิดของกราฟเป็นโครงสร้างข้อมูลในคำจำกัดความข้างต้น ในวิทยาการคอมพิวเตอร์และเทคโนโลยีสารสนเทศ กราฟถูกกำหนดให้เป็นโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้น โครงสร้างข้อมูลเชิงเส้นคืออะไร และกราฟแตกต่างจากโครงสร้างเหล่านี้อย่างไร โครงสร้างข้อมูลเชิงเส้นมีลักษณะพิเศษคือเชื่อมโยงองค์ประกอบต่างๆ ผ่านความสัมพันธ์ประเภท "พื้นที่ใกล้เคียงแบบเรียบง่าย" โครงสร้างข้อมูลเชิงเส้นได้แก่ อาร์เรย์ ตาราง รายการ คิว สแต็ก สตริง ในทางตรงกันข้าม โครงสร้างข้อมูลแบบไม่เชิงเส้นคือองค์ประกอบที่องค์ประกอบต่างๆ อยู่ในระดับต่างๆ ของลำดับชั้น และแบ่งออกเป็น 3 ประเภท ได้แก่ ดั้งเดิม สร้างขึ้น และคล้ายกัน ดังนั้นกราฟจึงเป็นโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้น
คำว่ากราฟมีต้นกำเนิดมาจากภาษากรีก มาจากคำว่า "ฉันเขียน" "ฉันอธิบาย" จากจุดเริ่มต้นของบทความนี้ เรารู้แล้วว่ากราฟอธิบายอะไร: อธิบายความสัมพันธ์ นั่นคือกราฟใดๆ ก็ตามที่อธิบายความสัมพันธ์ และในทางกลับกัน ความสัมพันธ์ใดๆ สามารถอธิบายได้เป็นกราฟ
แนวคิดพื้นฐานของทฤษฎีกราฟ
แนวคิดเรื่องอุบัติการณ์ยังจำเป็นในการพัฒนาอัลกอริธึมสำหรับการแก้ปัญหาเชิงปฏิบัติหลายอย่างเกี่ยวกับกราฟ ตัวอย่างเช่น คุณสามารถทำความคุ้นเคยกับการใช้งานซอฟต์แวร์ได้ การสำรวจกราฟเชิงลึกอันดับแรกซึ่งแสดงโดยเมทริกซ์อุบัติการณ์. แนวคิดนี้ง่ายมาก: คุณสามารถเคลื่อนที่ผ่านจุดยอดที่เชื่อมต่อกันด้วยขอบเท่านั้น และหากมีการกำหนดค่าบางค่าให้กับขอบ ("สเกล" ซึ่งส่วนใหญ่มักจะอยู่ในรูปแบบของตัวเลขกราฟดังกล่าวจะเรียกว่าถ่วงน้ำหนักหรือติดป้ายกำกับ) ก็สามารถแก้ไขปัญหาที่ซับซ้อนที่ใช้ได้ซึ่งบางส่วนได้กล่าวถึงในย่อหน้าสุดท้าย ของบทเรียนนี้
ปัญหาคลาสสิกของทฤษฎีกราฟและวิธีแก้
ตัวอย่างงานเกี่ยวกับทฤษฎีกราฟและการประยุกต์ใช้กราฟที่ได้รับการตีพิมพ์ครั้งแรกคืองาน "ปัญหาสะพานเคอนิกสเบิร์ก" (1736) ซึ่งเขียนโดยเลออนฮาร์ด ออยเลอร์ นักคณิตศาสตร์ผู้โด่งดังแห่งศตวรรษที่ 18 ปัญหาประกอบด้วยแม่น้ำ เกาะที่ถูกแม่น้ำสายนี้พัดพา และสะพานหลายแห่ง คำถามของปัญหา: เป็นไปได้ไหมที่หลังจากออกจากจุดหนึ่งแล้ว ที่จะข้ามสะพานแต่ละแห่งเพียงครั้งเดียวและกลับไปยังจุดเริ่มต้น? (ภาพด้านล่าง)
ปัญหาสามารถจำลองได้ดังนี้: มีจุดหนึ่งจุดติดกับแต่ละพื้นที่ และจุดสองจุดเชื่อมต่อกันด้วยเส้น ถ้าและเฉพาะในกรณีที่พื้นที่ที่สอดคล้องกันเชื่อมต่อกันด้วยสะพาน (รูปด้านล่าง เส้นเชื่อมต่อถูกวาดด้วยเส้นประ) . ดังนั้นกราฟจึงถูกสร้างขึ้น
คำตอบของออยเลอร์สำหรับคำถามปัญหามีดังนี้ หากปัญหานี้มีวิธีแก้ปัญหาเชิงบวก ดังนั้นในกราฟผลลัพธ์จะมีเส้นทางปิดผ่านขอบและมีแต่ละขอบเพียงครั้งเดียว หากมีเส้นทางดังกล่าว จุดยอดแต่ละจุดจะต้องมีจำนวนขอบเป็นจำนวนคู่เท่านั้น แต่กราฟผลลัพธ์จะมีจุดยอดที่มีจำนวนขอบเป็นคี่ ดังนั้นปัญหาจึงไม่มีวิธีแก้ปัญหาเชิงบวก
ตามประเพณีที่กำหนดไว้ กราฟออยเลอเรียนคือกราฟที่สามารถเคลื่อนที่ผ่านจุดยอดทั้งหมดได้ และในเวลาเดียวกันก็เคลื่อนที่ผ่านขอบด้านใดด้านหนึ่งเพียงครั้งเดียวเท่านั้น ในนั้นแต่ละจุดยอดจะต้องมีจำนวนขอบเป็นเลขคู่เท่านั้น ปัญหาของความยากปานกลางบนกราฟออยเลอร์อยู่ที่เนื้อหา “ประเภทพื้นฐานของกราฟ”
ในปี ค.ศ. 1847 Kirchhoff ได้พัฒนาทฤษฎีของต้นไม้เพื่อแก้ระบบสมการพีชคณิตเชิงเส้นไปพร้อมๆ กัน ช่วยให้สามารถค้นหาค่าของกระแสในแต่ละตัวนำ (ส่วนโค้ง) และในแต่ละวงจรของวงจรไฟฟ้า จากวงจรไฟฟ้าและวงจรที่มีความต้านทาน ตัวเก็บประจุ ตัวเหนี่ยวนำ ฯลฯ เขาพิจารณาโครงสร้างเชิงผสมที่สอดคล้องกันที่มีเฉพาะจุดยอดและการเชื่อมต่อ (ขอบหรือส่วนโค้ง) และสำหรับการเชื่อมต่อไม่จำเป็นต้องคำนึงถึงองค์ประกอบทางไฟฟ้าประเภทใด พวกเขาสอดคล้องกับ ดังนั้น Kirchhoff จึงแทนที่วงจรไฟฟ้าแต่ละวงจรด้วยกราฟที่สอดคล้องกัน และแสดงให้เห็นว่าในการแก้ระบบสมการ ไม่จำเป็นต้องพิจารณาแต่ละรอบของกราฟวงจรไฟฟ้าแยกกัน
เคย์ลีย์ในปี พ.ศ. 2401 ขณะที่ทำงานเกี่ยวกับปัญหาเชิงปฏิบัติในวิชาเคมีอินทรีย์เพียงอย่างเดียว เขาได้ค้นพบกราฟประเภทสำคัญที่เรียกว่าต้นไม้ เขาพยายามที่จะแสดงรายการไอโซเมอร์ของไฮโดรคาร์บอนอิ่มตัว โดยระบุจำนวนอะตอมของคาร์บอน เคย์ลีย์ได้กำหนดปัญหาขึ้นมาเป็นเชิงนามธรรม: จงหาจำนวนต้นไม้ทั้งหมดด้วย พีจุดยอด ซึ่งแต่ละจุดมีจุดยอดที่มีองศา 1 และ 4 เขาไม่สามารถแก้ปัญหานี้ได้ทันที และเขาเริ่มเปลี่ยนสูตรในลักษณะที่สามารถแก้ไขปัญหาการแจงนับใหม่ได้:
- ต้นไม้ที่หยั่งราก (ซึ่งเลือกจุดยอดอันใดอันหนึ่ง)
- ต้นไม้ทั้งหมด
- ต้นไม้ที่มีองศายอดไม่เกิน 4
- ต้นไม้ที่มีจุดยอดเป็น 1 และ 4 (คำชี้แจงปัญหาจากวิชาเคมี)
ปัญหากราฟเพื่อเสริมแนวคิดพื้นฐาน
ตัวอย่างที่ 1อนุญาต ก- ชุดตัวเลข 1, 2, 3: ก= (1, 2, 3) . สร้างกราฟเพื่อแสดงความสัมพันธ์”
สารละลาย. แน่นอนว่าตัวเลข 1, 2, 3 ควรแสดงเป็นจุดยอดของกราฟ จากนั้นจุดยอดแต่ละคู่จะต้องเชื่อมต่อกันด้วยขอบด้านเดียว ในการแก้ปัญหานี้ เรามาถึงแนวคิดพื้นฐานของทฤษฎีกราฟเช่น กราฟแบบมีทิศทางและแบบไม่มีทิศทาง. กราฟที่ไม่มีทิศทางคือกราฟที่ขอบไม่มีทิศทาง หรืออย่างที่พวกเขาพูดบ่อยกว่านั้น ลำดับของปลายทั้งสองด้านของขอบนั้นไม่มีนัยสำคัญ ที่จริงแล้ว กราฟที่สร้างขึ้นตอนต้นของบทเรียนนี้และแสดงถึงความสัมพันธ์ของคนรู้จักไม่จำเป็นต้องมีทิศทางที่ชัดเจน เนื่องจากอาจโต้แย้งได้ว่า “บุคคลที่ 1” มีความคุ้นเคยกับ “บุคคลที่ 2” ในระดับเดียวกัน เป็น "บุคคลที่ 2" กับ "บุคคลที่ 1" ในตัวอย่างปัจจุบันของเรา จำนวนหนึ่งมีค่าน้อยกว่าอีกจำนวนหนึ่ง แต่กลับกันไม่ได้ ดังนั้นขอบที่สอดคล้องกันของกราฟจะต้องมีทิศทางที่ระบุว่าตัวเลขใดน้อยกว่าอีกอัน นั่นคือลำดับของขอบสิ้นสุดมีความสำคัญ กราฟดังกล่าว (ที่มีขอบมีทิศทาง) เรียกว่ากราฟกำกับหรือไดกราฟ
ดังนั้นในฝูงชนของเรา กหมายเลข 1 น้อยกว่าหมายเลข 2 และหมายเลข 3 และหมายเลข 2 น้อยกว่าหมายเลข 3 เราแสดงข้อเท็จจริงนี้ตามขอบที่มีทิศทางซึ่งแสดงด้วยลูกศร เราได้รับกราฟดังต่อไปนี้:
ตัวอย่างที่ 2อนุญาต ก- ชุดตัวเลข 2, 4, 6, 14: ก= (2, 4, 6, 14) . สร้างกราฟเพื่อแสดงความสัมพันธ์ "หารด้วย" ในชุดนี้
สารละลาย. ในตัวอย่างนี้ ขอบบางส่วนจะมีทิศทาง และบางส่วนไม่มี นั่นคือเรากำลังสร้าง กราฟผสม. ลองเขียนความสัมพันธ์ในชุดนี้กัน: 4 หารด้วย 2 ลงตัว, 6 หารด้วย 2 ลงตัว, 14 หารด้วย 2 ลงตัว และแต่ละตัวเลขจากชุดนี้หารด้วยตัวมันเอง ความสัมพันธ์นี้ก็คือเมื่อตัวเลขหารด้วยตัวมันเองได้ จะแสดงในรูปแบบของขอบที่เชื่อมจุดยอดเข้ากับตัวมันเอง ขอบดังกล่าวเรียกว่า ลูป. ในกรณีนี้ไม่จำเป็นต้องบอกทิศทางของลูป ดังนั้นในตัวอย่างของเรา มีขอบกำกับปกติสามเส้นและสี่ลูป เราได้รับกราฟดังต่อไปนี้:
ตัวอย่างที่ 3ให้ชุดที่กำหนด ก= (α, β, γ) และ บี= (ก, ข, ค) . สร้างกราฟเพื่อแสดงความสัมพันธ์ “ผลคูณคาร์ทีเซียนของเซต”
สารละลาย. ดังที่ทราบจากคำนิยาม ผลคูณคาร์ทีเซียนของเซตไม่มีชุดองค์ประกอบที่เรียงลำดับของชุดเดียวกัน นั่นคือในตัวอย่างของเรา คุณไม่สามารถรวมตัวอักษรกรีกกับภาษากรีก และภาษาละตินกับภาษาละตินได้ ข้อเท็จจริงนี้แสดงเป็น กราฟทวิภาคีนั่นคือส่วนหนึ่งที่จุดยอดแบ่งออกเป็นสองส่วนเพื่อให้จุดยอดที่เป็นของส่วนเดียวกันไม่ได้เชื่อมต่อถึงกัน เราได้รับกราฟดังต่อไปนี้:
ตัวอย่างที่ 4ตัวแทนอสังหาริมทรัพย์จ้างผู้จัดการ Igor, Sergey และ Peter วัตถุ O1, O2, O3, O4, O5, O6, O7, O8 ได้รับการซ่อมบำรุง สร้างกราฟเพื่อแสดงความสัมพันธ์ “อิกอร์ทำงานกับวัตถุ O4, O7”, “เซอร์เกย์ทำงานกับวัตถุ O1, O2, O3, O5, O6”, “ปีเตอร์ทำงานกับวัตถุ O8”
สารละลาย. กราฟที่แสดงความสัมพันธ์เหล่านี้จะเป็นแบบสองฝ่ายด้วย เนื่องจากผู้จัดการไม่ได้ทำงานร่วมกับผู้จัดการและวัตถุนั้นไม่ได้ทำงานกับวัตถุนั้น อย่างไรก็ตาม กราฟจะถูกกำหนดทิศทางซึ่งต่างจากตัวอย่างก่อนหน้านี้ ตัวอย่างเช่น ในความเป็นจริง Igor ทำงานกับวัตถุ O4 แต่วัตถุ O4 ไม่ทำงานกับ Igor บ่อยครั้ง เมื่อคุณสมบัติของความสัมพันธ์นั้นชัดเจน ความจำเป็นต้องกำหนดทิศทางไปยังขอบอาจดูเหมือนเป็น "ความโง่เขลาทางคณิตศาสตร์" แต่ถึงกระนั้น และสิ่งนี้เป็นไปตามธรรมชาติที่เข้มงวดของคณิตศาสตร์ หากความสัมพันธ์เป็นแบบด้านเดียว ก็จำเป็นต้องบอกทิศทางไปที่ขอบ ในการใช้งานเชิงสัมพันธ์ ความเข้มงวดนี้จะให้ผลดี เช่น ในโปรแกรมที่ออกแบบมาเพื่อการวางแผน ซึ่งมีการใช้กราฟด้วย และเส้นทางไปตามจุดยอดและขอบจะต้องผ่านไปอย่างเคร่งครัดในทิศทางที่กำหนด ดังนั้นเราจึงได้กราฟสองฝ่ายกำกับต่อไปนี้:
และอีกครั้งกับตัวอย่างที่มีตัวเลข
ตัวอย่างที่ 5มาให้ชุดหนึ่งครับ ค = {2, 3, 5, 6, 15, 18} . สร้างกราฟที่ใช้ความสัมพันธ์ซึ่งกำหนดคู่ของตัวเลขทั้งหมด กและ ขจากหลาย ๆ คน คซึ่งเมื่อหารองค์ประกอบที่สองด้วยองค์ประกอบแรก เราจะได้ผลหารที่เป็นจำนวนเต็มที่มากกว่า 1
สารละลาย. กราฟที่แสดงความสัมพันธ์เหล่านี้จะถูกกำหนดทิศทาง เนื่องจากเงื่อนไขมีการกล่าวถึงองค์ประกอบที่สองและองค์ประกอบแรก กล่าวคือ ขอบจะถูกเปลี่ยนทิศทางจากองค์ประกอบแรกไปยังองค์ประกอบที่สอง จากนี้จะเห็นได้ชัดเจนว่าองค์ประกอบใดเป็นองค์ประกอบแรกและองค์ประกอบใดเป็นองค์ประกอบที่สอง เรายังเพิ่มคำศัพท์บางอย่าง: ขอบที่มุ่งเน้นมักจะเรียกว่าส่วนโค้ง กราฟของเราจะมี 7 ส่วนโค้ง: จ1 = (3, 15) , จ2 = (3, 18) , จ3 = (5, 15) , จ4 = (3, 6) , จ5 = (2, 18) , จ6 = (6, 18) , จ7 = (2, 6) . ในตัวอย่างนี้ ขอบ (ส่วนโค้ง) ของกราฟเป็นเพียงตัวเลข แต่หมายเลขซีเรียลไม่ใช่สิ่งเดียวที่สามารถกำหนดให้กับส่วนโค้งได้ ส่วนโค้งยังสามารถกำหนดมาตราส่วนได้ เช่น ต้นทุนในการส่งสินค้าจากจุดหนึ่งไปยังอีกจุดหนึ่ง แต่เราจะมาทำความคุ้นเคยกับตุ้มน้ำหนักส่วนโค้งในภายหลังและในรายละเอียดเพิ่มเติม ดังนั้นเราจึงได้กราฟกำกับดังต่อไปนี้:
ดังที่เราทราบแล้วจากส่วนเบื้องต้นทางทฤษฎี ทฤษฎีกราฟไม่ได้คำนึงถึงลักษณะเฉพาะของเซต และด้วยความช่วยเหลือของกราฟเดียวกัน จึงสามารถกำหนดความสัมพันธ์ของเซตที่มีเนื้อหาต่างกันมากได้ นั่นคือเนื้อหานี้สามารถสรุปได้เมื่อสร้างแบบจำลองงาน เรามาดูตัวอย่างที่แสดงให้เห็นคุณสมบัติอันน่าทึ่งของทฤษฎีกราฟกัน
ตัวอย่างที่ 6บนกระดานหมากรุกขนาด 3 X 3 จะมีอัศวินขาว 2 คนและอัศวินดำ 2 คนวางอยู่ดังแสดงในรูปด้านล่าง
เป็นไปได้ไหมที่จะย้ายอัศวินไปยังสถานะที่แสดงในรูปต่อไปนี้ โดยลืมว่าสองชิ้นไม่สามารถอยู่บนจัตุรัสเดียวกันได้
สารละลาย. ในกราฟที่สร้างขึ้น คู่จุดยอดจะเชื่อมต่อกันด้วยความสัมพันธ์ "การเคลื่อนไหวของอัศวิน" นั่นคือจุดยอดหนึ่งคือจุดยอดที่อัศวินจากไปและอีกจุดหนึ่งคือจุดยอดที่มาถึงและเซลล์ตรงกลางของตัวอักษร "r" จะอยู่นอกความสัมพันธ์นี้ เราได้รับกราฟดังต่อไปนี้:
แต่การออกแบบกลับกลายเป็นเรื่องยุ่งยาก มองเห็นเซลล์ของกระดานหมากรุกได้ และขอบกราฟหลายอันตัดกัน เป็นไปได้ไหมที่จะสรุปจากรูปลักษณ์ทางกายภาพของกระดานหมากรุกและจินตนาการถึงความสัมพันธ์ให้ง่ายขึ้น? ปรากฎว่ามันเป็นไปได้ ในกราฟใหม่ จุดยอดที่อยู่ใกล้เคียงจะเป็นจุดเชื่อมต่อกันด้วยความสัมพันธ์แบบ "การเคลื่อนไหวของอัศวิน" ไม่ใช่จุดยอดที่อยู่ติดกันบนกระดานหมากรุก (รูปด้านล่าง)
ตอนนี้เห็นได้ง่ายว่าคำตอบสำหรับคำถามนี้เป็นเชิงลบ ในสถานะเริ่มต้นไม่มีอัศวินดำอยู่ระหว่างอัศวินขาวสองคน แต่ในสถานะสุดท้ายจะต้องมีอัศวินดำคนนี้ ขอบของกราฟถูกวางไว้เพื่อไม่ให้อัศวินสองคนที่อยู่ติดกันไม่สามารถกระโดดข้ามกันได้
ตัวอย่างที่ 7ปัญหาเรื่องหมาป่า แพะ และกะหล่ำปลี บนฝั่งแม่น้ำด้านหนึ่งมีชายคนหนึ่ง (H) เรือ หมาป่า (V) แพะ (Kz) และกะหล่ำปลี (Kp) บุคคลและวัตถุที่ขนส่งได้ไม่เกินหนึ่งรายการสามารถอยู่ในเรือได้ในเวลาเดียวกัน บุคคลจะต้องขนส่งสิ่งของทั้งหมดไปยังอีกด้านหนึ่งโดยสังเกตสภาพ: จะต้องไม่ปล่อยหมาป่าไว้กับแพะและแพะกับกะหล่ำปลีโดยไม่มีใครดูแล
สารละลาย. ในกราฟที่สร้างขึ้น จุดยอดคือการกำหนดค่า และขอบคือความสัมพันธ์ "การเชื่อมต่อด้วยการนั่งเรือเที่ยวเดียว" ระหว่างการกำหนดค่า การกำหนดค่าหมายถึงการจัดเรียงออบเจ็กต์บนฝั่งเดิมและฝั่งตรงข้าม แต่ละการกำหนดค่าจะแสดงเป็น ( ก|บี) , ที่ไหน ก- วัตถุที่ตั้งอยู่บนชายฝั่งเดิมและ บี- วัตถุที่อยู่ฝั่งตรงข้าม การกำหนดค่าเริ่มต้นจึงเป็น - (PMCpKz| ) . เช่น หลังจากขนแพะไปอีกฝั่งแล้ว โครงร่างจะเป็นดังนี้ (วีเคพี|ชเคซ) . การกำหนดค่าสุดท้ายจะเป็นเสมอ ( |PMCpKz) . ตอนนี้เราสามารถสร้างกราฟได้แล้ว โดยรู้แล้วว่าจุดยอดและขอบหมายถึงอะไร:
ลองวางจุดยอดของกราฟเพื่อให้ขอบไม่ตัดกัน และจุดยอดที่อยู่ติดกันคือจุดยอดที่เชื่อมโยงกันด้วยความสัมพันธ์บนกราฟ จากนั้นการดูความสัมพันธ์จะง่ายขึ้นมาก (หากต้องการขยายภาพให้คลิกซ้ายที่ภาพ):
ดังที่เราเห็น มีเส้นทางต่อเนื่องที่แตกต่างกันสองเส้นทางตั้งแต่การกำหนดค่าเริ่มต้นไปจนถึงเส้นทางสุดท้าย ดังนั้น ปัญหาจึงมีวิธีแก้ไขที่แตกต่างกันสองวิธี (และทั้งสองวิธีถูกต้อง)
ทฤษฎีกราฟและปัญหาประยุกต์สมัยใหม่ที่สำคัญที่สุด
ตามทฤษฎีกราฟ วิธีการต่างๆ ได้รับการพัฒนาขึ้นเพื่อแก้ไขปัญหาประยุกต์ซึ่งมีการสร้างแบบจำลองระบบที่ซับซ้อนมากในรูปแบบของกราฟ ในโมเดลเหล่านี้ โหนดประกอบด้วยส่วนประกอบแต่ละส่วน และขอบแสดงถึงการเชื่อมต่อระหว่างส่วนประกอบต่างๆ โดยทั่วไปแล้ว กราฟถ่วงน้ำหนักจะใช้เพื่อสร้างแบบจำลองเครือข่ายการขนส่ง ระบบคิว และการวางแผนเครือข่าย เราได้พูดคุยเกี่ยวกับสิ่งเหล่านี้แล้วนี่คือกราฟที่กำหนดน้ำหนักให้กับส่วนโค้ง
ตัวอย่างเช่น มีการใช้กราฟต้นไม้เพื่อสร้าง ต้นไม้การตัดสินใจ(ให้บริการสำหรับการวิเคราะห์ความเสี่ยง การวิเคราะห์กำไรและขาดทุนที่เป็นไปได้ภายใต้เงื่อนไขของความไม่แน่นอน) โดยใช้ทฤษฎีกราฟพัฒนาและ แบบจำลองทางคณิตศาสตร์อื่นๆ อีกมากมายเพื่อแก้ไขปัญหาเฉพาะสาขาวิชา
กราฟและปัญหาการไหล
การกำหนดปัญหา มีระบบท่อน้ำแสดงด้วยกราฟในรูปด้านล่าง
แต่ละส่วนโค้งของกราฟแสดงถึงท่อ ตัวเลขที่อยู่เหนือส่วนโค้ง (สเกล) คือความจุของท่อ โหนดเป็นสถานที่ที่มีการเชื่อมต่อท่อ น้ำไหลผ่านท่อไปในทิศทางเดียวเท่านั้น ปม ส- แหล่งน้ำโหนด ต- คลังสินค้า. จำเป็นต้องเพิ่มปริมาณน้ำที่ไหลจากแหล่งไปยังท่อระบายน้ำให้ได้มากที่สุด
เพื่อแก้ไขปัญหาการไหล คุณสามารถใช้วิธี Ford-Fulkerson แนวคิดของวิธีการ: การค้นหาการไหลสูงสุดจะดำเนินการเป็นขั้นตอน ที่จุดเริ่มต้นของอัลกอริทึม โฟลว์จะถูกตั้งค่าเป็นศูนย์ ในแต่ละขั้นตอนต่อมา ค่าของการไหลจะเพิ่มขึ้น ซึ่งเป็นเส้นทางที่เสริมกันซึ่งไหลเพิ่มเติมมาถึง ขั้นตอนเหล่านี้จะถูกทำซ้ำตราบเท่าที่มีเส้นทางเพิ่มเติมอยู่ ปัญหานี้ได้ถูกนำไปใช้กับระบบแบบกระจายต่างๆ อย่างประสบความสำเร็จ: ระบบจ่ายไฟ, เครือข่ายการสื่อสาร, ระบบรางรถไฟ และอื่นๆ
กราฟและการวางแผนเครือข่าย
ในการวางแผนปัญหาของกระบวนการที่ซับซ้อนซึ่งประกอบด้วยงานจำนวนมาก ซึ่งบางงานดำเนินการแบบคู่ขนานและบางงานตามลำดับ กราฟถ่วงน้ำหนักหรือที่เรียกว่าเครือข่าย PERT ถูกนำมาใช้กันอย่างแพร่หลาย
PERT - เทคนิคการประเมินและทบทวนโปรแกรม (โครงการ) - เทคนิคในการประเมินและวิเคราะห์โปรแกรม (โครงการ) ซึ่งใช้ในการบริหารโครงการ
เครือข่าย PERT เป็นกราฟกำกับแบบไม่วนแบบถ่วงน้ำหนัก โดยแต่ละส่วนโค้งแสดงถึงงาน (การกระทำ การปฏิบัติงาน) และน้ำหนักของส่วนโค้งคือเวลาที่ต้องใช้ในการทำงานให้เสร็จสิ้น
หากมีส่วนโค้งในเครือข่าย ( ก, ข) และ ( ข, ค) จากนั้นงานที่แสดงโดยส่วนโค้ง ( ก, ข) จะต้องเสร็จสิ้นก่อนงานที่แสดงโดยส่วนโค้ง ( ข, ค) . แต่ละจุดยอด ( โวลต์ฉัน)แสดงถึงช่วงเวลาซึ่งงานทั้งหมดกำหนดโดยส่วนโค้งที่สิ้นสุดที่จุดยอด ( โวลต์ฉัน).
ในคอลัมน์เช่นนี้:
- จุดยอดหนึ่งซึ่งไม่มีรุ่นก่อน กำหนดเวลาเริ่มต้นของการทำงาน
- จุดยอดหนึ่งซึ่งไม่มีผู้ติดตามนั้นสอดคล้องกับช่วงเวลาที่ชุดงานเสร็จสมบูรณ์
เส้นทางที่มีความยาวสูงสุดระหว่างจุดยอดเหล่านี้ของกราฟ (ตั้งแต่ต้นจนจบกระบวนการทำงาน) เรียกว่าเส้นทางวิกฤติ เพื่อลดเวลาที่ต้องใช้ในการทำงานที่ซับซ้อนทั้งหมดให้เสร็จสิ้น มีความจำเป็นต้องหางานที่อยู่บนเส้นทางวิกฤติและลดระยะเวลาลงโดยการดึงดูดนักแสดง กลไก และเทคโนโลยีใหม่เพิ่มเติม
บล็อกทั้งหมด "ทฤษฎีกราฟ"
เนื้อหาจากวิกิพีเดีย – สารานุกรมเสรี
ทฤษฎีกราฟ- สาขาวิชาคณิตศาสตร์แบบไม่ต่อเนื่องที่ศึกษาคุณสมบัติของกราฟ โดยทั่วไปแล้ว กราฟจะแสดงเป็นเซต ยอดเขา(โหนด) เชื่อมต่อแล้ว ซี่โครง. ในคำจำกัดความที่เข้มงวด คู่ของเซตดังกล่าวเรียกว่ากราฟ , ที่ไหน เป็นสับเซตของเซตนับได้ใดๆ และ - เซตย่อย .
ทฤษฎีกราฟค้นหาการประยุกต์ใช้งาน เช่น ในระบบสารสนเทศทางภูมิศาสตร์ (GIS) บ้าน โครงสร้าง บล็อก ฯลฯ ที่มีอยู่หรือที่ออกแบบใหม่จะถือเป็นจุดยอด ส่วนถนน โครงข่ายสาธารณูปโภค สายไฟ ฯลฯ ที่เชื่อมต่อกันจะถือเป็นจุดยอด การใช้การคำนวณต่างๆ ที่ดำเนินการกับกราฟดังกล่าว ช่วยให้สามารถค้นหาเส้นทางเลี่ยงที่สั้นที่สุดหรือร้านขายของชำที่ใกล้ที่สุด หรือวางแผนเส้นทางที่เหมาะสมที่สุดได้
ทฤษฎีกราฟประกอบด้วยปัญหาที่ยังไม่ได้รับการแก้ไขจำนวนมากและสมมติฐานที่ยังไม่ได้รับการพิสูจน์
ประวัติความเป็นมาของทฤษฎีกราฟ
Leonard Euler ถือเป็นผู้ก่อตั้งทฤษฎีกราฟ ในปี ค.ศ. 1736 เขาได้กำหนดและเสนอวิธีแก้ปัญหาของสะพานทั้งเจ็ดแห่งเคอนิกสแบร์กในจดหมายฉบับหนึ่งของเขา ซึ่งต่อมาได้กลายเป็นหนึ่งในปัญหาคลาสสิกของทฤษฎีกราฟ
ศัพท์เฉพาะทางทฤษฎีกราฟ
การแสดงกราฟบนเครื่องบิน
เมื่อแสดงกราฟในภาพวาด ระบบสัญลักษณ์ต่อไปนี้มักใช้บ่อยที่สุด: จุดยอดของกราฟจะแสดงเป็นจุด หรือเมื่อระบุความหมายของจุดยอด สี่เหลี่ยม วงรี ฯลฯ โดยที่ความหมายของจุดยอดถูกเปิดเผยภายใน รูป (กราฟผังงานของอัลกอริทึม) หากมีขอบระหว่างจุดยอด จุดที่เกี่ยวข้อง (รูปร่าง) จะเชื่อมต่อกันด้วยเส้นหรือส่วนโค้ง ในกรณีของกราฟที่มีทิศทาง ส่วนโค้งจะถูกแทนที่ด้วยลูกศร หรือมีการระบุทิศทางของขอบอย่างชัดเจน บางครั้งคำจารึกอธิบายจะถูกวางไว้ข้างขอบ ซึ่งเผยให้เห็นความหมายของขอบ ตัวอย่างเช่น ในกราฟการเปลี่ยนผ่านของเครื่องจักรที่มีสถานะจำกัด มีกราฟระนาบและกราฟไม่มีระนาบ กราฟระนาบคือกราฟที่สามารถแสดงเป็นรูปภาพ (ระนาบ) โดยไม่มีขอบตัดกัน (กราฟที่ง่ายที่สุดคือรูปสามเหลี่ยมหรือจุดยอดที่เชื่อมต่อกัน) มิฉะนั้นกราฟจะไม่อยู่ในระนาบ ในกรณีที่กราฟไม่มีวงจร (มีอย่างน้อย 1 เส้นทาง ครั้งหนึ่งการเคลื่อนตัวของขอบและจุดยอดโดยกลับไปสู่จุดยอดเดิม) โดยทั่วไปเรียกว่า "ต้นไม้" ต้นไม้ประเภทที่สำคัญในทฤษฎีกราฟคือ ต้นไม้ไบนารี ซึ่งแต่ละจุดยอดมีขอบขาเข้าหนึ่งอันและปลายขาออกสองอันพอดี หรือมีขอบเขตจำกัด - ไม่มีขอบขาออกและมีจุดยอดรากหนึ่งอันโดยไม่มีขอบขาเข้า
ไม่ควรสับสนระหว่างรูปภาพของกราฟกับกราฟ (โครงสร้างนามธรรม) เนื่องจากสามารถเชื่อมโยงการแสดงกราฟิกได้มากกว่าหนึ่งรายการกับกราฟเดียว รูปภาพนี้มีวัตถุประสงค์เพียงเพื่อแสดงว่าจุดยอดคู่ใดเชื่อมต่อกันด้วยขอบ และคู่ใดไม่ได้เชื่อมต่อกัน ในทางปฏิบัติมักจะเป็นเรื่องยากที่จะตอบคำถามว่าภาพสองภาพเป็นแบบจำลองของกราฟเดียวกันหรือไม่ (กล่าวอีกนัยหนึ่งว่ากราฟที่สอดคล้องกับภาพนั้นเป็นแบบมอร์ฟิกหรือไม่) ภาพบางภาพอาจให้ความชัดเจนมากกว่าภาพอื่นๆ ทั้งนี้ขึ้นอยู่กับงาน
ปัญหาบางประการของทฤษฎีกราฟ
- ปัญหาสะพานทั้งเจ็ดแห่งเคอนิกส์แบร์กเป็นหนึ่งในผลลัพธ์แรกๆ ในทฤษฎีกราฟ ซึ่งตีพิมพ์โดยออยเลอร์ใน
- ปัญหาสี่สีถูกกำหนดขึ้นในปี พ.ศ. 2395 แต่ได้รับการพิสูจน์ที่ไม่คลาสสิกในปี พ.ศ. 2519 เท่านั้น (4 สีเพียงพอสำหรับแผนที่บนทรงกลม (เครื่องบิน))
- ปัญหาพนักงานขายที่กำลังเดินทางเป็นหนึ่งในปัญหา NP-complete ที่มีชื่อเสียงที่สุดปัญหาหนึ่ง
- ปัญหาก๊กเป็นอีกปัญหา NP-สมบูรณ์
- การหาต้นไม้ที่ขยายน้อยที่สุด
- กราฟมอร์ฟฟิซึม - เป็นไปได้ไหมที่จะได้รับอีกอันหนึ่งโดยการเปลี่ยนหมายเลขจุดยอดของกราฟหนึ่งใหม่?
- Planarity ของกราฟ - เป็นไปได้หรือไม่ที่จะพรรณนากราฟบนระนาบโดยไม่มีจุดตัดของขอบ (หรือมีจำนวนเลเยอร์ขั้นต่ำซึ่งใช้ในการติดตามการเชื่อมต่อระหว่างองค์ประกอบของแผงวงจรพิมพ์หรือไมโครวงจร)
การประยุกต์ทฤษฎีกราฟ
ดูสิ่งนี้ด้วย
เขียนบทวิจารณ์เกี่ยวกับบทความ "ทฤษฎีกราฟ"
หมายเหตุ
วรรณกรรม
- ดิสเทล อาร์.ทฤษฎีกราฟทรานส์ จากอังกฤษ - โนโวซีบีสค์: สำนักพิมพ์ของสถาบันคณิตศาสตร์, 2545 - 336 หน้า ไอ 5-86134-101-X.
- ดีสเทล อาร์.. - NY: Springer-Verlag, 2005. - หน้า 422.
- บาซาเกอร์ อาร์., ซาตี ที.
- Belov V.V., Vorobiev E.M., Shatalov V.E.ทฤษฎีกราฟ - ม.: สูงกว่า. โรงเรียน พ.ศ. 2519 - หน้า 392
- เบิร์ก เค.
- Emelichev V. A. , Melnikov O. I. , Sarvanov V. I. , Tyshkevich R. I.บรรยายเรื่องทฤษฎีกราฟ อ.: Nauka, 1990. 384 หน้า (แก้ไข 2, แก้ไข M.: URSS, 2009. 392 p.)
- ซิคอฟ เอ.เอ.. - อ.: “หนังสือมหาวิทยาลัย”, 2547. - หน้า 664. - ISBN 5-9502-0057-8.(อ.: Nauka, 1987. 383c.)
- การประยุกต์ทางเคมีของโทโพโลยีและทฤษฎีกราฟ เอ็ด อาร์ คิง. ต่อ. จากอังกฤษ อ.: มีร์, 1987.
- เคอร์ซานอฟ เอ็ม. เอ็น.กราฟในเมเปิล อ.: Fizmatlit, 2550. 168 หน้า vuz.exponenta.ru/PDF/book/GrMaple.pdf eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
- คริสโตฟิเดส เอ็น.
- Cormen TH และคณะส่วนที่ 6 อัลกอริทึมสำหรับการทำงานกับกราฟ // อัลกอริทึม: การสร้างและการวิเคราะห์ = อัลกอริทึมเบื้องต้น - ฉบับที่ 2 - อ.: วิลเลียมส์, 2549. - หน้า 1296. - ISBN 0-07-013151-1.
- โอเรโอ. - ฉบับที่ 2 - อ.: วิทยาศาสตร์, 2523. - หน้า 336.
- Salii V. N. Bogomolov A. M.. - อ.: ฟิสิกส์และวรรณคดีคณิตศาสตร์, 2540. - ISBN 5-02-015033-9.
- สวามี เอ็ม., ทูลาสิรามัน เค.
- ทัตต์ ดับเบิลยู.
- วิลสัน อาร์.
- ฮาราริ เอฟ.. - อ.: มีร์, 2516.(Ed. 3, M.: KomKniga, 2006. - 296 p.)
- ฮารารี เอฟ. พาลเมอร์ อี.. - โลก, 1977.
- เซอร์เกย์ เมลนิคอฟ// วิทยาศาสตร์กับชีวิต . - พ.ศ. 2539. - ฉบับที่. 3. - หน้า 144-145.บทความนี้เกี่ยวกับเกมกราฟ Sim ที่คิดค้นโดย Gustav Simmons
ลิงค์
- : โปรแกรมที่ให้เครื่องมือและวิธีการมากมายแก่ผู้ใช้ในการแสดงภาพและค้นหาข้อมูลในกราฟ
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ข้อความที่ตัดตอนมาจากทฤษฎีกราฟ
แต่ก่อนที่เขาจะพูดจบเจ้าชายอังเดรรู้สึกน้ำตาแห่งความอับอายและความโกรธที่ไหลอยู่ในลำคอก็กระโดดลงจากหลังม้าแล้ววิ่งไปที่ธง- พวกคุณเอาเลย! – เขาตะโกนอย่างเด็ก ๆ
"นี่ไง!" คิดว่าเจ้าชาย Andrei คว้าเสาธงและได้ยินเสียงนกหวีดของกระสุนอย่างยินดีซึ่งเห็นได้ชัดว่ามุ่งเป้าไปที่เขาโดยเฉพาะ ทหารหลายคนล้มลง
- ไชโย! - เจ้าชาย Andrei ตะโกนโดยแทบไม่ถือธงในมือของเขาและวิ่งไปข้างหน้าด้วยความมั่นใจว่าทั้งกองพันจะวิ่งตามเขาไป
แท้จริงแล้วเขาวิ่งเพียงไม่กี่ก้าวเท่านั้น ทหารคนหนึ่งออกเดินทาง จากนั้นก็อีกคนหนึ่ง และทั้งกองทหารก็ตะโกนว่า "ไชโย!" วิ่งไปข้างหน้าและทันเขา นายทหารชั้นประทวนของกองพันวิ่งขึ้นไปหยิบธงซึ่งสั่นจากน้ำหนักในมือของเจ้าชาย Andrei แต่ถูกสังหารทันที เจ้าชายอังเดรคว้าธงอีกครั้งแล้วลากไปที่เสาแล้วหนีไปพร้อมกับกองพัน ข้างหน้าเขาเห็นทหารปืนใหญ่ของเรา บางคนต่อสู้ บางคนละทิ้งปืนใหญ่และวิ่งเข้าหาเขา เขายังเห็นทหารราบฝรั่งเศสที่คว้าม้าปืนใหญ่และหันปืน เจ้าชาย Andrei และกองพันของเขาอยู่ห่างจากปืนไปแล้ว 20 ก้าว เขาได้ยินเสียงกระสุนปืนดังอย่างต่อเนื่องเหนือเขา และทหารก็ส่งเสียงครวญครางอยู่ตลอดเวลาและล้มลงไปทางขวาและซ้ายของเขา แต่เขาไม่ได้มองดูพวกเขา เขามองเฉพาะสิ่งที่เกิดขึ้นตรงหน้าเขาเท่านั้น - บนแบตเตอรี่ เขาเห็นชัดเจนว่าร่างหนึ่งของทหารปืนใหญ่ผมแดงที่มีชาโกะเคาะอยู่ด้านหนึ่งดึงธงด้านหนึ่ง ในขณะที่ทหารฝรั่งเศสกำลังดึงธงเข้าหาตัวเขาเองในอีกด้านหนึ่ง เจ้าชายอันเดรย์มองเห็นความสับสนและสีหน้าขมขื่นบนใบหน้าของทั้งสองคนอย่างชัดเจนซึ่งเห็นได้ชัดว่าไม่เข้าใจสิ่งที่พวกเขากำลังทำอยู่
"พวกเขากำลังทำอะไร? - เจ้าชาย Andrei คิดเมื่อมองดูพวกเขา: - ทำไมปืนใหญ่ผมแดงถึงไม่วิ่งเมื่อเขาไม่มีอาวุธ? ทำไมชาวฝรั่งเศสไม่แทงเขา? ก่อนที่เขาจะไปถึงตัวเขา ชาวฝรั่งเศสจะจำปืนและแทงเขาจนตาย”
แท้จริงแล้วชาวฝรั่งเศสอีกคนหนึ่งซึ่งถือปืนได้เปรียบวิ่งไปหานักสู้และต้องตัดสินชะตากรรมของปืนใหญ่ผมสีแดงซึ่งยังไม่เข้าใจว่าอะไรรอเขาอยู่และดึงธงออกมาอย่างมีชัย แต่เจ้าชายอังเดรไม่เห็นว่ามันจะจบลงอย่างไร ดูเหมือนว่าทหารคนหนึ่งที่อยู่ใกล้ ๆ ราวกับกำลังเหวี่ยงไม้อันทรงพลังมากระแทกหัวเขา มันเจ็บเล็กน้อย และที่สำคัญที่สุด มันไม่เป็นที่พอใจ เพราะความเจ็บปวดนี้สร้างความบันเทิงให้เขาและขัดขวางไม่ให้เขามองเห็นสิ่งที่เขากำลังมองอยู่
"นี่คืออะไร? ฉันกำลังล้ม? ขาของฉันกำลังหลีกทาง” เขาคิดแล้วล้มลงบนหลังของเขา เขาลืมตาขึ้นโดยหวังว่าจะเห็นว่าการต่อสู้ระหว่างฝรั่งเศสกับทหารปืนใหญ่จบลงอย่างไร และอยากรู้ว่าทหารปืนใหญ่ผมแดงถูกฆ่าหรือไม่ ไม่ว่าปืนจะถูกยึดไปหรือช่วยชีวิตไว้ก็ตาม แต่เขาไม่เห็นอะไรเลย ไม่มีอะไรอยู่เหนือเขาอีกต่อไปแล้ว ยกเว้นท้องฟ้า ท้องฟ้าสูง ไม่ชัดเจน แต่ก็ยังสูงอย่างล้นหลาม มีเมฆสีเทาค่อยๆ คืบคลานไปทั่ว “ เงียบสงบและเคร่งขรึมมากขนาดไหนไม่เหมือนที่ฉันวิ่งเลย” เจ้าชายอังเดรคิด“ ไม่เหมือนที่เราวิ่งตะโกนและต่อสู้ มันไม่เหมือนกับการที่ชาวฝรั่งเศสและทหารปืนใหญ่ดึงธงของกันและกันด้วยใบหน้าที่ขมขื่นและหวาดกลัว - ไม่เหมือนการที่เมฆคลานข้ามท้องฟ้าอันสูงส่งที่ไม่มีที่สิ้นสุดนี้เลย ทำไมฉันไม่เคยเห็นท้องฟ้าสูงขนาดนี้มาก่อน? และฉันรู้สึกดีใจมากที่ในที่สุดฉันก็จำเขาได้ ใช่! ทุกอย่างว่างเปล่า ทุกอย่างเป็นเพียงการหลอกลวง ยกเว้นท้องฟ้าอันไม่มีที่สิ้นสุดนี้ ไม่มีอะไร ไม่มีอะไรนอกจากเขา แต่ถึงแม้จะไม่มีก็ไม่มีอะไรนอกจากความเงียบและสงบ และขอบคุณพระเจ้า!…”
ที่ปีกขวาของ Bagration เวลา 9 โมงเช้าธุรกิจยังไม่เริ่ม ไม่ต้องการที่จะยอมรับข้อเรียกร้องของ Dolgorukov ในการเริ่มต้นธุรกิจและต้องการเบี่ยงเบนความรับผิดชอบจากตัวเขาเอง เจ้าชาย Bagration แนะนำให้ส่ง Dolgorukov ไปถามผู้บัญชาการทหารสูงสุดเกี่ยวกับเรื่องนี้ Bagration รู้ดีว่าเนื่องจากระยะห่างเกือบ 10 คำที่แยกปีกด้านหนึ่งออกจากอีกปีกหนึ่งหากปีกที่ส่งมาไม่ถูกฆ่า (ซึ่งเป็นไปได้มาก) และแม้ว่าเขาจะพบผู้บัญชาการทหารสูงสุดซึ่งยากมากก็ตาม ผู้ส่งไปคงไม่มีเวลากลับมาก่อนค่ำ
Bagration มองไปรอบ ๆ กลุ่มผู้ติดตามของเขาด้วยดวงตากลมโตไร้อารมณ์และนอนไม่หลับและใบหน้าเด็ก ๆ ของ Rostov ซึ่งแข็งตัวด้วยความตื่นเต้นและความหวังโดยไม่ได้ตั้งใจเป็นคนแรกที่สบตาเขา เขาส่งมา.
- จะเป็นอย่างไรหากข้าพเจ้าเข้าเฝ้าฝ่าพระบาทต่อหน้าผู้บัญชาการทหารสูงสุด ฯพณฯ ? - Rostov กล่าวโดยจับมือของเขาไว้ที่กระบังหน้า
“ คุณสามารถมอบมันให้กับฝ่าบาทได้” Dolgorukov กล่าวและขัดจังหวะ Bagration อย่างเร่งรีบ
หลังจากได้รับการปล่อยตัวจากโซ่ Rostov ก็นอนหลับได้หลายชั่วโมงก่อนเช้าและรู้สึกร่าเริง กล้าหาญ เด็ดเดี่ยวด้วยความยืดหยุ่นของการเคลื่อนไหว ความมั่นใจในความสุขของเขา และในอารมณ์ที่ทุกสิ่งดูเหมือนง่าย สนุก และเป็นไปได้
ความปรารถนาทั้งหมดของเขาเป็นจริงในเช้าวันนั้น มีการต่อสู้ทั่วไปเขาเข้าร่วมด้วย นอกจากนี้เขายังเป็นระเบียบเรียบร้อยภายใต้แม่ทัพที่กล้าหาญที่สุด ยิ่งกว่านั้นเขากำลังเดินทางไปทำธุระที่ Kutuzov และอาจถึงตัวอธิปไตยด้วยซ้ำ เช้าสดใส ม้าข้างใต้เขาสบายดี วิญญาณของเขามีความสุขและมีความสุข เมื่อได้รับคำสั่งแล้ว เขาก็ลงจากม้าแล้วควบม้าไปตามแถว ในตอนแรกเขาขี่ม้าไปตามแนวทหารของ Bagration ซึ่งยังไม่ได้ออกปฏิบัติการและยืนนิ่งอยู่ จากนั้นเขาก็เข้าไปในพื้นที่ที่ถูกครอบครองโดยทหารม้าของ Uvarov และที่นี่เขาสังเกตเห็นการเคลื่อนไหวและสัญญาณของการเตรียมการสำหรับคดีนี้แล้ว เมื่อผ่านกองทหารม้าของ Uvarov เขาก็ได้ยินเสียงปืนใหญ่และเสียงปืนที่อยู่ข้างหน้าเขาอย่างชัดเจน การยิงรุนแรงขึ้น
ในอากาศบริสุทธิ์ยามเช้าไม่มีอีกต่อไปเหมือนเมื่อก่อนในช่วงเวลาที่ไม่ปกติอีกต่อไปสอง, สามนัดจากนั้นก็หนึ่งหรือสองนัดปืนและตามเนินเขาของภูเขาด้านหน้า Pratzen เสียงปืนดังขึ้นถูกขัดจังหวะ ด้วยการยิงปืนบ่อยครั้งจนบางครั้งปืนใหญ่หลายนัดไม่ได้แยกออกจากกันอีกต่อไป แต่รวมเข้าด้วยกันเป็นเสียงคำรามร่วมกัน
เห็นได้ชัดว่าควันปืนดูเหมือนวิ่งไปตามเนินเขาไล่ตามกันและควันปืนหมุนวนเบลอและรวมเข้าด้วยกันอย่างไร จากความแวววาวของดาบปลายปืนระหว่างควัน มองเห็นฝูงทหารราบที่กำลังเคลื่อนไหวและแถบปืนใหญ่แคบๆ พร้อมกล่องสีเขียว
รอสตอฟหยุดม้าบนเนินเขาสักครู่เพื่อตรวจสอบสิ่งที่เกิดขึ้น แต่ไม่ว่าเขาจะดึงความสนใจของเขาหนักแค่ไหน เขาก็ไม่สามารถเข้าใจหรือคาดเดาสิ่งที่เกิดขึ้นได้ บางคนกำลังเคลื่อนไหวไปที่นั่นท่ามกลางควัน ผืนผ้าใบของกองทหารบางส่วนเคลื่อนไหวทั้งด้านหน้าและด้านหลัง แต่ทำไม? WHO? ที่ไหน? มันเป็นไปไม่ได้ที่จะเข้าใจ ภาพและเสียงเหล่านี้ไม่เพียงแต่กระตุ้นความรู้สึกโง่เขลาหรือขี้อายในตัวเขาเท่านั้น แต่ยังให้พลังงานและความมุ่งมั่นแก่เขาอีกด้วย
“เอาล่ะ ให้มันมากกว่านี้!” - เขาหันไปหาเสียงเหล่านี้ในใจและเริ่มควบม้าไปตามแนวอีกครั้งโดยเจาะลึกเข้าไปในพื้นที่ของกองทหารที่เริ่มปฏิบัติการแล้ว
“ฉันไม่รู้ว่ามันจะอยู่ที่นั่นได้อย่างไร แต่ทุกอย่างจะเรียบร้อย!” รอสตอฟคิดว่า
หลังจากผ่านกองทหารออสเตรียบางส่วนแล้ว Rostov สังเกตเห็นว่าส่วนถัดไปของแนว (คือผู้พิทักษ์) ได้เข้าปฏิบัติการแล้ว
“ยิ่งดี! ฉันจะลองดูให้ละเอียดกว่านี้” เขาคิด
เขาขับรถไปเกือบแนวหน้า ทหารม้าหลายคนควบม้าเข้ามาหาเขา คนเหล่านี้คือทวนชีวิตของเราที่กลับมาจากการโจมตีในตำแหน่งที่ไม่เป็นระเบียบ Rostov ผ่านพวกเขาไปโดยไม่ได้ตั้งใจสังเกตเห็นหนึ่งในนั้นเต็มไปด้วยเลือดและควบม้าต่อไป
“ฉันไม่สนใจเรื่องนี้!” เขาคิดว่า. ก่อนที่เขาจะขี่ม้าไปหลายร้อยขั้นหลังจากนั้น ไปทางซ้ายตลอดความยาวของสนาม ทหารม้าจำนวนมากบนหลังม้าสีดำ ในชุดเครื่องแบบสีขาวแวววาวก็ปรากฏตัวขึ้น วิ่งเหยาะ ๆ ตรงมาหาเขา รอสตอฟควบม้าของเขาเต็มกำลังเพื่อหลีกทางให้ทหารม้าเหล่านี้ และเขาคงจะหนีไปจากพวกเขาได้ถ้าพวกเขายังคงเดินแบบเดิม แต่พวกเขาก็เร่งความเร็วขึ้นเรื่อยๆ จนม้าบางตัวควบม้าไปแล้ว รอสตอฟได้ยินเสียงพวกเขากระทืบและเสียงกระทบอาวุธของพวกเขาชัดเจนมากขึ้นเรื่อยๆ และม้า ร่าง และแม้แต่ใบหน้าของพวกเขาก็มองเห็นได้ชัดเจนยิ่งขึ้น คนเหล่านี้คือทหารม้าของเรา ที่กำลังเข้าโจมตีทหารม้าฝรั่งเศสซึ่งกำลังเคลื่อนตัวเข้าหาพวกเขา
ทหารม้าก็ควบม้าไปแต่ยังคงจับม้าไว้ Rostov เห็นหน้าพวกเขาแล้วและได้ยินคำสั่ง: "เดินทัพ, เดินขบวน!" พูดโดยเจ้าหน้าที่ที่ปล่อยม้าเลือดของเขาด้วยความเร็วเต็มพิกัด รอสตอฟกลัวว่าจะถูกบดขยี้หรือล่อให้โจมตีฝรั่งเศส จึงควบม้าไปด้านหน้าให้เร็วที่สุดเท่าที่จะทำได้ และยังไม่สามารถผ่านพวกมันไปได้
ทหารม้าคนสุดท้ายซึ่งเป็นชายร่างใหญ่มีรอยย่นขมวดคิ้วด้วยความโกรธเมื่อเห็นรอสตอฟอยู่ข้างหน้าซึ่งเขาจะชนกันอย่างหลีกเลี่ยงไม่ได้ ทหารม้าคนนี้คงจะล้ม Rostov และชาวเบดูอินของเขาลงอย่างแน่นอน (Rostov เองก็ดูตัวเล็กและอ่อนแอมากเมื่อเทียบกับคนและม้าตัวใหญ่เหล่านี้) หากเขาไม่คิดที่จะเหวี่ยงแส้เข้าตาม้าของทหารม้า ม้าสีดำหนักห้านิ้วเบือนหน้าหนีโดยวางหูลง แต่ทหารม้าที่มีรอยเจาะแทงก็แทงเดือยอันใหญ่เข้าที่ข้างตัวเธอ และม้าก็โบกหางและเหยียดคอแล้วรีบเร่งเร็วขึ้นอีก ทันทีที่ทหารม้าผ่าน Rostov เขาก็ได้ยินพวกเขาตะโกน: "ไชโย!" และเมื่อมองย้อนกลับไปเขาเห็นว่าแนวหน้าของพวกเขาปะปนอยู่กับคนแปลกหน้า อาจเป็นชาวฝรั่งเศส ทหารม้าที่สวมอินทรธนูสีแดง มันเป็นไปไม่ได้ที่จะเห็นอะไรเพิ่มเติม เพราะหลังจากนั้นทันที ปืนใหญ่ก็เริ่มยิงจากที่ไหนสักแห่ง และทุกอย่างก็ถูกปกคลุมไปด้วยควัน
ในขณะนั้นขณะที่ทหารม้าเดินผ่านเขาหายไปในควัน Rostov ลังเลว่าจะควบตามพวกเขาหรือไปในที่ที่เขาต้องการไป นี่เป็นการโจมตีที่ยอดเยี่ยมของทหารม้าซึ่งทำให้ชาวฝรั่งเศสประหลาดใจ รอสตอฟกลัวที่จะได้ยินในภายหลังว่าในบรรดาชายหนุ่มรูปงามจำนวนมากเจ้าหน้าที่และนักเรียนนายร้อยที่ขี่ม้าหลายพันตัวควบม้าผ่านเขาไปมีเพียงสิบแปดคนเท่านั้นที่ยังคงอยู่หลังการโจมตี