กราฟแบบกำกับและแบบไม่มีทิศทาง
กราฟคือโครงสร้างทางคณิตศาสตร์ที่ประกอบด้วยชุดของจุดยอดและขอบ กราฟแสดงชุดของวัตถุ (แสดงด้วยจุดยอด) ที่เชื่อมต่อผ่านลิงก์บางส่วน (แสดงด้วยขอบ) การใช้สัญลักษณ์ทางคณิตศาสตร์ กราฟสามารถแสดงด้วย G โดยที่ G=(V, E) และ V คือเซตของจุดยอด และ E คือเซตของขอบ ในกราฟที่ไม่มีทิศทางจะไม่มีทิศทางที่เกี่ยวข้องกับขอบที่เชื่อมกับจุดยอด ในกราฟกำกับจะมีทิศทางที่เกี่ยวข้องกับขอบที่เชื่อมจุดยอด
กราฟไม่มีทิศทาง
ดังที่กล่าวไว้ก่อนหน้านี้ กราฟที่ไม่มีทิศทางคือกราฟที่ไม่มีทิศทางในขอบที่เชื่อมโยงจุดยอดในกราฟรูปที่ 1 แสดงกราฟที่ไม่มีทิศทางพร้อมชุดของจุดยอด V={V1, V2, V3} ชุดขอบในกราฟด้านบนสามารถเขียนได้เป็น V={(V1, V2), (V2, V3), (V1, V3)} นอกจากนี้ยังสามารถสังเกตได้ว่าไม่มีสิ่งใดขัดขวางการเขียนชุดขอบเป็น V={(V2, V1), (V3, V2), (V3, V1)} เนื่องจากขอบไม่มีทิศทาง ดังนั้นขอบในกราฟที่ไม่มีทิศทางจึงไม่เรียงเป็นคู่ นี่คือลักษณะสำคัญของกราฟที่ไม่มีทิศทาง กราฟแบบไม่มีทิศทางสามารถใช้เพื่อแสดงความสัมพันธ์แบบสมมาตรระหว่างวัตถุที่แสดงด้วยจุดยอดได้ ตัวอย่างเช่น เครือข่ายถนนสองทางที่เชื่อมต่อกลุ่มเมืองต่างๆ สามารถแสดงโดยใช้กราฟที่ไม่ระบุทิศทาง เมืองสามารถแสดงด้วยจุดยอดในกราฟ และขอบเป็นตัวแทนของถนนสองทางที่เชื่อมระหว่างเมือง
กราฟกำกับ
กราฟกำกับคือกราฟที่ขอบของกราฟที่เชื่อมกับจุดยอดมีทิศทาง รูปที่ 2 แสดงกราฟกำกับด้วยชุดของจุดยอด V={V1, V2, V3} ชุดขอบในกราฟด้านบนสามารถเขียนได้เป็น V={(V1, V2), (V2, V3), (V1, V3)} ขอบในกราฟที่ไม่มีทิศทางเป็นคู่ที่เรียงลำดับ อย่างเป็นทางการ ขอบ e ในกราฟกำกับสามารถแสดงโดยคู่ลำดับ e=(x, y) โดยที่ x คือจุดยอดที่เรียกว่าจุดกำเนิด แหล่งกำเนิด หรือจุดเริ่มต้นของขอบ e และจุดยอด y เรียกว่าจุดปลาย จุดยอดหรือจุดสิ้นสุด ตัวอย่างเช่น เครือข่ายถนนที่เชื่อมต่อกลุ่มเมืองโดยใช้เส้นทางเดียวสามารถแสดงโดยใช้กราฟที่ไม่ระบุทิศทาง เมืองสามารถแสดงด้วยจุดยอดในกราฟ และขอบที่กำกับไว้แสดงถึงถนนที่เชื่อมระหว่างเมืองโดยพิจารณาจากทิศทางที่การจราจรบนถนน
กราฟแบบตรงและแบบไม่มีทิศทางต่างกันอย่างไร
ในกราฟกำกับ ขอบคือคู่ลำดับ โดยที่คู่คำสั่งแสดงทิศทางของขอบที่เชื่อมจุดยอดทั้งสอง ในทางกลับกัน ในกราฟที่ไม่มีทิศทาง ขอบคือคู่ที่ไม่เรียงลำดับ เนื่องจากไม่มีทิศทางที่เกี่ยวข้องกับขอบ กราฟแบบไม่มีทิศทางสามารถใช้เพื่อแสดงความสัมพันธ์แบบสมมาตรระหว่างวัตถุได้ In-degree และ out-degree ของแต่ละโหนดในกราฟแบบไม่มีทิศทางจะเท่ากัน แต่สิ่งนี้ไม่เป็นความจริงสำหรับกราฟแบบกำกับ เมื่อใช้เมทริกซ์เพื่อแสดงกราฟแบบไม่บอกทิศทาง เมทริกซ์จะกลายเป็นกราฟสมมาตรเสมอ แต่สิ่งนี้ไม่เป็นความจริงสำหรับกราฟที่กำกับทิศทาง กราฟที่ไม่ระบุทิศทางสามารถแปลงเป็นกราฟที่มีทิศทางโดยแทนที่ขอบแต่ละด้านด้วยขอบชี้ตรงสองด้านไปในทิศทางตรงกันข้าม อย่างไรก็ตาม ไม่สามารถแปลงกราฟกำกับเป็นกราฟที่ไม่มีทิศทาง