Xem mẫu
- ĐẠI HỌC
KHOA CÔNG NGHỆ THÔNG TIN
ĐỒ ÁN
TỐT NGHIỆP ĐẠI HỌC
TÊN ĐỀ TÀI
XÂY DỰNG BÀI TOÁN GHÉP ĐÔI KHÔNG TRỌNG SỐ
Họ và tên:
Chuyên nghành: Công nghệ thông tin
Lớp: cntt
Khoá: 20162020
Hướng dẫn: Tiến sỹ
Hà Nội, 12/2020
1
- LỜI CAM ĐOAN
Em xin cam đoan: Đồ án tốt nghiệp “ Xây dựng bài toán ghép đôi không
trọng số “ này là công trình nghiên cứu của cá nhân em, được thực hiện trên
cơ sở nghiên cứu lý thuyết và ứng dụng , dưới sự hướng dẫn khoa học của
Tiến sĩ Phạm Minh Hoàn , Trường Đại học Kinh tế quốc dân .
Em xin chịu trách nhiệm về lời cam đoan này.
Hà Nội, ngày 12 tháng 12 năm 2020
Tác giả
2
- LỜI CÁM ƠN
Để hoàn thành bài nghiên cứu này, em xin chân thành cám ơn Trường
Đại học Kinh tế quốc dân, Phòng đào tạo, các thầy, cô giáo giảng dạy lóp
Công nghệ thông tin 58B đã quan tâm, tạo điều kiện thuận lợi, tận tình giảng
dạy và giúp đỡ em trong thời gian theo học tại trường.
Đặc biêt, em xin bày tỏ lòng biết ơn sâu sắc đến TS. Phạm Minh Hoàn,
người đã dành nhiều thời gian, tam huyết hướng dẫn em trong suốt quá trình
nghiên cứu và hoàn thành đồ án .
Mặc dù đã cố gắng hết sức hoàn thiện luận văn, tuy nhiên chắc chắn vẫn
còn nhiều thiếu sót, rất mong nhận được sự góp ý quý báu của quý thầy cô
và các bạn.
Xin trân trọng cám ơn !
Hà Nội, ngày 12 tháng 12 năm 2020
Tác giả
3
- MỤC LỤC
4
- LỜI NÓI ĐẦU
Ngày nay việc giải quyết các bài toán lớn cho hệ thống đòi hỏi
sự hợp tác chặt chẽ giữa các chuyên gia trong các lĩnh vực chuyên
môn, như các chuyên gia Toán, Toán ứng dụng và các chuyên gia Tin
học, kỹ sư lập trình. Việc thiết lập được một mô hình hợp lý, phản
ánh đƣợc bản chất của bài toán thực tế đồng thời khả thi về phương
diện tính toán luôn là điều đáng được quan tâm.
Đặc biệt trong các chuyên ngành liên quan thì toán học là
chuyên ngành rất được quan tâm, một trong số đó là Lý thuyết đồ
thị. Đồ thị biểu diễn được rất nhiều cấu trúc, nhiều bài toán thực tế
có thể được biểu diễn bằng đồ thị. Ví dụ, cấu trúc liên kết của một
website có thể được biểu diễn bằng một đồ thị có hướng như sau:
các đỉnh là các trang web hiện tại có tại website, tồn taị một cạnh có
hướng nối từ trang A tới trang B khi và chỉ khi A có chứa 1 liên kết
tới B. Do vậy, sự phát triển của các thuật toán xử l đồ thị là một
trong các mối quan tâm chính của khoa học máy tính .
Mặc dù Lý thuyết đồ thị đã được khoa học phát triển từ rất lâu
nhưng có nhiều ứng dụng hiện đại , đặ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 ...Những ý
tưởng cơ bản của lý thuyết đồ thị được nhà toán học Thụy sỹ
Leonhard Euler đưa ra từ thế kỷ 18. Ông đã dùng lý thuyết đồ thị để
giải quyết bài toán cầu Konigsberg nổi tiếng.
Đồ thị cũng được dùng để giải nhiều bài toán thuộc những lĩnh
vực rất khác nhau như : người ta có thể dùng đồ thị để biểu diễn sự
5
- cạnh tranh của các loài trong môi trường sinh thái, dùng đồ thị biểu
diễn ai có ảnh hưởng đến ai trong một tổ chức nào đó và cũng có
thể dùng đồ thị để giải các bài toán như bài toán tính số các tổ hợp
khác nhau của các chuyến xe giữa hai thành phố trong một mạng giao
thông, bài toán đi tham quan tất cả các phố của một thành phố sao
cho mỗi phố đi qua đúng một lần, hay bài toán tìm số màu cần thiết
để tô các vùng khác nhau của một bản đồ,...Đồ thị với các trọng số
được gán cho các cạnh của nó có thể dùng để giải các bài toán như
bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng
giao thông, bài toán phân công lao động sao cho tổng lợi nhuận thu
được là lớn nhất. Đặc biệt, nhiều bài toán trong thực tế sử dụng mô
hình đồ thị và các thuật toán trên đồ thị được giải quyết rất hiệu quả
như: bài toán điều hành taxi, bài toán xếp lớp học theo tín chỉ có thể
đưa về mô hình bài toán tìm bộ ghép cực đại trên đồ thị và sử dụng
các thuật toán tương ứng.
Chính vì đồ thị có thể được sử dụng để giải quyết nhiều bài
toán thuộc nhiều lĩnh vực khác nhau một cách dễ dàng và phổ biến
như vậy nên đồ thị giữ một vai trò hết sức quan trọng trong cuộc
sống, đặc biệt là trong lĩnh vực công nghệ thông tin, dựa vào đồ thị
và các thuật toán trên đồ thị người ta có thể xây dựng nên các phần
mềm hữu ích giải các bài toán thực tế một cách nhanh chóng và tối
ưu .
Nhận thấy tính thiết thực của vấn đề này và được sự gợi ý
của giảng viên hướng dẫn, tôi đã chọn nội dung nghiên cứu về
―Bài toán ghép đôi không trọng số trên đồ thị, ứng dụng giải
6
- một số bài toán trong thực tế.” làm đề tài cho luận văn tốt nghiệp
của mình . Báo cáo được bố cục thành 3 chương:
Chương 1: Cơ sở lý thuyết đồ thị và độ phức tạp thuật toán.
Chương 2 : Bài toán tìm bộ ghép cực đại trên đồ thị và các thuật toán.
Chương 3: Ứng dụng bài toán ghép đôi trong thực tế .
7
- CHƯƠNG 1 : CƠ SỞ LÝ THUYẾT VỀ ĐỒ THỊ VÀ ĐỘ PHỨC TẠP
THUẬT TOÁN
1.1. Các khái niệm cơ bản
1.1.1. Khái niệm đồ thị
Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được
mô tả hình thức:
G = (V, E)
V gọi là tập các đỉnh,
E là tập các cạnh,
Có thể coi E là tập các cặp (u, v) với u và v là hai đỉnh của V.
Một số hình ảnh của đồ thị:
Cạnh liên thuộc, đỉnh kề , bậc
Đối với đồ thị vô hướng G = (V, E) . Xét một cạnh e ϵ E, nếu e = (u,v) thì
ta nói hai đỉnh u và v là kề nhau và cạnh e này liên thuộc với đỉnh u và đỉnh v.
Với một đỉnh v trong đồ thị, ta định nghĩa bậc của v , ký hiệu deg(v) là số
cạnh liên thuộc với v. Dễ thấy rằng trên đơn đồ thị thì số cạnh liên thuộc với
v cũng là số đỉnh kề với v.
Định lý: giả sử G = (V, E) là đồ thị vô hướng với m cạnh, khi đó tổng tất cả
các bậc đỉnh trong V sẽ bằng 2m:
8
-
Đối với đồ thị có hướng G = (V, E). Xét một cung e ϵ E, nếu e = (u, v) thì
ta nói u nối tới v và v nối từ u, cung e là đi ra khỏi đỉnh u và đi vào đỉnh v.
Đỉnh u khi đó được gọi là đỉnh đầu, đỉnh v được gọi là đỉnh cuối của cung e.
Với mỗi đỉnh v trong đồ thị có hướng, ta định nghĩa : Bán bậc ra của v ký
hiệu deg+(v) là số cung đi ra khỏi nó; bán bậc vào ký hiệu deg(v) là số cung
đi vào đỉnh đó.
Định lý: giả sử G = (V, E) là đồ thị có hướng với m cung, khi đó tổng tất cả
các bán bậc ra của các đỉnh bằng tổng tất cả các bán bậc vào và bằng m:
= m
1.1.2. Các loại đồ thị
Có thể phân loại đồ thị theo đặc tính và số lượng của tập các
cạnh E:
Cho đồ thị G = (V, E).
Định nghĩa 1:
Một đơn đồ thị vô hƣớng là một bộ G = , trong đó:
V ≠ Ø là tập hợp hữu hạn gồm các đỉnh của đồ thị.
E là tập hợp các cặp không có thứ tự gồm hai phần tử khác
nhau của V gọi là các cạnh.
Như vậy, theo định nghĩa trên, trong một đơn đồ thị không thể
có các cặp cạnh nối cùng một cặp đỉnh (do E là tập hợp nên không
thể có 2 cặp trùng nhau), các cạnh đều không phân biệt thứ tự nên
cạnh [u,v] và cạnh [v,u] đều được coi là một cạnh duy nhất, điều
này phù hợp với việc biểu diễn các con đường 2 chiều, và hiển nhiên
là không có cặp [u,u] nào đó trong E.
9
- Ví dụ
a) Đơn đồ thị vô hướng b) Không phải đơn đồ c) Không phải đơn đồ thị vô
thị vô hướng do có các hướng do có cạnh nối
một cặp cạnh nối cùng một đỉnh với chính nó.
cặp đỉnh
Tuy nhiên, trên thực tế, cũng có thể trong một hệ thống giao
thông vẫn tồn tại nhiều con đường đi nối cùng hai địa điểm, hoặc
cũng có thể có một con đường để đi từ một địa điểm nào đó rồi lại
quay về chính nó (đây có thể là một con đường nội bộ của một trung
tâm mua sắm, …). Khi đó, tính chất của đơn đồ thị vô hướng nhất
định nghĩa trên không cho phép n biểu diễn được hệ thống giao
thông trong trường hợp này. Muốn vậy, ta phải dùng một loại đồ thị
tổng quát hơn, đó là: đa đồ thị vô hướng.
Định nghĩa 2:
Đa đồ thị vô hướng là một bộ G = , trong đó
V ≠ Ø là tập hợp hữu hạn gồm các đỉnh của đồ thị.
E là một họ các cặp không có thứ tự của V gọi là các
cạnh.
Lưu ý:
Khi ta nói E là một họ nghĩa là nó có thể có những cặp
trùng nhau (khác với khái niệm tập hợp).
Các cạnh nối cùng một cặp đỉnh được gọi là các cạnh
song song.
10
- Các cạnh nối từ một đỉnh với chính nó được gọi là
khuyên.
Ví dụ
e1
a) Đa đồ thị vô hướng: e1 và e2 là b) Đa đồ thị vô hướng: e là khuyên
các cạnh song song
Điểm chung của hai loại đồ thị đã được định nghĩa ở trên là
tính chất vô hướng (hai chiều) của các cạnh. Trong thực tế, cũng có
khi ta phải chú trọng đến tính có hướng của các cạnh nối này (chẳng
hạn như biểu diễn các con đường một chiều). Từ đó, ta có thêm loại
đồ thị: Đơn đồ thị có hướng và đa đồ thị có hướng. Về cơ bản, hai
loại này cũng tương tự như hai loại mà ta định nghĩa ở trên, chỉ thêm
sự khác biệt là tính chất có thứ tự của các cạnh.
Định nghĩa 3:
Đơn đồ thị có hướng là một bộ G = , trong đó:
V ≠ Ø là tập hợp hữu hạn gồm các đỉnh của đồ thị.
E là tập hợp các cặp có thứ tự gồm hai phần tử khác nhau
của V gọi là các cung.
a) Đơn đồ thị có b) Không phải đơn đồ thị c) Không phải đơn đồ thị có
11
- hướng có hướng do các các cặp hướng do
có cung nối một cung nối cùng một cặp
đỉnh với chính nó.
đỉnh.
Định nghĩa 4:
Đa đồ thị có hướng là một bộ G = , trong đó
V ≠ là tập hợp hữu hạn gồm các đỉnh của đồ thị.
E là một họ các cặp cạnh thứ tự của V gọi là các cung.
Các cung nối cùng một cặp đỉnh được gọi là các cung song song.
Ví dụ
e1
e
a) Đa đồ thị có hướng: e1 và e2 là các b) Đa đồ thị có hướng: e
là cung song song. khuyên .
Định nghĩa 5:
Một giả đồ thị G = (V, E) gồm một tập các đỉnh V, một tập các
cạnh E và một hàm f từ E tới {{u,v} | u,v V}. Một c nh là một
khuyên nếu f(e) =
{u} với một đỉnh u nào đó.
Một số thuật ngữ cơ bản
+ Cho đồ thị vô hướng G = .
12
- Hai đỉnh u và v của đồ thị được gọi là kề nhau nếu (u,v)
là một cạnh của đồ thị.
Nếu e = (u,v) là cạnh của đồ thị thì ta nói cạnh này là liên
thuộc với hai đỉnh u và v. Cạnh được nói là nối đỉnh u và v. Đỉnh u và
v được gọi là đỉnh đầu của cạnh e.
+ Cho đồ thị vô hướng G = . Bậc của đỉnh v trong đồ thị, kí
hiệu là deg(v), là số cạnh liên thuộc với n. Đỉnh có bậc 0 được gọi là
đỉnh cô lập, đỉnh có bậc 1 gọi là đỉnh treo.
Ví dụ
Cho đồ thị vô hướng G = sau:
V = {1, 2, 3, 4, 5, 6}
E = {(1,2), (2,3), (1,4), (1,5), (2,5), (4,5), (2,4)}
Bậc của các đỉnh:
deg(1) = 3 deg(2) = 4 deg(3) = 1
deg(4) = 3 deg(5) = 3 deg(6) = 0
Đỉnh 3 là đỉnh treo
Đỉnh 6 là đỉnh cô lập
+ Cho G = là đồ thị vô hướng. Khi đó ta có tổng số bậc của
các đỉnh của đồ thị sẽ bằng hai lần số cạnh của n. Nói cách khác, ta
có:
∑deg (v) =2|E|
vV
13
- Trong đồ thị vô hƣớng, số đỉnh bậc lẻ là
một số chẵn.
+ Cho đồ thị có hướng G = .
Hai đỉnh u và v của đồ thị được gọi là kề nhau nếu (u,v)
là một cung của đồ thị.
Nếu e=(u,v) là cung của đồ thị thì ta nói cung này đi ra
khỏi đỉnh u và đi vào đỉnh v. Đỉnh u được gọi là đỉnh đầu của cung e
và đỉnh v được gọi là đỉnh cuối của cung e.
+ Cho đồ thị có hướng G=.
Bán bậc ra của đỉnh v trong đồ thị, ký hiệu là deg+(v), là
số cạnh đi ra khỏi v.
Bán bậc vào của đỉnh v trong đồ thị, ký hiệu là deg (v), là
số cạnh vào v.
Ví dụ
Xét đồ thị có hướng G = sau:
Hình 7: Đồ thị có hướng
V = {1, 2, 3, 4, 5, 6}
E = {(1,2), (2,3), (1,4), (5,1), (5,2), (2,6), (6,3), (4,5), (6,5), (3,4)}
Bậc của các đỉnh:
Bán bậc ra: deg+(1)=2 deg+(2)=2 deg+(3)=1
deg+(4)=1 deg+(5)=2 deg+(6)=2
14
- Bán bậc vào: deg(1)=1 deg(2)=2 deg(3)=2
deg(4)=2 deg(1)=2 deg(1)=1
Tương tự như đồ thị vô hướng, đối với đồ thị có hướng ta
cũng có kết quả gần tương tự về bậc của các đỉnh của đồ thị.
+ Cho G = là đồ thị có hướng. Tổng bán bậc ra của các đỉnh
bằng tổng bán bậc vào của các đỉnh và bằng số cạnh của đồ thị.
∑deg+(v)=deg(v)=|E|
vV vV
+ Đồ thị vô hướng G = được gọi là liên thông nếu luôn tìm
được đường đi giữa hai đỉnh bất kỳ của n .
1.1.3. Biểu diễn đồ thị trên máy tính
Lý thuyết đồ thị được ứng dụng trong rất nhiều lĩnh vực khác
nhau. Để sử dụng được đồ thị hiệu quả và nhanh chóng hơn, chúng
ta phải biểu diễn và xử lý được đồ thị với máy tính. Cách biểu diễn
thông thường bằng hình vẽ và mô tả tập hợp sẽ không phải hợp với
cách thức lưu trữ dữ liệu và xử lý trên máy tính. Chúng ta phải tìm
một cấu trúc dữ liệu thích hợp để biểu diễn đồ thị trên máy tính.
Có nhiều phương pháp khác nhau để biểu diễn đồ thị trên máy tính.
Sau đây chúng ta sẽ lần lượt tìm hiểu một số phương pháp thông
dụng.
1.1.3.1. Danh sách cạnh
15
- Trong trường hợp đồ thị có n đỉnh, m cạnh, ta có thể biểu diễn đồ thị
dưới dạng danh sách cạnh, trong cách biểu diễn này, ngƣời ta liệt kê
tất cả các cạnh của đồ thị trong một danh sách, mỗi phần tử của
danh sách là một cặp (u, v) tương ứng với một cạnh của đồ thị.
(Trong trường hợp đồ thị có hướng thì mỗi cặp (u, v) tương ứng với
một cung, u là đỉnh đầu và v là đỉnh cuối của cung). Danh sách được
lưu trong bộ nhớ dưới dạng mảng hoặc danh sách móc nối.
Ví dụ với đồ thị dưới đây:
Cài đặt trên mảng:
1 2 3 4 5
(1,3) (2,4) (3,5) (4,1) (5,2)
5 2
nil
Ví dụ biểu diễn đồ thị danh sách cạnh
Ưu điểm của danh sách cạnh:
• Trong trường hợp đồ thị thưa (có số cạnh tương đối nhỏ: chẳng hạn
m
- • Trong một số trường hợp, ta phải xét tất cả các cạnh của đồ thị
thì cài đặt trên danh sách cạnh làm cho việc duyệt các cạnh dễ dàng
hơn. (Thuật toán Kruskal chẳng hạn)
Nhược điểm của danh sách cạnh:
• Nhược điểm cơ bản của danh sách cạnh là khi ta cần duyệt tất
cả các đỉnh kề với đỉnh v nào đó của đồ thị, thì chẳng có cách nào khác
là phải duyệt tất cả các cạnh, lọc ra những cạnh có chứa đỉnh v và xét
đỉnh còn lại.
Điều đó khá tốn thời gian trong trường hợp đồ thị dày (nhiều cạnh).
1.1.3.2. Danh sách kề
Sử dụng danh sách liền kề để biểu diễn đồ thị không có cạnh
bội. Danh sách này chỉ rõ các đỉnh nối với mỗi đỉnh của đồ thị.
Đỉnh Đỉnh liền kề
1 2, 3,4, 5
2 1,3, 4, 5
3 1,2,4
4 1,2,3
5 1,2
Ví dụ biểu diễn đồ thị danh sách liền kề
Ưu điểm của danh sách kề:
17
- • Đối với danh sách kề, việc duyệt tất cả các đỉnh kề với một
đỉnh v cho trước là hết sức dễ dàng, cái tên "danh sách kề" đã cho thấy
rõ điều này. Việc duyệt tất cả các cạnh cũng đơn giản vì một cạnh
thực ra là nối một đỉnh với một đỉnh khác kề n .
Nhược điểm của danh sách kề
• Về lý thuyết, so với hai phương pháp biểu diễn trên, danh sách
kề tốt hơn hẳn. Chỉ có điều, trong trường hợp cụ thể mà ma trận kề
hay danh sách cạnh không thể hiện nhược điểm thì ta nên dùng ma
trận kề (hay danh sách cạnh) bởi cài đặt danh sách kề có phần dài
dòng hơn.
1.1.3.3. Ma trận liền kề
Giả sử G = (V, E) là một đồ thị đơn trong đó |V| = n và các đỉnh
được liệt kê tuỳ v1,…,vn. Ma trận liền kề A của G ứng với danh
sách các đỉnh này là ma trận không một cấp n*n có phần tử hàng i,
cột j bằng 1 nếu vi và vj liền kề nhau, và bằng 0 nếu chúng không
được nối với nhau.
1 0 1 1 1 1
2 1 0 1 1 1
1 1 0 1 0
3
4 1 1 1 0 0
5 1 1 0 0 0
1 2 4 5
18
- Hình 10: Ví dụ biểu diễn đồ thị ma trận kề
Các tính chất của ma trận liền kề:
1. Đối với đồ thị vô hướng G, thì ma trận liền kề tương ứng là ma trận
đối xứng (aij = aji), điều này không đúng với đồ thị có hướng.
2. Nếu G là đồ thị vô hướng và A là ma trận liền kề 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 = deg(i)
3. Nếu G là đồ thị có hướng và A là ma trận liền kề tương ứng thì trên
ma trận A:
• Tổng các số trên hàng i = Bán bậc ra của đỉnh i = deg+(i)
• Tổng các số trên cột i = Bán bậc vào của đỉnh i = deg(i)
Trong trường hợp G là đơn đồ thị, ta có thể biểu diễn ma trận liền kề A
tương ứng là các phần tử logic.Aij = TRUE nếu (i, j) E và aij =
FALSE nếu (i, j) ∉ E
Ưu điểm của ma trận liền kề:
• Đơ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: auv ≠ 0.
Nhược điểm của ma trận liền kề:
• Bất kể số cạnh của đồ thị là nhiều hay ít, ma trận liền kề luôn luôn
đòi
hỏi n2 ô nhớ để lưu các phần tử ma trận, điều đó gây lãng phí bộ nhớ
dẫn tới việc không thể biểu diễn được đồ thị với số đỉnh lớn.
19
- Với một đỉnh u bất kỳ của đồ thị, nhiều khi ta phải xét tất cả các đỉnh v
khác kề với nó, hoặc xét tất cả các cạnh liên thuộc với n . Trên ma
trận liền kề việc đó được thực hiện bằng cách xét tất cả các đỉnh v
và kiểm tra điều kiện auv ≠ 0. Như vậy, ngay cả khi đỉnh u là đỉnh cô
lập (không kề với đỉnh nào) hoặc đỉnh treo (chỉ kề với 1 đỉnh) ta
cũng buộc phải xét tất cả các đỉnh và kiểm tra điều kiện trên dẫn tới
lãng phí thời gian.
1.1.3.4. Ma trận liên thuộc
Giả sử G = (V, E) là một đồ thị vô hướng, v1, v2, vn là tập các
đỉnh còn e1, e2, ..., em là tập các cạnh của nó. Khi đó ma trận liên
thuộc theo thứ tự trên của V và E là ma trận M = [mij] trong đ :
mij = 1 nếu cạnh ej nối với đỉnh vi
mij = 0 nếu cạnh ej không nối với
e1 e2 e3 e4 e5 e6 e7 e8
v1 1 0 0 0 1 1 1 0
v2 1 1 1 1 0 0 0 0
v3 0 0 0 1 0 1 0 1
v4 0 0 1 0 0 0 1 1
v5 0 1 0 0 1 0 0 0
Ví dụ biểu diễn đồ thị ma trận liên thuộc
20
nguon tai.lieu . vn
