MỤC LỤC
MỤC LỤC ................................................................................................... 1
MỞ ĐẦU ..................................................................................................... 3
CHƯƠNG 1 ................................................................................................. 4
GIỚI THIỆU TỔNG QUAN VÀ NGÔN NGỮ............................................ 4
LẬP TRÌNH DELPHI.................................................................................. 4
1.1. Giới thiệu đề tài................................................................................. 4
1.2. Ngôn ngữ lập trình Delphi ................................................................. 5
1.2.1. Giới thiệu ngôn ngữ lập trình Delphi .......................................... 5
1.2.2. DELPHI và WIN32 API ............................................................. 6
1.2.3. Các thành phần điều khiển chủa Windows.................................. 7
1.2.4. Ngôn ngữ Object Pascal............................................................ 11
CHƯƠNG 2 ............................................................................................... 17
ĐỒ THỊ VÀ ỨNG DỤNG CỦA ĐỒ THỊ .................................................. 17
2.1. Đồ thị ............................................................................................. 17
2.1.1. Định nghĩa đồ thị ...................................................................... 17
2.1.2. Các loại đồ thị.......................................................................... 18
2.1.3. Một số khái niệm và tính chất cơ bản của đồ thị ....................... 19
2.1.4. Các dạng biểu diễn của đồ thị ................................................... 24
2.2. Số ổn định và tô màu đồ thị ............................................................. 30
2.2.1. Số ổn định trong, số ổn định ngoài, nhân đồ thị ........................ 30
2.2.2. Tô màu đồ thị........................................................................... 36
2.3. Chu trình, đường đi Euler và Hamilton trong đồ thị......................... 41
2.3.1. Chu trình và đường đi Euler...................................................... 41
2.3.2. Chu trình và đường đi Hamilton ............................................... 43
2.4. Đường đi ngắn nhất trong đồ thị ...................................................... 45
2.4.1. Đường đi ngắn nhất trong đồ thị không có trọng số .................. 45

1



di ngắn nhất giữa hai thành phố trong mạng giao thông, giải các bài toán về lập
lịch, thời khoá biểu và phân bố tần số cho các trạm phát thanh truyền hình …
Lý thuyết đồ thị là một nhánh quan trọng của của toán học tổ hợp đã được
nghiên cứu sâu sắc trong hàng trăm năm. Nhiều tính chất quan trọng và hữu ích
của đồ thị đã được chứng minh, nhưng vẫn còn rất nhiều vấn đề khó chưa giải
quyết xong. Ở đề tài này với mục đích tìm hiểu vấn đề cơ bản của lý thuyết đồ thị
và đi sâu tìm hiểu một số thuật toán trên đồ thị và cài đặt bằng ngôn ngữ lập trình
Delphi.
Trong thời gian làm đồ án mặc dù đã cố gắng rất nhiều nhưng do kiến thức
của bản than có hạn, ngôn ngữ lập trình phải tự tìm hiểu, nên đề tài không tránh
khỏi những thiếu sót. Em kính mong nhận được sự đánh giá và chỉ bảo của các
thầy cô giáo để đề tài của em được hoàn thiện hơn. Một lần nữa em xin chân
thành cảm ơn thầy giáo Th.S Bùi Ngọc Tuấn đã tận tình hướng dẫn giúp em hoàn
thành đồ án này.
Em xin chân thành cảm ơn !

3


CHƯƠNG 1
GIỚI THIỆU TỔNG QUAN VÀ NGÔN NGỮ
LẬP TRÌNH DELPHI

1.1. Giới thiệu đề tài
"Ứng dụng của đồ thị trong Tin học" là đề tài mang tính nghiên cứu lý
thuyết, có tầm quan trọng và có ý nghĩa thiết thực cao. Khái niệm đồ thị ở đây
khác với những đồ thị thông thường đã biết, đây là một lĩnh vực về lý thuyết đồ
thị nghiên cứu những cấu trúc mang tính rời rạc là một bộ phận quan trọng của
Toán học rời rạc.
Lý thuyết đồ thị có nhiều ứng dụng trong các ngành kỹ thuật và đã được

Bảo Sơn.

1.2. Ngôn ngữ lập trình Delphi
1.2.1. Giới thiệu ngôn ngữ lập trình Delphi
Delphi có tiền thân là ngôn ngữ lập trình Pascal (thật sự từ ngôn ngữ hướng
đối tượng Object Pascal). Pascal là một ngôn ngữ rõ ràng mạch lạc thường được
dùng trong công việc nghiên cứu giảng dạy hơn là dùng viết những ứng dụng
chuyên nghiệp như hệ điều hành hay các chương trình thương mại cao cấp.
Nhưng Delphi thì hoàn toàn mới. Delphi đã đưa ra ngôn ngữ Pascal trưởng thành
lên rất nhiều, có lẽ phải gọi là ngôn ngữ Delphi thì đúng hơn. Để làm việc bằng
Delphi phải học và nắm bắt thêm rất nhiều từ khoá và kỹ thuật mới, nhất là khái
niệm lập trình hướng đối tượng. Với môi trường phát triển Delphi, hầu như bạn
có thể kiến tạo bất kỳ chương trình ứng dụng Windows nào từ những tập tin thực
thi EXE, thư viện liên kết động DLL, ứng dụng OLE, thành phần ActiveX đến
các ứng dụng WEB trên mạng Internet, các ứng dụng giao diện đồ hoạ, các ứng
dụng về truy xuất cơ sở dữ liệu client – server, tích hợp những công nghệ hiện
đại như JAVA, CORBA, NIDAS … Nhìn chung với các ứng dụng chuyên
nghiệp đòi hỏi thời gian phát triển nhanh và có tính chuyên môn cao thì Delphi là
một lựa chọn tốt nhất. Kết hợp khả năng truy xuất cấp thấp của C cộng với tận
dụng những chức năng cao cấp của hệ điều hành, Delphi xứng đáng để các lập
trình viên đầu tư vào nó.

5


1.2.2. DELPHI và WIN32 API
Delphi đã dành cho các nhà lập trình gần như toàn bộ khả năng điều khiển
hệ điều hành Windows thông qua các thành phần đối tượng mà không cần phải
quan tâm đền các hàm Win32 API. Bạn có thể thay đổi bộ mặt cũng như cách
hàm xử của chương trình thông qua những phương thức hay thuộc tính của đối

Windows API. Nhiều và còn nhiều lý do nữa để bạn sử dụng WIN32 API như là
một công cụ tốt nhất dùng mở tung mọi cánh cửa Windows từ bất kỳ môi trường
phát triển ứng dụng Windows nào khác không riêng gì môi trường phát triển
Delphi.
1.2.3. Các thành phần điều khiển chủa Windows
a. Nút nhấn (Button)
Nút nhấn được Delphi đặt trong lớp đối tượng TButton, tình huống thường
được sử dụng nhất là là OnClick. Khi người dùng Click chuột vào nút nhấn, tình
huống này sẽ được gọi để phản ứng lại bằng một tác vụ nào đó.
b. Nhãn (Lable)
Nhãn là thành phần đơn giản nhất trong thư viện VCL. Đối tượng nhãn chỉ
dùng để trình bày một chuỗi văn bản thông thường, nhằm mục đích mô tả thêm
thông tin cho các đối tượng khác. Nhãn cũng có thể được dùng để đưa kết quả ra
màn hình dưới dạng chuỗi.
Trong Delphi, nhãn được đặt trong lớp đối tượng có tên là TLable. Thuộc tính
thường được sử dụng nhất của nhãn là:
Caption thể hiện nội dung nhãn.
Font

định font chữ, kiểu chữ cho nhãn.

Transparent cho phép màu nền của nhãn trùng với màu nền của Form.
c. Ô đánh dấu
Ô đánh dấu hay cũng gọi là CheckBox cho phép người dùng chọn hay bỏ
chọn một yêu cầu nào đó.
Checkbox được Delphi đặt trong lớp TCheckBox. Thuộc tính thường được sử
dụng nhất của CheckBox là Checked mang kiểu Boolean. Nếu Checked = True, ô
đánh dấu đang ở trạng thái chọn. Nếu Checked = False, người dùng đã bỏ chọn ô
đánh dấu. Khi ô đánh dấu được kích chuột để yêu cầu thay đổi trạng thái, tình
huống OnClick sẽ phát sinh.

dòng trong Memo cộng lại, mỗi dòng cách nhau bởi ký tự 10 và 13. Tình huống
thường được sử dụng nhất của Memo là tình huống OnChange, tình huống này
được gọi khi người dùng thay đổi hoặc thêm dữ liệu vào Memo.

8


g. Danh sách (ListBox)
Danh sách chứa một danh sách mục chọn, mỗi mục chọn thường được thể
hiện là một chuỗi. ListBox cho phép chọn mỗi lần một hay nhiều mục cùng lúc.
Danh sách được Delphi đặt trong lớp đối tượng có tên là TlistBox. Thuộc tính
thường được sử dụng nhất của danh sách là:
Items Dùng để thêm bớt các mục chọn vào danh sách.
ItemIndex Cho biết hoặc thiết lập mục chọn hiện hành.
Selected Kiểm tra xem một mục chọn trong danh sách có được chọn hay không.
MultiSelect Cho phép danh sách được chọn đồng thời nhiều mục.
Sorted Tự động sắp xếp các mục chọn theo thứ tự ABC.
Các tình huống mà ListBox thường phát sinh là:
OnClick Khi người dùng kích chuột vào mục chọn.
OnDblClick Khi người dùng kích đôi chuột vào một mục chọn.
OnKeyPress Khi người dùng nhấn phím để chọn một mục.
OnKeyDown/ OnKeyUp Xử lý khi người dùng nhấn và nhả phím.
h. Danh sách sổ(ComboBox)
Danh sách sổ ComboBox mỗi lần chỉ thể hiện được một mục và là mục đang
ở trạng thái chọn.
Danh sách sổ được Delphi đặt trong lớp đối tượng có tên là TcomboBox.
Thuộc tính thường được sử dụng nhất ComboBox là:
Text Nội dung của mục chọn hiện hành.
Items Danh sách các mục chọn.
ItemIndex Lấy về hoặc thiết lập mục chọn hiện hành cho ComboBox.

ItemIndex Nút Radio đang được chọn.
Caption Tiêu đề của nhóm ô chọn.
Column Phân cột cho các ô chọn.
Tình huống mà nhóm ô chọn thường phát sinh là OnClick, nó được gọi khi
người dùng kích chuột vào một trong các ô chọn trong nhóm.
k. Nhóm các đối tượng (GroupBox)
Có thể sử dụng nhóm chứa các đối tượng mang tên GroupBox để phân loại
đối tượng theo chủ đề. Thành phần này được Delphi đặt trong lớp đối tượng có
tên là TGroupBox.
Tương tự TRadioGroup, TGroupBox cũng dùng thuộc tính Caption để thể
hiện tiêu đề cho nhóm. TGroupBox cũng cung cấp các tình huống như OnClick,

10


OnMouseUp, OnMouseDown … nhưng hầu như rất ít khi dùng đến chúng, nó
thường chỉ được dùng với mục đích gom các đối tượng lại với nhau theo chủ đề.
Nó đóng vai trò như một vật chứa.
l. Bảng chứa (Panel)
Bảng chứa dùng để gom, nhóm các đối tượng con lại với nhau. Thành phần
bảng chứa Panel được Delphi đặt trong lớp đối tượng có tên là TPanel.
Các thuộc tính thường được sử dụng nhất của Panel là:
Align Canh lề cho bảng chứa.
BevelInner Đường viền trong.
BevelOuter Đường viền ngoài.
BevelWidth Độ dày của đường viền.
Visibled Cho phép bảng chứa hiển thị hoặc không.
m. Trình đơn chính (MainMenu)
Trình đơn chính MainMenu là một dãy các lựa chọn nằm phía trên cửa sổ.
Đối tượng này được Delphi đặt tên là TMainMenu.


SmallInt

-32768 to 32767

2

Integer

-2147483648 to 2147483647

4

Cardinal

0 to 2417483647

4

LongInt

-2147483648 to 2147483647

4

11


b. Kiểu thực
Type


8

Type

Range of Values

Byte of Memory Required

ByteBool

Byte-size Boolean

1

Word-size Boolean

2

WordBool

Word-size Boolean

2

LongBool

Double word-size Boolean

4

Length

Element It Hold

Null

ShortString

255

ANSIChar

No

ANSIChar

Yes

AnsiString

up to ~3 GB

String

either 255 or up to ~3GB

ANSIChar

Yes


b. Kiểu Record.
Kiểu Record là một tập hợp gồm nhiều phần tử có các kiểu khác nhau hợp lại.
Mỗi phần tử trong cấu trúc bản ghi được gọi là trường.
Cú pháp khai báo bản ghi:
Type recordTypeName = Record
fieldList 1 : type 1;
fieldList 2 : type 2;
…
fieldList n : type n;
End;
c. Kiểu miền con (Subrange Type)

13


Kiểu miền con của một kiểu rời rạc là một miền trị của kiểu rời rạc đó.
Cú pháp khai báo kiểu miền con:
Ví dụ:
Type
Ngay=(sun,mon,tue,wed,thu,fri,sat);
Chuthuong=’a’..’z’;
Sonho=100..200;
d. Kiểu tập hợp (Set type)
Kiểu miền con là một tập các giá trị có cùng kiểu thứ tự. Mỗi biến kiểu tập
hợp có thể chứa nhiều phần tử của tập hợp. Tập hợp chỉ chứa được tối đa 256
phần tử, bao gồm cả tập hợp rỗng.
Cú pháp khai báo: Set of baseType;
Trong đó baseType là kiểu thứ tự bất kỳ có số phần tử không quá 256.
1.2.4.3. Các cấu lệnh cấu trúc
Dạng 1:


caseList n : statement n;
else
Statement t;
End;
Với cú pháp trên, khi lệnh case thực thi, phải có ít nhất một lệnh statement được
gọi vì trong trường hợp xấu nhất là khi biểu thức selectorExpression không thoả
mãn các điều kiện của caseList thì lệnh statement t của mệnh đề else sẽ được gọi.
c. Lệnh REPEAT
Repeat
Statement 1;
.
.
statement n;
Until expression;
Trong đó, expression là một biểu thức so sánh trả về giá trị đúng hoặc sai.
Câu lệnh Repeat sẽ thực thi từng lệnh satement bên trong khối. Sau khi thực hiện
lệnh cuối cùng, biểu thức expression trong mệnh đề Until sẽ được kiểm tra. Nếu
expression trả về giá trị TRUE, lệnh Repeat sẽ ngừng thực thi, điều khiển
chương trình sẽ thoát ra khỏi vòng lặp. Nếu expression trả về giá trị FALSE ,
điều khiển chương trình sẽ nhảy về đầu vòng lặp Repeat, tiếp tục thực hiện lại
lệnh đầu tiên.

15


d. Lệnh WHILE
While expression Do statement;
Lệnh While tương tự như lệnh Repeat, ngoại trừ biểu thức giá trị điều kiện
lặp được kiểm tra đầu tiên, trước khi bước vào thực hiện các lệnh khác chứa

này, các loại đồ thị khác nhau được phân biệt bởi kiểu và số lượng cạnh nối hai
đỉnh nào đó của đồ thị.
Giả sử X là tập hữu hạn, không rỗng các phần tử nào đó và U  XX. Bộ G
= <X, U> được gọi là đồ thị hữu hạn. Mỗi phần tử xX gọi là một đỉnh và mỗi
phần tử u = (x,y)  U gọi là một cạnh của đồ thị G = <X, U>.
Xét một cạnh u  U khi đó tồn tại 2 đỉnh x, y  X sao cho u = (x, y), ta nói rằng
x nối với y hoặc x và y thuộc u.
x

u

y

- Nếu cạnh u = (x, y) mà x và y là hai đỉnh phân biệt thì ta nói x, y là hai đỉnh kề
nhau.
- Nếu u = (x, x) thì u là cạnh có hai đỉnh trùng nhau ta gọi đó là một khuyên.
- Nếu u = (x, y) mà x,y là cặp đỉnh có phân biệt thứ tự hay có hướng từ x đến y
thì u là một cung, khi đó x là gốc còn y là ngọn hoặc x là đỉnh ra, y là đỉnh vào.
- Khi giữa cặp đỉnh (x, y) có nhiều hơn một cạnh thì ta nói những cạnh cùng cặp
đỉnh là những cạnh song song hay là cạnh bội

y

x

y

a)
a. Tại đỉnh y có một khuyên


A

B
A

D

C

B

C

D

D

a)

b)

Hình 1.2 a.Đơn đồ thị

b. Đa đồ thị

C

c)
c. Giả đồ thị


thuộc đỉnh x khi đó m(x) được gọi là bậc của đỉnh x. Nếu x có một khuyên thì
m(x) được cộng thêm 2.

m(x) = 3

m(x) = 2

x

x

- Nếu m(x) = 0 thì đỉnh x được gọi là đỉnh cô lập.
- Nếu m(x) = 1 thì đỉnh x được gọi là đỉnh treo.
Ta đặt
m(G) 

 m(x)
xX

thì m(G) được gọi là bậc của đồ thị vô hướng G = <X, U>
* Bậc đồ thị có hướng
Cho đồ thị có hướng G= <X,U> xét 1 đỉnh x  X, ta ký hiệu m +(x) là số các
cung vào của đỉnh x, còn m-(x) là số các cung ra khỏi x. Khi đó ta gọi m+(x) là
bậc vào của đỉnh x còn m-(x) là bậc ra của đỉnh x.
- Nếu m+(x) + m-(x) = 0 thì đỉnh x được gọi đỉnh là cô lập.
- Nếu m+(x) + m-(x) = 1 thì đỉnh x được gọi là đỉnh treo.
Ta đặt
m(G) 

m

nếu xoá một khuyên u = (x, x) thì bậc của G cũng giảm đi 2, còn nếu xoá hết
cạnh, hết khuyên thì bậc của đồ thị bằng 0. Từ đó suy ra định lý.
Hệ quả: Số đỉnh bậc lẻ của đồ thị G = <X,U> là một số chẵn
Chứng minh:
Gọi A và B tương ứng là tập đỉnh bậc lẻ và tập đỉnh bậc chẵn của đồ thị. Ta
2m   m(x) 
xX

 m(x)   m(x)
x A

x B

có:
Do vế trái chẵn nên tổng vế phải cũng là số chẵn. Mà tổng bậc của các đỉnh
bậc chẵn (x  A) là số chẵn nên tổng bậc của các đỉnh bậc lẻ (xB) phải là số
chẵn, do tất cả các số hạng của nó là số lẻ, nên tổng này phải gồm một số chẵn
các số hạng. Vì vậy số đỉnh bậc lẻ phải là số chẵn.
2.1.3.2. Đường đi và chu trình
* Đường đi
Xét đồ thị G = <X,U> với

20


- Tập đỉnh X = {x1,x2,...,xn}
- Tập cạnh U = {u 1,u2,...,u m}
Tập hợp các đỉnh kề nhau từ xi đến xj được gọi là 1 đường đi, kí hiệu
xixi1xi2 ... xj  xiuixi1ui1xi2ui2 ... ujxj
Trong đó các cạnh, các đỉnh trong đường đi có thể lặp lại

21


Định lý:
Nếu trong đồ thị G = <X,U> các đỉnh đều có bậc không nhỏ hơn 2 (x  X
| m(x)  2) thì trong G tồn tại ít nhất một chu trình.
Chứng minh:
Xét tất cả các đường đi đơn. Vì đồ thị là hữu hạn cho nên số các đường đi
đơn là hữu hạn. Chọn một đường đi là dài nhất nào đó ví dụ từ xi1 đến xij +1 (xem
hình vẽ dưới đây). Theo giả thiết m(x)  2 nên tồn tại ít nhất một đỉnh xi0 và một
cạnh nối đỉnh xi1 và xi0. Đỉnh xi0 thuộc một trong các đỉnh trên đường đi đã chọn
chẳng hạn xij vì đường đi là dài nhất, nên chứng tỏ tồn tại một chu trình trong
đường đi.
xi1

xi2

xi3

xij

xij+

xi0

2.1.3.3. Đồ thị liên thông
Cho đồ thị G = <X,U>. Hai đỉnh phân biệt x,y X được gọi là liên thông
nếu tồn tại một đường đi nối các đỉnh x, y với nhau. Đồ thị G được gọi là liên
thông nếu với hai đỉnh phân biệt bất kỳ trong đồ thị đều là liên thông.
Ví dụ như hình 3.1 là một đồ thị liên thông vì luôn có đường đi nối hai đỉnh

Hình 3.3

Ví dụ như đồ thị trong hình 3.3 có ba thành phần liên thông sau:
G1 = <X1, U1> với X1= {A,B,C} và U1 = {AB, AC, CB}
G2 = <X2, U2> với X2= {D, E} và U2 = {DE}
G3 = <X3, U3> với X3= {F} và U3 = 
Cho đồ thị có hướng G = <X, U>
- G được gọi là đồ thị liên thông yếu nếu đồ thị vô hướng tương ứng với nó là
liên thông
- G là liên thông một chiều nếu với hai đỉnh x,y khác nhau bất kỳ của G luôn có
đường đi x - y hoặc đường đi y - x.
- G là liên thông mạnh (liên thông 2 chiều) nếu hai đỉnh x,y khác nhau bất kỳ của
G đều có đường đi x - y và đường đi y - x.
A

B

A

B

A

B

D

D

D

cặp điểm đó ứng với một cạnh (cung) của đồ thị.
Ví dụ 1: Cho đồ thị G = <X,U> trong đó
X = {A, B, C, D, E} và

U = {AB, AC, AD, AE, BD, CD, CE}
D

C
B

A

E

E

a)

B

A

D

b)

C

Hình 4.1
Hình 4.1.a và hình 4.1.b đều là biểu diễn hình học của đồ thị G đã cho ở trên

24


Ta có f : G1  G2
f(a) = m

f(c) = n

f(d) = q

f(b) = p

Nếu a, b  X1 kề nhau thì f(a), f(b)  X2 kề nhau.
Vậy đây là 2 đồ thị đẳng cấu với nhau, ta có thể xem G1 và G2 thực chất chỉ
là 1 chỉ có điều biểu diễn ở dạng hình học khác nhau, các tên đỉnh khác nhau. Để
xét 2 đồ thị có đẳng cấu không là việc khó, tuy nhiên để xét 2 đồ thị không đẳng
cấu với nhau thì đơn giản hơn.
Đối với 2 đồ thị đẳng cấu thì các đồ thị đó có những tính chất bất biến như sau:
- Số đỉnh bằng nhau
- Số cạnh bằng nhau
- Bậc các đỉnh tương ứng cùng như nhau
- 2 Ma trận kề cũng như nhau
- Các chu trình cũng như nhau
2.1.4.3. Một số đồ thị đặc biệt
Do tính chất, dạng biểu diễn có những nét đặc thù riêng biệt nên ta phân
loại một số đồ thị thành các dạng đặc biệt sau:
* Đồ thị đều
Là một đồ thị mà mọi đỉnh có cùng bậc, nếu bậc này bằng k thì đó là đồ thị k
- đều