luận án tiến sĩ chu trình hamilton và chu trình dài nhất trong một số lớp đồ thị có tổng bậc lớn (tóm tắt)
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (930.9 KB, 27 trang )
BỘ GIÁO DỤC VÀ ĐÀO TẠO
VIỆN HÀN LÂM
KHOA HỌC VÀ CÔNG NGHỆ VN
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
Nguyễn Hữu Xuân Trƣờng
CHU TRÌNH HAMILTON VÀ CHU TRÌNH DÀI NHẤT
TRONG MỘT SỐ LỚP ĐỒ THỊ CÓ TỔNG BẬC LỚN
Chuyên ngành: Cơ sở toán học cho tin học
Mã số: 62 46 01 10
LUẬN ÁN TIẾN SĨ TOÁN HỌC
Hà Nội – 2016
1
Công trình đƣợc hoàn thành tại: Học Viện Khoa Học và Công Nghệ - Viện Hàn Lâm
Khoa Học và Công Nghệ Việt Nam, số 18 Hoàng Quốc Việt, Cầu Giấy, Hà Nội, Việt Nam.
Ngƣời hƣớng dẫn khoa học: 1. PGS.TSKH. Vũ Đình Hòa
2. GS.TS. Vũ Đức Thi
Phản biện 1:…………………………………………………………….………..
……………………………………………………………………………………
Phản biện 2:…………………………………………………………….………..
……………………………………………………………………………………
Phản biện 3:…………………………………………………………….………..
……………………………………………………………………………………
Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp nhà nước họp tại:
…………………………………………………………….…………….
…………………………………………………………………………………….
Vào hồi
giờ
ngày
tháng
năm
Có thể tìm hiểu luận án tại thư viện: …………………………………….….
2
MỞ ĐẦU
Các vấn đề của lý thuyết đồ thị đã có từ vài trăm năm trước (năm 1736 với bài toán 7
cây cầu ở thành phố Konigsber) nhưng phải tới vài chục năm gần đây, theo cùng sự phát
triển của công nghệ thông tin, thì lý thuyết đồ thị mới thực sự phát triển mạnh mẽ không
ngừng cả về chiều sâu cũng như chiều rộng. Sự phát triển của lý thuyết đồ thị gắn liền với
những tên tuổi các nhà toán học lớn như Euler, Gauss, Hamilton, Erdos... Một trong những
lý do khiến lý thuyết đồ thị phát triển mạnh mẽ như vậy là vì lý thuyết đồ thị khá gần gũi
với thực tế và có những ứng dụng sâu rộng trong công nghệ thông tin và nhiều ngành khoa
học khác.
Vấn đề chu trình là một vấn đề trung tâm của lý thuyết đồ thị và đã có rất nhiều công
trình nghiên cứu tới vấn đề này, đặc biệt là chu trình Hamilton với khoảng 400 bài báo khoa
học được đăng tải trên các tạp chí khoa học quốc tế có uy tín hàng đầu trong vòng 20 năm
gần đây [25], [26], [27]. Hiện nay, các nghiên cứu về chu trình nói chung và chu trình
Hamilton rộng trên nhiều khía cạnh, trong đó tập trung chủ yếu tới bậc của đỉnh; ngoài ra
còn nghiên cứu trên các đồ thị 1-tough, đồ thị path-tough, đồ thị có tập láng giềng lớn, đồ
thị phẳng, đồ thị ngẫu nhiên, đồ thị lưỡng phân và chu trình dài nhất, chu trình
Dominating... Tại Việt Nam, một số tác giả cũng đã tập trung nghiên cứu về chu trình
Hamilton trên các lớp đồ thị khác nhau, chẳng hạn như Ngô Đắc Tân nghiên cứu trên lớp đồ
thị split và cubic, Vũ Đình Hòa nghiên cứu trên lớp đồ thị 1-tough có tổng bậc lớn…
Chu trình Hamilton có nhiều ứng dụng trong thực tế, ví dụ như trong bài toán người
bán hàng, lập kế hoạch, hay trong thiết kế vi mạch, thiết kế đường truyền trong mạng… Bài
toán
(xác định sự tồn tại của chu trình Hamilton trong đồ thị) được biết là bài toán
[23] nên trong trường hợp tổng quát sẽ không có thuật toán tốt (thời gian đa thức) để giải
nó. Do đó, việc tìm ra được các trường hợp thuộc lớp của bài toán
cũng như việc thiết
kế được thuật toán thời gian đa thức để xác định được chu trình Hamilton có ý nghĩa hết sức
quan trọng.
Các nghiên cứu hiện nay hầu hết là dựa trên những lớp đồ thị đặc biệt và tập trung vào
việc chỉ ra sự tồn tại của chu trình Hamilton trong những lớp đồ thị đó. Có rất nhiều lớp đồ
thị được xét tới, trong đó phần lớn các lớp đồ thị này được xác định theo điều kiện tổng bậc
(của đỉnh) đủ lớn [15], [17], [18], [20], [22], [29], [30], [31], [36]... Một số tác giả nghiên
cứu độ phức tạp của bài toán
[3], [15], [23], [34], [37], hoặc đánh giá số lượng chu trình
Hamilton [14]… Một số khác nghiên cứu đến việc thiết kế các thuật toán để xác định chu
trình Hamilton, trong đó có các thuật toán Backtrack, Heuristic và các thuật toán thời gian
đa thức áp dụng cho những lớp đồ thị đặc biệt [5], [12], [22], [28], [38], [44]…
Trong [15] (Định lý 16), các tác giả đã đánh giá độ phức tạp của bài toán
đồ thị thỏa mãn
vẫn còn là bài toán
với mọi
với lớp
. Có thể nói rằng kết
quả này là tiền đề cho nghiên cứu về chu trình Hamilton của tác giả trong luận án. Thêm
vào đó, một số kết quả trong [11], [17], [32], [36] đã khẳng định sự tồn tại của chu trình
Hamilton trong các lớp đồ thị được xác định theo điều kiện của tổng bậc
và
đủ
lớn, tuy nhiên các lớp đồ thị được xác định theo điều kiện và
là chưa có thuật toán xác
định chu trình Hamilton.
3
Cùng với chu trình Hamilton, chu trình dài nhất trong đồ thị cũng được tập trung
nghiên cứu tới và có nhiều kết quả đối với chu trình dài được áp dụng cho việc chứng minh
sự tồn tại cũng như thiết kế thuật toán để xác định chu trình Hamilton. Trong một bài báo
của các tác giả D. Bauer, G. Fan, H. J. Veldman [8] đã đưa ra một Giả thuyết đánh giá độ
dài chu trình dài nhất theo giá trị
mà cho tới nay vẫn chưa có chứng minh thỏa đáng
nào cho Giả thuyết này.
Mục tiêu nghiên cứu của luận án là:
Nghiên cứu bài toán
trung vào trường hợp
trên các lớp đồ thị có tổng bậc
và
lớn, trong đó tập
.
Đánh giá độ phức tạp của bài toán
chuyển từ lớp
sang lớp .
theo một tham số . Xác định
để bài toán
Xây dựng thuật toán thời gian đa thức để xác định chu trình Hamilton trong một số
lớp đồ thị đã khảo sát.
Đánh giá tính hiệu quả và khả thi của các thuật toán bằng chương trình thực
nghiệm trên các đồ thị lớn.
Đánh giá độ dài của chu trình dài nhất trong lớp đồ thị 1-tough với
.
Kết cấu của luận án gồm: phần mở đầu, 4 chương và phần kết luận.
Chƣơng 1: Tổng quan về chu trình trong đồ thị.
Giới thiệu một số vấn đề cơ bản của lý thuyết đồ thị, các khái niệm, các quy ước và ký
hiệu sử dụng trong luận án. Tiếp đến, giới thiệu tổng quan về vấn đề chu trình trong đồ thị,
trọng tâm là chu trình Hamilton. Ngoài ra, tác giả đưa ra một số kết quả nghiên cứu về bao
đóng của đồ thị để sử dụng trong một số chứng minh của luận án.
Chƣơng 2: Một số lớp đa thức của bài toán
.
Chương này nghiên cứu về chu trình Hamilton theo hai bài toán
nguyên dương, số thực là tham số) như sau:
Instance: Đồ thị
Question:
(với
.
có là đồ thị Hamilton?
Instance: Đồ thị
Question:
thỏa mãn
và
thỏa mãn
.
có là đồ thị Hamilton?
Tác giả tập trung vào việc đánh giá độ phức tạp của bài toán theo tham số
các lớp đa thức của bài toán
.
để tìm ra
Chƣơng 3: Thuật toán đa thức xác định chu trình Hamilton trong đồ thị
và
.
4
Chương này sẽ thiết kế thuật toán đa thức xác định chu trình Hamilton cho các lớp đồ
thị
và
, sau đó tác giả tiến hành thực nghiệm trên các đồ thị lớn (hàng
nghìn đỉnh) để cho thấy tính hiệu quả và khả thi thực hiện của các thuật toán. Thêm vào đó,
tác giả đưa ra một số đề xuất mới để làm tăng hiệu năng thực hiện của thuật toán.
Chƣơng 4: Đánh giá độ dài chu trình dài nhất trong đồ thị 1-tough với
.
Chương này của luận án sẽ đưa ra một chứng minh cho Giả thuyết của các tác giả
Bauer, Fan, Veldman [8] về cận dưới của độ dài chu trình dài nhất rằng:
Nếu
là đồ thị 1-tough và
thì
.
Giả thuyết trên cũng đã được một số tác giả khác quan tâm và tìm cách chứng minh,
tuy nhiên các chứng minh đưa ra đều chưa thỏa đáng. Cho đến nay vẫn chưa có chứng minh
đúng nào cho Giả thuyết này và đây vẫn là vấn đề mở.
CHƢƠNG 1. TỔNG QUAN VỀ CHU TRÌNH TRONG ĐỒ THỊ
1.1. Một số khái niệm và quy ƣớc
Trong luận án chỉ xét tới các đồ thị hữu hạn, đơn, vô hướng và không có trọng số.
Khái niệm đường đi và chu trình trong luận án là đơn, nghĩa là chúng chỉ đi qua các
đỉnh không quá một lần. Một đường đi (đơn)
là một đồ thị con không
rỗng có cấu trúc:
và
, trong đó,
với mọi
. Các đỉnh
được nối bởi , và gọi là các đỉnh cuối; các đỉnh
gọi là các đỉnh trong của .
Nếu
là một đường đi và
một chu trình, khi đó chu trình được viết như sau:
chu trình gọi là độ dài của nó, ký hiệu là
.
được gọi là
. Số cạnh của
thì
Các ký hiệu khi viết không kèm theo đồ thị tường minh thì hiểu mặc định là đồ thị .
Ví dụ, viết
tương ứng thay cho
.
Giả sử
có thể xem
là một đường đi và là một chu trình của đồ thị . Trong luận án, đôi khi ta
như là một tập đỉnh con của (tương ứng thay cho
).
Một đường đi là mở rộng (theo tập đỉnh) của đường đi
tự, một chu trình là mở rộng của chu trình nếu
nếu
.
Với
, ta ký hiệu
là đoạn đường chạy dọc theo từ đỉnh
vậy, nếu
là các đỉnh cuối của thì
cũng chính là . Ngoài ra, |
đỉnh nằm trên đoạn đường con này.
. Tương
tới đỉnh . Như
| quy ước là số
Giả sử chu trình
. Ta quy định một chiều quay ⃗⃗⃗ theo
thứ tự chỉ số các đỉnh (chỉ số được lấy theo
). Với đỉnh
, ký hiệu
lần
lượt là đỉnh liền trước và liền sau của
theo chiều quay đã định. Với tập đỉnh
thì
,
. Với số nguyên dương
, ký hiệu
5
và
đầu từ một đỉnh
và kết thúc tại
. Ta ký hiệu đoạn đường trên bắt
theo chiều quay đã quy định bởi ⃗⃗⃗ , đoạn
đường đó theo chiều ngược lại ký hiệu là ⃖⃗⃗⃗ . Nếu là một thành phần liên thông của
, ký hiệu
là tập hợp các láng giềng của trên . Một dãy cung ngoại biên nối
hai đỉnh trên là một đường đi có các đỉnh cuối là 2 đỉnh đó và các đỉnh trong thuộc
. Đặc biệt, một cạnh nối 2 đỉnh trên cũng là một dãy cung ngoại biên.
Đôi khi ta cũng thường không viết dấu phẩy (,) ngăn cách giữa các đỉnh của một chu
trình hoặc một đường đi. Ví dụ, viết
thay cho
.
1.3. Chu trình Hamilton
Chu trình đi qua mọi đỉnh của đồ thị, mỗi đỉnh đi qua đúng một lần, gọi là chu trình
Hamilton. Đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton. Tương tự, đường đi
qua mọi đỉnh của đồ thị, mỗi đỉnh đi qua đúng một lần, gọi là đường Hamilton và đồ thị có
đường Hamilton gọi là đồ thị nửa Hamilton.
Lịch sử phát sinh đồ thị Hamilton được xuất phát từ trò chơi đố vui của William
Rowan Hamilton vào năm 1859. Chu trình Hamilton có nhiều ứng dụng trong thực tế, ví dụ
như trong bài toán người bán hàng, lập kế hoạch, hay trong thiết kế vi mạch, thiết kế đường
truyền trong mạng… Cho đến nay, vấn đề chu trình Hamilton vẫn còn là mở và trở thành
một vấn đề trung tâm của lý thuyết đồ thị với rất nhiều công trình nghiên cứu. Thông qua ba
bài tổng quan của Ronald J. Gould trong [25], [26], [27] thì có thể thấy rằng trong vòng 20
năm trở lại đây có khoảng 400 bài báo khoa học nghiên cứu về chu trình Hamilton được
đăng tải trên các tạp chí khoa học quốc tế có uy tín hàng đầu.
Trong luận án sẽ nghiên cứu chu trình Hamilton theo hướng sau:
Nghiên cứu bài toán
trên lớp đồ thị có tổng bậc
và
lớn.
Nghiên cứu độ phức tạp của bài toán và xác định ranh giới để bài toán
từ lớp
sang lớp .
chuyển
Xây dựng thuật toán thời gian đa thức để xác định chu trình Hamilton trong một số
lớp đồ thị đã khảo sát mà bài toán
thuộc lớp .
1.3.1. Độ phức tạp của bài toán
Bài toán
đã được chứng minh trong [23] là các bài toán
.
(Hamiltonian Cycle Problem)
Instance: Đồ thị .
Question:
có là đồ thị Hamilton?
Một số tác giả đã nghiên cứu đến độ phức tạp của bài toán
trên những lớp đồ thị
đặc biệt, chẳng hạn như trong [37] đánh giá độ phức tạp trên lớp đồ thị có hướng phẳng, hay
6
trong [3] nghiên cứu trên hai lớp đồ thị dạng lưỡng phân... Trong [15], các tác giả đã chỉ ra
rằng bài toán
trên lớp đồ thị
vẫn còn là bài toán
Định lý 1.1 [15, Định lý 16].
với mọi
là bài toán
với mọi
:
.
Kết quả trên là một tiền đề quan trọng để tác giả tiếp tục nghiên cứu đến độ phức tạp
của bài toán
trên các lớp đồ thị có tổng bậc
và
lớn.
1.3.3. Một số điều kiện đủ đối với bậc của đỉnh
Các kết quả nghiên cứu về chu trình Hamilton hầu hết tập trung ở điều kiện đủ, đặc
biệt là điều kiện đủ đối với bậc của đỉnh. Ta bắt đầu bằng với một kết quả của Dirac:
Định lý 1.4 [17]. Nếu đồ thị
đỉnh và bậc mỗi đỉnh đều không nhỏ hơn thì
với
là
đồ thị Hamilton.
Định lý Dirac là trường hợp riêng của Định lý Ore.
Định lý 1.5 [36]. Nếu đồ thị
đỉnh và
với
thì
là đồ thị Hamilton.
Với đồ thị tough, mở rộng cho Định lý Ore, Jung có kết quả sau:
Định lý 1.6 [29]. Cho
Hamilton.
là đồ thị 1-tough với
Mở rộng kết quả cho
đỉnh và
. Khi đó,G là đồ thị
có:
Định lý 1.7 [18]. Cho G là đồ thị 1-tough với
đỉnh và
. Khi đó,
là đồ
thị Hamilton.
Với đồ thị -liên thông, Bondy đưa ra kết quả tổng quát cho
Định lý 1.8 [11]. Nếu
như sau:
là đồ thị -liên thông thỏa mãn
thì
là đồ thị
Hamilton.
Liên quan đến khoảng cách có kết quả sau:
Định lý 1.10 [32, Định lý 5]. Cho
là đồ thị 2-liên thông với
. Khi đó xảy ra một trong hai trường hợp sau:
1.
là đồ thị Hamilton.
2.
là số lẻ và ̅
̅
̅
đỉnh thỏa mãn
.
1.3.4. Một số thuật toán xác định chu trình Hamilton
Các nghiên cứu về thuật toán xác định chu trình Hamilton được tiếp cận theo các
hướng sau:
Thuật toán Backtrack (Quay lui).
Thuật toán Heuristic.
Thuật toán tìm kiếm chu trình Hamilton cho các lớp đồ thị đặc biệt.
7
Các thuật toán Backtrack luôn đảm bảo tìm được chu trình Hamilton (nếu có) hoặc sẽ
kết thúc sau khi vét cạn các trường hợp mà đồ thị không có chu trình Hamilton, tuy nhiên
khả năng thực hiện hạn chế và thời gian chạy không khả thi trên các đồ thị lớn. Các thuật
toán Heuristic có sự cải tiến về khả năng thực hiện trên các đồ thị lớn và thời gian chạy
tuyến tính hoặc đa thức, tuy nhiên nó không đảm bảo rằng sẽ tìm được chu trình Hamilton,
mặc dù được thực hiện trên đồ thị Hamilton. Dưới đây là một số thuật toán Backtrack và
Heuristic xác định chu trình Hamilton trong đồ thị [5], [12], [38]:
Bảng 1.1. Một số thuật toán Backtrack và Heuristic xác định chu trình Hamilton
Thuật toán
Pósa
UHC
HAM
SparseHam
HideHam
DB2
LongPath
LinearHam
Snakes and Ladders
MultiPath
MultiPath cải tiến
KTC
Tác giả
Pósa
Angluin and Valiant
Bollobas, Fenner and Frieze
Frieze
Broder, Frieze and Shamir
Brunacci
Kocay and Li
Thomason
P. Baniasadi, V. Ejov, J.A. Filar, M.
Haythorpe, S. Rossomakhine
Kocay
Andrew Chalaturnyk
Shufelt and Berliner
Loại
Heuristic
Heuristic
Heuristic
Heuristic
Heuristic
Heuristic
Heuristic
Heuristic
Heuristic
Backtrack
Backtrack
Backtrack
Một số tác giả khác đã nghiên cứu tới việc xây dựng các thuật toán xác định chu trình
Hamilton trong các lớp đồ thị đặc biệt. Các thuật toán này là chính xác và đảm bảo tìm được
chu trình Hamilton, thời gian đa thức, tuy nhiên nhược điểm là không thực hiện được trên
đồ thị tổng quát. Gần đây, các tác giả trong [28] đã đưa ra thuật toán thời gian
trên đồ thị Circular-Arc, trong [22] sử dụng phương pháp “tham lam” và 2-matching để xây
dựng thuật toán thời gian
xác định chu trình Hamilton trong đồ thị ngẫu
nhiên… Với đồ thị Ore (lớp đồ thị
), một số tác giả cũng đưa ra thuật toán đa thức để
xác định chu trình Hamilton, chẳng hạn như thuật toán
do Albertson đề xuất [4]…
1.4. Bao đóng đồ thị
Bổ đề 1.2 [10]. Giả sử đồ thị có bậc và hai đỉnh không kề nhau
thỏa mãn
. Khi đó,
là đồ thị Hamilton khi và chỉ khi là đồ thị Hamilton.
Khái niệm bao đóng của đồ thị được Bondy và Chvátal đưa ra lần đầu tiên trong [10].
Bao đóng của đồ thị , ký hiệu bởi
là đồ thị thu được từ bằng cách bổ sung thêm
các cạnh nối các cặp đỉnh không kề nhau có tổng bậc không nhỏ hơn , quá trình này được
thực hiện cho đến khi nào không còn cặp đỉnh không kề nhau mà có tổng bậc không nhỏ
hơn nữa. Bao đóng của một đồ thị luôn xác định duy nhất, không phụ thuộc vào thứ tự
cạnh mới được thêm vào [2].
8
Hình 1.5. Quá trình tạo bao đóng đồ thị.
Trong việc bổ sung lần lượt các cạnh mới để tạo bao đóng
, ta thực hiện việc gán
nhãn tăng dần theo thứ tự các cạnh được bổ sung bằng mảng . Trước hết, [ ]
với
mọi cạnh
và đặt
. Khi cạnh mới đầu tiên
được bổ sung, ta gán [ ]
, và thu được đồ thị mới
. Quá trình được thực hiện liên tục cho đến khi
không có cạnh nào được bổ sung nữa và thu được đồ thị cuối cùng là
. Rõ ràng
là:
.
Thuật toán 1.2. Xây dựng đồ thị bao đóng và gán nhãn cho các cạnh.
Input: Đồ thị .
Output: Đồ thị
và các cạnh được gán nhãn.
Procedure Construct_Cl
Begin
For each
do
Begin
[ ]
;
For each
do If
Then
[ ]
[ ]
;
End;
For each
do
[ ]
;
[ ]
[ ]
;
Repeat
Stop
True;
For each
do
For each
do
If
and
Then
Begin
Stop
False;
;
[
;
[ ]
[ ]
;
[ ]
]
;
[ ]
;
, ta đặt:
[ ]
End;
Until Stop;
End;
Nếu
là một đồ thị con của
[ ]
.
9
Mệnh đề 1.2. Nếu
Hamilton.
là đồ thị Hamilton khi và chỉ khi
thì
là đồ thị
Thuật toán 1.3. Biến đổi chu trình Hamilton của đồ thị bao đóng.
Input:
là một chu trình Hamilton của
.
Output: Một chu trình Hamilton của đồ thị .
Procedure TransformCycle( )
Begin
While ( [ ]
) do
Begin
Tìm
[
]
[ ];
Tìm
[
và
]
[
]
[ ];
;
Đánh số lại các đỉnh trên
theo thứ tự mới:
;
End;
End;
1.6. Chu trình trong đồ thị có tập láng giềng lớn
Định lý 1.20 [8]. Nếu
là đồ thị 2-liên thông và
Định lý 1.21 [8]. Nếu
là đồ thị 1-tough và
thì
thì
.
.
Bauer, Fan, Veldman đã đưa ra Giả thuyết quan trọng sau:
Giả thuyết 1.3 [8, Giả thuyết 27]. Nếu
.
là đồ thị 1-tough và
thì
1.7. Kết luận Chƣơng 1
Như vậy, chương này đầu tiên đã giới thiệu các khái niệm cơ bản nhất của lý thuyết đồ
thị cần thiết cho luận án. Kế đến giới thiệu các Bổ đề, Thuật toán cơ bản, đặc biệt là bao
đóng đồ thị làm nền tảng cơ sở quan trọng cho các chứng minh trong luận án. Cuối cùng
trình bày tổng quan về chu trình trong đồ thị, tập trung trọng tâm tới chu trình Hamilton với
các vấn đề nêu ra là: độ phức tạp bài toán của
, một số điều kiện cần và đủ cho một đồ
thị là Hamilton, một số thuật toán để xác định chu trình Hamilton trong đồ thị. Ngoài ra, chu
trình Dominating, chu trình trong đồ thị có tập láng giềng lớn cũng được đề cập tới.
Định lý 1.1 của các tác giả trong [15] đã chỉ ra rằng bài toán
vẫn còn là bài toán
với mọi
trong lớp đồ thị
là tiền đề để tác giả tiếp tục nghiên
cứu bài toán
cho lớp đồ thị tổng quát hơn theo các giá trị
(với tổng quát) và
trong Chương 2 và Chương 3. Giả thuyết 1.3 của các tác giả trong [8] đưa ra đánh giá về độ
10
dài của chu trình dài nhất hiện nay vẫn còn là vấn đề mở, trong Chương 4 tác giả sẽ đưa ra
một chứng minh cho Giả thuyết này.
CHƢƠNG 2. MỘT SỐ LỚP ĐA THỨC CỦA BÀI TOÁN
2.1. Giới thiệu bài toán
và
Với số nguyên dương
Instance: Đồ thị
Question:
Với
và số thực ta xét bài toán tổng quát sau:
thỏa mãn
.
có là đồ thị Hamilton?
khi ta chỉ xét tới các cặp đỉnh khoảng cách 2:
, mở rộng cho bài toán
Instance: Đồ thị
Question:
thỏa mãn
.
có là đồ thị Hamilton?
Trường hợp
thì
và
chính là bài toán
2.2. Độ phức tạp của bài toán
trong trường hợp tổng quát.
và
Từ Định lý 1.1, dễ dàng suy ra Hệ quả sau:
Hệ quả 2.1.
là bài toán
.
Định lý 2.1.
là bài toán
.
Định lý 2.2.
là bài toán
Như vậy, với
.
thì bài toán
vẫn còn là bài toán
Giả thuyết 2.1. Với mọi số nguyên dương
thì bài toán
.
thuộc lớp .
2.3. Độ phức tạp của bài toán
2.3.1. Một số kết quả với
Từ Định lý 1.4 (Dirac) và Định lý 1.5 (Ore) ta hiển nhiên có:
Hệ quả 2.2.
và
là các bài toán thuộc lớp .
Từ Định lý 1.8 (Bondy) cho trường hợp
Hệ quả 2.3. Mọi đồ thị
Điều kiện
thỏa mãn
2-liên thông thỏa mãn
, ta có:
là đồ thị Hamilton.
là tốt nhất có thể theo nghĩa là tồn tại vô hạn đồ thị 2-liên thông
nhưng không Hamilton, chẳng hạn các đồ thị
̅
với
.
11
Hệ quả 2.4.
là bài toán thuộc lớp .
Hệ quả 2.5.
là bài toán thuộc lớp .
Với kết quả của Bondy (Định lý 1.8) cho trường hợp
thì không thể kết luận cho
độ phức tạp của bài toán
vì điều kiện 3-liên thông không phải là điều kiện cần của một
đồ thị Hamilton. Ta sẽ chứng minh
cũng là bài toán thuộc lớp bằng việc
khảo sát lớp đồ thị thỏa mãn
.
Định lý 2.3. Cho đồ thị
2-liên thông thỏa mãn
. Khi đó, hoặc
Hamilton, hoặc
và có cấu trúc thuộc một trong 3 dạng sau:
1. Dạng 1: Tồn tại
| |
sao cho
là đồ thị
. (Hình 2.1)
Hình 2.1. Đồ thị Dạng 1, Định lý 2.3.
2. Dạng 2: có ba đồ thị con đầy đủ
và một đỉnh
sao cho tồn tại
,
,
và
. Hơn
nữa, tồn tại ba đỉnh
,
,
sao cho
. Ngoài ra, đỉnh có thể kề với bất kỳ đỉnh còn lại nào. (Hình 2.2)
Hình 2.2. Đồ thị Dạng 2, Định lý 2.3.
3. Dạng 3:
đỉnh
có ba đồ thị con đầy đủ
với
sao cho
. (Hình 2.3)
|
||
||
|
và tồn tại các
12
Hình 2.3. Đồ thị Dạng 3, Định lý 2.3.
Hệ quả 2.6. Mọi đồ thị 2-liên thông thỏa mãn
là đồ thị Hamilton.
và
Từ thuật toán đa thức nhận biết 3 dạng đồ thị đặc biệt không Hamilton trong Định lý
2.3, ta có:
Định lý 2.4.
là bài toán thuộc lớp .
2.4. Bài toán
Từ Định lý 1.10, để đánh giá được độ phức tạp của bài toán
thuật toán thời gian
sau:
thuộc dạng: ̅
Thuật toán 2.4. Nhận biết đồ thị
̅
ta sẽ đưa ra
̅
Input: Đồ thị .
Output: Is_Graph4 = True nếu ̅
̅
̅
,
ngược lại, Is_Graph4 = False.
Chương trình:
Function Boolean Is_Graph4
Begin
If (
) Then Return False;
Tính bậc các đỉnh của
;
;
For each
If (
If (| |
do
) Then
) and (
;
là tập đỉnh độc lập) Then
Return True
Else Return False;
End;
Hệ quả 2.7.
Hệ quả 2.8.
là bài toán thuộc lớp .
là bài toán thuộc lớp .
.
13
2.5. Kết luận Chƣơng 2
Bài toán
đã được đánh giá độ phức tạp trong [15] và Chương này tác giả đã tiếp
tục nghiên cứu mở rộng theo hai bài toán
(với nguyên dương tổng quát) và
.
Các kết quả đạt được như sau:
Với
thì các bài toán
Với
thì các bài toán
vẫn còn là bài toán
và
.
thuộc lớp .
Như vậy, có thể nói rằng Giả thuyết 2.1 đã được tác giả giải quyết đến trường hợp
, với
thì vẫn còn là vấn đề mở.
Dựa trên các kết quả đạt được và Hệ quả 2.6, tác giả đưa ra Giả thuyết thứ hai:
Giả thuyết 2.2. Với mọi số nguyên dương , nếu đồ thị
thì
2-liên thông thỏa mãn
và
là đồ thị Hamilton.
CHƢƠNG 3. THUẬT TOÁN ĐA THỨC XÁC ĐỊNH CHU TRÌNH
HAMILTON TRONG ĐỒ THỊ
VÀ
Chương này tác giả sẽ đề xuất các thuật toán đa thức xác định chu trình Hamilton cho
hai lớp đồ thị
. Thêm vào đó, tác giả đề xuất việc sử dụng bao
và
đóng đồ thị để mở rộng lớp đồ thị thực hiện thuật toán. Cuối cùng, tác giả tiến hành thực
nghiệm trên các đồ thị có số đỉnh lớn để cho thấy tính hiệu quả và khả thi thực hiện của các
thuật toán đề xuất.
3.1. Thuật toán cho lớp đồ thị
Bổ đề 3.1. Cho là đồ thị thỏa mãn
và là đồ thị Hamilton. là một chu trình
bất kỳ trong ,
là một thành phần liên thông của
. Giả sử các đỉnh của
được đánh số theo một chiều quay trên lần lượt là
. Nếu có không quá
đỉnh thì sẽ xảy ra một trong các trường hợp sau:
1. Tồn tại
sao cho
2. Tồn tại
với
.
, khi đó
3. Tồn tại
4. Tồn tại
.
sao cho
kề với tất cả các đỉnh
.
a. Thuật toán 3.1. Xác định chu trình Hamilton cho đồ thị
Input: Đồ thị
,
2-liên thông thỏa mãn
Output: Chu trình Hamilton của
chu trình Hamilton.
Procedure Hamilton2*;
nếu
.
.
là đồ thị Hamilton, hoặc trả lời
không có
14
BEGIN
// Kiểm tra
1:
2:
3:
4:
5:
If ( ̅
̅
Begin
Thông báo
Kết thúc;
End;
// Trường hợp
6:
không là đồ thị Hamilton
̅
) Then
không có chu trình Hamilton;
là đồ thị Hamilton
Tìm một chu trình tùy ý
của đồ thị
;
// Vòng lặp mở rộng tập đỉnh của
7:
8:
9:
10:
While
Begin
| |
Do
Tìm một thành phần liên thông
của –
Đánh số các đỉnh của
lần lượt là
// Mở rộng chu trình
11:
12:
13:
14:
15:
End
17:
Else If tồn tại
Begin
Tìm
sao cho
Tìm một đường đi
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
Then
;
nối x với y trong
⃖⃗⃗⃗
Thay thế
thành chu trình mới
End
Else If tồn tại
Then
Begin
Chọn
tùy ý và tìm
sao cho
Tìm một đường đi
nối x với y trong
⃖⃗⃗⃗
Thay thế
thành chu trình mới
End
Else
Begin
Tìm
và tìm
Tìm một đường đi
Thay thế
34:
End;
35:
End;
END;
33:
Then
;
nối x với y trong ;
⃗⃗⃗
thành chu trình mới
;
16:
18:
;
theo 4 trường hợp
If tồn tại
Begin
Tìm
sao cho
Tìm một đường đi
Thay thế
;
sao cho
nối x với y trong
⃗⃗⃗
thành chu trình
Thuật toán 3.1 cần không quá
phép toán thực hiện.
;
⃗⃗⃗
;
;
;
⃗⃗⃗
;
;
;
⃗⃗⃗
;
15
3.2. Thuật toán cho lớp đồ thị
Ý tưởng của thuật toán là trong trường hợp 2-liên thông thì xây dựng một chu trình
tùy ý trong với thời gian đa thức, sau đó mở rộng cho đến khi đủ đỉnh bằng cách
nối thêm một số cạnh cho cặp đỉnh không kề nhau có tổng bậc không nhỏ hơn , đồng thời
kết hợp với việc gán nhãn cho các cạnh (được trình bày trong phần 1.4). Cuối cùng, ta sử
dụng Thuật toán 1.3 (TransformCycle) để tìm chu trình Hamilton cho đồ thị ban đầu từ .
a. Thuật toán 3.2. Xác định chu trình Hamilton cho đồ thị
Input: Đồ thị
2-liên thông thỏa mãn
Output: Chu trình Hamilton
.
của .
Procedure Hamilton3;
BEGIN
// Gán nhãn bằng 1 cho tất cả các cạnh của
For each
2:
;
Tìm một chu trình tùy ý
của đồ thị
While | |
Do
Begin
Đánh số lại các đỉnh của
3:
4:
5:
6:
7:
8:
in
[ ]
1:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
If tồn tại
Begin
Tìm
sao cho
Tìm một đường đi
;
–
;
Then
;
nối x với y trong
⃗⃗⃗
Thay thế
thành chu trình mới
End
Else If tồn tại
Then
Begin
Tìm
sao cho
;
Tìm một đường đi
nối x với y trong
⃖⃗⃗⃗
Thay thế
thành chu trình mới
End
Else
Begin
Tìm hai đỉnh
24:
25:
27:
của
;
theo 3 trường hợp
bất kỳ thuộc
// Bổ sung cạnh mới
26:
;
Tìm một thành phần liên thông
Tìm tập đỉnh
;
// Mở rộng
9:
do
[
Tìm
]
;
;
;
sao cho
;
;
;
;
cho đồ thị và gãn nhãn
;
⃗⃗⃗
;
16
28:
29:
30:
31:
Tìm một đường đi
Thay thế
End;
End;
// Biến đổi
32:
nối x với y trong
⃖⃗⃗⃗
thành chu trình mới
thành chu trình Hamilton của
;
⃗⃗⃗
;
ban đầu
TransformCycle( );
END;
Thuật toán 3.2 cần không quá
phép toán thực hiện.
3.3. Sử dụng bao đóng cho các lớp đồ thị có tổng bậc lớn
Theo Mệnh đề 1.2 thì là đồ thị Hamilton khi và chỉ khi
là đồ thị Hamilton.
Trong đồ thị bao đóng
, bậc của mỗi đỉnh đều không nhỏ hơn bậc của đỉnh tương ứng
trong đồ thị (Vì
), do đó các điều kiện về tổng bậc
lớn trong đồ thị bao
đóng
sẽ có nhiều khả năng thỏa mãn hơn so với đồ thị ban đầu. Sau khi tìm được
một chu trình Hamilton trong đồ thị
, sử dụng Thuật toán 1.3 sẽ tìm được một chu
trình Hamilton trong đồ thị ban đầu từ chu trình . Do đó, tác giả đưa ra đề xuất sau:
Hình 3.1. Sơ đồ thuật toán xác định chu trình Hamilton sử dụng bao đóng đồ thị
17
Đề xuất 3.1. Sử dụng bao đóng đồ thị kết hợp với các thuật toán xác định chu trình
Hamilton trong các lớp đồ thị có tổng bậc lớn để có thể thực hiện cho lớp đồ thị tổng quát
hơn.
Như vậy, thay vì việc không áp dụng được thuật toán cho đồ thị ban đầu, khi chuyển
sang đồ thị bao đóng thì khả năng áp dụng được thuật toán sẽ cao hơn. Với Thuật toán 3.1
và 3.2 khi sử dụng bao đóng đồ thị như sơ đồ thuật toán trên cũng chỉ cần không quá
phép toán thực hiện.
Với các đồ thị có tổng bậc lớn thì số cạnh cũng lớn nên khi chạy chương trình cho
Thuật toán tìm chu trình Hamiltton trên đồ thị bao đóng thì thời gian tăng không đáng kể.
3.4. Chƣơng trình thực nghiệm
Phần này sẽ xây dựng chương trình thực nghiệm cho hai thuật toán 3.1 và 3.2 mà tác
giả đã đề xuất để xác định chu trình Hamilton cho lớp đồ thị
và
.
3.4.1. Giới thiệu chƣơng trình
Hình 3.2. Sơ đồ khối thực hiện chương trình
Chương trình thực nghiệm sẽ được xây dựng theo sơ đồ khối đưa ra trong Hình 3.2 và
phần thực hiện Tìm Chu trình Hamilton theo thuật toán tƣơng ứng sẽ được đo thời gian.
Tác giả xây dựng hai chương trình thực nghiệm xác định chu trình Hamilton như sau:
Bảng 3.1. Các chương trình thực nghiệm xác định chu trình Hamilton
Chƣơng trình
Lớp đồ thị
Chương trình 1
Chương trình 2
.
.
Thuật toán áp dụng
Thuật toán 3.1
Thuật toán 3.2
Thời gian
18
Việc xác định giá trị
kỳ có thuộc lớp
hoặc
nên việc kiểm tra một đồ thị bất
cần thuật toán
hoặc
, do đó Chương trình
chỉ mất thời gian là
có thể nhận dữ liệu đầu vào là đồ thị tổng quát và thực hiện khả thi với các đồ thị lớn.
Chương trình sử dụng ngôn ngữ lập trình C# và được tiến hành thực nghiệm trên máy
tính sử dụng Hệ điều hành Windows7, bộ vi xử lý Core i3 2.53 GHz, RAM 8GB.
3.4.2. Bộ dữ liệu đầu vào
Do không có đồ thị mẫu và cũng chưa có tác giả nào tiến hành thực nghiệm việc tìm
chu trình Hamilton trên những lớp đồ thị
và
nên tác giả sẽ xây dựng
hai bộ dữ liệu được sinh ngẫu nhiên gồm các đồ thị 2-liên thông thỏa mãn điều kiện đầu vào
tương ứng của Thuật toán 3.1 hoặc Thuật toán 3.2 để thực nghiệm.
Bộ dữ liệu 1 gồm các đồ thị thỏa mãn điều kiện
điều kiện
, nhưng không thỏa mãn
. Bộ dữ liệu 2 gồm các đồ thị thỏa mãn điều kiện
không thỏa mãn điều kiện
.
Bảng 3.2. Danh sách các đồ thị được tiến hành thực nghiệm
Số đỉnh
( )
Đồ thị
Bộ dữ liệu 1
(
)
Bộ dữ liệu 2
1000
S2sao-1000
S3-1000
2000
S2sao-2000
S3-2000
3000
S2sao-3000
S3-3000
4000
S2sao-4000
S3-4000
5000
S2sao-5000
S3-5000
6000
S2sao-6000
S3-6000
7000
S2sao-7000
S3-7000
8000
S2sao-8000
S3-8000
9000
S2sao-9000
S3-9000
10000
S2sao-10000
S3-10000
(
)
3.4.3. Đánh giá hiệu năng
Bảng 3.3. Thống kê thời gian chạy chương trình khi sử dụng Thuật toán 1.1
Chƣơng trình 1
Đồ thị
S2sao-1000
S2sao-2000
S2sao-3000
Chƣơng trình 2
Thời gian (s)
Đồ thị
2.467 S3-1000
19.664 S3-2000
64.895 S3-3000
Thời gian (s)
2.283
17.945
61.586
, nhưng
19
S2sao-4000
S2sao-5000
S2sao-6000
S2sao-7000
S2sao-8000
S2sao-9000
S2sao-10000
154.620
300.194
525.644
836.379
1249.134
1780.245
2416.288
S3-4000
S3-5000
S3-6000
S3-7000
S3-8000
S3-9000
S3-10000
141.135
264.959
476.623
754.716
1122.091
1618.704
2200.797
Thuật toán 3.1 và Thuật toán 3.2 đều có điểm chung là sử dụng Thuật toán 1.1 để xây
dựng một chu trình ban đầu, sau đó mở rộng cho đến khi có đủ đỉnh do đó độ dài
của chu trình ban đầu sẽ có ảnh hưởng rất lớn đến thời gian chạy chương trình.
Thuật toán 1.1 tìm một chu trình bất kỳ trong đồ thị làm chu trình khởi tạo ban đầu,
tuy nhiên độ dài của là thường là nhỏ. Để tăng tốc độ thực hiện cho chương trình thì có
thể sử dụng một số phương pháp Heuristic thay cho Thuật toán 1.1 để chu trình ban đầu
có độ dài lớn, khi đó số vòng lặp mở rộng chu trình sẽ giảm đáng kể.
Đề xuất 3.2. Tìm một đường đi dài nhất có thể, sau đó tìm cặp đỉnh
thuộc sao
cho
và đoạn đường
dài nhất có thể. Khi đó, ta có một chu trình độ dài lớn là
;
Đề xuất trên có thể được thực hiện bởi Thuật toán
sau.
Thuật toán 3.3. Xác định một chu trình có độ dài lớn trong đồ thị 2-liên thông
Input: Đồ thị 2-liên thông .
Output: Một chu trình
của
có độ dài lớn.
Procedure Create_Long_Cycle()
Begin
Tìm một cạnh
;
;
Stop = False;
While Not(Stop) Do
Begin
Stop = True;
For each
If
Do
và (
là một đỉnh cuối của
Begin
;
;
Stop = False;
End;
End;
Found = False; Length =
;
) Then
20
While Not(Found) Do
Begin
sao cho |
If tồn tại
Begin
| = Length và
Then
; Found = True;
End
Else Length = Length – 1;
End;
End;
Thay thế Thuật toán 1.1 bởi Thuật toán 3.3 để tìm chu trình khởi tạo ban đầu , tác giả
đã cải tiến được đáng kể thời gian chạy hai chương trình.
Bảng 3.4. Tổng hợp thời gian chạy Chương trình 1 trước và sau khi cải tiến.
Chƣơng trình 1
Đồ thị
S2sao-1000
S2sao-2000
S2sao-3000
S2sao-4000
S2sao-5000
S2sao-6000
S2sao-7000
S2sao-8000
S2sao-9000
S2sao-10000
Độ dài
ban đầu
4
4
4
4
4
4
4
4
4
4
Thời gian
(s)
2.467
19.664
64.895
154.620
300.194
525.644
836.379
1249.134
1780.245
2416.288
Chƣơng trình 1 cải tiến
Độ dài ban
đầu
999
1997
2988
3980
4997
5990
6987
7951
8997
9986
Thời gian
(s)
0.032
0.098
0.653
1.738
0.482
1.996
3.470
16.556
1.496
7.569
Bảng 3.5. Tổng hợp thời gian chạy Chương trình 2 trước và sau khi cải tiến.
Chƣơng trình 2
Đồ thị
S3-1000
S3-2000
S3-3000
S3-4000
S3-5000
S3-6000
S3-7000
S3-8000
S3-9000
S3-10000
Độ dài
ban đầu
3
3
3
3
3
3
3
4
3
3
Thời gian
(s)
2.283
17.945
61.586
141.135
264.959
476.623
754.716
1122.091
1618.704
2200.797
Chƣơng trình 2 cải tiến
Độ dài
ban đầu
994
1998
2992
3995
4997
5997
6995
7998
8998
9998
Thời gian
(s)
0.065
0.123
0.436
0.639
0.799
1.418
1.753
2.192
2.569
3.373
21
Phân tích sự ảnh hưởng của độ dài chu trình khởi tạo ban đầu đối với thời gian chạy
chương trình, tác giả chọn đồ thị S3-2000 để tiến hành thực nghiệm (bằng Chương trình 2).
Kết quả thực nghiệm được đưa ra trong Bảng 3.6 và Hình 3.3 như sau:
Bảng 3.6. Thống kê thời gian chạy Chương trình 2 trên đồ thị S3-2000 theo độ dài chu trình khởi
tạo ban đầu.
Độ dài
ban đầu
Thời gian (s)
3
17.945
200
14.802
400
12.266
600
10.095
800
8.588
1000
6.737
1200
5.380
1400
4.391
1600
2.893
1800
1.587
1998
0.123
Hình 3.3. Biểu đồ thời gian chạy Chương trình 2 trên đồ thị S3-2000 theo độ dài chu trình khởi tạo
ban đầu.
3.5. Kết luận Chƣơng 3
Chương này đã đề xuất hai thuật toán chính xác để xác định chu trình Hamilton trong
lớp đồ thị
và
. Hai thuật toán này đã được đánh giá trên phương diện
lý thuyết là không quá
phép toán thực hiện và tác giả cũng đã tiến hành thực nghiệm
trên các đồ thị lớn từ 1000 đỉnh đến 10000 đỉnh. Kết quả thực nghiệm đã cho thấy tính khả
thi, hiệu quả và ý nghĩa thực tiễn của các thuật toán do tác giả đề xuất.
22
Tác giả đã tiến hành thực nghiệm theo hai chương trình khác nhau và đánh giá được
yếu tố ảnh hưởng chính đến thời gian chạy chương trình là độ dài của chu trình khởi tạo ban
đầu bằng lý thuyết và thực nghiệm. Việc cải tiến chương trình bằng Thuật toán 3.3 đã giảm
được đáng kể thời gian chạy chương trình.
Tác giả cũng đã đưa ra một đề xuất quan trọng khác cho việc mở rộng lớp đồ thị có thể
áp dụng các thuật toán tìm chu trình Hamilton trên các đồ thị có tổng bậc lớn bằng việc xây
dựng bao đóng đồ thị. Việc sử dụng bao đóng tuy có làm tăng thời gian chạy chương trình
nhưng ưu điểm là thực hiện được trên lớp đồ thị tổng quát hơn, và đặc biệt là trên các đồ thị
có tổng bậc lớn thì thời gian chạy chương trình tăng không đáng kể.
CHƢƠNG 4. ĐÁNH GIÁ ĐỘ DÀI CHU TRÌNH DÀI NHẤT TRONG ĐỒ THỊ
1-TOUGH VỚI
4.1. Giới thiệu Giả thuyết Bauer
Giả thuyết 1.3 của Bauer, Fan, Veldman đánh giá độ dài chu trình dài nhất rằng [8]:
Nếu đồ thị
là đồ thị 1-tough và
thì
.
Giả thuyết này cũng đã được một số tác giả quan tâm và tìm cách chứng minh, tuy
nhiên các chứng minh đưa ra đều chưa thỏa đáng, chẳng hạn như chứng minh của tác giả Tri
Lai [43] bị sai tại Proposition 26. Cho đến nay vẫn chưa có chứng minh đúng nào cho Giả
thuyết này và đây vẫn là vấn đề mở. Chương này tác giả sẽ đưa ra chứng minh của mình cho
Giả thuyết 1.3 này.
Trong toàn bộ chứng minh của Chương, các Quy ước 4.1, 4.2, 4.3, 4.4, 4.5 đều được
sử dụng ngay sau khi phát biểu cho đến hết Chương.
Quy ƣớc 4.1. Giả sử rằng đồ thị
là 1-tough thỏa mãn
và không Hamilton.
Theo Quy ước 4.1 ta cần chứng minh rằng
.
4.2. Các Tính chất và Bổ đề
Tính chất 4.1. Mọi chu trình dài nhất của
Với một chu trình dài nhất
của
|
đều là chu trình Dominating.
(cũng là chu trình Dominating) ta định nghĩa:
|
và
Quy ƣớc 4.2. Lấy ⃗⃗⃗ là một chu trình dài nhất của
mãn
và một đỉnh
sao cho
với một chiều quay định hướng thỏa
. Đặt
.
Tính chất 4.2 (Tham khảo chứng minh của Định lý 9 trong [9]).
Tính chất 4.3 [41, Bổ đề 9]. | |
Tính chất 4.4. | |
.
.
.
.
23
Bổ đề 4.1 [42]. Cho ⃗⃗⃗ là một chu trình có độ dài của đồ thị . Giả sử rằng
chu trình độ dài
và không có chu trình
độ dài với
là một đỉnh cô lập của
. Đặt
, và với
thì:
,
Đặt
⋃
(a)
.
⋃
và
(b) Nếu
thì
(c)
không có
, và
.
. Khi đó:
.
.
Quy ƣớc 4.3. Giả sử rằng hai tập đỉnh
được xây dựng như trong Bổ đề 4.1 với đỉnh
(nói trong Bổ đề 4.1) chính là đỉnh được xác định từ Quy ước 4.2.
Tính chất 4.5.
(a) Không có cạnh nối một đỉnh của
(c)
là tập đỉnh độc lập.
(d)
và
.
| |.
, do đó
(b)
với một đỉnh của
.
Quy ƣớc 4.4. Nhận thấy rằng mọi đỉnh
nên
. Ta lấy cố
| | , xuất hiện lần lượt
định một đỉnh
và kí hiệu đỉnh của là
trên ⃗⃗⃗ sao cho
. Với
, đặt
và
. Theo Bổ đề
4.1 (b),
và do đó
sẽ là hợp của các đường rời nhau ⃗⃗⃗ , ta gọi là các
arc. Một arc với đỉnh được gọi là một -arc. Khi đó ⃗⃗⃗
là 1-arc khi và chỉ khi
(chính là một đỉnh thuộc ). Hai arc được gọi là kề nhau nếu tồn tại một cạnh nối
giữa một đỉnh thuộc arc này với một đỉnh thuộc arc còn lại.
Tính chất 4.6.
là tập đỉnh độc lập.
(a)
(b)
| |
.
Tính chất 4.7.
có ít nhất hai arc với độ dài không nhỏ hơn 2.
Quy ƣớc 4.5.
| | và
.
Tính chất 4.8 [41, Bổ đề 4].
Định nghĩa 4.1. Cặp đỉnh
Định nghĩa 4.2. Đường đi
1.
2.
và
là các tập đỉnh độc lập.
được gọi là bad-pair nếu
và |
trong
gồm tất cả các đỉnh của ⃗⃗⃗
với
và
⃖⃗⃗⃗
gồm tất cả các đỉnh của
với
và
được gọi là bad-path nếu
|
| |.
là một trong hai dạng sau:
, các đỉnh cuối của
là
và
, các đỉnh cuối của
là
và
.
.
24
Tính chất 4.9. Không có cặp đỉnh nào trong
Bổ đề 4.2. Không có đường đi nào trong
Bổ đề 4.3. Nếu
là bad-pair.
là bad-path.
với
thì
hoặc
.
Bổ đề 4.4. Nếu
với
Bổ đề 4.5. Giả sử rằng
. Tương tự,
Bổ đề 4.9. Giả sử rằng
sao cho
hoặc
thì
Vì
| |
⃗⃗⃗
-arc
.
có một -arc
⃗⃗⃗
có một -arc
sao cho không có -arc
{ } thì
hoặc
. Nếu
thì
⃗⃗⃗
. Nếu tồn tại một đỉnh
.
và không có -arc
{ } thì
.
Bổ đề 4.10. Giả sử rằng
⃗⃗⃗
và đỉnh
và
với
có một
}
với mọi
.
với
. Tương tự, nếu
Bổ đề 4.8. Giả sử rằng
. Khi đó, {
.
. Khi đó
với
với mọi
Bổ đề 4.6. Giả sử rằng
và
thì
.
Bổ đề 4.7. Giả sử rằng
sao cho
thì
nào thuộc
.
⃗⃗⃗
và một -arc
⃗⃗⃗
và một -arc
⃗⃗⃗
với
nào thuộc
⃗⃗⃗
. Nếu
với
,
và một -arc ⃗⃗⃗
với
⃗⃗⃗
⃗⃗⃗ . Nếu
| |
và theo Tính chất 4.6 (b), ta có hoặc
. Ta xét hai trường hợp:
và
,
| |
, hoặc
| |
Trƣờng hợp 1.
. Trong trường hợp này, theo Tính chất 4.7 thì
bao gồm hai 2-arc và còn lại là các 1-arc.
Trƣờng hợp 2.
hai khả năng sau:
| |
. Trong trường hợp này, theo Tính chất 4.7 thì xảy ra
Trƣờng hợp 2.1.
bao gồm một 2-arc, một 3-arc và các 1-arc.
Trƣờng hợp 2.2.
bao gồm ba 2-arc và còn lại là các 1-arc.
4.3. Chứng minh cho các trƣờng hợp
Trong phần này sẽ chứng minh rằng tất cả các trường hợp trên đều không xảy ra bằng
phương pháp phản chứng. Chứng minh gồm có 4 Mệnh đề và 21 Khẳng định.
