MỤC LỤC
Bài 1 Các khái niệm cơ bản của lý thuyết ñồ thị
3

Mục tiêu 3

a. Nhắc lại lý thuyết 3

b. ðề bài tập 3

c. Hướng dẫn giải 4

d. Bài tập tự giải 5

Bài 2 Biểu diễn ñồ thị trên máy tính
6

Mục tiêu 6

a. Nhắc lại lý thuyết 6

b. ðề bài tập 6

c. Hướng dẫn giải 7

d. Bài tập tự giải 10

Bài 3 ðồ thị Euler
12

Mục tiêu 12


b. ðề bài tập 20

c. Hướng dẫn giải 21

d. Bài tập tự giải 28

Bài 7

Cây và cây khung
29

Mục tiêu 29

a. Nhắc lại lý thuyết 29

b. ðề bài tập 30

c. Hướng dẫn giải 30

d. Bài tập tự giải 36

Bài 8 Thảo luận về cài ñặt thuật toán tìm cây khung nhỏ nhất trên ñồ thị
38

Bài 9, 10 Bài toán tìm ñường ñi ngắn nhất
38

Mục tiêu 38


tuệ nhân tạo, ). Bài tập ñể củng cố và nâng cao kiến thức trong môn học này
Về nội dung, bám sát với chương trình của nhà trường và hệ thống bài tập cũng ñược
biên soạn theo các chương lý thuyết. Với mỗi bài sẽ ñược chia thành 4 phần:
Phần A. Nhắc lại lý thuyết: tóm tắt các kiến thức cơ bản, các ví dụ và các lưu ý hữu
ích, các kinh nghiệm trong khi lập trình
Phần B. ðề bài tập: ñưa ra các loại bài tập khác nhau, với các mức ñộ khác nhau.
Phần C. Bài tập mẫu: Hướng dẫn giải một số bài tiêu biểu trong phần B, có phân
tích thuật toán và cài ñặt chương trình.
Phần D. Bài tập tự giải: Người học thực hiện việc giải các bài tập này.
Mong rằng tài liệu này ñáp ứng ñược phần nào nhu cầu của học sinh, sinh viên. Bộ môn:

Công ngh
ệ phần mềm

Khoa: Công nghệ thông tin
Trường: ðại học sư phạm kỹ thuật Hưng YênBài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2011
Trang 3

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

chỉ ra các thành phần liên thông?
c. ðồ thị G, G1, G2, G3, G4 và G5 có chu trình không? Chỉ ra các chu trình của ñồ thị (nếu
có)?
A

B

C

D

Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2011
Trang 4
c. Hướng dẫn giải
Bài 1
a.
Tên ñồ thị Tập ñỉnh V Tập cạnh E Loại ñồ thị
G1 1, 2, 3, 4 (1,2); (1,4); (2,3); (2,4); (3,4) Vô hướng
G2 5, 6, 7 (5,7); (6,5); (6,7) Có hướng
G3 8, 9 (8,9) Vô hướng
G4 0
G 1, 2, 3, 4, 5, 6, 7,
8, 9, 0
(1,2); (1,4); (2,3); (2,4); (3,4);
(8,9); (5,7); (6,5); (6,7)
Hỗn hợp



8

9

0
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 - 2011
Trang 5

d. Bài tập tự giải
Bài tập 1 ðồ thị sau là ñồ thị vô hướng hay ñồ thị có hướng? ðưa ra các cạnh vô hướng
(nếu có) của ñồ thị? ðưa ra các cạnh có hướng (nếu có) của ñồ thị? Tính bậc các ñỉnh của
ñồ thị vô hướng? Tính bậc vào(ra) của các ñỉnh trên ñồ thị có hướng? Kiểm tra tính liên
thông của ñồ thị? ðưa ra 1 ñường ñi ñộ dài 5 của ñồ thị? Chỉ ra ít nhất 1 chu trình của ñồ thị
(nếu có)? Bài tập 2 Khi về nghỉ hè mỗi bạn sinh viên của lớp TK7 trường ðHSPKTHY ñều trao ñổi
ñịa chỉ với ít nhất một nửa số bạn trong lớp. Chứng minh rằng trong thời gian nghỉ hè mỗi
bạn của lớp TK7 ñều có thể báo tin trực tiếp hay gián tiếp cho các bạn trong lớp.
Hướng ñẫn:

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

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
- Biểu diễn ñồ thị dạng ma trận kề
A=( a
i,j
: i, j = 1, 2, . . . ,n)
a
i,j
= 1 , nếu có cạnh từ i sang j hay (i, j) ∈ E, i, j =1, 2,. . ., n.
a
i, j
= 0, trong trường hợp còn lại tức là không có cạnh(i, j)
- Biểu diễn ñồ thị dạng danh sách các cạnh (cung)
E=(e
i,j
: i= 1, 2, . . . ,m; j = 1, 2)
(e
i,1
,e
i,2
) là cạnh thứ i trong m cạnh (cung) của ñồ thị.


0
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 - 2011
Trang 7

c. Hướng dẫn giải
Bài 1
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

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

Danh sách cung
1 2
1 4
2 1
2 3
2 4
3 2
3 4
4 1
4 2
4 3
5 7
6 5
6 7
1 2 4
2 1 4
3 4
4 1 2 3
5 7
6 5 7
8 9
9 8
0


for (int i = 0; i < m; i++)
{
Console.Write("Canh thu {0}:", i + 1);
A = int.Parse(Console.ReadLine());
B = int.Parse(Console.ReadLine());
x = int.Parse(Console.ReadLine());
ft.WriteLine("{0} {1} {2}", A, B, x); //ghi DL vao
}
ft.Close();
}
//doc tep "d:/trr/DScanh.in", DS canh, ghi BD ma tran ke "d:/trr/mtrke.out"
static public void doctep()
{
try
{
StreamReader fi = new StreamReader(filenameIN);
StreamWriter fo = File.CreateText(filenameOUT);
//lan luot doc DL ve tung canh trong tep DScanh.in, luu Gtr thu dc vao mang a[i,j]
// lan luot ghi Dl tu a[i,j] vao teo mtrke.out
Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2011
Trang 9

string s;
int i, j, n, m;
s = fi.ReadLine();
string[] n1 = new string[3]; n1 = s.Split('\t');
n = int.Parse(n1[0]);
m = int.Parse(n1[1]);
int[,] a = new int[n, n]; //mang luu do thi theo mtran ke
//tep "d:/trr/DScanh.out" luu D1 so dinh va so canh cua dthi

Console.WriteLine(e.Message);
}
Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2011
Trang 10

}
public static void Main()
{
nhaptep();
doctep();
Console.ReadLine();
}
}
}
Kết quả ñầu vào và ñầu ra tương ứng cho chương trình trên
"d:/dsc.in" "d:/mtk.out" "d:/dsc.in" "d:/mtk.out"
6 15
1 2 33
1 3 17
1 4 85
1 5 85
1 6 85
2 3 18
2 4 20
2 5 85
2 6 85
3 4 16
3 5 4
3 6 85
4 5 9

0 0 4 14 10 0 2 0 0
0 0 0 0 0 2 0 1 6
8 11 0 0 0 0 1 0 7
0 0 2 0 0 0 6 7 0

d. Bài tập tự giải
Bài tập 1 Biểu diễn ñồ thị dưới dạng dạng ma trận kề, danh sách cạnh, danh sách kề

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

Bài tập 2 Cài ñặt chương trình nhập ñồ thị biểu diễn dạng ma trận kề (danh sách
cạnh(cung), danh sách kề) từ tệp và hiển thị ñồ thị ra màn hình.
Bài tập 3 Cài ñặt chương trình nhập ñồ thị biểu diễn dạng ma trận kề (danh sách
cạnh(cung), danh sách kề) từ tệp và hiển thị ñồ thị biểu diễn dạng còn lại ra màn hình.
Bài tập 4 ðọc dữ liệu từ file text (ñồ thị biểu diễn dạng ma trận kề) và lưu vào danh sách kề
và hiển thị ra màn hình.
Bài tập 5 ðọc dữ liệu từ file text (ñồ thị biểu diễn dạng ma trận kề) và lưu vào danh sách
cạnh và hiển thị ra màn hình.
Bài tập 6 ðọc dữ liệu từ file text (ñồ thị biểu diễn dạng danh sách cạnh) và lưu vào danh
sách kề và hiển thị ra màn hình.
Bài tập 7 ðọc dữ liệu từ file text (ñồ thị biểu diễn dạng danh sách kề) và lưu vào ma trận kề
và hiển thị ra màn hình.
Bài tập 8 ðọc dữ liệu từ file text (ñồ thị biểu diễn dạng danh sách kề) và lưu vào danh sách
cạnh và hiển thị ra màn hình.
Bài tập 9 Cài ñặt chương trình nhập ñồ thị vô hướng biểu diễn dạng ma trận kề (danh sách
cạnh(cung), danh sách kề) từ tệp. Tính bậc các ñỉnh của ñồ thị.
Bài tập 10 Cài ñặt chương trình nhập ñồ thị có hướng biểu diễn dạng ma trận kề (danh sách
cạnh(cung), danh sách kề) từ tệp. Tính bậc vào, bậc ra của các ñỉnh của ñồ thị.
Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2011

b. ðề bài tập
Bài 1 ðồ thị sau có là ñồ thị nửa Euler hay ñồ thị Euler không? Giải thích?
Bài 2 Dùng thuật toán Flor ñể tìm tìm chu trình Euler cho ñồ thị.

c. Hướng dẫn giải
Bài 1 ðồ thị sau có là ñồ thị nửa Euler hay ñồ thị Euler không? Giải thích?

ðồ 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ị G3 không là ñồ thị Euler
Thật vậy G3 có 3 ñỉnh a,d và g có bậc là 1 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ẻ

ðồ thị G4 là ñồ thị nửa Euler vì theo hệ quả
Thật vây, các ñỉnh 3,4,5 có bậc là 2 là bậc chẵn, các ñỉnh 1
và 2 có bậc là 3 là bậc lẻ
1
2
3 4
5
g


d

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

Bài 2 Dùng thuật toán Flor ñể tìm tìm chu trình Euler cho ñồ thị sau:

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 cùng ñi theo cạnh (x,u) (xoá (x,u), x và u).
d. Bài tập tự giải
Bài tập 1 ðồ thị sau có là ñồ thị nửa Euler hay ñồ thị Euler không? Dùng thuật toán Flor ñể
tìm chu trình Euler(ñường Euler) nếu ñồ thị nửa Euler(ñồ thị Euler) sau: Bài tập 2 Một xe chở khách du lịch cần ñi tham quan các con ñường giữa N thành phố (các
thành phố ñược ñánh số từ 0 dến N-1, N<100). Giữa 2 thành phố bất kỳ nếu có ñường ñi
ñến nhau thì bao giờ cũng là ñường 2 chiều, và hai thành phố bất kỳ ñược nối trực tiếp với
nhau bởi nhiều nhất một con ñường.
Liệu có cách nào qua tất cả các ñường, mỗi ñường ñúng 1 lần hay không? Xây dựng giải
thuật và cài ñặt chương trình giúp cho người lái xe khách du lịch.

Bài 1 ðồ thị sau có là ñồ thị nửa Hamilton hay ñồ thị Hamilton không? Giải thích?
Bài 2 Liệt kê tất cả các chu trình Hamilton của ñồ thị.
c. Hướng dẫn giải
Bài 1 ðồ thị sau có là ñồ thị nửa Hamilton hay ñồ thị Hamilton không? Giải thích?

ðồ thị G1 là ñồ thị Hamilton

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

g

a

d

b

c

e

f

G3
a

b

e


}
public Node(int v, Node next)
{
this.v = v;
this.next = next;
1
2
3 4
5
a

d

b

c

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

}
}
class Program
{
static int m, n, v0;
static Node t;
static Node[] ke ;
static int []dinh;
static bool[] chuaxet;

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

ke[i] = null;
chuaxet[i] = true;
}
}
public static void Hamilton(int k)
{
Node p = new Node();
p = ke[dinh[k - 1]];
while(p != null)
{
if ((k == n + 1) && (p.v == v0))
HienThi();
else
if (chuaxet[p.v])
{
dinh[k] = p.v;
chuaxet[p.v] = false;
Hamilton(k+1);
chuaxet[p.v] = true;
}
p = p.next;
}
}
static void HienThi()
{
for (int i = 1; i <= n; i++)

con cờ ñó theo ñúng luật domino sao cho các con cờ hình thành vòng tròn hay không, nếu
có hãy chỉ ra một cách sắp. Cài ñặt chương trình.
Bài tập 3 Tổng thư ký ðại hội ñồng Liên hợp quốc triệu tập một cuộc họp có N nhà ngoại
giao của N tổ chức tham gia. Các ñại diện ngoại giao ñược bố trí ngồi quanh một bàn tròn.
Giữa một số tổ chức có quan hệ căng thẳng, vì vậy không thể xếp họ ngồi cạnh nhau ñược.
Thông tin về quan hệ giữa các tổ chức ñược cho dưới dạng cặp số nguyên i, j nếu giữa 2 tổ
chức này có quan hệ căng thẳng. Hãy lập trình giúp Tổng thư ký Liên hợp quốc bố trí chỗ
ngồi quanh bàn họp. Các tổ chức ñược ñánh số từ 1 tới N, 0 < N <= 500.
Dữ liệu vào: từ file CONF.INP, dòng ñầu tiên chứa số nguyên N, các dòng sau, mỗi
dòng một cặp số i, j cho biết các ñại diện i và j không ngồi cạnh nhau ñược. Kết thúc là một
dòng chứa 2 số 0.
Kết quả: ñưa ra file CONF.OUT. Nếu không có cách bố trí thỏa mãn yêu cầu thì ñưa
ra thông báo KHONG CO, trong trường hợp ngược lại – ñưa ra dãy N số nguyên xác ñịnh vị
trí ai ngồi cạnh ai quanh bàn tròn.
Bài tập 4 Có 12 người ngồi chung 1 bàn tiệc tròn. Mỗi người có ít nhất 6 người quen. Hãy
chỉ ra cách sắp xếp sao cho mỗi người ñều ngồi cạnh người mình quen . Tổng quát, hãy sắp
N người ngồi chung quanh bàn tròn sao cho mỗi người ñều ngồi cạnh người mình quen.
Biết mỗi người có ít nhất (N + 1)/2 người quen.
Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2011
Trang 20

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.
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.
- 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.

Duyệt rộng

Cách 2: Ta dùng hàng ñợi mô tả lại từng bước thuật toán
- ðưa 1 và hàng ñợi.
- Lặp: Lấy từ hàng ñợi ra, duyệt tất cả ñỉnh kề chưa xét ñưa vào hàng ñợi chờ xét
Kết quả theo từng bước của thuật toán duyệt rộng ñược mô tả trong bảng sau:
Trạng thái hàng ñợi ðỉnh ñang duyệt Các ñỉnh ñã duyệt Các ñỉnh chưa
duyệt
1

1 1 2,3,4,5
2 4

2 1,2 3,4,5
4 3 5

4 1,2,4 3,5
3 5 3 5

3 1,2,4,3 5
5 3 5

5 1,2,4,3,5
3 5

3 1,2,4,3,5
5

5 1,2,4,3,5


4
3 1,2,3 4,5
4

5

4
4 1,2,3,4 5
5 4
5 1,2,4,3,5
4

4 1,2,4,3,5
static int[] S = new int[Smax]; //cai dat ngan xep, toi da 1000 ptu
static int top; //qf: dau hang, ql: cuoi hang
Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2011
Trang 23

static public void initS(); //Khoi tao ngan xep
static public bool fullS(); //Kiem tra day
static public bool emptyS(); //Kiem tra rong
static public void pushS(int x); //Dua phan tu vao ngan xep
static public int popS(); //lay phan tu tu ngan xep ra
}
Chương trình minh họa:
using System;
using System.Text;
using System.IO;
namespace LTDT
{
class duyetdothi
{
static string filename = "d:/trr/mtk_b2_t216.in";
static int [,] a; //luu do thi mtran ke
static int xp,n,count;
//dinh xuat phat khi duyet, n la so dinh cua do thi, count dem so thu tu khi duyet
static int[] kq; //luu thhu tu duyet
static bool[] xet; //danh dau xet cho n dinh cua do thi; n la so dinh cua do thi
//doc do thi (BD theo ma tran ke) tu tep txt
static public void doctep(string filename)
//hien thi do thi
static private void hien_dt(int[,] x)
//Duyet do thi => dua ra thu tu duyet

{
kq[count++] = i;
xet[i] = true; //danh dau xet cho dinh i, va day i vao Q
Queue.putQ(i);
}
}while (!Queue.emptyQ());
}
static private void DFS()
{
init();
//1. day dinh xp vao Queue, danh dau xet cho dinh xp
Stack.pushS(xp); xet[xp] = true;
kq[count++] = xp;
//cai dat theo thuat toan MR:
//lap qua trinh lay tu Q ra de xet, danh dau xet trc khi day vao Q
do
{
int u = Stack.popS(); //lay u o dau Q , la dinh dg xet
for (int i = 0; i < n; i++) //tim tat ca cac dinh i ke u, va chua xet
if (a[u, i] > 0 && xet[i] == false)
{
kq[count++] = i;
xet[i] = true; //danh dau xet, va day vao Q
Stack.pushS(i);
}
} while (!Stack.emptyS());
}
//ghi thu tu duyet
Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2011
Trang 25

}
static void Main()
{
menu();
Console.ReadKey();
}
}
}