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

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

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

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

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

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

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

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

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

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

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

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

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

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

ปรับแต่ง Wallpaper ง่ายๆ ด้วยโปรแกรม Paint บน Window 7

พบกันอีกครั้งนะครับ กระผม iBoom ครับ วันนี้ว่างๆ เลยมาแชร์ความรู้ง่ายๆนะครับ ^^


"ช่วงนี้ ใช้ wallpaper อันเดิมจนเบื่อแล้วอ่ะ ทำไงดี"
「เปลี่ยน wallpaper เป็นรูปอื่นสิขอรับ」
"มีแต่รูปที่มันไม่พอดีกับขนาดของจออ่ะ ใหญ่เกินมั่งล่ะ เล็กเกินมั่งล่ะ - -"
「ลองเอารูปที่มีมาปรับแต่งดูมั๊ยขอรับ」
"ทำไงอ่ะ Photoshop ก็ไม่มี?"
「ใช้ Paint ก็ได้หนิขอรับ」
"มาๆ ลองดูหน่อยละกัน"



ผมได้รูปนี้มาจาก 9gag ครับ สวยดี (รูปอาจโหลดนานหน่อยนะจ๊ะ)

ลองเปลี่ยนรูปนี้เป็น wallpaper ผลลัพธ์ที่ได้ก็คือ

「สวยใช้ได้นะขอรับ」
"รูปมันไม่เต็มจออ้ะ -*-"
「เรื่องมากจริงๆเล้ย」

ผมอยากให้ Clould กับ Tifa ยืนพิงของจอแต่ละด้านอ่ะครับ ตรงกลางจะได้โล่งๆ
วิธีการก็คือ Capture รูป Wallpaper ไว้แล้วเอาไปแก้ใน Paint ครับ
ขั้นแรกต้อง Capture รูป ก่อน
    โดยการ เอา icon บน Desktop ออก
            คลิ๊กขวาที่ที่ว่างบน Desktop -> เลือก View -> เลือก Show desktop icons เพื่อเอาเครื่องหมายถูกออก
            「คลิ๊กที่รูปเพื่อดูขนาดใหญ่นะขอรับ」

            จะได้ wallpaper ที่ไม่มี icon อยู่

            จากนั้นเอา taskbar ข้างล่างออก โดยการคลิ๊กขวาที่ taskbar -> เลือก Properties
            ที่แท็บ Taskbar ติ๊กถูกที่ Auto-hide the taskbar กด OK

                                         

            จะได้ wallpaper ว่างๆ ไม่มีไอคอน ไม่มี Taskbar ดังรูปข้างล่าง
      

             
            เมื่อได้ wallpaper โล่งๆ แบบข้างบนแล้ว ให้ Print screen wallpaper โล่งๆ นี้ไว้ โดยการกดปุ่ม PrtSc บนแป้นพิมพ์ (อ่า keyboard นั่นแหละครับ)
           ทีนี้ก็เปิดโปรแกรม paint ขึ้นมาครับ ใช้ cursor ลากพื้นที่กระดานวาดรูปให้เล็กลงแบบรูปข้างล่าง

     
           จากนั้น paste รูปที่เราได้ print screen เตรียมไว้ก่อนหน้านี้ลงบนกระดานวาดรูป แบบนี้

      
            จะเห็นว่าโปรแกรม Paint จะจัดขนาดรูปให้พอดีกับรูปที่เรา Print Screen ไว้ แถมรูปนี้ยังมีขนาดเท่ากับขนาดหน้าจอของเราพอดีเป๊ะๆ อีกด้วยนะครับ โอ้วว !!

            「ทำไมรูปถึงเท่ากับขนาดจอพอดีล่ะขอรับ?」
           "ก็เรา Print Screen wallpaper เอาไว้ไงล่ะเลยได้รูปขนาดเท่า wallpaper พอดีไง ^^ "


           หลังจากเราวางรูปที่จะแก้ไขลงบนกระดานวาดรูปของ Paint แล้วเราก็จะเริ่มแก้ไขรูปกันแล้วนะครับ



           วิธีการก็คือ ใช้เครื่องมือที่ชื่อว่า selection เพื่อเลือกบริเวณของรูปที่ต้องการโยกย้าย
      
           ก่อนอื่นต้องซูมกระดานวาดรูปให้มองรูปได้ในขนาดเต็ม โดยการ กด Ctlr + การหมุน scroll mouse เพื่อซูมกระดานวาดรูปเข้าออก เมื่อได้กระดานที่มองได้เต็มรูป จะเริ่มการแก้ไขรูปโดยการใช้ selection เลือกพื้นที่ที่ต้องการโยกย้าย

           ในที่นี้ผมเลือก Tifa แล้วลากไปยังมุมซ้ายของ wallpaper และย้าย Cloud ไปทางขวา

           「เราสามารถใช้ cursor ลากรูป หรือใช้ ปุ่มลูกศรบนแป้นพิมพ์ ย้ายรูปก็ได้ขอรับ 」
           "นอกจากนี้ยังย่อ-ขยายรูป ลบ เพิ่ม ได้ตามต้องการด้วยนะครับ"

          เมื่อได้รูปที่ต้องการแล้วก็อย่าลืมบันทึก (save) รูปเอาไว้ครับ
          จากนั้นลองนำไปใช้เป็น Wallpaper ดู จะได้ Wallpaper หน้าตาแบบนี้

            ถ้าหากแก้ไขครั้งแรกแล้วไม่พอใจ สามารถแก้ไขรูปได้เรื่อยๆนะครับ โดยการเลือกรูปที่เซฟไว้ แล้วเปิดรูปด้วย Paint เหมือนเดิม เท่านี้ก็สามารถแก้ไขรูปได้เรื่อยๆ จนกว่าจะพอใจแล้วครับ ^^

            "เท่านี้ก็ได้ Wallpaper สวยๆ (รึเปล่าหว่า) มาตกแต่งบน Desktop ของตัวเองแล้วนะครับ"
            「โอ้วว ง่ายแค่นี้เองขอรับ >w< 」