เครื่องตรวจสอบลำดับดีกรีของกราฟ

ลำดับดีกรีเหล่านี้เป็นกราฟไม่มีทิศทางอย่างง่ายได้หรือไม่? เครื่องตรวจสอบลำดับดีกรีของกราฟของ MiniWebtool ใช้อัลกอริทึม Havel–Hakimi แสดงการลดรูปแต่ละขั้น และสร้างตัวอย่างกราฟกับเมทริกซ์ประชิดเมื่อสร้างกราฟจากลำดับนั้นได้

ใช้ฟรีวันละ 3 ครั้งไม่ต้องสมัครสมาชิกผลลัพธ์ทันที

เครื่องตรวจสอบลำดับดีกรีของกราฟลองใช้เลย — ฟรี ▼

Havel-Hakimi: ตัดดีกรีที่มากที่สุด d ออก แล้วลบ 1 จากดีกรีถัดไป d ค่า

ป้อนลำดับดีกรีด้านล่างเพื่อดูว่ากราฟเรียบง่ายสามารถมีลำดับนี้ได้หรือไม่ พร้อมแต่ละขั้นตอนและกราฟตัวอย่าง

Embed เครื่องตรวจสอบลำดับดีกรีของกราฟ Widget

เกี่ยวกับ เครื่องตรวจสอบลำดับดีกรีของกราฟ

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

ลำดับดีกรีคืออะไร?

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

ลำดับดีกรีจะถูกเรียกว่า graphical หากมีกราฟอย่างง่ายอย่างน้อยหนึ่งกราฟ (ไม่มีวงวนในตัว, ไม่มีเส้นเชื่อมซ้ำ) ที่มีดีกรีจุดยอดตรงกับลำดับนั้น ไม่ใช่ทุกลำดับของจำนวนเต็มไม่เป็นลบจะเป็น graphical ตัวอย่างเช่น (3, 1, 1) ไม่เป็น graphical เพราะจุดยอดหนึ่งจุดต้องมีการเชื่อมต่อ 3 เส้นแต่มีจุดยอดอื่นเหลืออยู่เพียง 2 จุด

อัลกอริทึม Havel-Hakimi

อัลกอริทึม Havel-Hakimi (ตั้งชื่อตาม Václav Havel และ Samuel Louis Hakimi) เป็นอัลกอริทึมแบบเรียกซ้ำที่ใช้ตรวจสอบว่าลำดับจำกัดของจำนวนเต็มไม่เป็นลบที่กำหนดให้นั้นเป็น graphical หรือไม่ เป็นหนึ่งในอัลกอริทึมที่สง่างามที่สุดในคณิตศาสตร์แบบไม่ต่อเนื่อง

ขั้นตอนของอัลกอริทึม

function HavelHakimi(sequence):
  while sequence is not empty:
    เรียงลำดับ sequence จากมากไปน้อย
    ลบเลขศูนย์ที่อยู่ข้างหน้าออก
    if sequence ว่าง: return GRAPHICAL
    d ← องค์ประกอบแรก // ดีกรีที่มากที่สุด
    ลบองค์ประกอบแรกออก
    if d > จำนวนที่เหลืออยู่: return NOT GRAPHICAL
    ลบ 1 ออกจาก d องค์ประกอบถัดไปแต่ละตัว
    if มีองค์ประกอบใดเป็นลบ: return NOT GRAPHICAL
  return GRAPHICAL

ทฤษฎีบท Havel-Hakimi

สำหรับ $ n \geq 1 $ ลำดับแบบไม่เพิ่ม $ d_1 \geq d_2 \geq \cdots \geq d_n $ ของจำนวนเต็มไม่เป็นลบจะเป็น graphical ก็ต่อเมื่อ ลำดับ

$$d_2 - 1,\; d_3 - 1,\; \ldots,\; d_{d_1+1} - 1,\; d_{d_1+2},\; \ldots,\; d_n$$

เป็น graphical

Handshaking Lemma (บทนิยามการจับมือ)

ข้อกำหนดเบื้องต้นพื้นฐานสำหรับลำดับดีกรีใดๆ คือ Handshaking Lemma:

Handshaking Lemma

$$\sum_{i=1}^{n} d_i = 2|E|$$

ผลรวมของดีกรีจุดยอดทั้งหมดจะเท่ากับสองเท่าของจำนวนเส้นเชื่อม

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

ทฤษฎีบท Erdos-Gallai

อีกหนึ่งการระบุลักษณะของลำดับ graphical คือ ทฤษฎีบท Erdős–Gallai:

ทฤษฎีบท Erdős–Gallai

ลำดับแบบไม่เพิ่ม $ d_1 \geq d_2 \geq \cdots \geq d_n $ จะเป็น graphical ก็ต่อเมื่อผลรวมเป็นเลขคู่ และสำหรับแต่ละ $ k = 1, 2, \ldots, n $:

$$\sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{i=k+1}^{n} \min(d_i, k)$$

แม้ว่าทฤษฎีบท Erdős–Gallai จะให้การระบุลักษณะในรูปแบบปิด แต่อัลกอริทึม Havel-Hakimi มักถูกเลือกใช้ในทางปฏิบัติมากกว่าเนื่องจากความเรียบง่ายและข้อเท็จจริงที่ว่ามันสร้างกราฟขึ้นมาให้เห็นได้จริง

วิธีใช้เครื่องมือนี้

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

ทำความเข้าใจกับผลลัพธ์

คำตัดสิน (Verdict): ลำดับนั้นเป็น graphical (สามารถสร้างกราฟอย่างง่ายได้) หรือไม่
ตรวจสอบพาริตี (Parity Check): ผลรวมของดีกรีเป็นเลขคู่หรือไม่ (เงื่อนไขที่จำเป็น)
ขั้นตอนของอัลกอริทึม: การวนซ้ำแต่ละรอบของ Havel-Hakimi พร้อมการติดตามองค์ประกอบด้วยรหัสสี
การแสดงผลกราฟ: กราฟอย่างง่ายตัวอย่างที่สอดคล้องกับลำดับดีกรี (หากเป็น graphical)
เมทริกซ์ประชิด: การแสดงผลเมทริกซ์ 0/1 ของกราฟตัวอย่าง

การประยุกต์ใช้ลำดับดีกรี

การออกแบบเครือข่าย

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

การวิเคราะห์เครือข่ายสังคม

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

ชีวสารสนเทศศาสตร์

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

การศึกษาด้านการออกแบบอัลกอริทึม

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

คำถามที่พบบ่อย

ลำดับดีกรีในทฤษฎีกราฟคืออะไร?

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

อัลกอริทึม Havel-Hakimi คืออะไร?

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

การที่ลำดับเป็น graphical หมายถึงอะไร?

ลำดับของจำนวนเต็มไม่เป็นลบเรียกว่า graphical หากมีกราฟอย่างง่ายแบบไม่มีทิศทาง (ไม่มีวงวนในตัว, ไม่มีเส้นเชื่อมซ้ำ) ซึ่งจุดยอดมีดีกรีตรงตามลำดับเหล่านั้นพอดี ตัวอย่างเช่น (2, 2, 2) เป็น graphical เพราะสามารถสร้างรูปสามเหลี่ยมได้ ในขณะที่ (3, 1, 1) ไม่เป็น graphical เพราะจุดยอดเดียวไม่สามารถเชื่อมต่อกับจุดยอดอื่นอีก 3 จุดได้เมื่อมีจุดยอดอื่นเหลืออยู่เพียง 2 จุด

ทำไมผลรวมของลำดับดีกรีต้องเป็นเลขคู่?

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

ทฤษฎีบท Erdos-Gallai คืออะไร?

ทฤษฎีบท Erdős-Gallai ให้ชุดของอสมการที่ลำดับไม่เพิ่มของจำนวนเต็มไม่เป็นลบต้องสอดคล้องเพื่อให้เป็น graphical ลำดับ d1 >= d2 >= ... >= dn จะเป็น graphical ก็ต่อเมื่อผลรวมเป็นเลขคู่ และสำหรับแต่ละ k จาก 1 ถึง n ผลรวมของ k พจน์แรกต้องไม่เกิน k(k-1) บวกกับผลรวมของ min(dk, k) ของพจน์ที่เหลือ อัลกอริทึม Havel-Hakimi มักถูกเลือกใช้ในทางปฏิบัติมากกว่าเพราะนำไปใช้ได้ง่ายกว่า

แหล่งข้อมูลเพิ่มเติม

อ้างอิงเนื้อหา หน้าหรือเครื่องมือนี้ว่า:

"เครื่องตรวจสอบลำดับดีกรีของกราฟ" ที่ https://MiniWebtool.com/th/เครื่องตรวจสอบลำดับดีกรีของกราฟ/ จาก MiniWebtool, https://MiniWebtool.com/

โดยทีมงาน miniwebtool อัปเดตเมื่อ: 19 ก.พ. 2026

มี Developer API ให้ใช้งาน: เรียกใช้เครื่องมือนี้จากแอป ระบบอัตโนมัติ หรือเอเจนต์ของคุณด้วยคำขอ JSON HTTP หนึ่งครั้ง ดูเอกสาร API