TRƯỜNG ðẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN
KHOA CÔNG NGHỆ THÔNG TIN

BÀI TẬP
HỌC PHẦN TOÁN RỜI RẠC 2

Trình ñộ ñào tạo

Hệ ñào tạo:

:

ðại học
Chính quy/Liên thông Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 2

MỤC LỤC
Bài 1: Các khái niệm cơ bản của Lý thuyết ñồ thị 5
Mục tiêu 5
a. Nhắc lại lý thuyết 5
b. ðề bài tập 5
c. Hướng dẫn giải 6
d. Bài tập tự giải 7
Bài 2: Biểu diễn ñồ thị trên máy tính 10
Mục tiêu 10
a. Nhắc lại lý thuyết 10
b. ðề bài tập 10
c. Hướng dẫn giải 10
d. Bài tập tự giải 14
Bài 3: ðồ thị Euler 15
Mục tiêu 15
a. Nhắc lại lý thuyết 15
b. ðề bài tập 16
c. Hướng dẫn giải 16
d. Bài tập tự giải 19
Bài 4: ðồ thị hamilton 20
Mục tiêu 20
a. Nhắc lại lý thuyết 20
b. ðề bài tập 20
c. Hướng dẫn giải 20
d. Bài tập tự giải 22
Bài 5: Thảo luận cài ñặt ñồ thị, các thuật toán liệt kê chu trình Euler và Hamilton.
Thảo luận về bài tập lớn 23
Mục tiêu 23
a. Nhắc lại lý thuyết 23
b. ðề bài tập 23

Mục tiêu 97
a. Nhắc lại lý thuyết 97
b. ðề bài tập 98
c. Hướng dẫn giải 99
d. Bài tập tự giải 101

Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 5
Bài 1: Các khái niệm cơ bản của Lý thuyết ñồ thị
Mục tiêu
- Lưu trữ ñược ñồ thị trên máy tính theo những phương pháp khác nhau.
- Cài ñặt ñược chương trình chuyển ñổi giữa các phương pháp.
- Sinh viên có khả năng tự học.
a. Nhắc lại lý thuyết
- Hai ñỉnh x, y ñược gọi là cặp ñỉnh liên thông , nếu hoặc giữa x và y có ít nhất một
xích nối với nhau, hoặc tồn tại ít nhất một ñường ñi từ y sang x.
- ðồ thị vô hướng G(V,E) ñược gọi là ñồ thị liên thông, nếu mọi cặp ñỉnh của nó
ñều liên thông.
- ðồ thị có hướng G(V,E) ñược gọi là ñồ thị liên thông mạch, nếu mọi cặp ñỉnh của
nó ñều liên thông.
- Biểu diễn dạng hình học: Giả sử có ñồ thị G(V,E).
Biểu diễn ñỉnh: lấy các ñiểm trên mặt phẳng hay trên không gian tương ứng
với các phần tử của tập V và dùng ngay ký hiệu các phần tử này ñẻ ghi trên các
ñiểm tương ứng.
Biểu diễn cạnh: Nếu cạnh a với hai ñỉnh ñầu là x,y thì nó ñược biểu diễn
bằng ñoạn thẳng hay một ñoạn cong nối giữa hai ñiểm x, y và không ñi qua các
ñiểm tương ứng trong không gian.
Biểu diễn cung: nếu cung a có ñỉnh ñầu là x, ñỉnh cuối là y, thì nó ñược biểu
diễn bằng một ñoạn thẳng hoặc ñoạn cong ñược ñịnh hướng ñi từ x sang y và không

b.
Tên ñồ thị Tính liên thông Tên thành phần liên thông
G1 Có G1
G2 Có G2
G
1

1

4
3

2

5
7

6

8

9

00
G
2

G
3


bieetr ngồi chen giữa hai ñại biể nói trên , ñể người ngồi giữa hai người mà anh(
chị) ta quen.
Hướng ñẫn:
Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 8
ðể giải ñược bài toán trên trước hết ta xây dựng các ñồ thị tương ứng, sau ñó vận
dụng kết quả của ñịnh lý 4.1, hệ quả 4.1 và ñịnh lý 4.2 mà suy ra kết luận.
Xuây dựng ñồ thị
• ðỉnh: Lấy các ñiểm trong mặt phẳng hay trong không gian tương ứng với các
hòn ñảo thuộc quần ñảo ( các bạn học sinh trong lớp 11A, các ñại biểu ñến
họp).
• Cạnh: Hai ñiểm x, y ñược nối bằng một cạnh khi và chỉ khi hai hòn ñảo x, y
có ñường ngầm trực tiếp với nhau( các bạn x, y trao ñổi ñịa chỉ cho nhau, các
ñại biểu x, y quen nhau)
- ðồ thị nhân ñược ký hiệu bằng G
1
, (G
2
, G
3
)
- ðồ thị G
1
mô tả toàn bộ lưới ñường ngầm trong quần ñảo
- ðồ thị G
2
mô tả toàn bộ quan hệ trao ñổi ñịa chỉ trong lớp 11A
- ðồ thị G
3

Bài 4 Cho G ñồ thị như sau:
Chỉ ra tập ñỉnh, cạnh(vô hướng,có hướng, khuyên, ) của mỗi ñồ thị ñã cho? Chỉ
loại ñồ thị ñó? ðồ thị có liên thông ko? Nếu ñồ thị ko liên thông hãy chỉ ra các
Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 9
thành phần liên thông? ðồ thị có chu trình ko? Chỉ ra các chu trình của ñồ thị (nếu
có)?

Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 10
Bài 2: Biểu diễn ñồ thị trên máy tính
Mục tiêu
- Nêu ñược các cách biểu diễn ñồ thị và biểu diễn ñồ thị trên máy tính trên máy tính.
- ðưa ra ñược ma trận kề, danh sách các cạnh, cung tương ứng với 1 ñồ thị cho
trước.
- Lưu trữ ñược ñồ thị trên máy tính theo những phương pháp khác nhau.
- - Phân tích ñược bài toán thực tế tương ứng phần lý thuyết ñã học.
- Sinh viên có khả năng tự học.
a. Nhắc lại lý thuyết

b. ðề bài tập
Bài 1 Cho G ñồ thị gồm 4 phần G1, G2, G3 và G4 như sau:

G
2

G
3

G
4

Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 11
Tên ñồ thị a. ma trận kề
b. danh sách
cạnh(cung)
c.danh sách kề
G1 1 2 3 4
1 0 1 0 1
2 1 0 0 1
3 0 0 0 1
4 1 1 1 0
Danh sách cạnh
1 2
1 4
2 3
2 4
3 4
1 2 4
2 1 4
3 4

2 1
2 3
2 4
1 2 4
2 1 4
3 4
4 1 2 3
5 6 7
6 7
Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 12
6 0 0 0 0 1 0 1 0 0 0
7 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 1 0
9 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0

3 2
3 4
4 1
4 2
4 3
5 6
5 7
6 7
8 9
9 8
0


for j:=1 to m do
begin
write(‘Cho dinh dau va cuoi cua canh ‘,j,’:’);
readln(x,y);
new(t); t^.v:=x, t^.next:=Ke[y]; Ke[y]:=t;
new(t); t^.v:=y, t^.next:=Ke[x]; Ke[x]:=t;
end;
writeln(‘Danh sach ke cua cac dinh cua do thi:’);
for J:=1 to m do
begin
writeln(‘Danh sachcac dinh ke cua dinh ‘,j,’:’);
t:=Ke[j];
Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 14
while t^.next<>nil do
begin
write(t^.v:4);
t:=t^.next;
end;
end;
readln;
End.

d. Bài tập tự giải Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 15

2. Không bao giờ ñi qua một cầu, trừ phi không còn cách ñi nào khác.

b. ðề bài tập
Bài 1: ðồ thị sau có là ñồ thị nửa Euler hay ñồ thị Euler ko? Giải thích?
c. Hướng dẫn giải
Bài 1: ðồ thị sau có là ñồ thị nửa Euler hay ñồ thị Euler ko? Giải thích?

Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 17

ðồ thị G1 là ñồ thị nửa Euler
Thật vây, các ñỉnh a,b,e có bậc là 2,4,4 là bậc chẵn, các ñỉnh c và d có bậc là 3 là
bậc lẻ

ðồ thị G2 là ñồ thị nửa Euler
Thật vây, các ñỉnh c và d có bậc là 2 là bậc chẵn, các ñỉnh a và c có bậc là 1 là bậc
lẻ

a

b

e

c

d

G1


e

f

G3
1
2
3 4
5
Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 19

Xuất phát từ u, ta có thể ñi theo cạnh (u,v) hoặc (u,x), giả sử là (u,v) (xoá
(u,v)). Từ v có thể ñi qua một trong các cạnh (v,w), (v,x), (v,t), giả sử (v,w) (xoá
(v,w)). Tiếp tục, có thể ñi theo một trong các cạnh (w,s), (w,y), (w,z), giả sử (w,s)
(xoá (w,s)). ði theo cạnh (s,y) (xoá (s,y) và s). Vì (y,x) là cầu nên có thể ñi theo một
trong hai cạnh (y,w), (y,z), giả sử (y,w) (xoá (y,w)). ði theo (w,z) (xoá (w,z) và w)
và theo (z,y) (xoá (z,y) và z). Tiếp tục ñi theo cạnh (y,x) (xoá (y,x) và y). Vì (x,u) là
cầu nên ñi theo cạnh (x,v) hoặc (x,t), giả sử (x,v) (xoá (x,v)). Tiếp tục ñi theo cạnh
(v,t) (xoá (v,t) và v), theo cạnh (t,x) (xoá cạnh (t,x) và t), cuối cung ñi theo cạnh
(x,u) (xoá (x,u), x và u).
d. Bài tập tự giải Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 20
Bài 4: ðồ thị hamilton


ðồ thị G1 là ñồ thị Hamilton ðồ thị G2 là ñồ thị nửa Hamilton

ðồ thị G3 không có chu trình hay ñường ñi Hamilton
a

b

e

c

d

G1
a

d

b

c

G2
g

a

- Lưu trữ ñược ñồ thị trên máy tính theo những phương pháp khác nhau.
- Chuyển ñổi giữa các kiểu biểu diễn ñồ thị trên máy tính.
- Nâng cao khả năng làm việc nhóm.
- Rèn luyện tư duy sáng tạo.
- Phân tích ñược bài toán thực tế tương ứng phần lý thuyết ñã học.
- Sinh viên có khả năng tự học.
a. Nhắc lại lý thuyết
Xem lại trong bài 3 và bài 4
b. ðề bài tập
Bài 1 Tìm chu trình Euler trong ñồ thị G.
Bài 2 Tìm chu trình Halmiton trong ñồ thị G.

c. Hướng dẫn giải
Bài 1 ðề bài : Cài ñặt chương trình tìm chu trình Euler trong ñồ thị G.
Cho ñồ thị G=(X,E) tồn tại chu trình Euler. Hãy tìm chu trình (chi trình Euler là
chu trình ñi qua tất cả các cạnh của ñồ thị, mỗi cạnh ñi qua ñúng một lần).
Phân tích bài toán :
ðầu vào: ðồ thị G
ðầu ra: Chu trình Euler (nếu có)
2. Thuật toán:
Xuất phát từ một ñỉnh u bất kỳ, khi ñi qua cạnh nào thì xoá cạnh ñó khỏi ñồ thị và
ghi lại từ trái sang phải. Khi thực hiện thuật toán cần lưu ý nếu gặp cạnh bắc cầu
giữa 2 thành phần liên thông thì ta phải xoá hết thành phần liên thông rồi mới xoá
ñến cạnh bắc cầu.
Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 24
Khi xoá cạnh bắc cầu thì phải loại hết các ñỉnh trơ trọi (nghĩa là không kề với bất cứ
ñỉnh nào thuộc ñồ thị).
Cấu trúc dữ liệu:

End;
End;
Chương trình minh họa :
Program Chu_trinh_Euler;
Const Nmax=100;
Emax=100;
Var a:array[1…Nmax,1 Nmax]of integer;
Ctr: array[1…Emax,1,2]of integer;
dd: array[1…Nmax]of Boolean;
lt: array[1…Nmax]of integer;
SolC,N:integer;
(*Biến Solc là số cạnh của chu trình, sẽ tăng lên một ñơn vị mỗi khi ta ñi qua
một cạnh*).
Program Timtplt(k:integer);
(* Thủ tục này tìm thành phần liên thông giống như thuật toán tình thành phần
liên thông trình bày ở trên chỉ khác một ñiểm là ta chỉ tìm tplt ñối với các ñỉnh chưa
bị loại khỏi ñồ thị *).
Var i:integer;
Begin lt[k]:=sotp;