ทฤษฎีกราฟ ทฤษฎีกราฟเป็นสาขาอิสระที่ครอบคลุมของคณิตศาสตร์แยกส่วน ใช้ในการออกแบบเครือข่ายคอมพิวเตอร์ ท่อส่ง-การนำเสนอ กราฟ กราฟและการนำเสนอการใช้งาน

หากต้องการดูการนำเสนอด้วยรูปภาพ การออกแบบ และสไลด์ ดาวน์โหลดไฟล์และเปิดใน PowerPointบนคอมพิวเตอร์ของคุณ
เนื้อหาข้อความของสไลด์นำเสนอ: กราฟและการประยุกต์ในการแก้ปัญหา สารบัญ กราฟคืออะไร คุณสมบัติของกราฟ ประวัติความเป็นมาของการเกิดขึ้นของกราฟ ปัญหาของสะพานเคอนิกสเบิร์ก การใช้กราฟ สรุป กราฟคืออะไร ในทางคณิตศาสตร์ คำจำกัดความของกราฟมีดังนี้: A กราฟคือเซตของจุดที่ไม่ว่างเปล่าและเซตของเซ็กเมนต์ ซึ่งปลายทั้งสองของนั้นเป็นของเซตของจุดที่กำหนด จุดต่างๆ เรียกว่าจุดยอดของกราฟ และเส้นที่เชื่อมต่อกันคือขอบ ขอบของกราฟ จุดยอดของกราฟ ถัดไป กราฟคืออะไร จำนวนขอบที่โผล่ออกมาจากจุดยอดของกราฟ เรียกว่า องศาของจุดยอด จุดยอดของกราฟที่มีดีกรีคี่เรียกว่าคี่ และจุดยอดที่มีดีกรีคู่เรียกว่าคู่ เนื้อหาระดับคี่ ระดับคู่ คุณสมบัติของกราฟ ในกราฟ ผลรวมขององศาของจุดยอดทั้งหมดจะเป็นเลขคู่ ซึ่งเท่ากับจำนวนสองเท่าของจำนวนขอบของกราฟ จำนวนของจุดยอดคี่ของกราฟใดๆ จะเป็นจำนวนคู่ กราฟที่มีจุดยอด n โดยที่ n≥2 จะมีจุดยอดสองจุดที่มีองศาเท่ากันเสมอ คุณสมบัติของกราฟ หากในกราฟที่มีจุดยอด n จุด (n>2) จุดยอดสองจุดมีระดับเท่ากัน ดังนั้นในกราฟนี้จะมีจุดยอดระดับ 0 หนึ่งจุดหรือจุดยอดระดับ n-1 หนึ่งจุดเสมอ หากจุดยอดสมบูรณ์ กราฟไม่มีจุดยอด ดังนั้นจำนวนขอบจะเท่ากับ n(n-1)/2 คุณสมบัติของกราฟ กราฟที่สมบูรณ์ กราฟที่ไม่สมบูรณ์ คุณสมบัติของกราฟ กราฟที่มีทิศทาง กราฟที่ไม่มีทิศทาง กราฟไอโซมอร์ฟิก ประวัติความเป็นมาของกราฟ คำว่า "กราฟ" ปรากฏครั้งแรกในหนังสือของนักคณิตศาสตร์ชาวฮังการี ดี. โคนิก ในปี พ.ศ. 2479 แม้ว่าทฤษฎีบทที่สำคัญที่สุดเกี่ยวกับกราฟเริ่มแรกจะดำเนินไป กลับมาที่แอล. ออยเลอร์ ประวัติความเป็นมาเพิ่มเติมของการเกิดขึ้นของกราฟ รากฐานของทฤษฎีกราฟในฐานะวิทยาศาสตร์ทางคณิตศาสตร์ถูกวางในปี 1736 โดย Leonhard Euler โดยคำนึงถึงปัญหาของสะพาน Königsberg วันนี้งานนี้กลายเป็นงานคลาสสิกไปแล้ว เนื้อหา ปัญหาเกี่ยวกับสะพานเคอนิกส์แบร์ก อดีตเคอนิกส์แบร์ก (ปัจจุบันคือคาลินินกราด) ตั้งอยู่บนแม่น้ำเพรเกล ภายในเมืองมีแม่น้ำไหลผ่านเกาะสองแห่ง สะพานถูกสร้างขึ้นจากชายฝั่งไปยังเกาะต่างๆ สะพานเก่ายังไม่รอด แต่แผนที่เมืองยังคงอยู่ซึ่งแสดงภาพไว้ ถัดไป ปัญหาเกี่ยวกับสะพาน Königsberg ปัญหาต่อไปนี้แพร่หลายในหมู่ชาวเมือง Königsberg: เป็นไปได้ไหมที่จะเดินข้ามสะพานทั้งหมดแล้วกลับไปยังจุดเริ่มต้น โดยเยี่ยมชมแต่ละสะพานเพียงครั้งเดียว ปัญหาเพิ่มเติมเกี่ยวกับสะพาน Königsberg เป็นไปไม่ได้ที่จะเดินข้ามสะพาน Königsberg โดยปฏิบัติตามเงื่อนไขที่กำหนด เดินข้ามสะพานทั้งหมดโดยต้องแวะแต่ละสะพานแล้วกลับไปยังจุดเริ่มต้นของการเดินทาง ในภาษาทฤษฎีกราฟดูเหมือนปัญหาการวาดภาพกราฟแบบ "เส้นเดียว" เพิ่มเติม ปัญหาของสะพานเคอนิกสเบิร์ก แต่เนื่องจากกราฟในรูปนี้มีจุดยอดคี่สี่จุด จึงเป็นไปไม่ได้ที่จะวาดกราฟดังกล่าว "ด้วยเส้นขีดเดียว" เนื้อหา กราฟออยเลอร์ กราฟที่สามารถวาดได้โดยไม่ต้องยกดินสอออกจากกระดาษ เรียกว่า กราฟออยเลอร์ ในการแก้ปัญหาของสะพานเคอนิกส์แบร์ก ออยเลอร์ได้กำหนดคุณสมบัติของกราฟขึ้นมา: จำนวนจุดยอดคี่ (จุดยอดที่มีขอบเป็นจำนวนคี่นำไปสู่) ของกราฟต้องเป็นจำนวนคู่ ไม่สามารถมีกราฟที่มีจุดยอดคี่เป็นจำนวนคี่ได้ หากจุดยอดทั้งหมดของกราฟเท่ากัน คุณสามารถวาดกราฟได้โดยไม่ต้องยกดินสอออกจากกระดาษ และคุณสามารถเริ่มต้นจากจุดยอดใดก็ได้ของกราฟแล้วสิ้นสุด ที่จุดยอดเดียวกัน กราฟที่มีจุดยอดคี่มากกว่า 2 จุดไม่สามารถวาดด้วยเส้นขีดเดียวได้ กราฟออยเลอร์เพิ่มเติม หากจุดยอดทั้งหมดของกราฟเท่ากัน คุณสามารถวาดกราฟนี้ได้โดยไม่ต้องยกดินสอออกจากกระดาษ (“ด้วยการขีดครั้งเดียว”) โดยผ่านแต่ละขอบเพียงครั้งเดียว การเคลื่อนไหวสามารถเริ่มต้นจากจุดยอดใดก็ได้และสิ้นสุดที่จุดยอดเดียวกัน กราฟออยเลอร์เพิ่มเติม สามารถวาดกราฟที่มีจุดยอดคี่เพียงสองจุดโดยไม่ต้องยกดินสอออกจากกระดาษ และการเคลื่อนไหวจะต้องเริ่มจากจุดยอดคี่จุดใดจุดหนึ่งและสิ้นสุดที่จุดที่สอง กราฟออยเลอร์เพิ่มเติม กราฟที่มีจุดยอดคี่มากกว่าสองจุดไม่สามารถวาดด้วย "หนึ่งขีด" ได้ - การใช้กราฟ การใช้กราฟเพื่อทำให้การแก้ปัญหาง่ายขึ้น ปัญหาทางคณิตศาสตร์,ปริศนา,ภารกิจแห่งความฉลาด การประยุกต์ใช้ปัญหากราฟเพิ่มเติม: Arkady, Boris Vladimir, Grigory และ Dmitry จับมือกันเมื่อพวกเขาพบกัน (ต่างจับมือกันหนึ่งครั้ง) มีการจับมือกันกี่ครั้ง? การใช้กราฟเพิ่มเติม วิธีแก้ไข: A D C B D 1 2 3 4 5 6 7 8 9 10 เพิ่มเติม การใช้กราฟ ในรัฐ ระบบสายการบินได้รับการออกแบบในลักษณะที่เมืองใดๆ เชื่อมต่อกันด้วยสายการบินกับเมืองอื่นๆ ไม่เกินสามแห่ง และจาก เมืองใดไปยังเมืองอื่น ๆ คุณสามารถเดินทางได้โดยทำการเปลี่ยนแปลงไม่เกินหนึ่งครั้ง รัฐนี้สามารถมีเมืองได้สูงสุดกี่เมือง? การใช้กราฟ ให้มีบางเมือง A จากนั้นคุณสามารถเข้าถึงเมืองได้ไม่เกินสามเมืองและจากแต่ละเมืองไม่เกินสองเมือง (ไม่นับ A) ดังนั้นจำนวนเมืองทั้งหมดต้องไม่เกิน 1+3+6=10 หมายความว่ามีทั้งหมดไม่เกิน 10 เมือง ตามตัวอย่างในรูปแสดงถึงการมีอยู่ของสายการบิน การประยุกต์ใช้กราฟ มีกระดานหมากรุกขนาด 3x3 ที่มุมสองด้านบนมีอัศวินดำสองคน ด้านล่างมีสีขาวสองตัว (ภาพด้านล่าง) ในการเคลื่อนไหว 16 ครั้ง ให้วางอัศวินขาวแทนที่อัศวินดำ และอัศวินดำแทนที่อัศวินสีขาว และพิสูจน์ว่ามันเป็นไปไม่ได้ที่จะทำสิ่งนี้โดยใช้การเคลื่อนไหวน้อยลง การใช้กราฟ เมื่อขยายกราฟของการเคลื่อนไหวของอัศวินที่เป็นไปได้เป็นวงกลม เราพบว่าในตอนแรกอัศวินยืนอยู่ดังรูปด้านล่าง กราฟสรุปเป็นวัตถุทางคณิตศาสตร์ที่ยอดเยี่ยม ด้วยความช่วยเหลือซึ่งคุณสามารถแก้ทางคณิตศาสตร์ เศรษฐกิจ และ ปัญหาเชิงตรรกะ คุณยังสามารถไขปริศนาต่าง ๆ และทำให้เงื่อนไขของปัญหาในฟิสิกส์ เคมี อิเล็กทรอนิกส์ และระบบอัตโนมัติง่ายขึ้น กราฟใช้ในการรวบรวมแผนที่และแผนภูมิลำดับวงศ์ตระกูล มีแม้กระทั่งส่วนพิเศษทางคณิตศาสตร์ที่เรียกว่า "ทฤษฎีกราฟ" เนื้อหา

ไฟล์แนบ

กราฟคือเซตจำกัดของจุดยอด V และเซตของขอบ R ที่เชื่อมต่อคู่ของจุดยอด G=(V,R) ภาวะเชิงการนับของเซต V และ R เท่ากับ N และ M เซตของขอบสามารถเว้นว่างได้ ตัวอย่างของจุดยอดคือวัตถุในลักษณะใดก็ตาม (การตั้งถิ่นฐาน เครือข่ายคอมพิวเตอร์) ตัวอย่างของขอบ ได้แก่ ถนน ด้านข้าง เส้น

จุดยอดที่เชื่อมต่อกันด้วยขอบเรียกว่าจุดติดกัน ขอบที่มีจุดยอดร่วมจะเรียกว่าขอบที่อยู่ติดกัน ขอบและจุดยอดสองจุดใด ๆ เรียกว่าเหตุการณ์ ระดับของจุดยอดคือจำนวนขอบที่ตกกระทบกับจุดยอดนั้น แต่ละกราฟสามารถแสดงบนระนาบด้วยชุดจุดที่สอดคล้องกับจุดยอด ซึ่งเชื่อมต่อกันด้วยเส้นที่สอดคล้องกับขอบ

เส้นทางกราฟคือลำดับของจุดยอดและขอบ เส้นทางจะถูกปิด (แบบวน) หากจุดยอดเริ่มต้นและจุดสิ้นสุดตรงกัน เส้นทางจะเป็นสายโซ่ธรรมดาถ้าจุดยอดและขอบทั้งหมดแตกต่างกัน กราฟจะเชื่อมต่อกันหากจุดยอดแต่ละจุดสามารถเข้าถึงได้จากจุดอื่นๆ จุดยอดที่ไม่มีขอบตกกระทบเรียกว่าแยกออกจากกัน

เมทริกซ์เหตุการณ์

รายการการสื่อสาร

รายการซี่โครง

เมทริกซ์ที่อยู่ติดกันของกราฟกราฟแบบถ่วงน้ำหนักแบบไม่มีทิศทางที่เชื่อมต่อกัน

การสร้างต้นไม้เชื่อมต่อแบบทอดโดยมีน้ำหนักขั้นต่ำ อัลกอริธึมของ Kruskal ขอบทั้งหมดจะถูกลบออกจากกราฟ ส่งผลให้เกิดกราฟย่อยแบบขยายซึ่งจุดยอดทั้งหมดจะถูกแยกออกจากกัน แต่ละจุดยอดจะถูกวางลงในเซตย่อยซิงเกิลตัน ขอบจะถูกจัดเรียงตามการเพิ่มน้ำหนัก ขอบจะรวมตามลำดับตามลำดับน้ำหนักที่เพิ่มขึ้นในแผนผังที่ทอด

มี 4 กรณี: 1) จุดยอดทั้งสองของ Edge ที่รวมไว้เป็นของเซตย่อยซิงเกิลตัน จากนั้นจะรวมกันเป็นเซตย่อยใหม่ที่เชื่อมต่อกัน; 2) จุดยอดอันใดอันหนึ่งเป็นของเซตย่อยที่เชื่อมต่อกัน แต่อีกจุดหนึ่งไม่มี จากนั้นเราจะรวมอันที่สองไว้ในเซตย่อยที่อันแรกอยู่ 3) จุดยอดทั้งสองอยู่ในชุดย่อยที่เชื่อมต่อกัน จากนั้นเราจะรวมชุดย่อยเข้าด้วยกัน 4) จุดยอดทั้งสองอยู่ในเซ็ตย่อยที่เชื่อมต่อกัน จากนั้นเราจะแยกขอบนี้ออก

ตัวอย่างการสร้าง spanning tree ที่มีน้ำหนักขั้นต่ำสำหรับกราฟ GG Actions ที่จะดำเนินการ ชุดของจุดยอด กราฟ 1 มาสร้างกราฟย่อยแบบ spanning ด้วยการแยกและจุดยอด เราจะได้ชุดย่อยองค์ประกอบเดี่ยว 5 ชุด: (V 1 ), (V 2 ), (V 3 ), (V 4 ), (V 5 ) 2 ค้นหาขอบของน้ำหนักขั้นต่ำ (R 15) และเพิ่มลงในกราฟย่อยที่ขยาย เราสร้างเซตย่อยของจุดยอดที่เชื่อมต่อกัน: (V 1,V 5) เราบันทึกชุดย่อย (V 2), (V 3), (V 4)

การดำเนินการที่จะดำเนินการ ชุดของจุดยอด กราฟ 3 ในบรรดาจุดที่เหลือ ให้ค้นหาขอบของน้ำหนักขั้นต่ำ (R 45) และเพิ่มลงในกราฟย่อยที่ขยาย เพิ่มจุดยอดไปยังเซตย่อยที่เชื่อมต่อ: (V 1, V 5, V 4 ) เราบันทึกเซ็ตย่อย (V 2), (V 3) 4 ในบรรดาส่วนที่เหลือเราจะพบขอบของน้ำหนักขั้นต่ำ (R 23) และเพิ่มลงในกราฟย่อยที่ขยาย เราสร้างเซ็ตย่อยของจุดยอดที่เชื่อมต่อกันใหม่: (V 2, ว 3) เราบันทึกเซ็ตย่อยที่เชื่อมต่อชุดแรก (V 1,V 5, V 4)

การดำเนินการที่จะดำเนินการ ชุดของจุดยอด กราฟ 5 ในบรรดาส่วนที่เหลือ เราจะพบขอบของน้ำหนักขั้นต่ำ (R 25) และเพิ่มลงในกราฟย่อยแบบสแปน เรารวมชุดย่อยเป็นชุดย่อยที่เชื่อมต่อกัน (V 1,V 5, V 4, วี 2,วี 3) 6ขอบที่เหลือจะไม่รวมอยู่ในกราฟเพราะว่า จุดยอดทั้งหมดเป็นของชุดที่เชื่อมต่อกันชุดเดียวอยู่แล้ว

การดำเนินการที่จะดำเนินการ ชุดของกราฟจุดยอด 7 จะได้กราฟที่ประกอบด้วย: การขยาย (รวมจุดยอดทั้งหมด); เชื่อมต่อแล้ว (จุดยอดทั้งหมดสามารถเชื่อมต่อได้ด้วยเส้นทาง) ต้นไม้ (ไม่มีลูป); มีน้ำหนักน้อยที่สุด 8ผลลัพธ์ของต้นไม้ทอดข้ามจะมีน้ำหนักขั้นต่ำ: R 12 +R 25 +R 15 +R 45 = =80 9 จำนวนวงจรของกราฟ G คือ γ=m-n+1=8-5+1=4 ซึ่งสอดคล้องกับ จนถึงจำนวนขอบที่ไม่รวมอยู่ในต้นไม้

การประกาศตัวแปร อาร์เรย์จำนวนเต็มห้าองค์ประกอบสองตัว X และ Y เพื่อจัดเก็บพิกัดของจุดยอดกราฟ จำนวนเต็มอาร์เรย์สองมิติ R เพื่อจัดเก็บน้ำหนักของขอบกราฟ ตัวแปรจำนวนเต็ม i, n และ k สำหรับตัวนับลูป ตัวแปรจำนวนเต็ม S ถึง เก็บผลรวมของน้ำหนักของขอบของต้นไม้น้ำหนักขั้นต่ำ

การสร้างพิกัดแบบสุ่มของจุดยอด 5 จุดของกราฟ (วนซ้ำผ่าน i) การคำนวณน้ำหนักขอบ เอาต์พุตของเมทริกซ์ adjacency ของกราฟถ่วงน้ำหนัก (ลูปซ้อนโดย n และโดย k) เอาต์พุตของเมทริกซ์ adjacency ของกราฟที่ไม่มีทิศทางถ่วงน้ำหนัก - ครึ่งหนึ่งขององค์ประกอบของเมทริกซ์เริ่มต้น (ค่าเริ่มต้น k=n+1) เนื้อความของโปรแกรม

เรียกว่าจำนวนจุดยอด
ลำดับของกราฟ
เรียกว่าจำนวนขอบ
ขนาดของกราฟ

เงื่อนไขบางประการ-1

- ให้ R=(a,b) เป็นหนึ่งในขอบของกราฟ แล้ว
จุดยอด a และ b เรียกว่าจุดยอดปลาย
จุดยอดของซี่โครง;
- สิ้นสุดจุดยอดของขอบเดียวกัน
เรียกว่าเพื่อนบ้าน
- ขอบสองอันจะเรียกว่าติดกันถ้ามี
จุดยอดปลายทั่วไป
- สองขอบเรียกว่าหลายถ้า
ชุดของจุดยอดสิ้นสุดตรงกัน
- ขอบจะเรียกว่าลูปหากสิ้นสุด
จับคู่.

เงื่อนไขบางประการ-2

- องศาของจุดยอด V เขียนแทนด้วย deg(V)
เรียกว่าจำนวนขอบของ
โดยจุดยอดนี้เป็นขั้วหนึ่ง
- จุดยอดเรียกว่าแยกถ้า
มันไม่ใช่จุดสิ้นสุดของสิ่งใดสิ่งหนึ่ง
ซี่โครง;
- จุดยอดเรียกว่าใบไม้ถ้าเป็น
เป็นจุดสิ้นสุดของสิ่งหนึ่งอย่างแน่นอน
ซี่โครง สำหรับแผ่นงาน q ชัดเจน deg(q)=1

ตัวอย่าง:

องศา(C)=4
H1,…H4 - ใบไม้

อีกตัวอย่างหนึ่ง:

เมือง B และ D – โดดเดี่ยว
ท็อปส์ซู; เมือง G และ E เป็นเพียงใบไม้

กราฟที่สมบูรณ์

กราฟจะเรียกว่าสมบูรณ์ถ้ามี
จุดยอดสองจุดเชื่อมต่อกันด้วยขอบ
กราฟที่สมบูรณ์มีกี่เส้น?
สั่งอะไร?
กราฟที่สมบูรณ์ของลำดับ n มีจำนวนขอบ
เท่ากับ Cn2=n!/(2*(n-2)!) =n*(n-1)/2

มาพิสูจน์กัน...

กราฟที่สมบูรณ์โดยมีจุดยอดสองจุด
มีขอบเดียว - นี่ชัดเจน
แทน n=2 ลงในสูตร n*(n-1)/2
เราได้รับ:
n*(n-1)/2=1
สูตรนี้ถูกต้องเมื่อ n=2

สมมติฐานการเหนี่ยวนำ

สมมติว่าสูตรเป็นจริงสำหรับ
กราฟที่มีจุดยอด k
ให้เราพิสูจน์ว่านี่หมายถึง
ความถูกต้องของสูตรสำหรับกราฟ
โดยมีจุดยอด (k+1)

ลองเพิ่มจุดยอดอีกหนึ่งจุดให้กับกราฟที่สมบูรณ์ด้วยจุดยอด K

และเชื่อมต่อกับเคตัวแรก
ยอดเขา...

เราได้รับ:

เรานับดูว่าเราได้ซี่โครงกี่ซี่...

K*(K-1)/2 + เค
=
K*(K+1)/2
สำนวนสุดท้ายกลายเป็น
ถ้าอยู่ในสูตร n*(n-1)/2 แทนที่จะเป็น n
แทน K+1

จากการสันนิษฐานของความเป็นธรรม
คำสั่งสำหรับ n=k ดังต่อไปนี้
ความถูกต้องของคำสั่งเมื่อ
n=k+1
ทฤษฎีบทได้รับการพิสูจน์แล้ว

ตัวอย่างกราฟที่สมบูรณ์

คำชี้แจงที่สำคัญ

คู่ที่กำหนดขอบในกราฟที่ไม่มีทิศทางจะไม่เรียงลำดับ (เช่น
คู่ (a,b) และ (b,a) ไม่แตกต่างกัน)

กราฟกำกับ

หากมีขอบกราฟหลายอัน
คู่ที่สั่ง (เช่น (a,b) ≠ (b,a))
จากนั้นกราฟจะเรียกว่ากำกับ
(หรือไดกราฟ)
วิธีการปฐมนิเทศแนวคิด
ความหมายทางสายตา?
ง่ายมาก - มีการจัดหาซี่โครงมาให้
ลูกศร (ตั้งแต่ต้นจนจบ)!

ตัวอย่างไดกราฟ

กราฟผสม

กราฟผสมคือกราฟสามเท่า (V, E, A)
V – ชุดของจุดยอด;
E – ชุดที่ไม่มุ่งเน้น
ซี่โครง;
A คือเซตของขอบเชิง
โดยวิธีการเน้นขอบ
เรียกว่าส่วนโค้ง

กราฟมอร์ฟิซึม

ให้มีกราฟ G1 และ G2 สองตัว
หากมีการติดต่อแบบตัวต่อตัว F
ระหว่างจุดยอดของกราฟ G1 และ G2 โดยที่:
- หากมีขอบ (a,b) ในกราฟ G1 ก็จะมีขอบในกราฟ G2 ด้วย
คือขอบ (F(a),F(b))
- หากมีขอบ (p,q) ในกราฟ G2 ก็จะมีขอบในกราฟ G1 ด้วย
มีขอบ (F-1(p),F-1(q))
ดังนั้นกราฟ G1 และ G2 จึงเรียกว่า isomorphic และ
การติดต่อ F คือมอร์ฟิซึม

ชี้แจง

สำหรับไดกราฟและกราฟผสม
การปฏิบัติตาม F จะต้องรักษาไว้
การวางแนวของส่วนโค้ง

เงื่อนไขที่จำเป็นสำหรับมอร์ฟิซึม

ภายใต้เงื่อนไขใดระหว่างองค์ประกอบ
สองเซตจำกัด
สร้างแบบหนึ่งต่อหนึ่ง
จดหมายโต้ตอบ?
จากนั้นและเท่านั้นจำนวนของพวกเขา
องค์ประกอบก็เหมือนกัน
เงื่อนไขที่จำเป็นสำหรับมอร์ฟิซึม
จำนวนกราฟเท่ากัน
ยอดเขา

เงื่อนไขนี้เพียงพอหรือไม่?

ไม่ เพราะยอดเขาสามารถเป็นได้
เชื่อมต่อแตกต่างกัน

กราฟเหล่านี้เป็นกราฟแบบ isomorphic หรือไม่?

จำนวนจุดยอดเท่ากัน -
ตรงตามเงื่อนไขที่จำเป็น...

เรากำลังพยายามสร้างจดหมายโต้ตอบ F...

นี่ไม่ใช่มอร์ฟิซึม: G1 มีขอบ (A,D)
และภาพของขอบเหล่านี้ใน G2 ไม่ได้เชื่อมต่อกัน

ลองอีกครั้ง...

และนี่คือมอร์ฟิซึ่ม!

กราฟเหล่านี้เป็นกราฟแบบ isomorphic หรือไม่?

อนิจจา ไม่...

จากมุมมองทางทฤษฎีมีสองประการ
กราฟไอโซมอร์ฟิกเป็นกราฟเดียวกัน
วัตถุเดียวกัน (อาจแสดงแตกต่างออกไปเท่านั้น...)

เส้นทาง (โซ่):

เส้นทาง (ลูกโซ่) เป็นลำดับ
จุดยอด:
a1, a2, … , อัน
โดยที่จุดยอดที่อยู่ติดกัน ai และ ai+1
เชื่อมต่อกันด้วยซี่โครง
ความยาวของเส้นทางคือจำนวนส่วนประกอบ
ซี่โครง

เส้นทางตัวอย่าง:

(A, D, C) และ (A, B, D) เป็นเส้นทาง (A, B, C) ไม่ใช่ทาง

แนวคิดเรื่องเส้นทางสำหรับการเก็บรักษาไดกราฟ
แรงแต่ต้องเสริม-
ยอดเขาใกล้เคียงใน
ลำดับ
a1, a2, … , อัน
ต้องเชื่อมต่อกันด้วยส่วนโค้ง

รอบ

วงจรคือเส้นทางที่มีจุดเริ่มต้นและ
จุดยอดสุดท้ายตรงกัน
ความยาวของวงจรคือจำนวนส่วนประกอบต่างๆ
ซี่โครง
วงจรเรียกว่าง่ายถ้ามีขอบอยู่
จะไม่เกิดซ้ำ
วัฏจักรจะเรียกว่าประถมศึกษาถ้าเป็น
เรียบง่ายและไม่มีจุดยอดซ้ำอยู่ในนั้น

ส่วนประกอบการเชื่อมต่อ

จุดยอดของกราฟใดก็ได้
แบ่งออกเป็นชั้นเรียนเพื่อ
จุดยอดสองจุดใดๆ ของคลาส v1 เดียวกัน
และ v2 มีเส้นทางจาก v1 ถึง v2
คลาสเหล่านี้เรียกว่าส่วนประกอบ
การเชื่อมต่อ
หากกราฟมีองค์ประกอบเดียว
ความเชื่อมโยงจึงเรียกว่ากราฟ
สอดคล้องกัน

การแสดงกราฟด้วยเครื่อง

เมทริกซ์ที่อยู่ติดกัน

- ลองนับจุดยอดของกราฟ G กัน
จำนวนเต็มต่อเนื่องกันตั้งแต่ 1 ถึง n;
- มาสร้างตารางสี่เหลี่ยม n×n และ
เติมด้วยศูนย์
- หากมีขอบเชื่อมต่อกัน
จุดยอด i และ j จากนั้นอยู่ในตำแหน่ง (i,j) และ (j,i)
เราจะจัดหาหน่วย
- ตารางผลลัพธ์เรียกว่า
เมทริกซ์ adjacency ของกราฟ G

ตัวอย่าง

คุณสมบัติที่ชัดเจนบางประการของเมทริกซ์คำคุณศัพท์

- ถ้าจุดยอดถูกแยกออก ดังนั้นแถวของมัน และ
คอลัมน์จะเป็นศูนย์โดยสมบูรณ์
- จำนวนหน่วยในแถว (คอลัมน์)
เท่ากับระดับที่สอดคล้องกัน
ท็อปส์ซู;
- สำหรับเมทริกซ์กราฟแบบไม่มีทิศทาง
คำติดกันมีความสมมาตรด้วยความเคารพ
เส้นทแยงมุมหลัก
- ห่วงสอดคล้องกับยูนิตที่ยืนอยู่
เส้นทแยงมุมหลัก

ลักษณะทั่วไปสำหรับไดกราฟ

เมทริกซ์ที่อยู่ติดกันสำหรับไดกราฟ
ก็สามารถสร้างได้ในลักษณะเดียวกัน
แต่ต้องคำนึงถึงลำดับด้วย
จุดยอด คุณสามารถทำสิ่งนี้ได้:
ถ้าส่วนโค้งเริ่มต้นจากจุดยอด j และ
เข้าสู่จุดยอด k จากนั้นที่ตำแหน่ง (j,k)
เมทริกซ์ adjacency ควรตั้งค่าเป็น 1 และใน
ตำแหน่ง (k,j) ชุด -1

เมทริกซ์อุบัติการณ์

- ลองนับจุดยอดของกราฟ G กัน
จำนวนเต็มต่อเนื่องกันตั้งแต่ 1 ถึง
ไม่มี;
- มาสร้างโต๊ะสี่เหลี่ยมกันเถอะ
n แถวและ m คอลัมน์ (คอลัมน์
ตรงกับขอบของกราฟ)
- ถ้าขอบ j มีขั้ว
จุดยอดคือจุดยอด k จากนั้นอยู่ในตำแหน่ง
(k,j) ถูกตั้งค่าเป็นหนึ่ง ในทั้งหมด
ในกรณีอื่นๆ จะถูกตั้งค่าเป็นศูนย์

เมทริกซ์อุบัติการณ์สำหรับไดกราฟ

- ถ้าส่วนโค้งที่ j มาจากจุดยอด k
จากนั้นให้วาง 1 ในตำแหน่ง (k,j);
- หากส่วนโค้งที่ j เข้าสู่จุดยอด k แล้ว
-1 อยู่ในตำแหน่ง (k,j)
- ในกรณีอื่นในตำแหน่ง (k,j)
ยังคงเป็นศูนย์

เนื่องจากคอลัมน์เมทริกซ์
อุบัติการณ์อธิบายซี่โครงแล้ว
แต่ละคอลัมน์ต้องไม่มี
องค์ประกอบที่ไม่ใช่ศูนย์มากกว่าสององค์ประกอบ

ตัวอย่างเมทริกซ์อุบัติการณ์

รายการขอบ

อีกวิธีหนึ่งในการแสดงกราฟ
– อาร์เรย์สองมิติ (รายการคู่)
จำนวนคู่เท่ากับจำนวนขอบ
(หรือส่วนโค้ง)

ตัวอย่างรายการขอบ

เปรียบเทียบวิธีการนำเสนอแบบต่างๆ

- รายการขอบมีขนาดกะทัดรัดที่สุดและ
เมทริกซ์อุบัติการณ์น้อยที่สุด
กะทัดรัด;
- เมทริกซ์อุบัติการณ์จะสะดวกเมื่อ
ค้นหารอบ;
- Adjacency matrix ง่ายกว่า
ส่วนที่เหลือในการใช้งาน

การข้ามกราฟ

การสำรวจกราฟเรียกว่าการแจงนับ
จุดยอดเพื่อให้แต่ละจุดยอด
ดูครั้งเดียว

ข้อตกลง-1

ก่อนที่จะทำการค้นหาบนกราฟ
ด้วยจุดยอด n เราจะสร้างอาร์เรย์ Chk
ขององค์ประกอบ n รายการแล้วเติมเข้าไป
ศูนย์
ถ้า Chk[i] = 0 แล้วจุดยอด i-th ยังคงอยู่
ไม่ได้ดู.

ข้อตกลง-2

มาสร้างโครงสร้างข้อมูลกันดีกว่า
(ที่เก็บข้อมูล) ซึ่งเราจะ
จำจุดยอดในกระบวนการ
บายพาส อินเตอร์เฟซการจัดเก็บ
ควรมีสามฟังก์ชัน:
- นำมาด้านบน;
- แยกจุดยอด;
- ตรวจสอบว่าที่เก็บข้อมูลว่างเปล่าหรือไม่

ข้อตกลง-3

เมื่อวางจุดยอด j ไว้
ที่เก็บข้อมูล โดยมีเครื่องหมายกำกับว่า
ดูแล้ว (เช่น ติดตั้งแล้ว
ชเค[เจ]=1)

บายพาสอัลกอริทึม-1

1) ใช้จุดยอดเริ่มต้นตามอำเภอใจ
เราพิมพ์และเก็บไว้ในที่จัดเก็บ

3) นำจุดยอด Z จากที่เก็บข้อมูล
4) หากมีจุดยอด Q เชื่อมต่อกับ Z และไม่ใช่
ทำเครื่องหมายแล้วคืน Z ไปยังที่จัดเก็บ
ใส่ Q ลงในที่จัดเก็บ พิมพ์ Q;
5) ไปที่ขั้นตอนที่ 2

บายพาสอัลกอริทึม-2

1) ใช้จุดยอดเริ่มต้นตามอำเภอใจและ
เราเก็บมันไว้ในที่จัดเก็บ
2) ที่เก็บข้อมูลว่างเปล่าหรือไม่? ถ้าใช่ - จบ;
3) นำจุดยอด Z จากการจัดเก็บ พิมพ์ และ
ลบออกจากที่เก็บข้อมูล
4) วางจุดยอดทั้งหมดไว้ในที่เก็บข้อมูล
เกี่ยวข้องกับ Z และยังไม่ได้ระบุไว้
5) ไปที่ขั้นตอนที่ 2

โครงสร้างข้อมูลใดที่เหมาะกับการจัดเก็บข้อมูล?

- สแต็ค (PUSH – เพิ่ม; POP – ลบ)
- คิว (ENQUE – ป้อน; DEQUE –
สารสกัด)
โครงสร้างทั้งสองช่วยให้คุณสามารถตรวจสอบได้
ความพร้อมของข้อมูล

อัลกอริทึม-1 ร่วมกับสแต็ก
เรียกว่าการสำรวจเชิงลึกครั้งแรก
อัลกอริทึม-2 ร่วมกับคิว
เรียกว่าการข้ามผ่านครั้งแรกอย่างกว้าง

1 สไลด์

2 สไลด์

รากฐานของทฤษฎีกราฟปรากฏครั้งแรกในงานของเลออนฮาร์ด ออยเลอร์ (ค.ศ. 1707-1783 นักคณิตศาสตร์ชาวสวิส เยอรมัน และรัสเซีย) ซึ่งเขาบรรยายถึงการไขปริศนาและปัญหาความบันเทิงทางคณิตศาสตร์ ทฤษฎีกราฟเริ่มต้นด้วยวิธีแก้ปัญหาของออยเลอร์ต่อปัญหาสะพานทั้งเจ็ดแห่งเคอนิกสแบร์ก

3 สไลด์

ปริศนาต่อไปนี้เป็นเรื่องธรรมดาในหมู่ชาวเมืองKönigsbergมานานแล้ว: จะข้ามสะพานทั้งหมด (ข้ามแม่น้ำ Pregolya) ได้อย่างไรโดยไม่ต้องข้ามสะพานใดเลยสองครั้ง? หลายคนพยายามแก้ไขปัญหานี้ทั้งทางทฤษฎีและปฏิบัติระหว่างการเดิน แต่ไม่มีใครประสบความสำเร็จ แต่พวกเขาล้มเหลวในการพิสูจน์ว่ามันเป็นไปไม่ได้ในทางทฤษฎีด้วยซ้ำ ในแผนภาพอย่างง่ายของส่วนต่างๆ ของเมือง (กราฟ) สะพานสอดคล้องกับเส้น (ส่วนโค้งของกราฟ) และส่วนต่างๆ ของเมืองสอดคล้องกับจุดเชื่อมต่อเส้น (จุดยอดของกราฟ) ในระหว่างการใช้เหตุผล ออยเลอร์ได้ข้อสรุปดังนี้: เป็นไปไม่ได้ที่จะข้ามสะพานทั้งหมดโดยไม่ผ่านสะพานใดสะพานหนึ่งสองครั้ง

4 สไลด์

มี 4 กรุ๊ปเลือด เมื่อเลือดถูกถ่ายจากคนหนึ่งไปยังอีกคนหนึ่ง ไม่ใช่ว่าทุกกลุ่มจะเข้ากันได้ แต่เป็นที่ทราบกันดีว่ากลุ่มที่เหมือนกันสามารถถ่ายโอนจากคนสู่คนได้เช่น 1 – 1, 2 – 2 เป็นต้น และกลุ่มที่ 1 สามารถถ่ายโอนไปยังกลุ่มอื่น ๆ ทั้งหมดกลุ่มที่ 2 และ 3 ได้เฉพาะกลุ่มที่ 4 เท่านั้น งาน.

5 สไลด์

6 สไลด์

กราฟ กราฟเป็นรูปแบบข้อมูลที่นำเสนอในรูปแบบกราฟิก กราฟคือชุดของจุดยอด (โหนด) ที่เชื่อมต่อกันด้วยขอบ กราฟที่มีจุดยอดหกจุดและขอบเจ็ดจุด จุดยอดจะถูกเรียกว่าติดกันหากเชื่อมต่อกันด้วยขอบ

7 สไลด์

กราฟกำกับ - ไดกราฟ แต่ละขอบมีทิศทางเดียว ขอบดังกล่าวเรียกว่าส่วนโค้ง กราฟกำกับ

8 สไลด์

กราฟถ่วงน้ำหนัก นี่คือกราฟที่ขอบหรือส่วนโค้งกำหนดค่าตัวเลข (สามารถระบุได้เช่นระยะทางระหว่างเมืองหรือค่าขนส่ง) น้ำหนักของกราฟเท่ากับผลรวมของน้ำหนักของขอบกราฟ ตาราง (เรียกว่าเมทริกซ์น้ำหนัก) มีกราฟที่สอดคล้องกัน 1 2 4 2 3 เอ บี ซี ดี อี

สไลด์ 9

ปัญหาระหว่าง การตั้งถิ่นฐานมีการสร้างถนน A, B, C, D, E, F ความยาวที่แสดงในตาราง (การไม่มีตัวเลขในตารางหมายความว่าไม่มีถนนตรงระหว่างจุดต่างๆ) กำหนดความยาวของเส้นทางที่สั้นที่สุดระหว่างจุด A และ F (สมมติว่าการเดินทางทำได้เฉพาะบนถนนที่สร้างขึ้นเท่านั้น) 1) 9 2) 10 3) 11 4) 12

10 สไลด์

1. 2. 3. 4. 5. ความยาวที่สั้นที่สุด เส้นทาง A-B-C-E-Fเท่ากับ 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2 4 7 1 3 4 3 2