creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
ปั่นจักรยานชมเมือง


รูปที่เห็นคือแผนที่ถนนเชื่อมจุดท่องเที่ยวภายในเมือง 14 แห่ง เป็นไปได้หรือไม่ที่จะเดินทางผ่านทุกจุดจุดละ 1 ครั้ง?


ปัญหาข้อนี้แก้ได้ง่าย ๆ โดยใช้วิธีลงสี (coloring proof) ให้เราลงสีจุดที่อยู่ติดกันด้วยสีที่ต่างกัน จำนวนสีที่มากที่สุดที่เราใช้คือ 14 สี (เพราะมี 14 จุด) แต่จำนวนสีที่น้อยที่สุดเท่ากับเท่าไรนั้น เราต้องดูโครงสร้างของกราฟ ในที่นี้คือ 2 สี เพราะไม่มี 3 เมืองใดเชื่อมกันเป็นวง ขอใช้สีดำกับสีแดง ถ้าเราไม่เดินทางย้อนกลับเข้าจุดที่เพิ่งจากมา รูปแบบสีของจุดจะต้องสลับกัน ดำ-แดง-ดำ-แดง-... หรือ แดง-ดำ-แดง-ดำ... 14 เมืองจึงต้องมี 7 ดำ และ 7 แดง แต่จากรูปไม่ว่าเราจะลงสีอย่างไรก็ได้ 6 ดำ 8 แดง หรือ 6 แดง 8 ดำ ดังนั้นคำตอบคือเป็นไปไม่ได้ครับ










Create Date : 03 มีนาคม 2551
Last Update : 3 มีนาคม 2551 14:17:43 น. 0 comments
Counter : 1047 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.