วาดรูปโดยไม่ยกมือ: วาดได้ วาดไม่ได้ ? ทฤษฎีกราฟ

คิดว่าหลายคนน่าจะเคยเล่นเกมนี้กันนะครับ

วาดรูปที่ให้มาโดยห้ามยกมือ และห้ามทับเส้นเดิม

ตัวอย่างคลาสสิกคงเป็นรูปจดหมายเปิดแบบข้างล่างนี้ครับ

รูปนี้สามารถวาดได้โดยหลายๆวิธีครับ 

อย่างเช่น แบบนี้ เป็นต้น

แล้วสำหรับรูปจดหมายปิดแบบรูปด้านล่างล่ะครับ วาดได้รึเปล่า

ก่อนจะเฉลยคำตอบนะครับ ลองดูหลักการคิดกันก่อน

ถ้าหากลองวาดดูคงใช้เวลามากสำหรับรูปที่ซับซ้อน

เราจึงต้องทราบกฏเรื่องนี้กันก่อนครับ

ในการมองรูปนะครับ ต้องมองเป็นกราฟ

1. จุดตัดต่างๆเรียกว่า Node 

2. เส้นเชื่อมระหว่าง Node เรียกว่า Edge

สีเขียวคือ Node 

สีเหลืองคือ Edge

3. จำนวนเส้นที่เชื่อมกับ Node เรียกว่า Degree ของ Node

Node A,B,D,E มี Degree = 3

Node C มี Degree = 4

พิจารณาการวาดกราฟนั้นๆ ผ่านทุกๆ Edge ของกราฟและไม่ซํ้าทางเดิม

ทำได้โดยกฏต่อไปนี้

กฏข้อ 1 หากกราฟนั้นไม่มี Node ที่มี Degree คี่ 

สามารถเริ่มวาดจากจุดไหนก็ได้
โดยจุดสิ้นสุดจะเป็นจุดเดียวกับจุดเริ่มต้น

รูปที่ 1 กราฟที่ทุก Node เป็น Degree คู่

「ทำไมต้องกลับมาที่ Node เดิมด้วยล่ะขอรับ?」
"มาลองวิเคราะห์กันดูนะครับ"


เนื่องจากทุกๆ Node เป็น degree คู่
สมมุติว่าหน้าตาของ Node เริ่มต้นเป็นประมาณนี้

การเดินครั้งแรกคือเดินออกจาก Node นี้ แบบรูปข้างล่าง

หลังจากเดินไปยัง Node อื่นๆ ก็อาจกลับมาที่ Node เดิมได้

จากนั้นก็ออกจาก Node นี้โดยใช้เส้นทางที่เหลืออันใดอันหนึ่ง

สุดท้าย เมือเดินไปยัง Node อื่นที่เหลือครบแล้ว

 ก็จะกลับมายังจุดเริ่มต้นโดยใช้เส้นทางสุดท้ายที่เหลืออยู่

กฏข้อ 2 หากกราฟมี Node คี่ เพียง 2 Node เท่านั้น

สามารถวาดกราฟได้โดยเริ่มจาก Node คี่จุดแรก และสิ้นสุดที่ Node คี่อีกจุด

ในรูป Node สีแดงเป็น Node คี่

"ลองเดินบนกราฟนี้ดูซิ"
「แบบนี้น่าจะได้ขอรับ」

จะเห็นได้ว่าต้องเริ่มที่ node คี่ แล้วจบที่ node คี่เช่นกัน แต่เป็นคนละ node
วิเคราะห์กันดูนะครับว่าทำไมถึงเป็นแบบนั้น

เราจะมองที่ node คี่ทั้ง 2 node นะครับ
ดูที่เส้นทางการเข้าออกของแต่ละ node ครับ

ที่ Node คู่ สามารถรองรับการเข้า-ออก ได้เป็นคู่ๆ
ส่วน Node คี่นั้น เมื่อจับคู่การเข้า-ออก จะมีเส้นเหลืออยู่เส้นหนึ่ง
แบบนี้

A ไม่มีคู่
B ไม่มีคู่
ถ้า A ออก --> B ต้องเข้า
นั่นทำให้ เริ่มที่ Node ของ A ต้องจบที่ Node ของ B
ในกรณีตรงข้ามก็เช่นกันครับ

กฏข้อ 3 หากกราฟนั้นมี Node คี่มากกว่า 2 Node

ไม่สามารถวาดกราฟผ่านทุก Edge โดยไม่ซํ้าทางเดิมได้!

「ทำไมล่ะขอรับ?」


เมื่อกราฟมี Node คี่และคู่รวมอยู่ด้วยกัน
ลองโฟกัสที่ Node คี่ 3 Node ดูนะครับ

เริ่มเดินจาก Node 1 ไปยัง Node 2 ด้วยเส้นทางสีส้ม
เส้นทางเหล่านี้อาจจะผ่าน Node อื่นๆในกราฟมากมายนะครับ แต่จะไม่เขียนเอาไว้
จากนั้นไปยัง Node 3 ด้วยเส้นทางสีเขียว
กลับไปยัง Node 1 ด้วยเส้นทางสีฟ้า
ไปยัง Node 3 อีกครั้งด้วยเส้นทางสีดำ

จะเห็นว่า ที่ Node 3 ไม่เหลือทางออกให้ไปยัง Node 2 ได้เลย
หรือถ้าเส้นทางสีดำไปเข้า Node 2 ก่อน ก็ทำให้ ออกไป Node 3 ไม่ได้เช่นกัน
ทำให้มี edge เหลือ 1 ที่ครับ นั่นคือเดินไม่ครบทุก edge นั่นเอง

ทั้งนี้เพราะ Node คี่สำหรับเริ่มต้น ต้องการ Node คี่สำหรับสิ้นสุด 1 Node
ทำให้ Node คี่อื่นๆ ในกราฟเหลือ edge 1 เส้นเสมอครับ

"จบแล้วครับสำหรับเอนทรี่นี้ น่าจะตอบคำถามรูปจดหมายปิดได้แล้วนะครับ"
「ไม่เฉลยหรือขอรับ」
"ไม่เฉลยหรอก"
「หวังว่าคงได้ความรู้กันนะขอรับ」
"อ้อ นอกจากนี้ ถ้ากราฟมี node คี่ อยู่ละก็ มีได้ตั้งแต่ 2 node ขึ้นไปนะครับ"
「เอ๋ มี node เดียวไม่ได้หรือขอรับ」
"ไม่ได้จริงๆ นะ"



ลองวาดกราฟที่มี node คี่ เพียง 1 node ดูนะครับ
ผมลองแล้ว วาดไม่ได้อ่ะ >w<

ปัญหาวางหมากรุก: วางได้เยอะสุดกี่ตัว?

มีกระดานหมากรุกขนาด N*M
N,M >= 4

1. วาง Queen ได้มากสุดกี่ตัวโดยที่แต่ละตัวกินตัวอื่นไม่ได้ และไม่โดนตัวอื่นกินใน 1 ตาเดิน

 

    การเดินของ Queen คือ ตลอดแนวทแยง และตลอดแนวตรงดังรูป ที่ 1

รูปที่ 1 แสดงการเดินของ Queen

"ลองวาง Queen บนกระดาน 5*8 กันนะครับ"

「วางได้ประมาณนี้ขอรับ 」

รูปที่ 2 วาง Queen บนกระดาน 5*8

มาลองวิเคราะห์การวางควีนดูนะครับ

กระดานมี 5 แถว กับ 8 หลัก

 แต่ละแถววาง Queen ได้แค่ตัวเดียว

แต่ละหลักวาง Queen ได้แค่ตัวเดียว

เนื่องจากมีแค่ 5 แถว

ดังนั้น ถ้าวางดีๆ

ก็ยังวางได้ไม่เกิน 5 ตัวอยู่ดี 

ดังที่เห็นในรูปข้างบน

สรุปคือ วางควีนได้มากสุดเท่ากันเลขที่น้อยที่สุดของหลักและแถว

maxQueen = min(row, column)

2. วาง Rook ได้มากสุดกี่ตัวโดยที่แต่ละตัวกินตัวอื่นไม่ได้ และไม่โดนตัวอื่นกินใน 1 ตาเดิน

การเดินของ Rook คือ ตลอดแนวตรงดังรูป ที่ 3

รูปที่ 3 การเดิน Rook

การวิเคราะห์ Rook เหมือนกันกับ Queen เลยครับ

「ทำไมล่ะขอรับ」

"เพราะการเดินของ Rook เหมือน Queen ที่เดินทแยงไม่ได้ไงล่ะ"

การวาง Rook บนกระดานจึงมองจากแถวหรือหลักที่น้อยกว่าเช่นกัน

นั่นคือ 

ในแต่ละหลักวางได้ตัวเดียว

ในแต่ละแถววางได้ตัวเดียว

ดังนั้นจะได้สมการเดียวกันกับ Queen คือ

maxRook= min(row, column)

3. วาง King ได้มากสุดกี่ตัวโดยที่แต่ละตัวกินตัวอื่นไม่ได้ และไม่โดนตัวอื่นกินใน 1 ตาเดิน

King เดินได้ 1 ก้าว รอบทิศทาง ดังรูปที่ 4

รูปที่ 4 การเดินของ King

"บนกระดาน 5*9 การวาง King จะเป็นแบบไหน?"

「ประมาณนี้ขอรับ」

อ่า ทีนี้ลองวิเคราะห์กันดูครับ

พบว่า King แต่ละตัวกินพื้นที่ 2*2 ดังรูปครับ

จะเห็นว่า หลังจากแบ่งกระดานด้วยสี่เหลี่ยม 2*2 แล้ว

อาจมีส่วนที่เหลืออยู่จากการแบ่งนั้น ต้องนำมาคิดด้วยนะครับ

จากข้างบน 5x9

นำมาแบ่งด้วย 2x2

คือ 5x9 / 2x2

ได้ (5/2) * (9/2)

เท่ากับ 2 * 4 = 8 ซึ่งยังไม่ครบ

ต้องรวมเศษจากการแบ่งเข้าไปด้วย

เปลี่ยนเป็น (5/2 + 5%2) * (9/2 + 9%2)

เท่ากับ (2+1) * (4+1) = 3 * 5 = 15

ซึ่งเป็นคำตอบที่ถูกต้อง

ดังนั้น สรุปว่า

maxKing = (row/2 + row%2) * (column/2 + column%2)

4. วาง Knight ได้มากสุดกี่ตัวโดยที่แต่ละตัวกินตัวอื่นไม่ได้ และไม่โดนตัวอื่นกินใน 1 ตาเดิน

การเดินของ Knight เป็นรูปตัว L (เดินข้ามหมากตัวอื่นได้) แบบรูปที่ 5

รูปที่ 5 การเดินของ Knight

"กระดาน 8*8 วาง Knight ยังไงให้เยอะๆ?"

「แบบนี้ขอรับ」

นี่เป็นวิธีที่ดีที่สุดในการวาง Knight ลงบนกระดานครับ

กระดานขนาด 8x8 = 64
ได้ Knight 32 ตัว

 「แสดงว่าได้ Knight เป็น 1/2 เท่าของขนาดกระดานสินะขอรับ?」

"เกือบถูก แต่ยังไม่ใช่ เพราะเรา ยังไม่ได้พิจารณากรณีที่ขนาดกระดานเป็นเลขคี่"

พิจารณากรณีที่กระดานขนาดเป็นเลขคี่ดูครับ

เช่น เมื่อกระดานขนาด 3x5 = 15 เป็นเลขคี่

จะได้ตามรูปข้างล่าง

กระดาน 3x5 วาง knight ได้ 8 ตัว

3*5 = 15 

15/2 = 7.5 --> 8

ดังนั้น ได้สมการคือ

maxKnight = (row*column)/2 + (row*column)%2

"สำหรับปัญหาของคราวนี้ก็มีแค่นี้นะครับ"

「ไว้เจอกันอีกทีที่บทความหน้านะขอรับ ^^ 」