BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
------
TIỂU LUẬN
ĐƯỜNG ĐI TRONG MÊ CUNG
VÀ ỨNG DỤNG
Giáo viên hướng dẫn: PGS.TSKH.Trần Quốc Chiến
Học viên thực hiện: 1.Lê Châu Vân
( nhóm 1) 2.Đào Quang Hòa
3.Mai Xuân Kiên
4.Phạm Bình Nguyên
5.Lê Thị Bích Huy
Lớp: Phương pháp Toán Sơ Cấp
Khoá: 2009 - 2011
Kon Tum, tháng 03 năm 2010.
Trang 1
MỤC LỤC
1_ Lời nói đầu……………………………………………................….....…. Trang 02
2_Các thành viên trong nhóm.......................................................................... Trang 04
3_Phần nội dung.............................................................................................. Trang 05
4_Chương I: Đại cương về đồ thị ………………………………....……… Trang 05
5_Chương II: Các bài toán tìm đường đi trong mê cung ………....……… Trang 08
6_Chương III: Các bài toán ứng dụng……………………………....………. Trang 17
7_Kết luận…………………………………………………………....…… .. Trang 24
8_Tài liệu tham khảo…………………………………………….....……….. Trang 25
Trang 2
LỜI NÓI ĐẦU
Lý thuyết đồ thị là ngành học được phát triển từ lâu nhưng lại có nhiều ứng dụng
hiện đại. Những ý tưởng cơ bản của nó đã được nhà toán học Thụy sĩ vĩ đại Leonhard
Euler đưa ra từ thế kỷ 18.
Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Đây là

( nhóm 1) chọn đề tài: '' Đường đi trong mê cung và ứng dụng '' để viết bài tiểu luận này.
Các thành viên trong nhóm
STT Họ tên học viên Công việc (Theo mục ) Ghi chú Nhận xét của Giáo Viên
1 Lê Thị Bích Huy Lời mở đầu
Trang 4
Danh sách nhóm
Chương I
2 Lê Châu Vân Chương I
Chương II
3 Đào Quang Hoà Chương II
Chương III
4 Phạm Bình Nguyên Chương II
Chương III
5 Mai Xuân Kiên Chương III
Kết luận
Tài liệu tham khảo

PHẦN NỘI DUNG
CHƯƠNG I. ĐẠI CƯƠNG VỀ ĐỒ THỊ.
Trang 5
I. Các khái niệm cơ bản.
1. Đồ thị vô hướng.
a. Định nghĩa: Đồ thị vô hướng G = (V, E) gồm một tập V các đỉnh và tập E các
cạnh. Mỗi cạnh e E được liên kết với một cặp đỉnh v, w (không kể thứ tự).
b. Ví dụ:
Hình 1 Hình 2
H1: Đồ thị có 4 đỉnh, 7 cạnh H2: Đồ thị có 10 đỉnh, 10 cạnh
2. Đồ thị có hướng.
a. Định nghĩa: Đồ thị có hướng G = (V , E) gồm một tập V các đỉnh và tập E các
cạnh có hướng gọi là cung . Mỗi cung e E được liên kết với một cặp đỉnh (v, w)

- Nếu tại đỉnh nào đó mọi cạnh liên thuộc nó đã đi qua thì quay ngược lại
cho đến khi gặp đỉnh có cạnh chưa qua.
Bằng cánh này ta có thể đi qua tất cả các cạnh của đồ thị. Tuy nhiên để có
thể thực hiện thuật toán này ta cần phải nhớ thứ tự các cạnh đã đi qua.
b. Thuật toán Tarri.
Xuất phát từ đỉnh s đi theo cạnh của đồ thị theo các nguyên tắc sau:
- Đánh dấu hướng đã đi qua của cạnh.
- Với mỗi đỉnh bậc lớn hơn hoặc bằng 3 của đồ thị, cạnh dẫn đến nó lần
đầu tiên được đánh dấu đặc biệt.
- Tại mỗi đỉnh chọn cạnh chưa đi qua trước đó. Trường hợp các cạnh đã đi
qua thì chọn cạnh đi theo hướng ngược lại. Cạnh đánh dấu đặc biệt là
phương án cuối cùng nếu không còn cách nào khác.
Bằng cách này ta đi qua tất cả các cạnh của đồ thị. Như vậy nếu đồ thị liên thông thì
lúc nào đó ta sẽ đến đỉnh e.
* Qua hai thuật toán, ta thấy để thực hiện được thuật toán viener thì cần phải nhứ
thứ tự các cạnh đã đi qua, phải có phương tiện nhớ như "cuộn chỉ Ariadne" còn thuật toán
của Tarri thì chỉ cần đánh dấu nên hiệu quả hơn:
CHƯƠNG II. CÁC BÀI TOÁN TÌM ĐƯỜNG ĐI
TRONG MÊ CUNG.
Trang 8
A
B
- Bài toán 1: Cho mê cung như hình bên
Bài toán đặt ra là tìm đường đi từ vị trí A đến vị trí B?
Ta xây dựng đồ thị G từ mê cung trên bằng cách đặt các hành lang là các cạnh, các giao
điểm của chúng là các đỉnh.
Ta có G = (V, E), trong đó V = . Ta xây dựng đồ thị G:
Trang 9
Z
Y

B
A
X
5
X
9
X
10
X
8
B
A
A
X
2
X
1
X
9
X
10
X
8

B
X
3
X
5
X

t
a

c
ó

t
h
ể

đ
i

q
u
a

X

h
o
ặ
c

Y
.

G
i
ả

g
õ

c
ụ
t
.

T
a

b
u
ộ
c

p
h
ả
i

q
u
a
y

l
ạ
i


h
ư
a

đ
i

q
u
a

l
à

A
.
T
ạ
i

A
,

t
a

k
h
ô
n

y

t
a

c
h
ỉ

c
ó

t
h
ể

s
a
n
g

t
r
á
i

q
u
a


s
ử

t
ừ

Y

t
a

đ
i

t
ớ
i

Z
.

Đ
â
y

l
à

n
g

p
h
ả
i

q
u
a
y

l
ạ
i

Y
.

T
ừ

Y

t
a

đ
i

đ
ế

t
h
ể

đ
i

t
ừ

A

đ
ế
n

B

t
h
e
o

đ
ư
ờ
n
g
: