ทฤษฎีกราฟเบื้องต้น

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

กราฟมาประยุกต์ใช้ในศาสตร์สาขาต่าง ๆ เช่น วิทยาศาสตร์ สังคมศึกษา เศรษฐศาสตร์ พันธุศาสตร์ วิศวกรรมศาสตร์ เป็นต้น
บทนิยาม กราฟ G ประกอบด้วยเซตจำนวน 2 เซต คือ
1. เซตที่ไม่เป็นเวตว่างของจุดยอด (vertex) แทนด้วยสัญลักษณ์ V(G)
2. เซตของเส้นเชื่อม (edge) ที่เชื่อมระหว่างจุดยอดแทนด้วยสัญลักษณ์ E(G)

2. ดีกรี
ดีกรีของจุดยอด

จะเห็นว่า เส้นเชื่อมที่เกิดกับจุดยอด a ได้แก่ เส้นเชื่อม ab และ ac ดังนั้น จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด a คือ 2 สำหรับจุดยอด b มีเส้นเชื่อมที่เกิดกับจุดยอด b ได้แก่ เส้นเชื่อม ba, bc และ bb เป็นวงวน เกิดกับจุดยอด b กรณีที่มีเส้นเชื่อมเป็นวงวนจะกำหนดให้นับจำนวนเส้นเชื่อมที่เกิดกับจุดยอดนั้นเพิ่มขึ้น โดยให้นับเส้นเชื่อมที่เป็นวงวน 1 วง วงวนเป็น 2 ดังนั้นจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด b จึงเป็น 4บทนิยาม ดีกรี (Degree) ของจุดยอด V ในกราฟ คือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v
ต่อไปจะเรียกจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอดว่า ดีกรี ใช้สัญลักษณ์ deg v แทนดีกรีของจุดยอด v ตัวอย่างที่ 1 กำหนดกราฟ ดังรูป

จากรูปจะได้ว่า deg a = 2

deg b = 1

deg c = 3

deg d = 4
ตัวอย่างที่ 2 กำหนดกราฟ ดังรูป

จากรูปจะได้ว่า deg a = 5

deg b = 5

deg c = 5

deg d = 4

พิสูจน์ เนื่องจากเส้นเชื่อมแต่ละเส้นในกราฟเกิดกับจุดยอดเป็นจำนวน 2 ครั้ง ดังนั้นเส้นเชื่อมแต่ละเส้น

จะถูกนับ 2 ครั้งในผลรวมของดีกรีของจุดยอดทุกจุด

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

ข้อสังเกต ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเป็นจำนวนคู่เสมอ

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

วิธีทำ สมมติว่า กราฟมีเส้นเชื่อม n เส้น

จากทฤษฎีบท 1 ผลรวมของดีกรีของจุดยอดทุดจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ

ดังนั้น 22 = 2n

นั่นคือ n = 11

สรุปได้ว่า กราฟมีเส้นเชื่อม11 เส้น

ตัวอย่างที่ 4 จงหาจำนวนจุดยอดของกราฟที่มีเส้นเชื่อม 15 เส้น และมีจุดยอด 3 จุด ที่มีดีกรี 4 ส่วนจุดยอดที่เหลือมีดีกรี 3

วิธีทำ ให้ n เป็นจำนวนจุดยอดที่มีดีกรี 3

ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟ คือ (3)(4) + 3n

ดังนั้น (3)(4) + 3

เพราะฉะนั้น n = 6

ดังนั้น จำนวนจุดยอดทั้งหมดของกราฟ คือ 3 + 6 = 9 จุด

วิธีทำ สมมติว่า มีดีกรีที่มีจุดยอด 4 จุด และดีกรีของจุดยอดเท่ากับ 1, 1, 2 และ 3

ดังนั้น ผลรวมของดีกรีของจุดยอดทุกจุด คือ 1 + 1 + 2 + 3 = 7

ซึ่งเป็นจำนวนคี่ ขัดแย้งกับทฤษฎีบท 1

ดังนั้น เป็นไปไม่ได้ที่จะมีกราฟดังกล่าว

ตัวอย่างที่ 5 จงพิจารณาว่าเป็นไปได้หรือไม่ว่า จะมีกราฟที่มีจุดยอด 4 จุด และดีกรีของจุดยอด คือ 1, 1, 2 และ 3 ตามลำดับ

ตัวอย่างที่ 6 กำหนดกราฟ ดังรูป

จากรูปจะได้ว่า deg a = 2

deg b = 3

deg c = 0

deg d = 3

deg e = 2

ดังนั้น จุดยอด a, c และ e เป็นจุดยอดคู่

จุดยอด b และ d เป็นจุดยอดคี่

ทฤษฎีบท2 ทุกกราฟจะมีจุดยอดคี่เป็นจำนวนคู่

พิสูจน์ ให้ G เป็นกราฟ

ถ้า G ไม่มีจุดยอดคี่ นั่นคือ G มีจำนวนจุดยอดคี่เป็นศูนย์

จึงได้ว่าG มีจำนวนจุดยอดคี่เป็นจำนวนคู่

ต่อไปสมมติว่า กราฟ G มีจุดยอดคี่ k จุด คือ v1, v2, v3, …, vk

และมีจุดยอดคู่ n จุด คือ u1, u2, u3, …, un จากทฤษฎีบท 1

จะได้ว่า (deg v1 + deg v2 + … + deg vk) + (deg u1 + deg u2 + … + deg un) = 2q

เมื่อ q คือ จำนวนเส้นเชื่อมของ G

ดังนั้น deg v1 + deg v2 + … + deg vk = 2q – (deg u1 + deg u2 + … + deg un)

เนื่องจาก deg u1 + deg u2 + … + deg un ต่างก็เป็นจำนวนคู่

ดังนั้น 2q – (deg u1 + deg u2 + … + deg un) เป็นจำนวนคู่

นั่นคือ deg v1 + deg v2 + … + deg vk เป็นจำนวนคู่

แต่เนื่องจาก deg v1 + deg v2 + … + deg vk เป็นจำนวนคี่

เพราะฉะนั้น k จะต้องเป็นจำนวนคู่ จึงจะทำให้ deg v1 + deg v2 + … + deg vk

เป็นจำนวนคู่ สรุปได้ว่า กราฟ G มีจุดยอดคี่เป็นจำนวนคู่

จากตัวอย่างที่ 5 เราให้เหตุผลโดยอาศัยทฤษฎีบท 2 ดังนี้

สมมติว่า มีกราฟที่มีจุดยอด 4 จุด และดีกรีของจุดยอด คือ 1, 1, 2 และ 3

จะได้ว่า กราฟมีจุดยอดคี่เป็นจำนวน 3 จุด ซึ่งขัดแย้งกับทฤษฎีบท 2 สรุปได้ว่า ไม่มีกราฟที่มีสมบัติดังกล่าว

ตัวอย่างที่ 7 ถ้าในห้องประชุมแห่งหนึ่งมีผู้เข้าร่วมประชุมทั้งหมด 23 คน เป็นไปได้หรือไม่

ว่าผู้เข้าร่วมประชุมแต่ละคนจับมือทักทายผู้เข้าร่วมประชุมคนอื่นเพียง 7 คนเท่านั้น

วิธีทำ แปลงปัญหาดังกล่าวเป็นกราฟ โดยให้จุดยอดแทนผู้เข้าร่วมประชุม และเส้นเชื่อมแทน การจับมือทักทายของผู้เข้าร่วมประชุม

จะได้ว่า กราฟนี้มีจุดยอด 23 จุด และจุดยอดแต่ละจุดมีดีกรี 7

นั้นคือ กราฟมีจุดยอดคี่เป็นจำนวน 23 จุด ซึ่งเป็นจำนวนคี่ ขัดแย้งกับทฤษฎีบท 2

ดังนั้น เป็นไปไม่ได้ที่ผู้เข้าร่วมประชุมแต่ละคนจับมือกับคนอื่นเพียง 7 เท่านั้น

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

ออยเลอร์ได้ให้ทฤษฎีที่เกี่ยวกับปัญหานี้ไว้ดังนี้

- - เครือข่าย ที่แสดงเป็นกราฟจะประกอบด้วยจุดเชื่อมโยง (Vertices) และเส้นเชื่อมโยงระหว่างจุด เรียกว่า arcs

- - จุด ที่มีจำนวนเส้นที่เชื่อมออกไปยังจุดอื่นเป็นจำนวนคี่ เรียกว่า odd และถ้าจุดนั้นมีเส้นเชื่อมออกไปยังจุดอื่นเป็นจำนวนคู่ จะเรียกว่า even

- - เส้นทางออยเลอร์ คือเส้นทางที่ลากผ่านเส้นต่าง ๆ ในเครือข่าย โดยแต่ละเส้นลากผ่านได้เพียงครั้งเดียว

- ทฤษฎีของออยเลอร์ กล่าวว่า ถ้าหากว่าเครือข่ายใดมีจุดที่เป็น odd มากกว่าสองขึ้นไป จะไม่มีทางสร้างเส้นทางออยเลอร์ได้

ตัวอย่างจงพิจารณาว่ารูป A, B และ C เป็นกราฟหรือไม่ เพราะเหตุใด

A เป็นกราฟเนื่องจากเซตของจุดยอดไม่เป็นเซตว่าง

B ไม่เป็นกราฟเนื่องจากเซตของจุดยอดเป็นเซตว่าง

C เป็นกราฟเนื่องจากเซตของจุดยอดไม่เป็นเซตว่าง

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

จากกราฟ G1ที่กำหนดให้ จะได้ว่า

V(G1) = {A, B, C, D}

E(G1) = {e1, e2, e3, e4} = {AB, BC, AC, CD}

จากกราฟ G2ที่กำหนดให้ จะได้ว่า

V(G2) = {A, B, C, D}

E(G2) = { e1, e2, e3, e4, e5}

จากกราฟ G2ของตัวอย่างที่ 2 จะสังเกตเห็นได้ว่า เส้นเชื่อม e1และ e2เป็นเส้นเชื่อมที่เชื่อมระหว่างจุดยอดคู่เดียวกัน คือ จุดยอด A และ C หากเราเรียกเส้นเชื่อม e1และ e2โดยอาศัยจุดยอดของเส้นเชื่อม จะพบว่าทั้งเส้นเชื่อม e1และ e2มีชื่อ AC เหมือนกัน ทำให้ไม่สามารถแยกเส้นเชื่อมทั้งสองออกจากกันได้ จึงสรุปได้ว่า การเรียกชื่อเส้นเชื่อมจากจุดยอดทั้งสองของเส้นเชื่อมนั้น ทำได้ในกรณีที่ระหว่างจุดยอดทั้งสองมีเส้นเชื่อมเพียงเส้นเดียวเท่านั้น

บทนิยามจุดยอด u และ v ของกราฟเป็นจุดยอดประชิด(Adjacent Vertices) ก็ต่อเมื่อ มีเส้นเชื่อมระหว่างจุดทั้งสอง และเราเรียกจุดยอด u และ v ว่าจุดปลาย(End Point) ของเส้นเชื่อมนั้น

เส้นเชื่อม e ของกราฟเกิดกับ(Incident) จุดยอด v ถ้าจุดยอด v เป็นจุดปลายจุดหนึ่งของเส้นเชื่อม e

ตัวอย่างจงแสดงว่าจุดยอดใดเป็นจุดยอดประชิด และเส้นเชื่อมแต่ละเส้นเชื่อมเกิดกับจุดยอดใด

จุดยอด A และจุดยอด B เป็นจุดยอดประชิด

จุดยอด A และจุดยอด C เป็นจุดยอดประชิด

จุดยอด A และจุดยอด D ไม่เป็นจุดยอดประชิด

จุดยอด B และจุดยอด C เป็นจุดยอดประชิด

จุดยอด B และจุดยอด D ไม่เป็นจุดยอดประชิด

จุดยอด C และจุดยอด D เป็นจุดยอดประชิด

เส้นเชื่อม e1เกิดกับ จุดยอด A และ จุดยอด B

เส้นเชื่อม e2เกิดกับ จุดยอด B และ จุดยอด C

เส้นเชื่อม e3เกิดกับ จุดยอด A และ จุดยอด C

เส้นเชื่อม e4เกิดกับ จุดยอด C และ จุดยอด D

บทนิยามเส้นเชื่อมตั้งแต่ 2 เส้นเชื่อมที่เชื่อมระหว่างจุดยอดคู่เดียวกัน เรียกว่าเส้นเชื่อมขนาน(Parallel Edges)

เส้นเชื่อมที่เชื่อมจุดยอดเพียงจุดเดียว เรียกว่าวงวน(Loop)

จากภาพจะพบว่า เส้นเชื่อม e1และ e2เชื่อมระหว่างจุดยอดคู่เดียวกัน คือ จุดยอด A และ C ดังนั้นจะได้ว่า e1และ e2เป็นเส้นเชื่อมขนานที่เกิดกับจุดยอด A และ C นอกจากนี้จะพบอีกว่า e5เป็นเส้นเชื่อมที่เชื่อมจุดยอด B เพียงจุดเดียว จึงเรียก e5ว่า วงวน

หมายเหตุ

Ü ในการเขียนแผนภาพของกราฟนั้น จะกำหนดตำแหน่งของจุดยอด ณ ตำแหน่งใดก็ได้ และจะลากเส้นเชื่อมของกราฟเป็นเส้นตรง หรือเส้นโค้ง มีความยาวเป็นเท่าใดก็ได้ โดยที่เส้นเชื่อมที่ลากจะไม่ตัดกับตัวมันเอง และไม่ลากผ่านจุดยอดที่ไม่ใช่จุดปลายของเส้นเชื่อมนั้น เช่น กราฟ G1และ G2ถือว่าเป็นกราฟเดียวกัน