ประเภทของกราฟในโครงสร้างข้อมูลพร้อมตัวอย่าง

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

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

กราฟกำกับ

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

กราฟกำกับ

• เราสามารถไปจากโหนด A ถึง D
• อย่างไรก็ตาม เราไม่สามารถเดินทางจากโหนด D ไปยังโหนด A ได้ เนื่องจากเส้นเชื่อมชี้จาก A ไปยัง D เท่านั้น
• เนื่องจากกราฟไม่มีน้ำหนัก การเดินทางจากจุดยอด A ถึง D จะมีราคาเท่ากับการเดินทางจาก D ถึง F

กราฟไม่มีทิศทาง

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

กราฟไม่มีทิศทาง

ในกราฟด้านบน

• เราสามารถเคลื่อนที่จากจุด A ไปยังจุด B ได้
• เราสามารถเคลื่อนที่จาก B ไป A ได้เช่นกัน
• ขอบไม่มีทิศทาง

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

กราฟถ่วงน้ำหนัก

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

กำกับกราฟพร้อมน้ำหนัก

• จากจุด A ไปจุด B มีขอบ และน้ำหนักคือ 5 ซึ่งหมายความว่าการเคลื่อนที่จาก A ไป B จะมีค่าใช้จ่าย 5
• จุด A ชี้ไปยังจุด B แต่ในกราฟนี้ จุด B ไม่มีเส้นเชื่อมโดยตรงกับจุด A ดังนั้น เราจึงไม่สามารถเดินทางจากจุด B ไปยังจุด A ได้
• อย่างไรก็ตาม หากเราต้องการเดินทางจาก A ไป F จะมีหลายเส้นทาง เส้นทางเหล่านั้นคือ ADF และ ABF โดยเส้นทาง ADF จะมีค่าใช้จ่าย (10+11) หรือ 21
• ในที่นี้ เส้นทาง ABF จะมีค่าใช้จ่าย (5+15) หรือ 20 โดยเรากำลังบวกน้ำหนักของแต่ละขอบในเส้นทางเข้าด้วยกัน

ต่อไปนี้เป็นตัวอย่างของกราฟแบบไม่มีทิศทางที่มีค่าน้ำหนัก:

กราฟที่ไม่มีทิศทางพร้อมน้ำหนัก

ตรงนี้ขอบมีน้ำหนักแต่ไม่มีทิศทาง หมายความว่าการเดินทางจากจุดยอด A ไปยัง D มีค่าใช้จ่าย 10 และในทางกลับกัน

กราฟสองทิศทาง

กราฟสองทิศทางและกราฟไร้ทิศทางมีคุณสมบัติร่วมกันอย่างหนึ่ง คือ:

• โดยทั่วไป กราฟแบบไม่มีทิศทางจะมีเส้นเชื่อมระหว่างจุดยอดสองจุดได้เพียงเส้นเดียว

ตัวอย่างเช่น:

• ที่นี่ การย้ายจาก A ไป D หรือ D ไป A จะมีราคา 10
• ในกราฟแบบสองทิศทาง เราสามารถมีขอบสองด้านระหว่างจุดยอดสองจุดได้

นี่คือตัวอย่าง:

กราฟสองทิศทาง

การเดินทางจาก A ไป D จะมีค่าใช้จ่าย 17 แต่การเดินทางจาก D ไป A จะมีค่าใช้จ่าย 12 ดังนั้น เราจึงไม่สามารถกำหนดค่าน้ำหนักที่แตกต่างกันสองค่าได้ หากเป็นกราฟแบบไม่มีทิศทาง

กราฟไม่มีที่สิ้นสุด

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

กราฟไม่มีที่สิ้นสุด

กราฟว่าง

กราฟว่าง (Null Graph) คือกราฟที่มีเฉพาะจุดหรือจุดยอด แต่ไม่มีเส้นเชื่อม ถ้ากำหนดให้กราฟ G = (V, E) โดยที่ V คือจุดยอด และ E คือเส้นเชื่อม กราฟนั้นจะเป็นกราฟว่างก็ต่อเมื่อจำนวนเส้นเชื่อม E เป็นศูนย์ นี่คือตัวอย่างของกราฟว่าง:

กราฟว่าง

กราฟเล็กน้อย

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

มัลติกราฟ

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

มีเส้นเชื่อมสองเส้นจาก B ไปยัง A นอกจากนี้ จุดยอด E ยังมีวงวนในตัวเอง กราฟข้างต้นเป็นกราฟแบบมีทิศทางที่ไม่มีน้ำหนักบนเส้นเชื่อม

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

กราฟจะสมบูรณ์ก็ต่อเมื่อแต่ละจุดยอดมีเส้นเชื่อมแบบมีทิศทางหรือไม่มีทิศทางกับจุดยอดอื่นๆ ทุกจุด สมมติว่ามีจุดยอดทั้งหมด V จุด และแต่ละจุดยอดมีเส้นเชื่อม V-1 เส้นพอดี กราฟนี้จะเรียกว่ากราฟสมบูรณ์ ในกราฟประเภทนี้ แต่ละจุดยอดเชื่อมต่อกับจุดยอดอื่นๆ ทุกจุดด้วยเส้นเชื่อม ต่อไปนี้เป็นตัวอย่างของกราฟสมบูรณ์ที่มีห้าจุดยอด:

จากภาพจะเห็นว่าจำนวนโหนดทั้งหมดมีห้าโหนด และทุกโหนดมีเส้นเชื่อมสี่เส้นพอดี

กราฟที่เชื่อมต่อ

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

ต่อไปนี้เป็นคำอธิบายเกี่ยวกับกราฟเชื่อมต่อข้างต้น:

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

กราฟวงจร

กราฟจะเรียกว่ากราฟวัฏจักรได้ก็ต่อเมื่อมีวัฏจักรตั้งแต่หนึ่งวัฏจักรขึ้นไปในกราฟนั้น นี่คือตัวอย่างของกราฟวัฏจักร:

ในที่นี้ จุดยอด A, B และ C ก่อให้เกิดวงจร กราฟหนึ่งๆ สามารถมีวงจรได้หลายวงภายในกราฟนั้น

กราฟ Acyclic แบบกำกับ (DAG)

กราฟจะเรียกว่ากราฟแบบมีทิศทางและไม่มีวงจร (Directed Acyclic Graph หรือ DAG) หากไม่มีวงจรอยู่ภายในกราฟ DAG มีความสำคัญในการทำ... การเรียงลำดับโทโพโลยี หรือการค้นหาลำดับการดำเนินการ DAG ยังมีความสำคัญสำหรับการสร้างระบบการจัดตารางเวลาหรือการสแกนความสัมพันธ์ของทรัพยากร ฯลฯ อย่างไรก็ตาม กราฟข้างต้นไม่มีวงจรอยู่ภายใน นี่คือตัวอย่างง่ายๆ ของกราฟแบบมีทิศทางและไม่มีวงจร (DAG):

กราฟวงจร

กราฟวงจร (Cycle Graph) ไม่เหมือนกับกราฟวัฏจักร (Cyclic Graph) ในกราฟวงจร แต่ละโหนดจะมีเส้นเชื่อมเพียงสองเส้นเท่านั้น ซึ่งหมายความว่าแต่ละโหนดจะมีดีกรีเท่ากับสอง ตัวอย่างของกราฟวงจรมีดังนี้:

กราฟทวิภาคี

ประเภทนี้ กราฟ กราฟสองส่วน (Bipartite Graph) เป็นกราฟชนิดพิเศษที่จุดยอดแต่ละจุดถูกกำหนดให้กับสองเซต กราฟสองส่วนต้องเป็นไปตามกฎต่อไปนี้:

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

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

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

จุดยอดทั้งหมดมีดีกรีเป็นเลขคู่ จุดยอด A, D, E และ H มีดีกรีสอง จุดยอด C มีดีกรีสี่ ซึ่งเป็นเลขคู่

แฮมิลตันกราฟ

กราฟแฮมิลตัน (Hamilton Graph) คือกราฟเชื่อมต่อ (Connected Graph) ที่ผู้สำรวจสามารถเดินทางไปยังทุกจุดยอดจากจุดยอดที่กำหนดได้โดยไม่ต้องกลับไปยังจุดยอดเดิมหรือใช้ขอบเดิม กราฟเชื่อมต่อประเภทนี้เรียกว่า "กราฟแฮมิลตัน" เส้นทางที่ใช้ในการตรวจสอบว่ากราฟที่กำหนดเป็นกราฟแฮมิลตันหรือไม่ เรียกว่า เส้นทางแฮมิลตัน (Hamiltonian Path) ต่อไปนี้เป็นตัวอย่างกราฟแฮมิลตันอย่างง่าย:

ในภาพนี้ เราสามารถเยี่ยมชมจุดยอดทั้งหมดจากโหนดใดก็ได้ในกราฟด้านบน หนึ่งในเส้นทางที่สามารถเป็นได้ ADCHBEนอกจากนี้ยังสามารถหาวัฏจักรแฮมิลตันได้ วัฏจักรแฮมิลตันเริ่มต้นและสิ้นสุดที่จุดยอดเดียวกัน ดังนั้น วัฏจักรแฮมิลตันจะเป็น แอดช์บีเอ.

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