DANH MỤC HÌNH VẼ
Trang
Hình 1.1 Đồ thị hàm số y = sinx 4
Hình 1.2 Đồ thị biểu diễn ví dụ 1 5
Hình 1.3 Đồ thị biểu diễn ví dụ 2 6
Hình 1.4 Đồ thị biểu diễn ví dụ 3 6
Hình 1.5 Biểu diễn phẳng của Graph 7
Hình 1.6 Biểu diễn Graph con và Graph thành phần 8
Hình 1.7 Biểu diễn bậc của đỉnh 9
Hình 1.8 Dãy cạnh kế tiếp 9
Hình 1.9 Biểu diễn cạnh có hướng 12
Hình 2.1 Ma trận kề đồ thị vô hướng không trọng số và đồ thị có hướng có
tróng số 14
Hình 2.2 Biểu diễn cài đặt đồ thị bằng danh sách cạnh trên mảng và trên danh
sách móc nối 17
Hình 2.3 Đồ thị vô hướng không trọng số 20
Hình 2.4 Biểu diễn Graph bằng danh sách kề 22
Hình 2.5 Đồ thị vô hướng 24
Hình 2.6 Ma trận kề đồ thị trọng số vô hướng và đồ thị trọng số có hướng 31
Hình 2.7a Đồ thị trọng số có hướng 31
Hình 2.7b Biểu diễn đồ thị trọng số bằng danh sách lân cận kề 31
Hình 2.8 Đồ thị vô hướng có trọng số ví dụ 4 33
Hình 2.9 Cây khung DFS(1) và cây khung BFS(1) 37
Hình 2.10 Đồ thị vô hướng có trọng số ví dụ 5 40
MỤC LỤC
Trang
MỞ ĐẦU 1
Chương 1
MỘT SỐ VẤN ĐỀ VỀ LÝ THUYẾT GRAPH 4
1.1. Khái niệm cơ bản về graph 4
1.1.1. Những bài toán và vấn đề dẫn đến khái niệm graph [1] 4

xét, nhãn của nó không biến đổi ở các bước tiếp theo, vì thế ta đánh dấu
34
Bước lặp 34
Đỉnh 1 34
Đỉnh 2 34
Đỉnh 3 34
Đỉnh 4 34
Khởi tạo 34
0, 1 34
10, 1 34
6, 1 34
2, 1* 34
1 34
34
5, 4 34
3, 4 * 34
34
2 34
34
5, 4 * 34
34
34
34
Nhận xét: Từ bảng kết quả ta có thể truy xuất ra được đường đi từ đỉnh 1
tới tất cả các đỉnh còn lại trong đồ thị như sau: 34
Đường đi từ đỉnh 1 tới đỉnh 2: 34
Ta có đỉnh trước đỉnh 2 là Truoc[2] = 4 vậy 4 là đỉnh trước đỉnh 2 trên
đường đi này 34
Trước đỉnh 4 là Truoc[4] = 1 vậy 1 là đỉnh trước đỉnh 4 trên đường đi
này 34

3.2.3. Bài toán 3 - Bản đồ [2] 52
3.3. Một số bài toán về đường đi trong đồ thị 53
3.3.1. Bài toán 1 - Đường đi [4] 53
3.3.2. Bài toán 2 - Du lịch [4] 56
3.3.3. Bài toán 3 - Đến trường [7] 58
3.4. Một số bài toán về cây khung đồ thị 61
3.4.1. Bài toán 1 - Dự án 61
3.4.2. Bài toán 2 - Thay hệ thống [4] 64
3.4.3. Bài toán 3 – Bão Sơn Tinh 66
3.5. Kết luận chương 3 70
KẾT LUẬN 71
TÀI LIỆU THAM KHẢO 72
MỞ ĐẦU
1. Lý do chọn đề tài
Trên thực tế có nhiều bài toán liên quan tới một tập các đối tượng và
những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu
diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đồ thị.
Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ thứ XVIII bởi nhà toán
học Thụy Sĩ Leonhard Euler, ông đã dùng mô hình đồ thị để giải bài toán về
những cây cầu Konigsberg nổi tiếng. Mặc dù Lý thuyết đồ thị đã được khoa
học phát triển từ rất lâu nhưng lại có nhiều ứng dụng hiện đại. Đặc biệt trong
khoảng vài chục năm trở lại đây, cùng với sự ra đời của máy tính điện tử và
sự phát triển nhanh chóng của Tin học, Lý thuyết đồ thị càng được quan tâm
đến nhiều hơn. Đặc biệt là các thuật toán trên đồ thị đã có nhiều ứng dụng
trong nhiều lĩnh vực khác nhau như: Mạng máy tính, Lý thuyết mã, Tối ưu
hoá, Kinh tế học v.v
Một trong các mục tiêu khi đưa tin học vào nhà trường là nhằm giúp cho
học sinh có khả năng phân tích, tổng hợp, trừu tượng hóa, khái quát hóa vấn
đề và đặc biệt là phát triển tư duy. Hiện nay, có nhiều bài toán trong chương
trình trung học phổ thông được giải quyết nhờ vận dụng lý thuyết đồ thị. Để

Chương 3: Ứng dụng của Graph vào chương trình Tin học phổ thông:
Đưa ra và vận dụng lý thuyết Graph vào cài đặt một số bài toán cụ thể trong
chương trình tin học phổ thông theo từng dạng: Bài toán duyệt đồ thị, bài toán
về đường đi trên đồ thị, bài toán về cây khung đồ thị.
Kết luận: Nêu ra những vấn đề đã tìm hiểu, một số công việc chính đã
được thực hiện, hướng phát triển tiếp theo của đề tài trong tương lai.
Em xin chân thành cảm ơn Thầy giáo, TS Nguyễn Mạnh Đức - Giảng viên
Tin học, Khoa Toán, Đại học Sư phạm Thái Nguyên, người đã trực tiếp
hướng dẫn và tận tình chỉ bảo em trong suốt quá trình làm đề tài.
2
Em xin chân thành cảm ban chủ nhiệm Khoa Toán cùng các Thầy, Cô
trong khoa đã tạo điều kiện để em thực hiện đề tài này.
Tôi cũng xin cảm ơn các bạn sinh viên, người thân đã động viên, giúp đỡ
trong thời gian thực hiện đề tài.
Thái Nguyên, tháng 4 năm 2013
Sinh viên
Vi Văn Sơn
3
Chương 1
MỘT SỐ VẤN ĐỀ VỀ LÝ THUYẾT GRAPH
1.1. Khái niệm cơ bản về graph
1.1.1. Những bài toán và vấn đề dẫn đến khái niệm graph [1]
Hai chữ “đồ thị” vẫn thường xuyên xuất hiện trong toán học và cả trong
đời sống hàng ngày. Trong các giờ học toán, chúng ta có nói tới đồ thị của các
hàm số. Chẳng hạn, trong hình dưới có biểu diễn đồ thị của hàm số y=sinx.
Trong các công sở, các nhân viên phải
lập các biểu đồ theo dõi số lượng tiêu thụ
điện hoặc xăng dầu hàng tháng,và họ cũng
có thể gọi những biểu đồ đó là đồ thị
Tóm lại khái niệm đồ thị là một khái niệm

3
trên mặt phẳng và các giếng là
các điểm B
1
, B
2
, B
3
nào đó. Các con đường đi là các đường
(liên tục) nối các đỉnh A
i
với các đỉnh B
i
.
Khi đó, câu hỏi của bài toán là liệu có những điểm A
i
tới các điểm B
i
trên mặt phẳng sao cho không có hai con đường nào cắt nhau
hay không? Bằng cách thiết lập mô hình này, chúng ta đã thiết lập một graph
có 6 đỉnh và 9 cạnh.
Chúng ta thấy rằng để giải bài toán này, các kiến thức hình học không còn
giúp gì được cho chúng ta nữa. Bài toán đòi hỏi phải có kiến thức sâu sắc hơn
về mối quan hệ nào đó của quan hệ các đỉnh và các cạnh. [1]
Nhưng không phải chỉ với một số bài toán hoặc một số vấn đề toán học có
nguồn gốc hình học mới có thể đưa về mô hình đỉnh – cạnh như trên. Mô hình
đỉnh – cạnh của chúng ta tỏ ra là mô hình rất hiệu quả để nắm bắt được chính
xác bản chất toán học thật sự của nhiều đối tượng toán học. Các đỉnh được
biểu diễn cho các đại lượng tham gia và các cạnh nối chúng biểu diễn mối
quan hệ đi lại của chúng theo một tiêu chuẩn nào đó được đưa ra.

Trong hình 1.4 là một graph thỏa mãn yêu cầu
của bài toán với n=5.
6
Hình 1.4. Đồ thị
biểu diễn ví dụ 3
Hình 1.3. Đồ thị biểu
diễn ví dụ 2
Trong nhiều trường hợp, chúng ta chấp nhận những cạnh nối một đỉnh đã
cho với chính nó. Loại này được gọi là cạnh khuyên trong graph.
Trong lý thuyết graph có cho phép giữa hai đỉnh có thể có nhiều cạnh nối.
Trong trường hợp có nhiều cạnh (ít nhất là hai) nối 2 đỉnh khác nhau nào đó
của một graph, thì ta gọi cạnh đó là cạnh kép.
1.1.2. Định nghĩa graph và các khái niệm cơ bản
Thông thường chúng ta hay kí hiệu một graph bởi chữ G (chữ cái đầu của
từ “Graph” trong tiếng Đức, ngôn ngữ dùng để viết cuốn sách đầu tiên về lí
thuyết graph). Còn tập đỉnh thường được kí hiệu bởi chữ V (là chữ cái đầu
tiên của từ “Vertices”) và tập cạnh bởi chữ cái E (chữ cái đầu của từ
“Edges”). Graph không có cạnh có hướng thường được kí hiệu là G=(V,E),
còn graph có các cạnh có hướng được kí hiệu là G=[V,E]. Việc dùng kí hiệu
này không bắt buộc, mà chỉ là một thói quen mà thôi.
Định nghĩa đồ thị: Một đồ thị G = (V, E) bao gồm một tập hữu hạn V =
{v
1
, v
2
,…v
n
} các đỉnh (nút) và 1 tập hữu hạn E = {(v
i
, v

mà không có cạnh nào cắt nhau (ở một điểm không phải là điểm mút của các
cạnh). Hình vẽ như thế được gọi là một biểu diễn phẳng của graph.

Như chúng ta đã thấy trong các ví dụ trên, graph thường được biểu diễn
trên mặt phẳng: các đỉnh được tô đậm và các cạnh nối các đỉnh là các đoạn
thẳng hoặc là các đường cong nối các đỉnh này với nhau. Ngoài ra, chúng ta
7
Hình 1.5. Biểu diễn phẳng
của Graph
phải lưu ý rằng một graph có thể có nhiều biểu diễn trên mặt phẳng khác
nhau. Trong hình 1.5 chúng ta có hai biểu diễn trên mặt phẳng khác nhau của
một graph.
Graph được phân loại theo tính chất cạnh của chúng. Trong mỗi graph các
cạnh của graph thẳng hay cong, dài hay ngắn, các đỉnh ở vị trí nào, đều không
phải là điều quan trọng. Mà điều quan trọng là graph có bao nhiêu cạnh và
đỉnh nào được nối với đỉnh nào.
Một graph được gọi là graph vô hướng nếu tất cả các cạnh của nó đều là
cạnh vô hướng. Graph được gọi là graph có hướng nếu tất cả các cạnh của nó
đều là cạnh có hướng. Đỉnh xuất phát của một cạnh có hướng được gọi là
đỉnh đầu, và đỉnh kết thúc của cạnh được gọi là đỉnh cuối của nó. Trong
trường hợp graph có cả cạnh vô hướng cũng như cạnh có hướng thì graph
được gọi là graph hỗn hợp. Một graph được gọi là graph đơn nếu nó không
có khuyên và không có cạnh kép. Ngoài ra, ta gọi graph điểm là graph có
đúng một đỉnh và không có cạnh nào. Graph rỗng dùng để gọi một graph
không có đỉnh và cạnh nào cả.
1.1.3. Graph con và graph thành phần
Cho trước một graph G với tập đỉnh X và tập cạnh E.
Một graph G’ với tập đỉnh X’ và tập cạnh E’ được gọi là
graph con của graph G nếu X’
⊂

1.2.1.2. Dãy cạnh kế tiếp
Cho trước một graph G với tập đỉnh V và tập cạnh E.
Hai cạnh của một graph cho trước gọi là hai cạnh kề
nhau nếu như chúng có một đỉnh chung. Một dãy m
cạnh e
i
= (A
i,
A
i+1
) với i=1, 2,…,m được gọi là một dãy
cạnh nối tiếp và thường được kí hiệu là: H = (A
1
, e
1
, A
2
,

e
2
,…, e
k
,A
k+1
)
Trong trường hợp G là một graph đơn thì ta có thể biểu diễn một dãy cạnh
kế tiếp qua các đỉnh của chúng, chẳng hạn dãy cạnh kế tiếp của H của ta ở
trên được kí hiệu đơn giản là: H = (A
1

,…, e
k
,A
k+1
), đỉnh A
1
được gọi là đỉnh đầu vả
đỉnh A
k+1
được gọi là đỉnh cuối của H. H còn được gọi là dãy cạnh kế tiếp nối
A
1
với A
k+1
. Trong trường hợp A
1
≠ A
k
, dãy cạnh kế tiếp H được gọi là dãy
cạnh kế tiếp không khép kín. Còn khi A
1
= A
k
thì H được gọi là dãy cạnh kế
tiếp khép kín [1].
Một dãy cạnh kế tiếp e
1
, e
2
,…, e

Các lớp đỉnh này là đỉnh của graph thành phần liên thông trong graph cho
trước, được gọi là thành phần liên thông của graph đã cho.
1.2.1.4. Đường đi trong graph
Trong thực tế ứng dụng của cuộc sống, ta thường gặp một khái niệm khác
của dãy cạnh kế tiếp là những dãy cạnh kế tiếp được tuân thủ nguyên tắc tối
ưu là chúng không đi qua đỉnh nào của graph quá một lần. Một dãy cạnh kế
tiếp trong một graph cho trước được gọi là một đường đi nếu chúng không đi
qua đỉnh nào của graph quá 1 lần. Cũng tương tự như với dãy cạnh kế tiếp,
nếu a và b là hai đỉnh đầu tiên và đỉnh cuối cùng của đường W, thì ta nói rằng
W nối a với b. Chúng được gọi là đỉnh đầu và đỉnh cuối của con đường và
được xem là phải khác nhau.
Thông thường, đường đi được biểu diễn thông qua các đỉnh và các cạnh
nối chúng, chẳng hạn: W = (p
1
, e
1
, p
2
, e
2
, p
3
, e
3
,…, e
k-1
, P
k
)
với p

1
, e
2
, …, e
k
thì ta viết: C = (p
1
, e
1
, p
2
, e
2
, …, p
k
, e
k
, p
1
)
11
Trong trường hợp graph là một đơn graph, thì thay vì viết rõ các cạnh và
các đỉnh, chu trình được xác định duy nhất qua việc gọi tên các đỉnh nó đi
qua. Chẳng hạn chu trình C ở trên có thể viết thành: C = (p
1
, p
2
,…, p
k
, p

u
Hình 1.9. Biểu
diễn cạnh có
hướng
graph có hướng đơn. Ta nói rằng cung u liên hợp với đỉnh x, nếu như x là
đỉnh xuất phát hoặc là đỉnh đích của cung u. Nếu cung u liên hợp với đỉnh x,
thì cung u được gọi là liên hợp hướng ra ngoài (liên hợp hướng vào trong) đối
với đỉnh x là đỉnh xuất phát (đỉnh đích) của cung u.
1.3. Kết luận chương 1
Trong chương này chúng ta đã tìm hiểu tổng quan một số vấn đề về lý
thuyết đồ thị: Đưa ra một số bài và vấn đề dẫn đến khái niệm Graph, đưa ra
khái niệm cơ bản về Graph, Phân loại Graph, Lý thuyết về Graph vô hướng,
Graph có hướng… Trong đó có các khái niệm về bậc của đỉnh, chỉ số liên
thông, khái niệm về đường đi và chu trình trong Graph…
13
Chương 2
MỘT SỐ THUẬT TOÁN CƠ BẢN TRÊN GRAPH
2.1. Biểu diễn graph trên máy tính
Để giải quyết các bài toán về graph bằng máy tính, chúng ta cần phải lưu
giữ graph trong bộ nhớ. Có nhiều biểu diễn cấu trúc được sử dụng để biểu
diễn graph. Việc lựa chọn cấu trúc nào là tùy thuộc vào các ứng dụng và các
phép xử lý cần tác động lên graph trong ứng dụng ấy. Có hai cách biểu diễn
graph thường dùng: Dùng ma trận kề và dùng danh sách kề.
2.1.1. Biểu diễn bằng ma trận lân cận [6]
Giả sử G=(V, E) là một graph đơn có số đỉnh (Ký hiệu |V|) là n, không mất
tính tổng quát có thể coi các đỉnh được đánh số từ 1, 2,…, n. Khi đó ta có thể
biểu diễn đồ thị bằng một ma trận vuông A = [a
ij
] cấp n. Trong đó:
• a

ji
), điều này không đúng với đồ thị có hướng.
2. Nếu G là graph vô hướng và A là ma trận lân cận tương ứng thì trên ma
trận A:
Tổng các số trên hàng i = tổng các số trên cột i = Bậc của đỉnh i = d
G
(i)
Trong trường hợp G là graph đơn, ta có thể biểu diễn ma trận lân cận A
tương ứng là các phần tử logic. a
ij
= 1 nếu (i, j)
∈
E và a
ij
= 0 nếu (i, j)
∉
E.
Trong rất nhiều vấn đề ứng dụng của lý thuyết graph, mỗi cạnh e =(i, j)
của graph được gán với một con số c(e) (còn viết là c(i, j)) gọi là trọng số của
cạnh e. Graph trong trường hợp đó được gọi là graph có trọng số. Đối với
graph có trọng số, thay vì ma trận kề, để biểu diễn graph ta sử dụng ma trận
trọng số: Thay c[i, j] là trọng số c(i ,j) của cung (i, j) nếu có cung. Nếu không
có cung (i, j) thì người ta đặt a
ij
bằng một giá trị đặc biệt nào đó, có thể là 0,
+∞, hoặc -∞ tùy từng trường hợp cụ thể.
*Ưu điểm của ma trận lân cận:
• Đơn giản, trực quan, dễ cài đặt trên máy tính.
• Để kiểm tra xem hai đỉnh (u, v) của đồ thị có kề nhau hay không, ta chỉ
việc kiểm tra bằng một phép so sánh a

i,j,n,m:integer;
procedure init;
var x,y:integer;
begin
writeln('Nhap so dinh va so canh cua do thi: ');
readln(n,m);
for i:= 1 to m do
begin
writeln(' Nhap dinh dau va dinh cuoi canh ',i,' : ');
readln(x,y);
a[x,y]:=1;
a[y,x]:=1;
end;
end;
procedure process;
begin
assign(f,fo); rewrite(f);
for i:=1 to n do
begin
for j:=1 to n do
write(f,a[i,j],' ');
writeln(f);
end;
close(f);
16
end;
begin
clrscr;
init;
process;

uses crt;
type ds=^node;
node =record
dau,cuoi:integer;
next:ds;
end;
var canh,list:ds;
i,m:integer;
procedure init;
var x,y:integer;
begin
list:=nil;
write('Nhap so canh cua do thi: ');
readln(m);
for i:=1 to m do
begin
write('Nhap thong tin dinh dau va dinh cuoi canh ',i);
readln(x,y);
18
new(canh);
canh^.dau:=x;
canh^.cuoi:=y;
canh^.next:=list;
list:=canh;
end;
end;
procedure xuatds;
var k:byte;
begin
k:=1;

mảng Head[1 6] sẽ là: (0, 3, 5, 8, 10, 12). Như vậy đoạn từ vị trí Head[i]+1
đến Head[i+1] trong mảng A sẽ chứa các đỉnh kề với đỉnh i. Lưu ý rằng với
graph có hướng gồm m cung thì cấu trúc Forward Star cần phải đủ chứa m
phần tử, với graph vô hướng m cạnh thì cấu trúc Forward Star cần phải đủ
chứa 2m phần tử.
Chương trình sau biểu diễn graph vô hướng bằng danh sách kề trên ngôn
ngữ Pascal:
• Input: Nhập từ bàn phím số đỉnh, số cạnh, với mỗi cạnh (i, j) nhập đỉnh
đầu i và đỉnh cuối j.
• Output: Với mỗi đỉnh i, in ra danh sách các đỉnh kề với i, với danh sách
các đỉnh được lưu trữ theo cách 1.
Chương trình:
uses crt;
20
Hình 2.3. Đồ thị vô hướng
không trọng số.