|
|
|
..............เมือง Konigsberg , Prussia ( ปัจจุบัน เรียกว่า Kaliningrad และเป็นส่วนหนึ่งของรัสเซีย ) ถูกแบ่งออกเป็น 4 ส่วนตามสายของแม่น้ำ Pregel คือ 2 ฝั่งของแม่น้ำ เกาะ Kneiphof และพื้นที่ที่อยู่ระหว่าง แม่น้ำ 2 สายในศตวรรษ ที่ 18 มีการสร้างสะพานเชื่อมดินแดนทั้ง 4 เข้าด้วยกัน ทั้งหมด 7 สะพาน ดังรูปที่ 1
...............ประชาชนในเมืองจะเดินข้ามเมืองในวันอาทิตย์พวกเขาสงสัยว่าเป็นไปได้ไหมที่จะเริ่มต้นเดินที่จุดแห่งหนึ่งใน เมืองเดินทางผ่านสะพานทั้งหมดโดยไม่ข้ามซ้ำอีกครั้ง ( ข้ามสะพานเพียง 1 ครั้ง ต่อ 1 สะพาน )และกลับมายังจุด เดิม ลีโอนาด ออยเลอร์ ( Leonhard Euler ) นักคณิตศาสตร์ชาวสวิสได้แก้ปัญหานี้ในปี 1736.เขาแสดงให้เห็นว่า อาจเป็น ครั้งแรกที่ใช้ทฤษฎีกราฟ ออยเลอร์ศึกษาปัญหานี้โดยใช้ มัลติกราฟ ( Multigraph )โดยให้จุดยอดแทนดิน แดนทั้ง 4 และด้าน ( edges ) แทนสะพาน มัลติกราฟ แสดงให้เห็นดังรูปที่ 2
................ ปัญหาในการเดินทางข้ามสะพานทุกสะพาน โดยไม่ข้ามซ้ำสามารถนำมาใช้อีกครั้งในรูปแบบนี้คำถามที่ ี่เกิดขึ้น คือ ทุกด้านจะถูกบรรจุด้ายวงจรง่าย ๆ ในมัลติกราฟไหม
..หน้า [
1 ] [
2 ] [
3 ] [
4 ] [
5 ] [
6 ] [
7 ] [
8 ] [
9 ] [
10 ] [
11 ] [
12 ] [
ทบ. 1 ] [
ทบ. 2 ] [
ทบ.3 ]