ทฤษฎีกราฟคืออะไร และกราฟกำหนดไว้อย่างไร

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

ใบเสนอราคา (APA)

อเล็กซานเดอร์ บาร์ราซ่า | ก.ค. 2022
ปริญญาฟิสิกส์

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

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

ปัญหาสะพานทั้งเจ็ดแห่งKönigsberg

ออยเลอร์จำลองKönigsbergเป็นกราฟโดยที่แต่ละจุด (จุดยอดหรือโหนด) แสดงถึงสะพานและแต่ละเส้น (ขอบ) เป็นเส้นทางบนบก:

วิธีแก้ปัญหานี้คืออะไร?

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

กราฟออยเลอเรียนหรือวิถีออยเลอเรียน?

กราฟต่อไปนี้ทั้งหมดมีเส้นทางแบบออยเลอร์ _[5]. พวกเขาทั้งหมดมีวัฏจักรออยเลอร์หรือไม่?

ลองใช้กราฟที่สาม:

ลองนับจุดยอด:

เราจะเห็นว่าเส้นทางที่กำหนดโดยลำดับ {3,4,6,2,1,3,7,6,5,4,2} เป็นเส้นทางออยเลอร์เนื่องจาก มันผ่านกราฟทั้งหมดโดยไม่มีขอบซ้ำ แต่มันไม่ใช่วัฏจักรออยเลอร์ เนื่องจากมันไปไม่ถึงจุดเริ่มต้น จะเกิดอะไรขึ้นถ้าเรานับจุดยอดต่างกัน? ไม่มาก ยกเว้นว่าตอนนี้เส้นทางจะถูกกำหนดโดยลำดับที่แตกต่างกัน จะเกิดอะไรขึ้นหากเราเดินตามเส้นทางที่แตกต่างจากที่เสนอในวิธีแก้ปัญหาเบื้องต้นของเรา คำถามนี้ซับซ้อนกว่าที่จะตอบเล็กน้อย และเกี่ยวข้องกับอัลกอริทึมที่วิศวกรซอฟต์แวร์มักจะพึงพอใจ การเขียนโปรแกรม.

สำหรับหลักฐานที่เข้มงวดยิ่งขึ้นของสิ่งที่เปิดเผยที่นี่ เราต้องอ้างอิงผลลัพธ์ต่อไปนี้:

"เป็น จี กราฟที่เกี่ยวโยงกัน _[6]. แล้วใช่ จี มี วงจร ออยเลอร์ ดีกรีของจุดยอดแต่ละอันจะเท่ากัน ในขณะที่ if จี มีเส้นทางออยเลอร์, G มีจุดยอดสองจุดของดีกรีคี่ _[7] (จุดยอดตรงที่เส้นทางเริ่มต้นและสิ้นสุด)".

จากนั้นเราสามารถตรวจสอบได้ว่า อันที่จริง ในกราฟที่เราหามานั้น มีเพียงจุดยอด 3 และ 6 เท่านั้นที่มีดีกรีคี่ (นี่ จะเกิดขึ้นแม้ว่าจำนวนจุดยอดจะต่างกัน) ดังนั้น กราฟดังกล่าวจึงมีเส้นทาง eulerian _[8]. สำหรับกราฟที่เหลือ เราสามารถดำเนินการในลักษณะที่คล้ายคลึงกันและตรวจสอบว่ามีเส้นทางจริงหรือไม่และ วัฏจักรออยเลอร์หรือพูดอีกอย่างหนึ่งคือเราสามารถวาดกราฟดังกล่าวโดยไม่ต้องหยิบดินสอแล้วทำซ้ำ เส้น? คำตอบของคำถามนี้สามารถอนุมานได้จากสิ่งที่ได้อธิบายไปแล้ว อย่างไรก็ตาม ถือเป็นแบบฝึกหัด น่าสนใจในด้านทักษะยนต์ปรับ ความเฉลียวฉลาด และความอดทน ผมขอเชิญชวนผู้อ่านให้ค้นหาและวาดกราฟตั้งแต่ 6 ขึ้นไป จุดยอดด้วย วิถี ออยเลอเรียน

มีกราฟประเภทอื่นหรือไม่? ทฤษฎีกราฟมีการใช้งานในโลกแห่ง 'ของจริง' หรือไม่?

กราฟเหล่านี้ที่เราตรวจสอบอย่างสั้น ๆ เป็นเพียงหนึ่งในกราฟหลายประเภทที่เราพบในทฤษฎีกราฟ นอกจากนี้เรายังสามารถค้นหากราฟ เช่น ต้นไม้ ตัวแทนในชุดที่องค์ประกอบสามารถจำแนกเป็นลำดับชั้นและในการคำนวณการนับและ ความน่าจะเป็น_[9], ไดกราฟ, กราฟแฮมิลตัน _[10]ฯลฯ

รูปภาพของโมเดลกราฟิกและเครือข่ายใน Psycho. โดย Ruiz, Ana María

ปริศนาเหล่านี้ ถ้าเราต้องการเรียกมันว่า มีความเกี่ยวข้องอย่างมากในโลกปัจจุบัน ในสถานการณ์ที่หลากหลายเช่น: ชีววิทยา โมเลกุล _[11], การคำนวณ_[12], โทรคมนาคม _[13] และการวิเคราะห์เครือข่าย _[14]. ถ้าอย่างนั้นก็ควรที่จะถาม: อย่างน้อยก็น่าสงสัยไม่ใช่หรือว่าปัญหาของเกือบ ซ้ำซากจำเจ จะจบลงด้วยการเป็นหนึ่งในผลลัพธ์ทางคณิตศาสตร์ที่น่าสนใจและชัดเจนที่สุดหรือไม่? บางทีสำหรับเรื่องนี้ การมีส่วนร่วมของหนึ่งในจิตใจที่โด่งดังที่สุดของมนุษยชาติก็เป็นสิ่งจำเป็น