::. GRAPH TERMINOLOGY .::

บทนำ (Introduction)

..........ในส่วนนี้จะเป็นส่วนของการแนะนำศัพท์พื้นฐานบางส่วนในทฤษฎีกราฟ (Graph Theory) ซึ่งจะนำศัพท์เหล่านี้มาใช้ในการแก้ปัญหาที่แตกต่างกันหลายประเภท ปัญหาลักษณะหนึ่งคือ การตรวจสอบว่าจะสามารถเขียนกราฟโดยไม่มีด้าน 2 ด้านใดๆ ของกราฟนั้นที่ตัดกันบนระนาบได้หรือไม่ หรืออีกตัวอย่างหนึ่งคือ การตัดสินว่าจะมีความสอดคล้องแบบหนึ่งต่อหนึ่ง (One-to-one correspondence) ระหว่างจุดยอดของกราฟ 2 รูปซึ่งสร้างความสอดคล้องแบบหนึ่งต่อหนึ่งระหว่างด้านของกราฟเหล่านั้นหรือไม่ นอกจากนี้ในส่วนนี้จะแนะนำกลุ่มของกราฟที่สำคัญแบบต่างๆ ซึ่งมักนำมาใช้เป็นตัวอย่าง หรือใช้ในแบบจำลองต่างๆ

ศัพท์บัญญัติพื้นฐาน (Basic Terminology)

..........ในเบื้องต้นจะขอแนะนำศัพท์บัญญัติบางคำซึ่งอธิบายความหมายและลักษณะของจุดยอดและด้านของกราฟประเภท กราฟไม่ระบุทิศทาง

นิยามที่ 1 จุดยอด 2 จุด u และ v ใน Undirected graph G จะเรียกว่าอยู่ติดกัน (Adjacent or Neighbors) ถ้า {u,v} เป็นด้านของกราฟ G ถ้า e = {u,v} แล้วจะกล่าวได้ว่า ด้าน e เชื่อมต่อระหว่างจุดยอด u และ v และจะเรียกจุดยอด u และ v ว่าเป็น จุดปลาย (Endpoints) ของ ด้าน {u,v}

เพื่อระบุจำนวนของด้านที่เชื่อมต่อกับจุดยอดใดๆ ขอให้พิจารณานิยาม ต่อไปนี้

นิยามที่ 2 ระดับขั้นของจุดยอด (Degree of a vertex) ใน Undirected graph G คือ จำนวนของด้านที่เชื่อมต่อกับจุดยอดนั้นๆ และในกรณีของด้านที่มีลักษณะเป็นวง (Loop) จะก่อให้เกิดค่าดีกรีของจุดยอดเท่ากับ 2 สำหรับจุดยอดนั้นๆ โดยดีกรีของจุดยอด v เขียนแทนได้ด้วยสัญลักษณ์ deg(v)

รูปที่ 1 แสดง Undirected graph G และ H

ตัวอย่างที่ 1 จงหาค่าดีกรีของจุดยอด (Degree of a vertex) ของจุดยอดทุกจุดในกราฟ G และ H ดังแสดงในรูปที่ 1

วิธีทำ :

ในกราฟ G deg(a) = 2, deg(b) = deg(c) = deg(f) = 4, deg(d) = 1, deg(e) = 3 และ deg(f) = 0

ในกราฟ H deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1 และdeg(d) = 5

เมื่อค่าดีกรีของจุดยอดเท่ากับ 0 จะเรียกจุดยอดนั้นๆ ว่า เป็นอิสระ (Isolated) โดยจุดยอดที่เป็นอิสระจะไม่อยู่ติดกัน (Adjacent) กับจุดยอดอื่นๆ จุดยอด g ของกราฟ G ในตัวอย่างที่ 1 เป็นจุดยอดที่เป็นอิสระ และจะเรียกจุดยอดใดๆ ว่า จุดยอดแบบ Pendant ก็ต่อเมื่อจุดยอดนั้นมีดีกรีเท่ากับ 1 ดังนั้นจุดยอดแบบ Pendant จะอยู่ติดกันกับจุดยอดอื่นๆ เพียงจุดเดียว จุดยอด d ของกราฟ G ในตัวอย่างที่ 1 เป็นจุดยอดแบบ Pendant

เมื่อรวมค่าดีกรีของจุดยอดทุกจุดในกราฟ G = (V,E) แล้วจะได้ผลลัพธ์เป็นเช่นใด? แต่ละด้านของกราฟจะก่อให้เกิดค่าดีกรีของจุดยอดเท่ากับ 2 เนื่องจากด้านเกิดจากการเชื่อมต่อระหว่างจุดยอด 2 จุด ซึ่งหมายความว่าผลรวมของดีกรีของจุดยอดจะมีค่าเท่ากับ 2 เท่าของจำนวนด้านที่มีอยู่ทั้งหมด ผลลัพธ์ที่ได้จากการวิเคราะห์ข้างต้นเรียกว่า The Handshaking Theorem อันเนื่องจากการอุปมาเปรียบเทียบระหว่างด้านซึ่งเกิดจากจุดปลาย 2 จุดกับการจับมือซึ่งประกอบด้วยมือ 2 มือนั่นเอง

ทฤษฎีบทที่ 1 The Handshaking Theorem
ให้ G = (V,E) เป็น Undirected graph ที่ประกอบด้วยด้านทั้งหมด e ด้าน จะได้ว่า

สังเกตว่าทฤษฎีนี้สามารถประยุกต์ใช้ได้ แม้ว่ากราฟนั้นจะประกอบด้วยด้านหลายๆ ด้านที่เชื่อมต่อระหว่างจุดยอดคู่หนึ่งๆ (Multiple edge) หรือด้านที่มีลักษณะเป็นวง (Loop)

ตัวอย่างที่ 2 จงหาจำนวนด้านของกราฟที่มีจุดยอด 10 จุดโดยแต่ละจุดมีดีกรีของจุดยอดเท่ากับ 6

วิธีทำ :

เนื่องจากผลรวมของดีกรีของจุดยอดทั้งหมดคือ 6 ? 10 = 60 จากนั้นพิจารณา The Handshaking Theorem จะได้ว่า 2e = 60 ดังนั้น e = 30

ทฤษฎีบทที่ 1 แสดงให้เห็นว่าผลรวมของดีกรีของจุดยอดของ Undirected graph มีค่าเป็นจำนวนคู่เสมอ และจากความจริงนี้ก่อให้เกิดผลลัพธ์อื่นๆ อีกมาก ดังตัวอย่างเช่นทฤษฎีบทที่ 2 ดังต่อไปนี้

ทฤษฎีบทที่ 2 Undirected graph ใดๆ จะมีจุดยอดที่มีดีกรีเป็นจำนวนคี่เป็นจำนวนคู่เสมอ

พิสูจน์ : ให้ V₁ และ V₂ เป็นเซตของจุดยอดที่มีดีกรีเป็นจำนวนคู่และเซตของจุดยอดที่มีดีกรีเป็นจำนวนคี่ของ Undirected graph G = (V,E) ตามลำดับ ดังนั้น

เนื่องจาก deg(v) เป็นจำนวนคู่ สำหรับ v? V₁ พจน์แรกของด้านขวาของสมการข้างต้นจึงมีค่าเป็นจำนวนคู่ด้วย ยิ่งกว่านั้นผลรวมของทั้ง 2 พจน์ทางขวามือของสมการ ก็ เป็นจำนวนคู่ด้วย เนื่องจากมีผลรวมเป็น 2e ดังนั้นพจน์ที่ 2 ของผลรวมนั้นก็จะต้องมีค่าเป็นจำนวนคู่ด้วย และเนื่องจากทุกๆ พจน์ย่อยของผลรวมนี้มีค่าเป็นจำนวนคี่ ดังนั้นจึงต้องมีจำนวนพจน์ย่อยนี้เป็นจำนวนคู่ หรืออาจกล่าวได้ว่าจะมีจุดยอดที่มีดีกรีเป็นจำนวนคี่เป็นจำนวนคู่เสมอ

นอกจากนี้ยังมีศัพท์บัญญัติที่เป็นประโยชน์สำหรับกราฟที่มีด้านแบบ ไม่ระบุทิศทาง ดังนี้ :

นิยามที่ 3 เมื่อ (u,v) เป็นด้านแบบ ระบุทิศทาง ของกราฟ G จะกล่าวได้ว่า จุดยอด u เชื่อมต่อไปยังจุดยอด v และจุดยอด v เชื่อมต่อมาจากจุดยอด u และเรียกจุดยอด ว่า u จุดยอดเริ่มต้นของด้าน (u,v) และเรียกจุดยอด v ว่า จุดยอดปลายหรือจุดยอดสิ้นสุดของด้าน (u,v) โดยจุดยอดเริ่มต้นและจุดยอดสิ้นสุดของด้านที่มีลักษณะเป็นวง (Loop) จะเป็นจุดเดียวกัน

เนื่องจากด้านแบบ Directed edge ในกราฟจะถูกจัดเรียงเป็นคู่ๆ ดังนั้นจึงสามารถปรับเปลี่ยนนิยามของดีกรีของจุดยอด (Degree of a vertex) ใหม่เพื่อหาจำนวนด้านที่เชื่อมต่อกับจุดยอดเหล่านี้โดยแยกตามจุดยอดเริ่มต้นและจุดยอดสิ้นสุด

นิยามที่ 4 ในกราฟที่มีด้านแบบ Directed edge นั้น ดีกรีเข้า (in-degree) ของจุดยอด v ซึ่งเขียนแทนด้วย deg^-(v) คือ จำนวนของด้านที่มีจุดยอด v เป็นจุดยอดสิ้นสุด และ ดีกรีออก (out-degree) ของจุดยอด v ซึ่งเขียนแทนด้วย deg⁺(v) คือ จำนวนของด้านที่มีจุดยอด v เป็นจุดยอดเริ่มต้น (สังเกตว่า สำหรับด้านที่มีลักษณะเป็นวงนั้น ก่อให้เกิดดีกรีเข้าและดีกรีออกอย่างละ 1 แก่จุดยอดนั้นๆ)

ตัวอย่างที่ 3 จงหาค่าดีกรีเข้าและดีกรีออกของจุดยอดแต่ละจุดในกราฟ G ที่มีด้านแบบ Directed edge ดังแสดงในรูปที่ 2

ผลเฉลย :

รูปที่ 2 แสดง Directed graph G

ระดับขั้นเข้าของกราฟ G คือ deg^-(a) = 2, deg^-(b) = 2, deg^-(c) = 3, deg^-(d) = 2, deg^-(e) = 3 และ deg^-(f) = 0

ระดับขั้นออกของกราฟ G คือ deg⁺(a) = 4, deg⁺(b) = 1, deg⁺(c) = 2, deg⁺(d) = 2, deg⁺(e) = 3 และ deg⁺(f) = 0

เนื่องจากแต่ละด้านจะมีทั้งจุดยอดเริ่มต้นและจุดยอดสิ้นสุดเสมอ ดังนั้นผลรวมของดีกรีเข้าและผลรวมดีกรีออกของจุดยอดทุกจุดใน Directed graph จะมีค่าเท่ากันและมีค่าเท่ากับจำนวนด้านทั้งหมดในกราฟนั้นๆ ดังกล่าวไว้ในทฤษฎีบทต่อไปนี้

ทฤษฎีบทที่ 3 ให้ G = (V,E) เป็น Directed graph ดังนั้น

มีคุณสมบัติมากมายของกราฟที่มีด้านแบบ Directed edge ซึ่งไม่ขึ้นอยู่กับทิศทางของด้านแต่ละด้าน ดังนั้นโดยทั่วไปจึงมักไม่พิจารณาถึงทิศทางเหล่านี้ และ Undirected graph ที่เกิดจากการไม่พิจารณาทิศทางของแต่ละด้านใน Directed graph จะเรียกว่า Underlying undirected graph โดย Directed graph และ Underlying undirected graph ที่เกิดขึ้นจะมีจำนวนด้านเท่ากัน