<<가장 빠른 경로를 찾는 문제-a Hamiltonian path>>

A Math Forum Project

Problem of the Week Logo  
Discrete Math
Problem of the Week


_________________________________
Student Center || Teachers' Place || All Problems of the Week || Search Dmpows
_________________________________

Past Problems and Solutions
Last Week's Solution
   Become a Mentor
   Frequently Asked Questions

_____________________________________

Mother's Chores - posted November 15, 1999

탐의 어머니는 학교에서 탐과 헤어진 후, 그녀는 몇 가지 심부름을 해야 했다. 그녀는 약국, 슈퍼마켓과 우체국에 가야 했다. 약국, 슈퍼마켓과 우체국에 들리고 집에 도착하는데 걸리는 최소한의 거리는? 그녀는 오로지 길을 따라서 가야만 한다.이 마을안에는 두 개의 길이 있다. 가장 가까운 전체 블럭의 수로 길이를 측정한다. 그녀는 얼마나 많은 블럭들을 지나야만 집에 도착할 수 있는지 다이어그램이나 차트가 도움이 될 것이다.

힌트: 이런 trip 유형을 Hamiltonian path라고 부른다. 다음 website에서 Hamiltonian path의 정보를 알 수 있다.:

http://www.utc.edu/~cpmawata/petersen/lesson12.htm

http://www.utm.edu/departments/math/graph

Bonus: Using Graph Theory, draw a weighted graph using the stops as vertices, the paths between them as edges, and the distance between the stops as the weights. If you cannot upload your diagram, then you may describe your graph in detail


[Discrete Math Problem of the Week
[Past Problems and Solutions]  [Last Week's Solution
[Become a Mentor]
[Search all Discrete Math Problems of the Week]


Math Forum Home || Math Library || Quick Reference || Math Forum Search