BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC DÂN LẬP CỬU LONG
KHOA CÔNG NGHỆ THÔNG TIN
W€X

GIÁO TRÌNH THỰC HÀNH

LÝ THUYẾT ĐỒ THỊ VÀ
THUẬT GIẢI

Biên Soạn: ĐÀO ANH PHA

Vónh Long, 05/2006


Giáo Trình Thực Hành Lý Thuyết Đồ Thị

MỤC LỤC
MỘT SỐ BÀI TOÁN...................................................................................................2
BÀI TOÁN 1.................................................................................................................2
BÀI TOÁN 2.................................................................................................................3
BÀI TOÁN 3.................................................................................................................4
BÀI TOÁN 4.................................................................................................................5
BÀI TOÁN 6.................................................................................................................7
BÀI TOÁN 7.................................................................................................................8
BÀI TOÁN 8.................................................................................................................9
BÀI TOÁN 9...............................................................................................................10
BÀI TOÁN 10.............................................................................................................11
HƯỚNG DẪN CÀI ĐẶT BÀI TOÁN......................................................................12
BÀI TOÁN 1...............................................................................................................12
BÀI TOÁN 2...............................................................................................................17

011000
100110
100010
010010
011101
000010

Bac cao nhat: 4

Bai1.inp

Kết quả:

5
01001
10111
01001
01001
11110

Bac cao nhat: 4

Yêu cầu xử lý:
a) Tìm đỉnh có bậc cao nhất.
b) Tìm bậc nhỏ nhẩt của đỉnh.
c) Tìm đỉnh có bậc nhỏ nhất.
d) Tính tổng bậc của đồ thị.
e) Đếm số đỉnh bậc chẵn và bậc lẻ.
Kết quả:
Ví dụ:

00100
01010
00101
10010

DO THI LIEN THONG

Bai2.inp

Kết quả:

8
01000100
10100000
01010000
00101000
00010100
10001010
00000101
00000010

DO THI LIEN THONG

Bai2.inp

Kết quả:

6
011000
101000

000110

2

Bai3.inp

Kết quả:

5
00001
00100
01010
00101
10010

1

Bai3.inp

Kết quả:

8
01000100
10100000
01010000
00101000
00010100
10001010
00000101
00000010

10110
01010
01101
10010

1->2->3->4->5
1->2->4->5
1->5

Bai3.inp

Kết quả:

5
15
01011
10101
01010
10101
11010

1->2->3->4->5
1->2->5
1->4->3->2->5
1->4->5
1->5

Bai4.inp

Kết quả:

Ví dụ:
Bai5.inp
Kết quả:
5
01000
10111
01010
01101
01010

1->2->3->4->2->5->4

Bai5.inp

Kết quả:

5
01000
10111
01011
01101
01110

KHONG TON TAI DUONG DI

Bai5.inp

Kết quả:

5

Kết quả:
5
1
01000
10111
01010
01101
01010

1->2->3->4->5

Bai6.inp

Kết quả:

6
1
011000
101010
110001
000010
010100
001000

KHONG TON TAI DUONG DI

Bai6.inp

Kết quả:


một khoảng trắng.
Dữ liệu ra: xuất ra màn hình đường đi ngắn nhất từ đỉnh D đến C và giá trị đường đi
ngắn nhẩt tìm được.
Ví dụ:
Bai7.inp

Kết quả:

6

DUONG DI NGAN NHAT LA: 5

16

1->2->4->6

012000
102230
220540
025032
034304
000240

Bai7.inp

Kết quả:

6

DUONG DI NGAN NHAT LA: 8

- Dòng đầu lưu độ dài dây dẫn nhỏ nhất
- Các dòng còn lại lưu đường đi cần nối điện giữa đỉnh i nối với đỉnh j có
trọng số A[i,j] (i -> j = A[i][j]).
-

Ví dụ:
Bai8.inp

Bai8.out

5
03322
30232
32014
23104
22440

7
1 -> 4 = 2
4 -> 3 = 1
1 -> 5 = 2
3 -> 2 = 2

Bai8.inp
8
02340000
20304000
33076520
40700030
04600408

- Dòng i+2 (1 ≤ i ≤ n ) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi
một khoảng trắng.
Dữ liệu ra: xuất ra màn hình kế hoạch vận chuyển từ đỉnh D đến C và giá trị đường
đi ngắn nhẩt tìm được.
Ví dụ:
Bai9.inp
Kết quả:
6
16
012000
102230
220540
025032
034304
000240

KHOI LUONG VAN CHUYEN NHIEU NHAT LA: 2
1->3->4->6

Bai9.inp
Kết quả:
6
16
014000
102650
420730
067001
053003
000130



6

DUONG DI DAI NHAT LA: 16

16

1->2->4->3->5->6

012000
102230
220540
025032
034304
000240

Bai10.inp

Kết quả:

6

DUONG DI DAI NHAT LA: 25

16
014000
102650
420730
067001
053003

000010

Bac cao nhat: 4

Bai1.inp

Kết quả:

5
01001
10111
01001
01001
11110

Bac cao nhat: 4

Yêu cầu xử lý:
f) Tìm đỉnh có bậc cao nhất.
g) Tìm bậc nhỏ nhẩt của đỉnh.
h) Tìm đỉnh có bậc nhỏ nhất.
i) Tính tổng bậc của đồ thị.
j) Đếm số đỉnh bậc chẵn và bậc lẻ.
Ví dụ:

Biên Soạn: Đào Anh Pha

Kết quả:
f) Đỉnh 2,5.
g) Bậc 2.

/*Dọc file dữ liệu bài toán*/
void Doc_File(int **A,int &n) {
FILE*f = fopen(TenFile,"rb");
fscanf(f,"%d",&n);
*A = new int [n];
cout
int min = BacNhoNhat(A,n), Bac;
for(int i = 0; i

Giáo Trình Thực Hành Lý Thuyết Đồ Thị
cout
01000100
10100000
01010000
00101000
00010100
10001010
00000101
00000010

DO THI LIEN THONG

Bai2.inp

Kết quả:

6
011000
101000
110000
000011
000101
000110

DO THI KHONG LIEN THONG

Biên Soạn: Đào Anh Pha

Trang 17



#include <conio.h>
#include <iostream.h>
#define TenFile "Bai2.inp"
/*Dọc file dữ liệu*/
void Doc_File(int **A,int &n){
FILE*f = fopen(TenFile,"rb");
fscanf(f,"%d",&n);
*A = new int [n];
cout

Biên Soạn: Đào Anh Pha

Trang 19


Giáo Trình Thực Hành Lý Thuyết Đồ Thị

BÀI TOÁN 3
Viết chương trình đếm số thành phần liên thông của đồ thị vô hướng Anxn với:
- A[i,j] = 1 nếu có đường đi từ i đến j.
- A[i,j] = 0 nếu không có đường đi từ i đến j.
- A[i,j] = A[j,i].
Dữ liệu vào: cho trong file Bai2.inp nội dung dữ liệu giống dữ liệu Bài Tập2.
Dữ liệu ra: hiển thị số thành phần liên thông của đồ thị ra màn hình.
Ví dụ:
Bai3.inp
Kết quả:
6
011000
101000
110000
000011
000101
000110

2

Bai3.inp


xuất phát, tăng số thành phần liên thông lên 1 và chuyển sang bước 2.
Bước 2: Từ một đỉnh i đã đánh dấu, ta đánh dấu đỉnh j nếu A[i,j] = 1 và j chưa được đánh
dấu và chuyển sang bước 3.
Biên Soạn: Đào Anh Pha

Trang 20


Giáo Trình Thực Hành Lý Thuyết Đồ Thị

Bước 3: Thực hiện bước 2 cho đến khi không còn thực hiện được nữa chuyển sang
bước 4.
Bước 4: Nếu số số đỉnh đánh dấu bằng n (mọi đỉnh đều được đánh dấu) kết thúc thuật
toán, ngược lại quay về bước 1.
Chú ý: Nếu số thành phần liên thông bằng 1 đồ thị liên thông.
HƯỚNG DẪN CÀI ĐẶT

Cài đặt tương tự như bài toán 2.
CHƯƠNG TRÌNH MẪU
/*Hàm trả về số thành phần liên thông của đồ thị vô hướng */
int TPLien_Thong(int **A, int n) {
char*DanhDau = new char [n];
char ThanhCong;
int Dem=0, i,j, MLT=0;
for( i = 0; i
f. A[i,j] = A[j,i].
Hãy xác định mọi đường từ thành phố D đến thành phố C (nếu có).
Dữ liệu vào: đồ thị liên thông và cho trong file Bai4.inp
- Dòng đầu ghi số n là số đỉnh của một đồ thị (03->4->5
1->2->4->5
1->5

Bai3.inp

Kết quả:

5
15



Giáo Trình Thực Hành Lý Thuyết Đồ Thị

HƯỚNG DẪN THUẬT TOÁN
Sử dụng kỹ thuật tìm kiếm theo chiều sâu.
HƯỚNG DẪN CÀI ĐẶT
Sử dụng kỹ thuật cài đặt tìm kiếm theo phương pháp đệ quy.
CHƯƠNG TRÌNH MẪU
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define FileIn "Bai4.inp"
int Dem = 0;
//Dếm số đường đi
int*L;
//Lưu lại đường đã đi
char*DanhDau;
//Đánh dấu đỉnh đã đi
int **A,n,D,C;
/*Dọc file dữ liệu theo yêu cầu của chương trình*/
void Doc_File(){
FILE*f = fopen(FileIn,"rb");
fscanf(f,"%d%d%d",&n,&D,&C);
cout

}
void InDuongDi(int SoCanh) {
Dem++;
cout
if(Dem==0)
cout