Chu trình vô hướng hamilton

ĐỒ THị EULER VÀ ĐỒ THị HAMILTON Trong chương này chúng ta sẽ tập trung nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồ thị Hamilton. Trong quá trình trình bày nếu không có chú thích bổ xung gì thì ta hiểu thuật ngữ đồ thị dùng để chỉ đồ thị tổng quát (Đa đồ thị vô hướng hoặc có hướng), thuật ngữ cạnh dùng để chỉ cả cạnh lẫn cung cua đồ thị.

9p suatuoiconbo 29-07-2011 135 21   Download

Chu trình Hamilton Năm 1857 W. R. Hamilton, nhà toán học người Ailen đã đưa ra trò chơi sau đây: Trên mỗi đỉnh trong số 20 đỉnh của một khối đa diện 12 mặt ngũ giác đều có ghi tên một thành phố lớn của thế giới. Hãy tìm cách đi bằng các cạnh của khối này để đi qua tất cả các thành phố, mỗi thành phố đúng một lần. Bài toán này đã dẫn tới những khái niệm sau đây.

6p yeuthuong 01-12-2010 443 81   Download