สรุปเนื้อหาโครงสร้างการคำนวณเชิงไม่ต่อเนื่อง

นิยามของกราฟ: กราฟ G(V, E) ประกอบด้วยเซตของจุดยอด (Vertices: V) และเซตของเส้นเชื่อม (Edges: E) ที่เชื่อมระหว่างจุดยอด

• ประเภทของกราฟ:
  • กราฟเชิงเดี่ยว (Simple Graph): ไม่มีเส้นเชื่อมขนาน และไม่มีเส้นเชื่อมบ่วง (Loop)
  • กราฟหลายเชิง (Multigraph): อนุญาตให้มีเส้นเชื่อมขนานระหว่างคู่จุดยอดเดียวกัน
  • กราฟเทียม (Pseudograph): อนุญาตให้มีทั้งเส้นเชื่อมขนานและเส้นเชื่อมบ่วง (Loop)
• ดีกรีของจุดยอด (Degree: deg(v)): จำนวนเส้นเชื่อมที่มาตกกระทบกับจุดยอดนั้น (บ่วงนับดีกรีเพิ่ม 2)
• ทฤษฎีบทมือจับมือ (Handshaking Lemma): ผลรวมดีกรีของทุกจุดยอดในกราฟจะมีค่าเท่ากับ 2 เท่าของจำนวนเส้นเชื่อมเสมอ (∑ deg(v) = 2|E|) ส่งผลให้จำนวนจุดยอดที่มีดีกรีเป็นจำนวนคี่ ต้องมีจำนวนเป็น จำนวนคู่ เสมอ

• ทางเดิน (Walk): ลำดับสลับระหว่างจุดยอดและเส้นเชื่อม
• รอยเดิน (Trail): ทางเดินที่เส้นเชื่อมทุกเส้น ไม่ซ้ำกัน
• วิถี (Path): ทางเดินที่จุดยอดทุกจุด ไม่ซ้ำกัน
• วัฏจักรออยเลอร์ (Eulerian Circuit): รอยเดินปิดที่ผ่านเส้นเชื่อมทุกเส้นในกราฟเพียงครั้งเดียวแล้วกลับมาจุดเริ่มต้น
  → เงื่อนไข: กราฟเชื่อมโยง และ ทุกจุดยอดมีดีกรีเป็นจำนวนคู่
• รอยเดินออยเลอร์ (Eulerian Trail): รอยเดินที่ผ่านเส้นเชื่อมทุกเส้นในกราฟเพียงครั้งเดียวโดยจุดเริ่มและจุดจบต่างกัน
  → เงื่อนไข: กราฟเชื่อมโยง และ มีจุดยอดดีกรีคี่พอดี 2 จุด (เริ่มที่จุดคี่หนึ่ง ไปจบอีกจุดคี่หนึ่ง)
• กรณีมีจุดคี่ > 2 จุด: ไม่มีทั้งวัฏจักรและรอยเดินออยเลอร์ ต้องเพิ่มเส้นเชื่อมอย่างน้อย (จำนวนจุดคี่ ÷ 2) เส้น

• วงจรแฮมิลตัน (Hamiltonian Circuit): วงจรที่ผ่านจุดยอดทุกจุดในกราฟ พอดีครั้งเดียว แล้วกลับมายังจุดเริ่มต้น
• ทฤษฎีบทของดิเรค (Dirac's Theorem): กราฟเชิงเดี่ยวที่มี n ≥ 3 จุดยอด ถ้าทุกจุดยอดมีดีกรี deg(v) ≥ n/2 แล้วกราฟนั้นจะมีวงจรแฮมิลตัน (เป็นเงื่อนไขเพียงพอ แต่ไม่จำเป็น)
• กฎการสร้างวงจรแฮมิลตัน:
  1. จุดยอดที่มีดีกรี 2 เส้นเชื่อมทั้งสองต้องถูกเลือกอยู่ในวงจรเสมอ
  2. ห้ามสร้างวงจรย่อย (Sub-circuit) ที่ปิดลูปก่อนจะผ่านครบทุกจุดยอด
  3. เมื่อจุดยอดใดเลือกเส้นเชื่อมครบ 2 เส้นแล้ว ให้ตัดเส้นเชื่อมที่เหลือที่ตกกระทบจุดนั้นทิ้ง

• ต้นไม้ (Tree): กราฟเชื่อมโยงที่ ไม่มีวงจร (Acyclic) โดยกราฟต้นไม้ขนาด n จุดยอด จะมีเส้นเชื่อม e = n - 1 เส้นเสมอ
• จำนวนวงจรอิสระ (Fundamental Cycles): สำหรับกราฟที่มี n จุดยอด, e เส้นเชื่อม และ c ส่วนประกอบที่เชื่อมโยงกัน จำนวนวงจรอิสระจะเท่ากับ μ = e - n + c (ถ้า μ = 0 แสดงว่าไม่มีวงจร)
• เส้นสะพาน (Bridge / Cut-edge): เส้นเชื่อมที่หากลบออกแล้วจะทำให้จำนวนส่วนประกอบที่เชื่อมโยง (c) เพิ่มขึ้น (เส้นเชื่อมที่เป็นสะพานจะไม่ไม่อยู่บนวงจรใดๆ)

ต้นไม้ทอดข้าม (Spanning Tree): กราฟย่อยที่เป็นต้นไม้และครอบคลุมจุดยอดทุกจุดของกราฟ

• อัลกอริทึมของครูสกัล (Kruskal's Algorithm):
  เรียงลำดับเส้นเชื่อมตามน้ำหนักจากน้อยไปมาก พิจารณาเลือกทีละเส้น โดยเลือกเส้นที่ ไม่ทำให้เกิดวงจร (ปลายทั้งสองอยู่นอกคอมโพเนนต์เดียวกัน) ทำจนครบ n - 1 เส้น
• อัลกอริทึมของพริม (Prim's Algorithm):
  เริ่มต้นจากจุดยอดกำหนด 1 จุด ในแต่ละขั้นตอน ให้เลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดที่เชื่อมจากจุดยอดในต้นไม้ปัจจุบันไปยังจุดยอดที่ยังไม่ถูกรวม จนกระทั่งครอบคลุมทุกจุดยอด

ใช้หาเส้นทางที่สั้นที่สุดจากจุดเริ่มต้น (s) ไปยังจุดยอดอื่นๆ ในกราฟที่มีค่าน้ำหนักเป็นบวก (weight ≥ 0)

• ขั้นตอนการทำงาน:
  1. กำหนดระยะทางเริ่มต้น dist(s) = 0 และจุดอื่น dist(v) = ∞ ให้เซต T คือเซตของจุดยอดทั้งหมด
  2. เลือกจุด u ∈ T ที่มีค่า dist(u) น้อยที่สุด
  3. สำหรับจุดประชิด v ∈ T ของ u: ถ้า dist(u) + w(u,v) < dist(v) ให้ทำการอัปเดต dist(v) = dist(u) + w(u,v) และบันทึกจุดก่อนหน้า prev(v) = u
  4. เอา u ออกจาก T แล้วทำซ้ำจนกระทั่ง T ว่าง หรือถึงจุดหมายปลายทาง (t)

• ดีกรีเข้าและออก: ดีกรีเข้า (indeg(v)) คือจำนวนลูกศรชี้เข้าจุด, ดีกรีออก (outdeg(v)) คือจำนวนลูกศรชี้ออกจากจุด ผลรวม ∑ indeg = ∑ outdeg = |E|
• ระดับการเชื่อมโยงของกราฟทิศทาง:
  • เชื่อมโยงแบบอ่อน (Weakly Connected): กราฟจะเชื่อมโยงกันเมื่อทำการลบทิศทางของอาร์ค (Arc) ออกทั้งหมด
  • เชื่อมโยงแบบด้านเดียว (Unilaterally Connected): สำหรับทุกคู่จุดยอด u, v จะมีวิถีทิศทางจาก u → v หรือ จาก v → u อย่างน้อยหนึ่งทาง
  • เชื่อมโยงแบบแข็งแรง (Strongly Connected): สำหรับทุกคู่จุดยอด u, v จะมีวิถีทิศทางไป-กลับระหว่าง u → v และ v → u เสมอ

ข่ายงานประกอบด้วย แหล่งต้นทาง (Source: s), แหล่งปลายทาง (Sink: t), และเส้นเชื่อมที่มีความจุ (c) กำหนดให้การไหล 0 ≤ f ≤ c และปฏิบัติตามกฎอนุรักษ์การไหล (เข้า = ออก ที่จุดระหว่างทาง)

• ขั้นตอนการติดฉลาก (Augmenting Path Search):
  • เส้นทางไปข้างหน้า (Forward Edge): ทิศทางเดียวกับอาร์ค มีความจุเหลือ inc = c - f > 0
  • เส้นทางย้อนกลับ (Backward / Reverse Edge): ทิศทางสวนอาร์ค สามารถลดการไหลลงได้ inc = f > 0
• ปรับเพิ่มการไหลในเส้นทางที่ค้นพบด้วยค่า Δ = min(inc) ไปเรื่อยๆ จนกว่าจะไม่สามารถติดฉลากไปถึงจุดปลายทาง t ได้อีก

นิยามด้วย 5 สิ่งอันดับ M = (Q, Σ, q₀, δ, F) โดยประกอบด้วย เซตสถานะ (Q), ชุดตัวอักษรนำเข้า (Σ), สถานะเริ่มต้น (q₀), ฟังก์ชันการเปลี่ยนสถานะ (δ: Q × Σ → Q), และเซตของสถานะสิ้นสุด (F)

• การประมวลผล: อ่านสายอักขระ (String) ทีละสัญลักษณ์ เปลี่ยนสถานะตามฟังก์ชัน δ
• การยอมรับ (Acceptance): เมื่อประมวลผลสายอักขระจบ หากสถานะสุดท้ายอยู่ในเซต F (แทนด้วยวงกลมซ้อนสองชั้น ★) จะถือว่าสายอักขระนั้นได้รับการยอมรับ