http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập

37

CHƯƠNG III
ðỒ THỊ

Lý thuyết ñồ thị là một ngành khoa học ñược phát triển từ lâu nhưng lại có nhiều
ứng dụng hiện ñại. Những ý tưởng cơ bản của nó ñược ñưa ra từ thế kỷ 18 bởi nhà toán
học Thụy Sĩ tên là Leonhard Euler. Ông ñã dùng ñồ thị ñể giải quyết bài toán 7 chiếc
cầu Konigsberg nổi tiếng.
ðồ thị cũng ñược dùng ñể giải các bài toán trong nhiều lĩnh vực khác nhau. Thí
dụ, dùng ñồ thị ñể xác ñịnh xem có thực hiện một mạch ñiện trên một bảng ñiện phẳng
ñược không. Chúng ta cũng có thể phân biệt hai hợp chất hóa học có cùng công thức
phân tử nhưng có cấu trúc khác nhau nhờ ñồ thị. Chúng ta cũng có thể xác ñịnh xem hai
máy tính có ñược nối với nhau bằng một ñường truyền thông hay không nếu dùng mô
hình ñồ thị mạng máy tính. ðồ 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. Chúng ta cũng có thể dùng ñồ thị ñể lập lịch thi và phân chia
kênh cho các ñài truyền hình.
3.1. ðỊNH NGHĨA VÀ THÍ DỤ.
ðồ thị là một cấu trúc rời rạc gồm các ñỉnh và các cạnh (vô hướng hoặc có
hướng) nối các ñỉnh ñó. Người ta phân loại ñồ thị tùy theo ñặc tính và số các cạnh nối
các cặp ñỉnh của ñồ thị. Nhiều bài toán thuộc những lĩnh vực rất khác nhau có thể giải
ñược bằng mô hình ñồ thị. Chẳng hạn người ta có thể dùng ñồ thị ñể biểu diễn sự cạnh
tranh các loài trong một môi trường sinh thái, dùng ñồ thị ñể biểu diễn ai có ảnh hưởng
lên ai trong một tổ chức nào ñó, và cũng có thể dùng ñồ thị ñể biểu diễn các kết cục của
cuộc thi ñấu thể thao. Chúng ta cũng có thể dùng ñồ thị ñể giải các bài toán như bài toán

Một giả ñồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử
của nó gọi là các ñỉnh và một họ E mà các phần tử của nó gọi là các cạnh, ñó là các cặp
không có thứ tự của các ñỉnh (không nhất thiết là phân biệt).
Với v∈V, nếu (v,v)∈E thì ta nói có một khuyên tại ñỉnh v.
Tóm lại, giả ñồ thị là loại ñồ thị vô hướng tổng quát nhất vì nó có thể chứa các
khuyên và các cạnh bội. ða ñồ thị là loại ñồ thị vô hướng có thể chứa cạnh bội nhưng
không thể có các khuyên, còn ñơn ñồ thị là loại ñồ thị vô hướng không chứa cạnh bội
hoặc các khuyên.
Thí dụ 1: ðơn ñồ thị
Giả ñồ thị
3.1.4. ðịnh nghĩa:
Một ñồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các
phần tử của nó gọi là các ñỉnh và một tập E mà các phần tử của nó gọi là các cung, ñó là
các cặp có thứ tự của các phần tử thuộc V.
3.1.5. ðịnh nghĩa:
Một ña ñồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà
các phần tử của nó gọi là các ñỉnh và một họ E mà các phần tử của nó gọi là các cung,
ñó là các cặp có thứ tự của các phần tử thuộc V.
ðồ thị vô hướng nhận ñược từ ñồ thị có hướng G bằng cách xoá bỏ các chiều mũi
tên trên các cung ñược gọi là ñồ thị vô hướng nền của G.
Thí dụ 2:

v
3

v
4

v
5

v
6

v
6

v
7

v
3

v
4

v
5

v
6


trong một hệ sinh thái có thể mô hình hóa bằng ñồ thị “lấn tổ”. Mỗi loài ñược biểu diễn
bằng một ñỉnh. Một cạnh vô hướng nối hai ñỉnh nếu hai loài ñược biểu diễn bằng các
ñỉnh này là cạnh tranh với nhau.
2) ðồ thị ảnh hưởng. Khi nghiên cứu tính cách của một nhóm nguời, ta thấy một số
người có thể có ảnh hưởng lên suy nghĩ của những người khác. ðồ thị có hướng ñược
gọi là ñồ thị ảnh hưởng có thể dùng ñể mô hình bài toán này. Mỗi người của nhóm ñược
biểu diễn bằng một ñỉnh. Khi một người ñược biểu diễn bằng ñỉnh a có ảnh hưởng lên
người ñược biểu diễn bằng ñỉnh b thì có một cung nối từ ñỉnh a ñến ñỉnh b.
3) Thi ñấu vòng tròn. Một cuộc thi ñấu thể thao trong ñó mỗi ñội ñấu với mỗi ñội khác
ñúng một lần gọi là ñấu vòng tròn. Cuộc thi ñấu như thế có thể ñược mô hình bằng một
ñồ thị có hướng trong ñó mỗi ñội là một ñỉnh. Một cung ñi từ ñỉnh a ñến ñỉnh b nếu ñội
a thắng ñội b.
4) Các chương trình máy tính có thể thi hành nhanh hơn bằng cách thi hành ñồng thời
một số câu lệnh nào ñó. ðiều quan trọng là không ñược thực hiện một câu lệnh ñòi hỏi
kết quả của câu lệnh khác chưa ñược thực hiện. Sự phụ thuộc của các câu lệnh vào các
câu lệnh trước có thể biểu diễn bằng một ñồ thị có hướng. Mỗi câu lệnh ñược biểu diễn
bằng một ñỉnh và có một cung từ một ñỉnh tới một ñỉnh khác nếu câu lệnh ñược biểu
diễn bằng ñỉnh thứ hai không thể thực hiện ñược trước khi câu lệnh ñược biểu diễn bằng
ñỉnh thứ nhất ñược thực hiện. ðồ thị này ñược gọi là ñồ thị có ưu tiên trước sau.
3.2. BẬC CỦA ðỈNH.
3.2.1. ðịnh nghĩa:
Hai ñỉnh u và v trong ñồ thị (vô hướng) G=(V,E) ñược gọi là liền
kề nếu (u,v)∈E. Nếu e = (u,v) thì e gọi là cạnh liên thuộc với các ñỉnh u và v. Cạnh e
cũng ñược gọi là cạnh nối các ñỉnh u và v. Các ñỉnh u và v gọi là các ñiểm ñầu mút của
cạnh e.
3.2.2. ðịnh nghĩa:
Bậc của ñỉnh v trong ñồ thị G=(V,E), ký hiệu deg(v), là số các cạnh
liên thuộc với nó, riêng khuyên tại một ñỉnh ñược tính hai lần cho bậc của nó.
ðỉnh v gọi là ñỉnh treo nếu deg(v)=1 và gọi là ñỉnh cô lập nếu deg(v)=0.
Thí dụ 4:


v
3

v
4

v
5

v
6

v
7

http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập

40

3.2.3. Mệnh ñề:
Cho ñồ thị G = (V, E). Khi ñó
2|E| =
∑
∈Vv
v)deg(
.

| là một số chẵn.
3.2.5. Mệnh ñề:
Trong một ñơn ñồ thị, luôn tồn tại hai ñỉnh có cùng bậc.
Chứng minh: Xét ñơn ñồ thị G=(V,E) có |V|=n. Khi ñó phát biểu trên ñược ñưa về bài
toán: trong một phòng họp có n người, bao giờ cũng tìm ñược 2 người có số người quen
trong số những người dự họp là như nhau (xem Thí dụ 6 của 2.2.3).
3.2.6. ðịnh nghĩa:
ðỉnh u ñược gọi là nối tới v hay v ñược gọi là ñược nối từ u trong
ñồ thị có hướng G nếu (u,v) là một cung của G. ðỉnh u gọi là ñỉnh ñầu và ñỉnh v gọi là
ñỉnh cuối của cung này.
3.2.7. ðịnh nghĩa:
Bậc vào (t.ư. bậc ra) của ñỉnh v trong ñồ thị có hướng G, ký hiệu
deg
t
(v) (t.ư. deg
o
(v)), là số các cung có ñỉnh cuối là v.
Thí dụ 5: deg
t
(v
1
) = 2, deg
o
(v

t
(v
5
) = 1, deg
o
(v
5
) = 0,
deg
t
(v
6
) = 0, deg
o
(v
6
) = 0.
ðỉnh có bậc vào và bậc ra cùng bằng 0 gọi là ñỉnh cô lập. ðỉnh có bậc vào bằng 1
và bậc ra bằng 0 gọi là ñỉnh treo, cung có ñỉnh cuối là ñỉnh treo gọi là cung treo.
3.2.8. Mệnh ñề:
Cho G =(V, E) là một ñồ thị có hướng. Khi ñó

v
1

v
2

v
3

n
, là ñơn ñồ thị mà hai ñỉnh
phân biệt bất kỳ của nó luôn liền kề. Như vậy, K
n
có
2
)1(
−
nn
cạnh và mỗi ñỉnh của K
n

có bậc là n−1.
Thí dụ 6: K
1
K
2

K
3
K
4
K
5

3.3.2. ðồ thị vòng:
ðơn ñồ thị n ñỉnh v
C
3
C
4
C
5
C
6

3.3.3. ðồ thị bánh xe:
Từ ñồ thị vòng C
n
, thêm vào ñỉnh v
n+1
và các cạnh (v
n+1
,v
1
),
(v
n+1
,v
2
), , (v
n+1
,v
n
), ta nhận ñược ñơn ñồ thị gọi là ñồ thị bánh xe, ký hiệu là W

Q
n
có bậc là n và số cạnh của Q
n
là n.2
n-1
(từ công thức 2|E| =
∑
∈Vv
v)deg(
).
v
1

v
1

v
2

v
1

v
2

v
3

v

2

v
3

v
1

v
2

v
4

v
3

v
1

v
5

v
2

v
4

v

2

v
4

v
3

v
1

v
5

v
2

v
4

v
3

v
6

v
5

v

Thí dụ 9: Q
1

Q
2
Q
3
3.3.5. ðồ thị phân ñôi (ñồ thị hai phe):
ðơn ñồ thị G=(V,E) sao cho V=V
1
∪V
2
,
V
1
∩V
2
=∅, V
1
≠∅, V
2

. Như vậy K
m,n
có m.n cạnh, các ñỉnh của V
1
có bậc n và các ñỉnh của V
2

có bậc m.
Thí dụ 10:

K
2,4
K
3,3

3.3.6. Một vài ứng dụng của các ñồ thị ñặc biệt:

1) Các mạng cục bộ (LAN): Một số mạng cục bộ dùng cấu trúc hình sao, trong ñó tất
cả các thiết bị ñược nối với thiết bị ñiều khiển trung tâm. Mạng cục bộ kiểu này có thể
biểu diễn bằng một ñồ thị phân ñôi ñầy ñủ K
1,n
. Các thông báo gửi từ thiết bị này tới
thiết bị khác ñều phải qua thiết bị ñiều khiển trung tâm.
Mạng cục bộ cũng có thể có cấu trúc vòng tròn, trong ñó mỗi thiết bị nối với
ñúng hai thiết bị khác. Mạng cục bộ kiểu này có thể biểu diễn bằng một ñồ thị vòng C
n
.

1

v
2

v
3

v
4

v
5

v
6

v
1

v
2

v
3

v
4

v

9

v
1

v
2

v
8

v
7

v
6

v
5

v
4

v
3

v
9

v

Cuối cùng, một số mạng cục bộ dùng cấu trúc hỗn hợp của hai cấu trúc trên. Các
thông báo ñược truyền vòng quanh theo vòng tròn hoặc có thể qua thiết bị trung tâm. Sự
dư thừa này có thể làm cho mạng ñáng tin cậy hơn. Mạng cục bộ kiểu này có thể biểu
diễn bằng một ñồ thị bánh xe W
n
.
2) Xử lý song song: Các thuật toán ñể giải các bài toán ñược thiết kế ñể thực hiện một
phép toán tại mỗi thời ñiểm là thuật toán nối tiếp. Tuy nhiên, nhiều bài toán với số
lượng tính toán rất lớn như bài toán mô phỏng thời tiết, tạo hình trong y học hay phân
tích mật mã không thể giải ñược trong một khoảng thời gian hợp lý nếu dùng thuật toán
nối tiếp ngay cả khi dùng các siêu máy tính. Ngoài ra, do những giới hạn về mặt vật lý
ñối với tốc ñộ thực hiện các phép toán cơ sở, nên thường gặp các bài toán không thể giải
trong khoảng thời gian hợp lý bằng các thao tác nối tiếp. Vì vậy, người ta phải nghĩ ñến
kiểu xử lý song song.
Khi xử lý song song, người ta dùng các máy tính có nhiều bộ xử lý riêng biệt,
mỗi bộ xử lý có bộ nhớ riêng, nhờ ñó có thể khắc phục ñược những hạn chế của các máy
nối tiếp. Các thuật toán song song phân chia bài toán chính thành một số bài toán con
sao cho có thể giải ñồng thời ñược. Do vậy, bằng các thuật toán song song và nhờ việc
sử dụng các máy tính có bộ ña xử lý, người ta hy vọng có thể giải nhanh các bài toán
phức tạp. Trong thuật toán song song có một dãy các chỉ thị theo dõi việc thực hiện
thuật toán, gửi các bài toán con tới các bộ xử lý khác nhau, chuyển các thông tin vào,
thông tin ra tới các bộ xử lý thích hợp.
Khi dùng cách xử lý song song, mỗi bộ xử lý có thể cần các thông tin ra của các
bộ xử lý khác. Do ñó chúng cần phải ñược kết nối với nhau. Người ta có thể dùng loại
ñồ thị thích hợp ñể biểu diễn mạng kết nối các bộ xử lý trong một máy tính có nhiều bộ
xử lý. Kiểu mạng kết nối dùng ñể thực hiện một thuật toán song song cụ thể phụ thuộc
vào những yêu cầu với việc trao ñổi dữ liệu giữa các bộ xử lý, phụ thuộc vào tốc ñộ
mong muốn và tất nhiên vào phần cứng hiện có.
Mạng kết nối các bộ xử lý ñơn giản nhất và cũng ñắt nhất là có các liên kết hai
chiều giữa mỗi cặp bộ xử lý. Các mạng này có thể mô hình bằng ñồ thị ñầy ñủ K


http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập

44

ñược gán nhãn P(i,j), 0 ≤ i, j ≤ m−1. Các kết nối hai chiều sẽ nối bộ xử lý P(i,j) với bốn
bộ xử lý bên cạnh, tức là với P(i,j±1) và P(i±1,j) chừng nào các bộ xử lý còn ở trong
lưới.
Mạng kết nối quan trọng nhất là mạng kiểu siêu khối. Với các mạng loại này số
các bộ xử lý là luỹ thừa của 2, n=2
m
. Các bộ xử lý ñược gán nhãn là P
0
, P
1
, , P
n-1
. Mỗi

là ma trận
A=
),()(
,1
ZnMa
njiij
∈
≤≤
,
trong ñó a
ij
là số cạnh hoặc cung nối từ v
i
tới v
j
.
Như vậy, ma trận liền kề của một ñồ thị vô hướng là ma trận ñối xứng, nghĩa là
jiij
aa
=
, trong khi ma trận liền kề của một ñồ thị có hướng không có tính ñối xứng.
Thí dụ 11: Ma trận liền kề với thứ tự các ñỉnh v
1
, v
2
, v
3
, v
4
là:

P(2,0)
P(2,1)
P(2,2)
P(2,3)
P(3,0)
P(3,1)
P(3,2)
P(3,3)
P
1

P
2

P
3

P
4

P
5

P
6

P
0

P

5
là:

















01011
10200
01001
01210
110113.4.2. ðịnh nghĩa:
Cho ñồ thị vô hướng G=(V,E), v
1
, v

j
không nối với ñỉnh v
i
.
Thí dụ 12: Ma trận liên thuộc theo thứ tự các ñỉnh v
1
, v
2
, v
3
, v
4
, v
5
và các cạnh e
1
, e
2
, e
3
,
e
4
, e
5
, e
6
là:



=(V
2
,E
2
) ñược gọi là ñẳng cấu nếu
tồn tại một song ánh f từ V
1
lên V
2
sao cho các ñỉnh u và v là liền kề trong G
1
khi và chỉ
khi f(u) và f(v) là liền kề trong G
2
với mọi u và v trong V
1
. Ánh xạ f như thế gọi là một
phép ñẳng cấu.
Thông thường, ñể chứng tỏ hai ñơn ñồ thị là không ñẳng cấu, người ta chỉ ra
chúng không có chung một tính chất mà các ñơn ñồ thị ñẳng cấu cần phải có. Tính chất
như thế gọi là một bất biến ñối với phép ñẳng cấu của các ñơn ñồ thị.
Thí dụ 13: 1) Hai ñơn ñồ thị G
1
và G
2
sau là ñẳng cấu qua phép ñẳng cấu f: a
a
x,
b
a

4

v
3

v
1

v
2

v
3

v
4

v
5

e
1

e
2

e
3

e

46

2) Hai ñồ thị G
1
và G
2
sau ñều có 5 ñỉnh và 6 cạnh nhưng không ñẳng cấu vì trong G
1

có một ñỉnh bậc 4 mà trong G
2
không có ñỉnh bậc 4 nào. 3) Hai ñồ thị G
1
và G
2
sau ñều có 7 ñỉnh, 10 cạnh, cùng có một ñỉnh bậc 4, bốn ñỉnh
bậc 3 và hai ñỉnh bậc 2. Tuy nhiên G
1
và G
2
là không ñẳng cấu vì hai ñỉnh bậc 2 của G

là ñẳng cấu vì hai ma trận liền kề của G
1
theo thứ tự các ñỉnh
u
1
, u
2
, u
3
, u
4
, u
5
, u
6
và của G
2
theo thứ tự các ñỉnh v
6
, v
3
, v
4
, v
5
, v
1
, v
2
là như nhau và

3.5.1. ðịnh nghĩa:
Cho hai ñồ thị G
1
=(V
1
,E
1
) và G
2
=(V
2
,E
2
). Ta nói G
2
là ñồ thị con
của G
1
nếu V
2
⊂ V
1
và E
2
⊂ E
1
. Trong trường hợp V
1
=V
2

u

v

x

y

w

t

z

u
1

v
3

v
1

u
2

u
4

u
G G
1
G
2
G
3 G
4
G
5

G
1
, G
2
, G
3
và G
4
là các ñồ thị con của G, trong ñó G
2
và G
4

.
Thí dụ 15:

G
1
G
2
G
1
∪G
2

3.5.3. ðịnh nghĩa:
ðơn ñồ thị G’=(V,E’) ñược gọi là ñồ thị bù của ñơn ñồ thị G=(V,E)
nếu G và G’ không có cạnh chung nào (E ∩ E’=∅) và G ∪ G’là ñồ thị ñầy ñủ.
Dễ thấy rằng nếu G’ là bù của G thì G cũng là bù của G’. Khi ñó ta nói hai ñồ thị
là bù nhau.
Thí dụ 16:

G’ G G
1
’ G
1


=(x
n-1
,x
n
),
với x
0
=u và x
n
=v. Khi ñồ thị không có cạnh (hoặc cung) bội, ta ký hiệu ñường ñi này
a

e

d

c

b

a

c

b

a

d


b

x

y

z

u

v

u

x

y

z

w

x

y

z

u


x

v

u

z

y

http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập

48

bằng dãy các ñỉnh x
0
, x
1
, , x
n
. ðường ñi ñược gọi là chu trình nếu nó bắt ñầu và kết
thúc tại cùng một ñỉnh. ðường ñi hoặc chu trình gọi là ñơn nếu nó không chứa cùng một
cạnh (hoặc cung) quá một lần. Một ñường ñi hoặc chu trình không ñi qua ñỉnh nào quá
một lần (trừ ñỉnh ñầu và ñỉnh cuối của chu trình là trùng nhau) ñược gọi là ñường ñi
hoặc chu trình sơ cấp. Rõ ràng rằng một ñường ñi (t.ư. chu trình) sơ cấp là ñường ñi (t.ư.
chu trình) ñơn.
Thí dụ 17:
x

y

z

v

w

u

x

t

u

y

w

z

v

a


t

http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập

49

Trong ñồ thị trên, các ñỉnh cắt là v, w, s và các cầu là (x,v), (w,s).

3.6.4. Mệnh ñề:
Giữa mọi cặp ñỉnh phân biệt của một ñồ thị liên thông luôn có ñường
ñi sơ cấp.
Chứng minh: Giả sử u và v là hai ñỉnh phân biệt của một ñồ thị liên thông G. Vì G liên
thông nên có ít nhất một ñường ñi giữa u và v. Gọi x
0
, x
1
, , x
n
, với x
0
=u và x
n
=v, là dãy
các ñỉnh của ñường ñi có ñộ dài ngắn nhất. ðây chính là ñường ñi sơ cấp cần tìm. Thật
vậy, giả sử nó không là ñường ñi ñơn, khi ñó x
i
=x

chứa ñỉnh v và có n
2
ñỉnh. Vì G
1
, G
2
là hai trong số các thành phần
liên thông của G nên n
1
+n
2
≤ n. ta có:
deg(u)+deg(v) ≤ (n
1
−1)+(n
2
− 1) = n
1
+n
2
−2 ≤ n−2 <n.
ðiều mâu thuẫn ở trên dẫn ñến kết luận là ñồ thị G phải liên thông.
3.6.6. Hệ quả:
ðơn ñồ thị mà bậc của mỗi ñỉnh của nó không nhỏ hơn một nửa số ñỉnh
là ñồ thị liên thông.
3.6.7. Mệnh ñề:
Nếu một ñồ thị có ñúng hai ñỉnh bậc lẻ thì hai ñỉnh này phải liên
thông, tức là có một ñường ñi nối chúng.
Chứng minh: Cho G=(V,E) là ñồ thị thị có ñúng hai ñỉnh bậc lẻ là u và v. Giả sử u và v
không liên thông với nhau. Khi ñó chúng phải thuộc hai thành phần liên thông nào ñó

2
và v là ñỉnh trong G
3
. Do u, v thuộc hai thành phần liên thông khác nhau, nên trong
G
1
các ñỉnh u, v không liên thông. Nhưng trong G các ñỉnh u, v lại liên thông, nên mọi
ñường ñi nối u, v ñều phải ñi qua ñỉnh x.
http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập

50

ðiều kiện ñủ: Giả sử mọi ñường ñi nối u, v ñều ñi qua ñỉnh x, nên nếu bỏ ñỉnh x và các
cạnh liên thuộc với x thì ñồ thị con G
1
nhận ñược từ G chứa hai ñỉnh u, v không liên
thông. Do ñó G
1
là ñồ thị không liên thông hay ñỉnh x là ñiểm khớp của G.
3.6.9. ðịnh lý:
Cho G là một ñơn ñồ thị có n ñỉnh, m cạnh và k thành phần liên thông.
Khi ñó
2
)1)((
+
−
−

m
1
≤
2
)1)((
+
−
−
knkn
.
Giả sử G
i
và G
j
là hai thành phần liên thông của G’’ với n
i
và n
j
ñỉnh và n
i
≥ n
j
>1 (*).
Nếu ta thay G
i
và G
j
bằng ñồ thị ñầy ñủ với n
i
+1 và n

−
+
ji
jjjj
iiii
nn
nnnn
nnnn
.
Thủ tục này ñược lặp lại khi hai thành phần nào ñó có số ñỉnh thoả (*). Vì vậy m
1
là lớn
nhất (n, k là cố ñịnh) khi ñồ thị gồm k-1 ñỉnh cô lập và một ñồ thị ñầy ñủ với n-k+1
ñỉnh. Từ ñó suy ra bất ñẳng thức cần tìm.
3.6.10. ðịnh nghĩa:
ðồ thị có hướng G ñược gọi là liên thông mạnh nếu với hai ñỉnh
phân biệt bất kỳ u và v của G ñều có ñường ñi từ u tới v và ñường ñi từ v tới u.
ðồ thị có hướng G ñược gọi là liên thông yếu nếu ñồ thị vô hướng nền của nó là
liên thông.
ðồ thị có hướng G ñược gọi là liên thông một chiều nếu với hai ñỉnh phân biệt
bất kỳ u và v của G ñều có ñường ñi từ u tới v hoặc ñường ñi từ v tới u.
Thí dụ 20:

G G’
u

v
ðồ thị G là liên thông mạnh nhưng ñồ thị G’ là liên thông yếu (không có ñường
ñi từ u tới x cũng như từ x tới u).
3.6.11. Mệnh ñề:
Cho G là một ñồ thị (vô hướng hoặc có hướng) với ma trận liền kề A
theo thứ tự các ñỉnh v
1
, v
2
, , v
n
. Khi ñó số các ñường ñi khác nhau ñộ dài r từ v
i
tới v
j

trong ñó r là một số nguyên dương, bằng giá trị của phần tử dòng i cột j của ma trận A
r
.
Chứng minh: Ta chứng minh mệnh ñề bằng quy nạp theo r. Số các ñường ñi khác nhau
ñộ dài 1 từ v
i
tới v
j
là số các cạnh (hoặc cung) từ vi tới v
j
, ñó chính là phần tử dòng i cột
j của ma trận A; nghĩa là, mệnh ñề ñúng khi r=1.
Giả sử mệnh ñề ñúng ñến r; nghĩa là, phần tử dòng i cột j của A

. Theo giả thiết quy nạp b
ik
là số ñường ñi
khác nhau ñộ dài r từ v
i
tới v
k
.
ðường ñi ñộ dài r+1 từ v
i
tới v
j
sẽ ñược tạo nên từ ñường ñi ñộ dài r từ v
i
tới ñỉnh
trung gian v
k
nào ñó và một cạnh (hoặc cung) từ v
k
tới v
j
. Theo quy tắc nhân số các
ñường ñi như thế là tích của số ñường ñi ñộ dài r từ v
i
tới v
k
, tức là b
ik
, và số các cạnh
(hoặc cung) từ v

Trongmột phương án mạng kiểu lưới kết nối n=m
2
bộ xử lý song song, bộ xử lý P(i,j)
ñược kết nối với 4 bộ xử lý (P(i±1) mod m, j), P(i, (j±1) mod m), sao cho các kết nối
bao xung quanh các cạnh của lưới. Hãy vẽ mạng kiểu lưới có 16 bộ xử lý theo phương
án này.
4
44
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)
1 2 3
2 0 4
3 4 0










, b)
1 2 0 1
2 0 3 0
0 3 1 1






.

http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập

52

5.

Nêu ý nghĩa của tổng các phần tử trên một hàng (t.ư. cột) của một ma trận liền kề ñối
với một ñồ thị vô hướng ? ðối với ñồ thị có hướng ?

6.
Tìm ma trận liền kề cho các ñồ thị sau:
a
aa
a)
) )
) K
n
, b) C
n
, c) W















0111
1001
1001
1110
.
9.
Hai ñơn ñồ thị với ma trận liền kề sau ñây có là ñẳng cấu không?










Các ñồ thị G và G’ sau có ñẳng cấu với nhau không?
a)

b)

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.
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:
a)
n=2,
b)
n=3,
c)
n=4,


3

v
5

v
6

u
1

u
2

u
3

u
4

u
5

u
6

v
1

v

Trong một cuộc họp có ñúng hai ñại biểu không quen nhau và mỗi ñại biểu này có
một số lẻ người quen ñến dự. Chứng minh rằng luôn luôn có thể xếp một số ñại biểu
ngồi chen giữa hai ñại biểu nói trên, ñể mỗi người ngồi giữa hai người mà anh ta quen.
17.
Một thành phố có n (n ≥ 2) nút giao thông và hai nút giao thông bất kỳ ñều có số
ñầu mối ñường ngầm tới một trong các nút giao thông này ñều không nhỏ hơn n. Chứng
minh rằng từ một nút giao thông tuỳ ý ta có thể ñi ñến một nút giao thông bất kỳ khác
bằng ñường ngầm.