Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai
BT Toan roi rac
1

BÀI TẬP CHƯƠNG I
Bài 1:
Số mã vùng cần thiết nhỏ nhất là bao nhiêu để đảm bảo 25 triệu máy điện thoại khác nhau.
Mỗi điện thoại có 9 chữ số có dạng 0XX-8XXXXX với X nhận giá trị từ 0 đến 9.

Giải:

Vì số mã vùng có dạng: 0XX-8XXXXX, với X nhận các giá trị từ 0 đến 9 (10 số), có 07 ký tự X
do vậy sẽ có 10
7
trường hợp. Do đó, theo nguyên lý Dirichlet với 10 triệu máy điện thoại thì số mã vùng
cần thiết là:
][
35,2
000.000.10
000.000.25
==
⎢
⎣
⎡
⎥
⎦
⎤
. Vậy số mã vùng cần thiết thỏa yêu cầu bài toán là 3.

Bài 2:

⎢
⎣
⎡
⎥
⎦
⎤
.
Cách hiểu 2: (serial là 02 ký tự NN đầu tiên)
Bốn ký tự NNNN sẽ có 10
4
trường hợp, 02 ký tự XN sẽ có 26*10 = 260 trường hợp. Theo quy tắc
nhân, tổng số trường hợp sẽ là: 10
4
*260 = 2.600.000. Do đó, theo nguyên lý Dirichlet, số serial tối thiểu
phải là:

][
484,3
000.600.2
000.000.10
==
⎢
⎣
⎡
⎥
⎦
⎤
.
Vậy cần 04 số serial để đăng ký đủ cho 10 triệu xe.


Bắt đầu bằng 00 và kết thúc bằng 11.
Xâu nhị phân thỏa mãn đề bài phải có dạng: 00.xxxx.xx11. Hai ký tự đầu và 02 ký tự cuối là
không đổi, do vậy chỉ còn 06 ký tự ở giữa. Do đó số xâu nhị phân thỏa mãn đề bài là: 2
6

xâu.

Bài 4:
Khóa 29 CNTT có 150 SV học NNLT Java, 160 SV hoc Delphi, 40 SV học cả hai môn trên.
a. Tìm tất cả SV của khóa 29 biết rằng SV nào cũng phải học ít nhất 01 môn.
b. Biết tổng số SV là 285, hỏi có bao nhiêu SV không học Java hoặc Delphi.

Giải

Gọi J: SV học Java
D: SV học Delphi
a.
Số SV của khóa 29 là: 27040160150
1
=−+=−+== DJDJDJn IU SV
b.
Câu b có 02 cách hiểu:
Cách 01: không học ít nhất 01 môn.
Số SV không học Java hoặc Delphi là (áp dụng nguyên lý bù trừ) ta tính được:
24540285
2
=−=−= DJnn I
SV
Cách 02: không học Java cũng chẳng học Delphi:
Theo cách hiểu này, áp dụng nguyên lý bù trừ ta tính được số SV như sau:

887766
876
=−+−+−=++= nnnn

Cách 02: không phân biệt chữ thường với chữ hoa:
Cách làm hoàn toàn tương tự, nhưng thay vì sử dụng các số 62 và 52 thì ở đây sử dụng 02 số: 36
và 26. Kết quả sẽ là:

063.3602.684.483.263626362636
887766
876
=−+−+−=++= nnnnBài 6:
Có n lá thư bỏ vào n bì thư. Hỏi xác suất để xảy ra trường hợp không có lá thư nào bỏ đúng
được bì thư của nó.

Giải
Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai

BT Toan roi rac
3
Vì có n phong bì và n bì thư nên có tất cả N = n! cách bỏ thư khác nhau. Để đếm số cách bỏ thư
sao cho không lá thư nào đúng địa chỉ, ta áp dụng nguyên lý bù trừ:
N
= n! − N
1
+ N

1
− + (−1)
n

!
1
n
),
Dođó xác suất thỏa bài toán:
k
111 1
1 + - + +(-1)
!1!2!3! k!
NN
p
Nn
===−

Bài 7:
Chỉ ra rằng nếu chọn 5 số từ tập 8 số {1, 2, …, 7, 8} thì bao giờ cũng có ít nhất 01 cặp số có
tổng là 9.

Giải

Từ 8 số ở trên, ta chia thành 04 cặp: {1, 8}, {2, 7}, {3, 6}, {4, 5} và tổng của mỗi cặp đều bằng 9.
Như vậy, đề bài sẽ trở thành chọn 5 số từ 4 cặp số trên. Theo nguyên lý Dirichlet, phải có ít nhất 01 cặp
số được chọn hết. Vậy bài toán đã được chứng minh.

Bài 8:
Chứng minh rằng trong bất kỳ một nhóm 27 từ tiếng Anh nào cũng có ít nhất 2 từ bắt đầu

Nếu ký tự cuối cùng là 0 thì ký tự trước đó (ký tự thứ n – 1) chỉ có thể là 1 (vì nếu là 0 thì vi phạm
yêu cầu bài toán) nhưng ký tự trước đó nữa (thứ n – 2) có thể là 0 hay 1 đều được.
Từ 02 trường hợp trên ta suy ra được:
21 −−
+=
nnn
fff
Các điều kiện đầu:
2
1
=f , 3
2
=f
Có 13 xâu nhị phân có độ dài 5 và không có 2 số 0 liên tiếp.
Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai

BT Toan roi rac
4

Bài 11:
Dãy các số Fibonacci thõa
21 −−
+=
nnn
fff , cho điều kiện đầu:
⎩
⎨
⎧
=

nn
n
f
αα
⎛⎞⎛⎞
+−
=+
⎜⎟⎜⎟
⎜⎟⎜⎟
⎝⎠⎝⎠

với các điều kiện ban đầu :
12
1
0
12
1
2
1
0
0
5
15 15
1
1
1
22
5
f
f

Do đó các số Fibonacci được cho bởi công thức như sau:
11 5 11 5
22
55
nn
n
f
⎛⎞⎛⎞
+−
=−
⎜⎟⎜⎟
⎜⎟⎜⎟
⎝⎠⎝⎠Bài 12:
Tìm nghiệm của hệ thức truy hồi sau:
321
652
−−−
−+=
nnnn
aaaa trong đó các điều kiện đầu
là: 7
0
=a , 4
1
−=a , 8
2
=a .

ααα
+−+=
Với các điều kiện đầu được cho: 7
0
=a , 4
1
−=a , 8
2
=a . Ta có hệ phương trình như sau:
⎪
⎩
⎪
⎨
⎧
−=
=
=
⇒
⎪
⎩
⎪
⎨
⎧
++=
+−=−
++=
1
3
5
948


Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai

BT Toan roi rac
5
Với n đường t
hẳng, theo đề bài thì đường thẳng thứ n sẽ cắt n – 1 đường thẳng còn lại tại n – 1
điểm, tức là sẽ cắt n – 1 + 1 = n phần mặt phẳng. Do đó, số phần mặt phẳng tăng lên là n. Từ đó, ta có
được hệ thức truy hồi: nrr
nn
+=
−1
.
Các điều kiện đầu là:
n = 0: r
0
= 1.
n = 1: r
1
= 2.

BÀI TẬP CHƯƠNG II

Bài 14
Chứng minh rằng trong một đơn đồ thị luôn có ít nhất 02 đỉnh có cùng bậc.

Giải

Trong đồ thị đơn, số bậc tối đa cung

aaaa
trong đó các điều kiện đầu là: 7
0
=a ,
4
1
−=a
,
8
2
=a
.

Giải Phương trình đặc trưng 0)6)(1(0652
223
=−−−⇔=+−− xxxxxx
Các nghiệm của phương trình đặc trưng:
⎪
⎩
⎪
⎨
⎧
=
−=
=
3
2

⎧
−=
=
=
⇒
⎪
⎩
⎪
⎨
⎧
++=
+−=−
++=
1
3
5
948
324
7
3
2
1
321
321
321
α
α
α
ααα
ααα

SV
Vậy có 493 SV không học môn nào trong 03 môn: Pascal, Fortran và C.

Bài 18:
Hãy tìm số đỉnh, số cạnh, số bậc của mỗi đỉnh và xác định các đỉnh cô lập, đỉnh treo, ma
trận liền kề, ma trận liên thuộc trong mỗi đồ thị vô hướng sau:

Giải

Câu 18.1. Số đỉnh: 8
Số cạnh: 11
Đỉnh cô lập: D
Đỉnh treo: không có

Tên đỉnh a b C d e g h i
Bậc của định 3 2 4 0 5 3 2 3

Ma trận liền kề:
⎟
⎟
⎟
⎟
⎟
⎟

Bai tap toan roi rac co giai

BT Toan roi rac
7
Ma trận liên thuộc:
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜

⎨
⎧
=
=
=
=
),(
),(
),(
),(
4
3
2
1
ebe
iae
eae
cae

⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
=
=
=


Câu 18.2.
Số đỉnh: 5
Số cạnh: 12
Đỉnh cô lập: không có
Đỉnh treo: không có

Tên đỉnh a b c d e
Bậc của định 6 5 5 5 3

Ma trận liền kề:
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜

⎜
⎝
⎛
100000110000
111101000000
011110000000
000001101110
000000011111
121110987654321
e
d
c
b
a
eeeeeeeeeeee

trong đó:
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
=
=
=
),(
),(

cce
dbe
ebe
eae

⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
=
=
=
),(
),(
),(
),(
12
11
10
9
ede
dce
dce
dce

a

⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
0111
1001
1001
1110
.

Giải

Dựa vào ma trận liền kề của hai đơn đồ thị ta có thể vẽ lại các đồ thị bằng hình vẽ: Theo hình vẽ của hai đơn đồ thị ta thấy chúng không có cùng số cạnh, một bên có 4 cạnh và một
bên có 5 cạnh. Vậy hai đồ thị có ma trận liền kề đã cho ở trên không đẳng cấu.
Bài toán này có thể không cần vẽ hình lại cũng được, từ ma trận kề ta cũng có thể dễ dàng xác
định được số cạnh của mỗi đồ thị lần lượt là 4 v
à 5. Do vậy chúng không thể đẳng cấu.

u
3
u
4
u
5
u
6

Đồ thị thứ hai v
5
v
6
v
3
v
2
v
1
v
4
U
1
U
2

U
3
U
4

v
2

v
4

v
3

v
5

v
6

Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai

BT Toan roi rac
9
Số bậc của mỗi đỉnh
3 4 4 3 5 5

Chính vì vậy, hai đồ
thị trên là đẳng cấu.
b. Hình 02.


1
v
2
v
4
v
6

Bậc vào: deg
-
(X) 1 2 1 2 2 1
Bậc ra: deg
+
(X) 2 1 2 1 1 2

Vì vậy, hai đồ thị có hướng ở trên là đẳng cấu với nhau.

Bài 21: (3.1)
Cho G là đồ thị có v đỉnh và e cạnh, còn m và M tương ứng là bậc nhỏ nhất và lớn nhất các
đỉnh của G. Chứng tỏ rằng:
2e
mM
v
≤≤

Giải

Vì m và M tương ứng là bậc nhỏ nhất và lớn nhất các đỉnh của G, do đó ta dễ dàng có được:

1

2
.2.
2.
evm
e
vm e vM m M
evM
v
≥
⎧
⇔⇔≤≤⇔≤≤
⎨
≤
⎩
(đpcm)

Bài 22: (3.2)
Chứng minh rằng nếu G là đơn đồ thị phân đôi có v đỉnh và e cạnh, khi đó chứng minh bất
đẳng thức sau đây:
2
(1)
4
v
e ≤Giải

u
1

2
lần lượt là số đỉnh của mỗi phần (n
1
+ n
2
= v). Vì là đơn đồ thị phân đôi nên số cạnh
nhiều nhất khi nó là đơn đồ thị phân đôi đủ, tức là:
12
,nn
K
.
Khi đó, số cạnh nhiều nhất sẽ là:
12 12
(2)nnn enn=× ⇔≤
.
Ta dễ dàng có được:
22 22 2
12 1 122 1 122 12
()0 2 0 2 4nn n nnn n nnn nn− ≥⇔− +≥⇔+ +≥

22
(2)
12
12
()
44
nn v
nn e e
+
⇔≥≥⎯⎯→≥

⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠Giải


h.b
A
B
C
D
E
h.c
Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai

BT Toan roi rac
11
0111 11
1011 11
1101 11
.:
1110 11

1111 01
1111 10
n
aK
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟

1010 01
0101 01
.:
0 0 1 0 0 1

1 0 0 0 0 1
1111 10
n
cW
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠

,
0 0 1 1

0 0 1 1
.:
1 1 0 0

1 1 0 0
m

647 48Bài 25: (3.8)
Hai đồ thị với ma trận liền kề sau đây có đẳng cấu với nhau không?
0101
1001
(.1)
0001
1110
h
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠

0111
1001
(.2)
1001
1110
h
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠

h
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠Giải

Thưa thầy, theo em nghĩ thì đây là hai ma trận
liên thuộc chứ không phải là hai ma trận liền kề.
Và nếu là hai ma trận liên thuộc thì chúng đẳng cấu với nhau vì:
Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai

BT Toan roi rac
1212345
1
2
3
4
eeeee
v11000
(.1')
v10101

v
v
v
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠ Xét ánh xạ f từ V
1
lên V
2
sao cho:
''
11 2 2
''
33 44
() _&_() ;
() _&_() ;
f vv fvv
f vv fvv
⎧
==
⎪
⎨

vv
hh
vv
vv
vv
⎛⎞⎛⎞
⎜⎟⎜⎟
⎜⎟⎜⎟
⎜⎟⎜⎟
⇒
⎜⎟⎜⎟
⎜⎟⎜⎟
⎜⎟⎜⎟
⎝⎠⎝⎠Bài 27: (3.10)
Các cặp đồ thị sau có đẳng cấu với nhau không?

Giải

Bài này hoàn toàn giống bài số 20 đã giải ở trên.

Bài 28: (3.11)
Cho V = {2, 3, 4, 5, 6, 7, 8} và E là tập hợp các cặp phần tử (u, v) của V sao cho u < v và u với
v là các số nguyên tố cùng nhau. Hãy vẽ đồ thị có hướng
()
,GVE= .
Tìm số đường đi phân biệt độ dài 3 từ đỉnh 2 tới đỉnh 8.



Hãy tìm số đường đi độ dài n giữa hai đỉnh liền kề (t.ư không liền kề) tùy ý trong K
3,3
với
mỗi giá trị của n sau:
a. n = 2, b. n = 3, c. n = 4, d. n = 5.

Giải

Hai đỉnh liền kề phải ở 2 phần khác nhau. Một cạnh chỉ có thể nối từ 1 đỉnh ở phần (I) đến 1 đỉnh
ở phần (II) và ngược lại. Gọi m là số đường đi giữa 2 đỉnh bất kỳ trong K
3,3
có độ dài n.
TH1: n chẵn.
Nếu n chẵn thì đỉnh đầu và đỉnh cuối của đường đi phải ở cùng 1 phần, do vậy chúng không thể

5
6
4
(II) (I)
Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai

BT Toan roi rac
14
Bài tập chương III

Câu 1: Cho G là đồ thị có v đỉnh và e cạnh, còn M, m tương ứng là bậc lớn nhất và nhỏ nhất của các đỉnh
của G. Chứng tỏ rằng:
m ≤
v
e2
≤ M.
Câu 2: Chứng minh rằng nếu G là đơn đồ thị phân đôi có v đỉnh và e cạnh, khi đó
e ≤ v
2
/4.

Câu 4: Hãy vẽ các đồ thị vô hướng được biểu diễn bởi ma trận liền kề sau:
a)
123
204
340
⎛
⎝
⎜

⎛
⎝
⎜
⎜
⎜
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
⎟
⎟
⎟
. Câu 6: Tìm ma trận liền kề cho các đồ thị sau:
a) K
n
b) C
n
c) W
n
d) K
m,n
e) Q
n

⎜
⎜
⎜
⎜
⎝
⎛
0111
1001
1001
1110
.

Câu 9: Hai đơn đồ thị với ma trận liên thuộc sau đây có là đẳng cấu không?
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
01110
11000
10101
b) Câu 11: Cho V={2,3,4,5,6,7,8} và E là tập hợp các cặp phần tử (u,v) của V sao cho u<v và u,v nguyên tố
cùng nhau. Hãy vẽ đồ thị có hướng G=(V,E). Tìm số các đường đi phân biệt độ dài 3 từ đỉnh 2 tới đỉnh 8.

Câu 12: Hãy tìm số đường đi độ dài n giữa hai đỉnh liền kề (t.ư. không liền kề) tùy ý trong K
3,3
với mỗi
giá trị của n sau:

5
v
4

u
1

u
2

u
3

u
4

u
5

u
6

v
1

v
2

v
4

i
i
i
vvm
vvM
=
=
∑
∑
⎧
≥
⎪
⎨
≤
⎪
⎩2.
2
.2.
2.
evm
e
vm e vM m M
evM
v
≥
⎧
⇔⇔≤≤⇔≤≤

2
12
12
()
.
4
dd
dd e
+
≥≥
(đã chứng minh xong).

Câu 4:

a) b)

c) Câu 6:
0111 11
1011 11
1101 11
) :
1110 11

1111 01
1111 10
naK
⎡⎤
⎢⎥
⎢⎥
⎢⎥
⎢⎥

0 1 0 1 0 0
) :
0010 00

0000 01
1000 10
nbC
⎡⎤
⎢⎥
⎢⎥
⎢⎥
⎢⎥
⎢⎥
⎢⎥
⎢⎥
⎢⎥
⎢⎥
⎣⎦ n
0100 11
1010 01
0101 01
) W :
0010 01


1 1 0 0

1 1 0 0
m
n
m
n
d
⎡ ⎤
⎢ ⎥
⎧
⎪
⎢ ⎥
⎨
⎢ ⎥
⎪
⎢ ⎥
⎩
⎢ ⎥
⎢ ⎥
⎧
⎢ ⎥
⎪
⎢ ⎥
⎨
⎢ ⎥
⎪
⎢ ⎥
⎩
⎣ ⎦

1
e
2
e
2
e
3
e
5
e
5
e
3
e
4 e
4
e
1 G

4Hai đồ thị G
1
và G
2
hoàn toàn giống nhau nên chúng đẳng cấu với nhau
V
1
V
2

V
3
V
4

U
1
U
2

U
3
U
4
V
1
V

2
, u
3
, u
4
, u
5
, u
6
và
của G’ theo thứ tự các đỉnh v
2
, v
3
, v
6
, v
5
, v
1
, v
4
là như nhau và bằng:
010011
101011
010111
001011
111101
111110
⎡ ⎤


Đồ thị G2 v
3
v
2
v
5
v
4
v
1
v
6

Bậc vào: 1 2 1 2 2 1
Bậc ra: 2 1 2 1 1 2

Vì vậy, hai đồ thị G
1
,G
2
có hướng cho ở trên là đẳng cấu với nhau.
Câu 12:


,
(II) (I)
1 4
3
2
5
6
Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai

BT Toan roi rac
22
o Hai đỉnh không liền kề, n chẵn: b = 3
n-1
,
o Hai đỉnh không liền kề, n lẽ: b = 0. Áp dụng cho các trường hợp:

Số cạnh n = 2 n = 3 n = 4 n = 5
Liền kề 0 9 0 81
Không liền
kề
3 0 27 0

BÀI TẬP CHƯƠNG 4
ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON
Vì mọi đỉnh của C
n
đều có bậc là 2 nên C
n
luôn là đồ thị Euler.
c.
W
n
:
Chủ có một đỉnh có bậc là n – 1, còn lại các đỉnh khác đều có bậc là 3, do vậy đây không thể là đồ
thị Euler.
d.
Q
n
:
Vì mọi đỉnh đều có bậc là n, do vậy để Q
n
là đồ thị Euler thì n chẵn.

Bài 2:

Với các giá trị nào của m và n thì đồ thị phân đôi đầy đủ K
m,n
có:
a. Chu trình Euler.
b. Đường đi Euler.

Giải

a. Vì các đỉnh của đồ thị phân đôi đủ K

nm
n
mnm nm
nm
m
+
⎧
≥
⎪
⎪
⇔≤≤⇔=
⎨
+
⎪
≥
⎪
⎩

Câu 4:
Chứng minh rằng đồ thị lập phương Q
n
là một đồ thị Hamilton. Vẽ cây liệt kê tất cả các chu trình
Hamilton của đồ thị lập phương Q
3
.

Câu 5:
Trong một cuộc họp có 15 người mỗi ngày ngồi với nhau quanh một bàn tròn một lần. Hỏi có bao
nhiêu cách sắp xếp sao cho mỗi lần ngồi họp, mỗi người có hai người bên cạnh là bạn mới, và sắp
xếp như thế nào ?

3
4 5
6
7
Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai

BT Toan roi rac
24 Giải
Giả sử chúng ta xem mỗi một phòng là một đỉnh của đồ thị G và mỗi một cửa thông giữa các phòng là
một cạnh của đồ thị G thì theo yêu cầu của bài toán (qua tất cả các cửa và mỗi cửa chỉ qua một lần) ta
phải đi tìm đường đi Euler của đồ thị cho ở trên.
Sau đây là đường đi để tìm báu vật: (xuất phát từ phòng số 6, kết thúc ở phòng 18 là cửa cuối cùng)
6 Æ 2 Æ 1Æ 4 Æ 3 Æ 7 Æ 11 Æ 12 Æ 8 Æ 13 Æ 12 Æ 17 Æ 16 Æ 20 Æ 21 Æ 17 Æ 18 Æ 13 Æ 14
Æ 9 Æ 5 Æ 4 Æ 2 Æ 5 Æ 6 Æ 10 Æ 15 Æ 14 Æ 19 Æ 18.
Câu 8:
Đồ thị cho trong hình sau gọi là đồ thị Peterson P.
a) Tìm một đường đi Hamilton trong P.
b) Chứng minh rằng P \ {v}, với v là một đỉnh bất kỳ của P, là một đồ thị Hamilton.
d

c
1
9
12
8
10
3
11
5
4
67
2
Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai

BT Toan roi rac
25
Giải
Gọi V
o
(G) là tập tất cả các đỉnh bậc lẻ trong G.
V
o
(G)= {2, 4, 8, 11}
P
1
= { (2,4), (8,11) }
P

Giải

Đồ thị G có đường đi Hamilton từ s tới r nhưng không có chu trình Hamilton thì ta cần tìm một đường đi
từ s tới r qua tất cả các đỉnh còn lại nhưng không trở về đỉnh xuất phát .
Đường đi Hamilton là :
s Æ a Æ b Æ c Æ e Æ f Æ g Æ d Æ h Æ r
Từ đồ thị ta nhận thấy sẽ không có bất kỳ chu trình Hamilton nào xuất phát từ s và lại trở về s.
Câu 11:
Cho thí dụ về:
a) Đồ thị có một chu trình vừa là chu trình Euler vừa là chu trình Hamilton;
b) Đồ thị có một chu trình Euler và một chu trình Hamilton, nhưng hai chu trình đó không trùng
nhau;
c) Đồ thị có 6 đỉnh, là đồ thị Hamilton, nhưng không phải là đồ thị Euler;
d) Đồ thị có 6 đỉnh, là đồ thị Euler, nhưng không phải là đồ thị Hamilton.
Giải
a) b) a
c
b
s
r
f