ตัวอย่างไดกราฟ คำจำกัดความของกราฟกำกับ

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

กราฟแบบมีทิศทางและแบบไม่มีทิศทาง

ลิงค์(ลำดับของปลายทั้งสองของขอบกราฟไม่มีนัยสำคัญ) เรียกว่า ไม่มุ่งเน้น .

กราฟที่มีขอบทั้งหมดอยู่ ส่วนโค้ง(ลำดับของปลายทั้งสองของขอบกราฟมีนัยสำคัญ) เรียกว่า กราฟกำกับ หรือ ไดกราฟ .

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

กราฟวน, กราฟผสม, กราฟว่าง, มัลติกราฟ, กราฟธรรมดา, กราฟสมบูรณ์

หากกราฟประกอบด้วย ลูปจากนั้นสถานการณ์นี้ถูกกำหนดเป็นพิเศษโดยการเพิ่มคำว่า "with loops" เข้ากับลักษณะหลักของกราฟ เช่น "digraph with loops" หากกราฟไม่มีการวนซ้ำ คำว่า "ไม่มีการวนซ้ำ" จะถูกเพิ่มเข้าไป

ผสม เป็นกราฟที่มีขอบอย่างน้อยสองในสามประเภทที่กล่าวถึง (ลิงก์ ส่วนโค้ง ลูป)

กราฟที่ประกอบด้วยเท่านั้น ยอดเขาเปลือย, เรียกว่า ว่างเปล่า .

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

กราฟที่ไม่มีส่วนโค้ง (นั่นคือ ไม่มีทิศทาง) ไม่มีการวนซ้ำและหลายขอบเรียกว่า สามัญ . กราฟธรรมดาแสดงในรูปด้านล่าง

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

กราฟทวิภาคี

กราฟนี้เรียกว่ากราฟทวิภาคี ถ้าเซตของจุดยอดสามารถแบ่งออกเป็นสองเซตย่อยได้ โดยไม่มีขอบมาเชื่อมจุดยอดของเซตย่อยเดียวกัน

ตัวอย่างที่ 1สร้าง เต็มกราฟทวิภาคี

กราฟสองฝ่ายที่สมบูรณ์ประกอบด้วยจุดยอดสองชุดและลิงก์ที่เป็นไปได้ทั้งหมดที่เชื่อมต่อจุดยอดของชุดหนึ่งกับจุดยอดของอีกชุดหนึ่ง (รูปด้านล่าง)

กราฟออยเลอร์

เราได้สัมผัสแล้ว ปัญหาเกี่ยวกับสะพานเคอนิกสเบิร์ก. การแก้ปัญหาเชิงลบของออยเลอร์ต่อปัญหานี้ทำให้เกิดผลงานตีพิมพ์ครั้งแรกเกี่ยวกับทฤษฎีกราฟ ปัญหาการเคลื่อนที่ของสะพานสามารถสรุปได้จากปัญหาทฤษฎีกราฟต่อไปนี้ เป็นไปได้ไหมที่จะค้นหาวงจรในกราฟที่กำหนดซึ่งมีจุดยอดและขอบทั้งหมด กราฟที่เป็นไปได้เรียกว่ากราฟยูเลอเรียน

ดังนั้น, กราฟออยเลอร์ คือกราฟที่คุณสามารถเคลื่อนที่ผ่านจุดยอดทั้งหมดและในเวลาเดียวกันก็เคลื่อนที่ผ่านขอบด้านใดด้านหนึ่งได้เพียงครั้งเดียว ในนั้นแต่ละจุดยอดจะต้องมีจำนวนขอบเป็นเลขคู่เท่านั้น

ตัวอย่างที่ 2เป็นกราฟสมบูรณ์ที่มีจำนวนเท่ากัน nขอบที่แต่ละจุดยอดตกกระทบกัน กราฟยูเลอเรียน? อธิบายคำตอบ. ยกตัวอย่าง.

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

กราฟปกติ

นับปกติ เป็นกราฟที่เชื่อมต่อกันโดยที่จุดยอดทั้งหมดมีดีกรีเท่ากัน เค. ดังนั้น รูปที่ 2 แสดงตัวอย่างกราฟปกติที่เรียกว่ากราฟปกติ 4 เส้น และกราฟปกติ 2 เส้น หรือกราฟปกติระดับ 4 และระดับ 2 ตามระดับจุดยอด

จำนวนจุดยอดในกราฟปกติ เค- วุฒิการศึกษาต้องไม่น้อยกว่า เค+1. กราฟปกติที่มีดีกรีคี่สามารถมีจุดยอดเป็นเลขคู่ได้เท่านั้น

ตัวอย่างที่ 3สร้างกราฟปกติโดยให้วงจรที่สั้นที่สุดมีความยาว 4

สารละลาย. เราให้เหตุผลดังนี้: เพื่อให้ความยาวของวงจรเป็นไปตามเงื่อนไขที่กำหนด จำนวนจุดยอดในกราฟจะต้องเป็นผลคูณของสี่ หากจำนวนจุดยอดคือสี่ คุณจะได้กราฟดังรูปด้านล่าง เป็นเรื่องปกติ แต่รอบที่สั้นที่สุดมีความยาว 3

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

แฮมิลตันนับ

แฮมิลตันนับ เป็นกราฟที่มีวัฏจักรแฮมิลตัน วัฏจักรแฮมิลตัน เรียกว่าวงจรอย่างง่ายที่ผ่านจุดยอดทั้งหมดของกราฟที่กำลังพิจารณา ดังนั้น กล่าวง่ายๆ ก็คือ กราฟแฮมิลตันคือกราฟที่สามารถเคลื่อนที่ผ่านจุดยอดทั้งหมดได้ และแต่ละจุดยอดจะถูกทำซ้ำเพียงครั้งเดียวเท่านั้นเมื่อเคลื่อนที่ผ่าน ตัวอย่างของกราฟแฮมิลตันอยู่ในภาพด้านล่าง

ตัวอย่างที่ 4กำหนดกราฟทวิภาคีซึ่ง n- จำนวนจุดยอดจากชุด ก, ก ม- จำนวนจุดยอดจากชุด บี. กราฟจะเป็นกราฟ Eulerian ในกรณีใด และกราฟ Hamiltonian ในกรณีใด

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

ตัวอย่างบางส่วนจะให้ภาพร่างเล็กๆ น้อยๆ ของกราฟ กราฟทั่วไปคือแผนที่รถไฟใต้ดินหรือเส้นทางอื่นๆ โดยเฉพาะโปรแกรมเมอร์คุ้นเคยกับเครือข่ายคอมพิวเตอร์ซึ่งเป็นกราฟด้วย สิ่งทั่วไปที่นี่คือการมีจุดที่เชื่อมต่อกันด้วยเส้น ดังนั้นในเครือข่ายคอมพิวเตอร์ จุดต่างๆ คือเซิร์ฟเวอร์แต่ละเครื่อง และสายคือสัญญาณไฟฟ้าประเภทต่างๆ ในรถไฟใต้ดิน สถานีแรกคือสถานี ส่วนที่สองคืออุโมงค์ที่อยู่ระหว่างสถานีเหล่านั้น ในทฤษฎีกราฟจะเรียกว่าจุด ยอดเขา (โหนด) และเส้นคือ ซี่โครง (ส่วนโค้ง). ดังนั้น, กราฟคือชุดของจุดยอดที่เชื่อมต่อกันด้วยขอบ

คณิตศาสตร์ไม่ได้ดำเนินการกับเนื้อหาของสิ่งต่าง ๆ แต่ทำงานด้วยโครงสร้างซึ่งทำให้เป็นนามธรรมจากทุกสิ่งที่ได้รับโดยรวม ด้วยการใช้เทคนิคนี้ เราสามารถสรุปได้ว่าวัตถุบางอย่างเป็นกราฟ และเนื่องจากทฤษฎีกราฟเป็นส่วนหนึ่งของคณิตศาสตร์ จึงไม่มีความแตกต่างใดๆ เลยกับสิ่งที่วัตถุเป็นหลักการ สิ่งสำคัญเพียงอย่างเดียวคือไม่ว่าจะเป็นกราฟหรือไม่ นั่นคือมีคุณสมบัติที่จำเป็นสำหรับกราฟหรือไม่ ดังนั้น ก่อนที่จะยกตัวอย่าง เราเน้นในวัตถุที่พิจารณาเฉพาะสิ่งที่เราคิดว่าจะช่วยให้เราสามารถแสดงความคล้ายคลึงได้ เรามองหาสิ่งที่เป็นเรื่องธรรมดา

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

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

ต่อไปนี้เป็นสัญลักษณ์สำคัญที่ใช้ในทฤษฎีกราฟ:

• G=(V, E) โดยที่ G คือกราฟ V คือจุดยอด และ E คือขอบ
• |วี| – ลำดับ (จำนวนจุดยอด)
• |อี| – ขนาดกราฟ (จำนวนขอบ)

ในกรณีของเรา (รูปที่ 1) |V|=5, |E|=10;

เมื่อเข้าถึงจุดยอดอื่นได้จากจุดยอดใดๆ กราฟดังกล่าวจะถูกเรียก ไม่มุ่งเน้นกราฟที่เชื่อมต่อ (รูปที่ 1) หากกราฟเชื่อมต่อกันแต่ไม่ตรงตามเงื่อนไขนี้ กราฟดังกล่าวจะถูกเรียก มุ่งเน้นหรือไดกราฟ (รูปที่ 2)

กราฟแบบมีทิศทางและกราฟไม่มีทิศทางมีแนวคิดเรื่องระดับจุดยอด ระดับสูงสุดคือจำนวนขอบที่เชื่อมต่อกับจุดยอดอื่น ผลรวมขององศาทั้งหมดของกราฟเท่ากับสองเท่าของจำนวนขอบทั้งหมด สำหรับรูปที่ 2 ผลรวมของยกกำลังทั้งหมดคือ 20

ในไดกราฟ ต่างจากกราฟที่ไม่มีทิศทางตรง มันเป็นไปได้ที่จะย้ายจากจุดยอด h ไปยังจุดยอด s โดยไม่มีจุดยอดตรงกลาง เฉพาะเมื่อขอบออกจาก h แล้วเข้าไปที่ s แต่กลับกันไม่ได้

กราฟกำกับมีสัญกรณ์ดังต่อไปนี้:

G=(V, A) โดยที่ V คือจุดยอด A คือขอบที่มีทิศทาง

กราฟประเภทที่สามคือ ผสมกราฟ (รูปที่ 3) มีทั้งขอบแบบมีทิศทางและไม่มีทิศทาง อย่างเป็นทางการ กราฟผสมจะเขียนดังนี้: G=(V, E, A) โดยที่ตัวอักษรแต่ละตัวในวงเล็บหมายถึงสิ่งเดียวกันกับที่กำหนดไว้ก่อนหน้านี้

ในกราฟในรูปที่ 3 ส่วนโค้งบางอันมีทิศทาง [(e, a), (e, c), (a, b), (c, a), (d, b)] ส่วนโค้งบางอันไม่มีทิศทาง [(e, ง), (จ, ข), (ง, ค)…]

เมื่อมองแวบแรก กราฟสองกราฟขึ้นไปอาจมีโครงสร้างที่แตกต่างกัน ซึ่งเกิดขึ้นเนื่องจากการเป็นตัวแทนที่แตกต่างกัน แต่มันก็ไม่ได้เป็นเช่นนั้นเสมอไป ลองใช้กราฟสองอัน (รูปที่ 4)

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

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

ในกราฟใดๆ ที่เราพิจารณา คุณสามารถเลือกเส้นทางและมากกว่าหนึ่งเส้นทางได้ เส้นทางคือลำดับของจุดยอด ซึ่งแต่ละจุดเชื่อมต่อกับจุดถัดไปผ่านขอบ หากจุดยอดแรกและจุดสุดท้ายตรงกัน เส้นทางดังกล่าวจะเรียกว่าวงจร ความยาวของเส้นทางถูกกำหนดโดยจำนวนขอบที่ประกอบกันเป็นเส้นทาง ตัวอย่างเช่น ในรูปที่ 4.a เส้นทางคือลำดับ [(e), (a), (b), (c)] เส้นทางนี้เป็นกราฟย่อย เนื่องจากคำจำกัดความของกราฟหลังมีผลใช้ กล่าวคือ กราฟ G'=(V', E') เป็นกราฟย่อยของกราฟ G=(V, E) เฉพาะในกรณีที่ V' และ E' เป็นของ V, E .

ในบทเรียนแรก เมื่อแนะนำแนวคิดของกราฟ เราจะดูการแข่งขันระหว่างทีมกีฬาเป็นตัวอย่าง เรา. เชื่อมต่อสองทีมเช่น A และ C ด้วยความได้เปรียบของ AC ในกรณีที่ทีมเหล่านี้เคยเล่นกันมาแล้ว อย่างไรก็ตาม กราฟดังกล่าวไม่ได้ตอบคำถามที่สำคัญมากข้อเดียว: ใครชนะเกมนี้กันแน่?
ข้อบกพร่องนี้สามารถกำจัดได้อย่างง่ายดาย หากทีม A ชนะ C เราตกลงที่จะวางลูกศรบนขอบ AC โดยชี้จาก A ถึง C ให้เราสมมติว่าเรารู้ผลการแข่งขันทั้งหมดที่เล่นไปแล้ว และเพิ่มรูปที่ 1 ลูกศรที่ตรงกัน 1 อัน; ให้ผลลัพธ์เป็นกราฟที่แสดงในรูป 58.

รูปที่ 58.

กราฟนี้แสดงให้เห็นว่าทีม A ชนะ C, ทีม F แพ้ A และ B ชนะทุกเกม - โดยมี C, E, F เป็นต้น

ขอบเรียกว่ากราฟ มุ่งเน้นหากพิจารณาจุดยอดจุดหนึ่ง จุดเริ่มต้นของซี่โครง, และอื่น ๆ - ตอนจบ.
กราฟที่มีขอบวางตัวทั้งหมดเรียกว่ากราฟ ปฐมนิเทศกราฟ.
จุดยอดเดียวกันของกราฟกำหนดทิศทางสามารถใช้เป็นจุดเริ่มต้นของเส้นบางเส้นและจุดสิ้นสุดของเส้นอื่นได้ ดังนั้นยอดสองระดับจึงมีความโดดเด่น: ระดับทางออกและระดับเข้า
อัตราผลตอบแทนของจุดยอด A ของกราฟกำหนดทิศทางคือจำนวนขอบที่เล็ดลอดออกมาจาก A (สัญกรณ์: d+(A))
ระดับอินพุตของจุดยอด A ของกราฟกำกับคือจำนวนองค์ประกอบใน กซี่โครง (ชื่อ: d-(A))
จะเกิดอะไรขึ้นถ้าเกมบางเกมจบลงด้วยผลเสมอ? เราสามารถสะท้อนผลการจับสลากในกราฟได้โดยการปล่อยให้ขอบที่เกี่ยวข้องไม่มีทิศทาง ในกรณีนี้เราได้รับสิ่งที่เรียกว่า เอสเอ็มอีนับร่มรื่นซึ่งมีขอบทั้งแบบมุ่งเน้นและไม่เป็นเชิง
เส้นทางในกราฟกำกับ G จาก A1 ถึง An คือลำดับของขอบเชิง<А1; А2>, <А2; А3>, ..., <Аn-1; Аn>เพื่อให้จุดสิ้นสุดของแต่ละขอบก่อนหน้าเกิดขึ้นพร้อมกับจุดเริ่มต้นของขอบถัดไป และไม่มีขอบเกิดขึ้นมากกว่าหนึ่งครั้ง

ข้าว. 59
หากในกราฟกำกับ G มีเส้นทางจาก กถึงจุด B แล้วเดินทางกลับจาก ในถึง กอาจจะไม่ (รูปที่ 59)
หากมีเส้นทางตรงจาก A ไป B แสดงว่า B เป็นเส้นทาง เข้าถึงแม่จาก,
ในคอลัมน์ G ในรูป 38 V สามารถทำได้
จาก A, A ไม่สามารถเข้าถึงได้จาก B
วิธีง่ายๆในกราฟกำกับเส้นทางจะถูกเรียกโดยไม่มีจุดยอดมากกว่าหนึ่งครั้ง เส้นทางปิดในกราฟแบบกำหนดทิศทางเรียกว่าวงจรแบบกำหนดทิศทาง
ความยาวของเส้นทางเรียกว่าจำนวนขอบในเส้นทางนี้
ระยะทางจาก A ถึง B ในกราฟกำกับคือความยาวของเส้นทางที่สั้นที่สุดจาก A ถึง B หากไม่มีเส้นทางจาก A ถึง B ระยะทางจาก A ถึง B เรียกว่าอนันต์และเขียนแทนด้วย ? เราจะแสดงระยะทางจาก A ถึง B เป็น S (AB) สำหรับกราฟในรูปที่ 38
ส (AB) = 1, ส (CB) - 2, ส (BC) = ?
ปัญหา 9.1.
ในเมืองตากอากาศริมทะเลหลังจากกำหนดการจราจรทางเดียวแล้วปรากฎว่าจำนวนถนนที่คุณสามารถเข้าไปในแต่ละทางแยกได้เท่ากับจำนวนถนนที่คุณสามารถออกไปได้ พิสูจน์ว่าสามารถเสนอเส้นทางลาดตระเวนที่เริ่มต้นและสิ้นสุดที่จุดเดียวกันและผ่านแต่ละส่วนของถนนเพียงครั้งเดียว
สารละลาย.
เรามาสร้างไดกราฟ G ที่กำหนดการเคลื่อนไหวในเมืองกันดีกว่า
ไดกราฟเรียกว่า สอดคล้องกันถ้าจากจุดยอดใดจุดหนึ่งไปยังจุดอื่นสามารถไปตามส่วนโค้งได้โดยไม่ต้องคำนึงถึงการวางแนว เรียกว่าไดกราฟที่เชื่อมต่อกัน ออยเลอร์,ถ้ามีวัฏจักรออยเลอเรียน
ทฤษฎีบท 12 แผนภาพที่เชื่อมต่อกันคือออยเลอเรียนก็ต่อเมื่อสำหรับแต่ละจุดยอดของมันโวลต์ความเท่าเทียมกันถือง- (โวลต์) = ง+ (โวลต์) .
ทฤษฎีบทได้รับการพิสูจน์ในลักษณะเดียวกับทฤษฎีบทในปัญหา 4.2 ทุกประการ
จากเงื่อนไขของปัญหา จะตามมาว่าสำหรับจุดยอดของกราฟที่สร้างขึ้น G ความเท่าเทียมกัน d-(v) = d+(v) ยังคงอยู่ ดังนั้นกราฟ Eulerian G และวงจร Eulerian จะเป็นตัวกำหนดเส้นทางลาดตระเวนที่ต้องการ
ปัญหา 9.2
มีจุดทำเครื่องหมายไว้บนเครื่องบินจำนวนจำกัด จุดบางคู่เป็นจุดเริ่มต้นและจุดสิ้นสุดของเวกเตอร์ และจำนวนเวกเตอร์ที่เข้าสู่จุดใดๆ จะเท่ากับจำนวนเวกเตอร์ที่ออกจากจุดนั้น หาผลรวมของเวกเตอร์
สารละลาย.
จุดของระนาบร่วมกับเวกเตอร์จะทำให้เกิดไดกราฟ G เรียกว่า วงจรของไดกราฟ ซึ่งจุดยอดทั้งหมดแตกต่างกัน เรียกว่า รูปร่าง
ทฤษฎีบท 13 แผนภาพที่เชื่อมต่อกันชออยเลอร์ถ้าและถ้าเท่านั้นชคือการรวมตัวกันของรูปทรงที่ในทิศทางคู่ไม่มีขอบร่วมกัน
การพิสูจน์. ความจำเป็น ให้ G เป็นกราฟแบบออยเลอเรียน พิจารณาจุดยอดใดๆ ของมันคือ u1 ปล่อยให้จุดยอด u1 ไปตามส่วนโค้ง (u1, u2) ต่อไป ซึ่งสามารถทำได้เนื่องจากไดกราฟ G เชื่อมต่ออยู่ เนื่องจาก d-(u2) = d+(u2) ดังนั้น เราสามารถออกจากจุดยอด u2 ไปตามส่วนโค้ง (u2, u3) . ไดกราฟ G มีจำนวนจุดยอดที่จำกัด ดังนั้นสุดท้ายแล้วเราจะไปสิ้นสุดที่จุดยอดที่เราอยู่เดิม ส่วนของห่วงโซ่ที่เริ่มต้นและสิ้นสุดที่จุดยอด w คือเส้นขอบ C1 ลองลบส่วนโค้งของรูปร่าง C1 ออกจาก digraph G . ในกราฟผลลัพธ์ G1 (อาจถูกตัดการเชื่อมต่อ) องศาการเข้าและออกของจุดยอดที่เป็นของ C ลดลงหนึ่งองศา องศาการเข้าและออกของจุดยอดที่เหลือไม่เปลี่ยนแปลง ดังนั้น สำหรับจุดยอด v ใดๆ ของไดกราฟ C1 ความเท่าเทียมกัน d-(v) = d+(v) จะคงอยู่ ดังนั้นในไดกราฟ G1 เราสามารถเลือกเส้นขอบ C ได้ 2 ฯลฯ
ความเพียงพอได้รับการพิสูจน์โดยการรวมโครงร่างเข้ากับวัฏจักรออยเลอเรียน (ดูการพิสูจน์ทฤษฎีบทในปัญหา 4.2)
ทฤษฎีบทได้รับการพิสูจน์แล้ว เป็นไปได้ว่าไดกราฟ G ที่กำหนดเวกเตอร์ในปัญหาของเราไม่ได้เชื่อมโยงกัน เมื่อใช้ทฤษฎีบทที่พิสูจน์แล้วกับแต่ละส่วนที่เชื่อมต่อกันของไดกราฟ เราจะได้พาร์ติชั่นของเวกเตอร์เป็นรูปทรง ผลรวมของเวกเตอร์ที่อยู่ในเส้นชั้นความสูงหนึ่งมีค่าเท่ากับศูนย์ ดังนั้นผลรวมของเวกเตอร์ทั้งหมดจึงเป็นศูนย์

กราฟกำกับ(สั้น ๆ ดิกราฟ) - (หลาย) กราฟที่มีขอบกำหนดทิศทาง ขอบทิศทางเรียกอีกอย่างว่า ส่วนโค้งและในบางแหล่งก็เป็นเพียงซี่โครง กราฟที่ไม่มีการกำหนดทิศทางของขอบ เรียกว่า กราฟไม่มีทิศทาง หรือ ไม่ใช่ไดกราฟ.

แนวคิดพื้นฐาน

อย่างเป็นทางการ, ดิกราฟ D = (V , E) (\displaystyle D=(V,E))ประกอบด้วยมากมาย วี (\displaystyle V)ซึ่งเรียกว่าธาตุต่างๆ ยอดเขาและชุด E (\displaystyle E)สั่งจุดยอดคู่ u , v ∈ V (\displaystyle u,v\in V).

อาร์ค (u , v) (\displaystyle (u,v)) บังเอิญยอดเขา คุณ (\displaystyle คุณ)และ โวลต์ (\displaystyle โวลต์). ขณะเดียวกันพวกเขาก็พูดอย่างนั้น คุณ (\displaystyle คุณ) - จุดสุดยอดเริ่มต้นส่วนโค้งและ โวลต์ (\displaystyle โวลต์) - จุดสูงสุดสุดท้าย.

การเชื่อมต่อ

เส้นทางใน digraph คือลำดับสลับกันของจุดยอดและ ส่วนโค้ง, พิมพ์ วี 0 ( วี 0 , วี 1 ) วี 1 ( วี 1 , วี 2 ) วี 2 . . v n (\รูปแบบการแสดงผล v_(0)\(v_(0),v_(1)\)v_(1)\(v_(1),v_(2)\)v_(2)...v_(n))(จุดยอดอาจซ้ำกัน) ความยาวเส้นทาง- จำนวนส่วนโค้งในนั้น

เส้นทางมี เส้นทางใน digraph โดยไม่มีส่วนโค้งซ้ำ วิธีง่ายๆ- ไม่มีจุดยอดซ้ำ หากมีเส้นทางจากจุดยอดหนึ่งไปยังอีกจุดหนึ่ง ดังนั้นจุดยอดที่สอง ทำได้ตั้งแต่ครั้งแรก

เซอร์กิตมีอันปิดอยู่ เส้นทาง.

สำหรับ ครึ่งทางข้อจำกัดในทิศทางของส่วนโค้งจะถูกลบออก และ ครึ่งทางและ ครึ่งวงจร.

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

ขีดสุด แข็งแกร่งเรียกว่ากราฟย่อย องค์ประกอบที่แข็งแกร่ง; ส่วนประกอบด้านเดียวและ องค์ประกอบที่อ่อนแอถูกกำหนดไว้เหมือนกัน

การควบแน่นดิกราฟ D (\displaystyle D)เรียกว่าไดกราฟซึ่งมีจุดยอดเป็นส่วนประกอบที่แข็งแกร่ง D (\displaystyle D)และส่วนโค้งเข้า D ⋆ (\displaystyle D^(\star ))แสดงการมีส่วนโค้งอย่างน้อยหนึ่งส่วนระหว่างจุดยอดที่รวมอยู่ในส่วนประกอบที่เกี่ยวข้อง

คำจำกัดความเพิ่มเติม

กราฟอะไซคลิกกำกับหรือ เปลญวนมีไดกราฟที่ไม่ใช่คอนทัวร์

เรียกว่ากราฟกำกับที่ได้รับจากกราฟที่กำหนดโดยการเปลี่ยนทิศทางของขอบไปในทางตรงกันข้าม ย้อนกลับ.

รูปภาพและคุณสมบัติของไดกราฟทั้งหมดที่มีสามโหนด

ตำนาน: กับ- อ่อนแอ, ระบบปฏิบัติการ- ด้านเดียว เอสเอส- แข็งแกร่ง, เอ็น- เป็นกราฟกำกับ ช- เป็นเปลญวน (ไม่หมุนเวียน) ต- เป็นทัวร์นาเมนต์

0 ส่วนโค้ง	1 ส่วนโค้ง	2 ส่วนโค้ง	3 ส่วนโค้ง	4 ส่วนโค้ง	5 ส่วนโค้ง	6 ส่วนโค้ง
ว่างเปล่า, N, G	เอ็น, จี		ระบบปฏิบัติการ	ซีซี	ซีซี	เต็มซีซี
		ระบบปฏิบัติการ, เอ็น, จี	ซีซี, เอ็น, ที	ซีซี
		ซี เอ็น จี	OS, N, G, T	ระบบปฏิบัติการ
		ซี เอ็น จี	ระบบปฏิบัติการ

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

แน่นอนว่าเป็นการสมัครเข้าร่วมทัวร์นาเมนท์ ตัวอย่างเช่น ลูกศรเปลี่ยนจากทีมที่แพ้ไปยังทีมที่ชนะ ดังนั้นกราฟที่กำหนดทิศทางจึงไม่เพียงแต่แสดงเพียงใครเล่นเท่านั้น แต่ยังรวมถึงผู้ชนะด้วย

คุณยังสามารถกำหนดความสัมพันธ์ต่อไปนี้หรือการกำหนดลักษณะด้วยกราฟกำกับได้

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

ตัวอย่างเช่น ในการประเมินตัวอย่างที่ซับซ้อน (เช่น ในด้านธรณีวิทยา) ทิศทางของขอบบ่งบอกถึงความชอบ ไม่ควรมีรอบในระบบการตั้งค่าปกติ

ทันย่า นาตาชา

เพื่อให้คุณสามารถเลือกได้ตลอดเวลา ไม่เช่นนั้นจำเป็นต้องพิจารณาระบบการตั้งค่าอีกครั้ง

ทางเดียว.

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

คำถามคือภายใต้เงื่อนไขใดที่ถนนในเมืองสามารถกำหนดทิศทางในลักษณะที่สามารถขับรถจากจุดหนึ่งไปยังอีกจุดหนึ่งได้โดยไม่ละเมิดกฎจราจรบนถนน

ในภาษาของทฤษฎีกราฟมีสูตรดังนี้: ขอบของกราฟ G สามารถวางแนวภายใต้เงื่อนไขใดเพื่อว่าสำหรับจุดยอดคู่ใด ๆ จะมีสายโซ่เชิงเชื่อมโยงเข้าด้วยกัน?

เห็นได้ชัดว่าแต่ละกราฟจะต้องเชื่อมต่อกัน แต่ยังไม่เพียงพอ

เส้นขอบ E = (A,B) จะถูกเรียก เชื่อมต่อซี่โครง, หรือ คอคอดหากเป็นเส้นทางเดียวจาก A ถึง B (หรือกลับกัน)

ขอบที่เชื่อมต่อกันแบ่งจุดยอดทั้งหมดของกราฟออกเป็นสองชุด: ชุดที่สามารถเข้าถึงได้จาก A โดยไม่ผ่านขอบ E และชุดที่สามารถเข้าถึงได้จาก B โดยไม่ผ่าน E กราฟในกรณีนี้ประกอบด้วยสองส่วน G 1 และ G 2 เชื่อมต่อกันด้วยขอบ E เท่านั้น (รูปที่ a และ a+1)

บนแผนที่เมือง ขอบที่เชื่อมต่อกันเป็นทางหลวงสายเดียวที่เชื่อมต่อแต่ละส่วนของเมือง เป็นที่แน่ชัดว่าหากทางหลวงดังกล่าวมีการจราจรแบบเดินรถทางเดียว ก็จะไม่มีทางผ่านจากส่วนใดส่วนหนึ่งของเมืองไปยังอีกส่วนหนึ่งได้

หากขอบ E i = (A i, B i) ไม่ได้เชื่อมต่อกัน แสดงว่ามีเส้นทางอื่นที่เชื่อมต่อ A i และ B i และไม่ผ่านไปตาม E i ดังนั้นเราจะเรียกขอบดังกล่าวว่าขอบแบบวงกลม

รูปที่ 2 การผูกรูปที่ 2+1 สุดท้าย (เชื่อมโยง) รูปที่ 2+2 วงจร

ซี่โครงซี่โครง

ทฤษฎีบท 1 ถ้า จี- กราฟที่เชื่อมต่อแบบไม่มีทิศทาง จึงสามารถกำหนดทิศทางของขอบแบบวนรอบได้เสมอ ช โดยปล่อยให้ขอบที่เชื่อมต่อไม่มีทิศทางเพื่อให้จุดยอดคู่ใดๆ ในกราฟนี้สามารถเชื่อมต่อกันด้วยเส้นทางที่มีการกำหนดทิศทาง

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

เราสามารถพิสูจน์ทฤษฎีบทนี้ได้โดยระบุวิธีการวางแนวกราฟอย่างเหมาะสม เรามาเลือกกันได้เลย ช ขอบโดยพลการ จ = (ก,ข) . ถ้า อี - ขอบที่เชื่อมต่อจะยังคงอยู่สองด้านจากนั้นจึงจะสามารถเคลื่อนตัวออกได้ ก ถึง ใน และในทางกลับกัน (รูปที่ 2+3)

รูปที่.2+3 รูปที่. 2+4

ถ้า อี เป็นขอบวงจรแล้วรวมไว้ในบางรอบด้วย กับ, ซึ่งคุณสามารถตั้งค่าการวางแนวแบบวนได้ (รูปที่ 2+4)

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

ถ้า อี - การเชื่อมต่อซี่โครง เอบี จากนั้นมันจะยังคงเป็นสองด้าน แล้วสำหรับจุดยอดใดๆ เอ็กซ์ กราฟ เอ็น คุณจะพบห่วงโซ่ที่มุ่งเน้น ร กำลังเชื่อมต่อ X กับ A ซึ่งหมายถึง (ผ่านขอบ อี ) และด้วย ใน . กลับจากด้านบน ใน ผ่านขอบ อี คุณสามารถไปที่ ก แล้วตามห่วงโซ่โดยประมาณ ซี - จาก ก ถึง เอ็กซ์ (รูปที่ก+5) การแนบ อี ถึง ชม เราก็จะได้กราฟส่วนใหญ่แล้ว ช มีคุณสมบัติที่ต้องการ ถ้าขอบ อี= (ก,บี) เป็นวงจร มันเป็นของวงจรบางวงจร กับ . เราได้กำหนดทิศทางไว้แล้ว กับ จาก ก ก่อน ใน และต่อไป กับ สู่ยอดเขาแรก ดี จาก กับ ที่เป็นเจ้าของโดย เอ็น (รูปที่ ก+6).

ข้าว. รูป a+5 ก+6

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

องศาจุดยอด

สำหรับกราฟกำหนดทิศทาง เรามีหมายเลข p(A) ของขอบที่ส่งออกที่แต่ละจุดยอด และหมายเลข p * (A) ของขอบที่เข้า จำนวนขอบทั้งหมดคือ:

N = p(A 1) + p(A 2) +... + p(A n) = p * (A 1)+p * (A 2)+...+p * (A n)

กราฟมีหลายประเภทซึ่งองศาของจุดยอดมีคุณสมบัติพิเศษบางประการ เรียกว่ากราฟ เป็นเนื้อเดียวกันถ้าองศาของจุดยอดทั้งหมดเท่ากับจำนวน r เท่ากัน: สำหรับแต่ละจุดยอด A:

พี(A) = พี * (A) = ร

ออกกำลังกาย

สร้างกราฟกำกับที่เป็นเนื้อเดียวกันของระดับ r = 2 ด้วยจำนวนจุดยอด n = 2,6,7,8

ความสัมพันธ์.

ความสัมพันธ์และกราฟ

ระบบทางคณิตศาสตร์ทุกระบบเกี่ยวข้องกับวัตถุหรือองค์ประกอบจำนวนหนึ่ง (สัญลักษณ์: พีชคณิต, เรขาคณิต)

ในการสร้างทฤษฎีทางคณิตศาสตร์ เราไม่เพียงต้องการองค์ประกอบเหล่านี้เท่านั้น แต่ยังจำเป็นต้องมีองค์ประกอบเหล่านี้ด้วย ความสัมพันธ์ระหว่างพวกเขา. (ตัวอย่าง: สำหรับตัวเลข a > b; ในเรขาคณิต - ความเท่าเทียมกันของสามเหลี่ยม, // เส้นตรง; ในทฤษฎีเซต - ความเท่าเทียมกันและการรวมเซต)

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

ให้เราแนะนำคำจำกัดความทั่วไปของความสัมพันธ์ไบนารี R: аRв - в อยู่ในความสัมพันธ์ของ R กับ а

ตัวอย่างเช่น ความสัมพันธ์ a > b หมายความว่า b อยู่ในเซตของจำนวนทั้งหมดที่น้อยกว่า a

ในความเป็นจริง กราฟกำกับทุกกราฟ G จะกำหนดความสัมพันธ์บางอย่างในชุดจุดยอดของมัน ความสัมพันธ์นี้สามารถเขียนได้ในรูปแบบ: AGв. หมายความว่ากราฟมีขอบตรงที่เริ่มจาก a ถึง b

เงื่อนไขพิเศษ.

ให้ความสัมพันธ์ R เกิดขึ้น หากองค์ประกอบ a มีความสัมพันธ์ R กับตัวเอง องค์ประกอบนั้นจะสอดคล้องกับวงวนในกราฟ

ความสัมพันธ์ R ที่เงื่อนไขเป็นไปตามที่พอใจ สำหรับข้อใดข้อหนึ่ง, เรียกว่า สะท้อนแสง.

หากเงื่อนไข аRв ไม่เป็นที่พอใจสำหรับองค์ประกอบใดๆ ระบบจะเรียก R ทัศนคติต่อต้านแสงสะท้อนในกรณีนี้ ไม่มีจุดยอดใดของกราฟที่มีการวนซ้ำ

สำหรับแต่ละความสัมพันธ์ R เราสามารถกำหนดได้ อัตราส่วนผกผัน R*โดยพิจารณาว่า aR * เข้าถ้าและเฉพาะในกรณีที่ aR เข้า

จากคำจำกัดความของความสัมพันธ์ผกผัน เป็นที่ชัดเจนว่าหากกราฟ G ที่สอดคล้องกับ R มีขอบ (a, b) ดังนั้นกราฟ G * ที่สอดคล้องกับ R * จะต้องมีขอบ (b, a) กล่าวอีกนัยหนึ่งกราฟ G * เป็นสิ่งที่ตรงกันข้ามของ G นั่นคือ กราฟที่มีขอบเดียวกันกับ G แต่มีทิศทางตรงกันข้าม

เรียกว่าความสัมพันธ์ สมมาตรถ้า aRb หมายถึง bRa

ความสัมพันธ์แบบสมมาตรสอดคล้องกับกราฟที่มีขอบไม่มีทิศทาง ในทางกลับกัน กราฟที่มีขอบไม่มีทิศทางจะกำหนดความสัมพันธ์แบบสมมาตรบางอย่าง

เรียกว่าความสัมพันธ์ ต่อต้านสมมาตรถ้ามันตามมาจาก аrв ก็เห็นได้ชัดว่าไม่เกิดขึ้นใน Rа กราฟความสัมพันธ์แบบต่อต้านสมมาตรไม่มีขอบที่ไม่มีการบอกทิศทางหรือตรงข้ามกันซึ่งเชื่อมต่อจุดยอดคู่เดียวกัน นอกจากนี้ยังไม่มีการวนซ้ำเช่น ความสัมพันธ์เหล่านี้ต่อต้านการสะท้อนกลับ

อัตราส่วน สกรรมกริยาถ้าจากสองเงื่อนไข аRв และ вRс มันจะเป็นไปตามนั้น аRc

กราฟความสัมพันธ์แบบสกรรมกริยามีคุณสมบัติเฉพาะดังต่อไปนี้: สำหรับแต่ละคู่ของขอบ (a, b), (b, c) จะมี ต่อท้ายขอบ. เมื่อใช้คุณสมบัตินี้ซ้ำๆ เราได้ข้อสรุปว่าหากมีเส้นทางเชิงบนกราฟนี้ที่เปลี่ยนจากจุดยอด X ไปยังจุดยอด Y ก็จะมีขอบเชิง (x, y) ด้วยเช่นกัน

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

ความสัมพันธ์ที่เท่าเทียมกัน

ความสัมพันธ์ที่เท่าเทียมกันซึ่งโดยปกติจะแสดงด้วยสัญลักษณ์ ~ มีลักษณะเฉพาะด้วยคุณสมบัติสามประการต่อไปนี้:

1). การสะท้อนกลับ: a ~ a;

2). สมมาตร: จาก ~ ถึงÞถึง ~ a;

3). การผ่านผ่าน: จาก ~ ในและใน ~ c Þ a ~ c

ในความเป็นจริง ความสัมพันธ์ที่เท่าเทียมกันคือการสรุปคุณสมบัติของความเท่าเทียมกัน

ความสัมพันธ์ที่เท่าเทียมกันจะแนะนำพาร์ติชั่นให้กับเซตของจุดยอด คลาสความเท่าเทียมกันที่ไม่ต่อเนื่องกัน.

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

สั่งบางส่วน.

ทัศนคติ คำสั่งบางส่วน- นี่ (ใช้ตัวอย่างชุด):

1). การสะท้อนกลับ: A É A

2). การผ่านผ่าน: ถ้า A ê B และ B ê C Þ A ê C

3). อัตลักษณ์: ถ้า A ê B และ B ê AÞ A = B

ความสัมพันธ์แบบรวมที่เข้มงวด -

1). ป้องกันแสงสะท้อน: และ ÉA ไม่เคยเกิดขึ้น

2). การผ่าน: ถ้า A É B และ B É C แล้ว A É C

ความสัมพันธ์การสั่งซื้อ(ในความหมายที่เข้มงวด) เรียกว่าการเรียงลำดับที่เข้มงวด a>b ซึ่งนอกเหนือจากเงื่อนไขก่อนหน้านี้ ยังมีสิ่งต่อไปนี้ด้วย:

สภาพความสมบูรณ์.สำหรับสมาชิก b และ a ที่ไม่ตรงกันสองตัวใดๆ ความสัมพันธ์แบบใดแบบหนึ่งคือ a>b หรือ b>a จะเป็นที่น่าพอใจเสมอ

โดยทั่วไปแล้ว กราฟการเรียงลำดับบางส่วนจะแสดงในรูปแบบการเรียงลำดับ เนื่องจากขอบใดๆ (a, b) และ (b, c) มีขอบปิด (a, c) จึงสามารถละเว้นได้

กราฟแบน

เงื่อนไขสำหรับกราฟระนาบ

กราฟ Kuratovsky K 3.3

ปัญหากราฟของบ้านสามหลังและสามบ่อ

Kuratovsky นับ K 5

กราฟทั้งสองนี้ไม่แบน!

การขยายกราฟ- มีการวางจุดยอดใหม่บนขอบบางส่วน ดังนั้นขอบเหล่านี้

กลายเป็นโซ่พื้นฐานที่ประกอบด้วยหลายขอบ

การดำเนินการย้อนกลับซึ่งจุดยอดที่แยกออกจากโซ่พื้นฐานเรียกว่า การบีบอัดกราฟ.

ทฤษฎีบทของคูราตอฟสกี้

การที่กราฟจะแบนราบนั้น จำเป็นและเพียงพอที่จะไม่มีกราฟใดๆ อยู่ภายในตัวมันเองที่สามารถบีบอัดเป็นกราฟ K 3,3 หรือกราฟ K 5 ได้

สูตรของออยเลอร์

เราจะพิจารณากราฟระนาบที่ก่อตัวบนระนาบ เครือข่ายรูปหลายเหลี่ยม. ซึ่งหมายความว่าขอบของกราฟระนาบ G ก่อให้เกิดชุดของรูปหลายเหลี่ยมที่อยู่ติดกัน โดยแบ่งระนาบออกเป็นส่วนของรูปหลายเหลี่ยม

จากคำจำกัดความของกราฟหลายเหลี่ยมจะเป็นไปตามที่กราฟทั้งสองเชื่อมโยงกัน นอกจากนี้เรายังกำหนดว่าไม่มีรูปหลายเหลี่ยมอยู่ภายในอีกรูปหนึ่ง ขอบขอบเขตของรูปหลายเหลี่ยมแต่ละอันนั้นก่อตัวเป็นวงจร ซึ่งบางครั้งเรียกว่า วงจรขั้นต่ำ. ส่วนของระนาบที่อยู่ภายในรูปหลายเหลี่ยมเรียกว่า ขอบของกราฟ. กราฟก็ประกอบด้วย รอบสูงสุด C 1ล้อมรอบกราฟทั้งหมดด้วยใบหน้าทั้งหมด เราจะพิจารณาส่วนของระนาบที่อยู่ด้านนอก C 1 เช่นเดียวกับหน้ากราฟที่มีขอบเขต C 1 - ไม่มีที่สิ้นสุดหน้า F ¥ .

ให้เราแสดงโดย

จำนวนจุดยอด ขอบ และใบหน้า รูปหลายเหลี่ยมเชิงพื้นที่.

ทฤษฎีบทของออยเลอร์

ค - พี + ​​ก = 2

การพิสูจน์:สูตรนี้ชัดเจนสำหรับรูปหลายเหลี่ยมที่มี n ขอบ อันที่จริงไม่มีจุดยอดและขอบ n เช่นเดียวกับสองหน้า F 1 F ¥

เรามาเพิ่มขอบใหม่ให้กับกราฟด้วยขอบ r โดยวาดไปตามหน้า F ¥ สายโซ่พื้นฐานที่เชื่อมต่อจุดยอดสองจุดของกราฟสูงสุด G หากส่วนโค้งนี้มีขอบ r เราจะต้องเพิ่ม r - 1 จุดยอดใหม่และอีก 1 จุด ขอบใหม่ แต่แล้ว

ค ' - p' + g ' = (c + g - 1) - (p + g) + (g + 1) = c - p + g (=2!)

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

การเป็นตัวแทนเมทริกซ์

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

ก) สำหรับกราฟที่ไม่มีทิศทาง เมทริกซ์เหตุการณ์เป็นเมทริกซ์ที่มีแถวตรงกับจุดยอดและคอลัมน์ถึงขอบ องค์ประกอบเมทริกซ์จะเท่ากับ 1 ถ้าจุดยอดตกกระทบที่ขอบ มิฉะนั้น องค์ประกอบเมทริกซ์จะใช้ค่า 0

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

2. เมทริกซ์ของรอบ C

ก) สำหรับกราฟที่ไม่มีทิศทาง แถวของเมทริกซ์วงจรจะสัมพันธ์กับวงจรอย่างง่ายของกราฟ และคอลัมน์จะสัมพันธ์กับขอบของกราฟ องค์ประกอบเมทริกซ์ a ij =1 ถ้าวงจร C i มีขอบ e j มิฉะนั้น ij =0

ข) สำหรับกราฟกำหนดทิศทาง a ij =1, -1 หรือ 0 ขึ้นอยู่กับว่าการวางแนวของวงรอบ C i และส่วนโค้ง e j นั้นเหมือนกันหรือตรงกันข้าม หรือวงรอบที่กำหนดไม่มีส่วนโค้ง e j เลยหรือไม่

3. เมทริกซ์ adjacency ของจุดยอด (หรือเพียงแค่เมทริกซ์ adjacency) V เป็นเมทริกซ์ที่มีแถวและคอลัมน์สอดคล้องกับจุดยอด และองค์ประกอบเมทริกซ์ a ij ในกรณีของกราฟที่ไม่มีทิศทางจะเท่ากับจำนวนขอบที่เชื่อมต่อจุดยอด i และ เจ สำหรับกราฟกำหนดทิศทาง องค์ประกอบ a ij เท่ากับจำนวนขอบที่พุ่งจากจุดยอด i ถึงจุดยอด j

ทฤษฎีบทพื้นฐานที่เกี่ยวข้องกับการแสดงเมทริกซ์ของกราฟ

1) อันดับ (จำนวนสูงสุดของคอลัมน์อิสระเชิงเส้น) ของเมทริกซ์อุบัติการณ์ A ของกราฟที่เชื่อมต่อ (แบบมีทิศทางและแบบไม่มีทิศทาง) ที่มีจุดยอด n เท่ากับ (n-1)

2). ลำดับของเมทริกซ์วงจร C ของกราฟที่เชื่อมต่อกับขอบ m และจุดยอด n คือ (m-n+1)

ตัวอย่างการใช้เมทริกซ์คำคุณศัพท์

การแม็ปต่อไปนี้แสดงให้เห็นว่ากราฟ G 1 และ G 2 เป็น isomorphic

เมทริกซ์ที่อยู่ติดกันเกี่ยวข้องกับการเรียงสับเปลี่ยนแถวและคอลัมน์พร้อมกัน ซึ่งสามารถทำได้โดยใช้การแปลงความคล้ายคลึงและเมทริกซ์การเรียงสับเปลี่ยน

A 2 =PA 1 P" โดยที่

พ = หรือ p ij =d p(i),j (สัญลักษณ์โครเนกเกอร์)

และ P" คือเมทริกซ์ทรานสโพส

การค้นหาเมทริกซ์ P อาจเป็นเรื่องยาก

มอร์ฟิซึมของ G 1 และ G 2 หมายความว่า A 1 และ A 2 มีค่าลักษณะเฉพาะที่เหมือนกัน อย่างไรก็ตาม เงื่อนไขนี้ไม่เพียงพอ (ตัวอย่างด้านล่าง)