BÀI TẬP TOÁN RỜI RẠC
***
CHƯƠNG 2:
ĐỒ THỊ
ĐỒ THỊ
Giảng viên : Nguyễn Mậu Hân
Sinh viên thực hiện : Nguyễn Thị Diệu Hằng
Lớp : Tin K30D
1
* Bài 1:
Cho G là một đồ thị có v đỉnh và e cạnh.M và 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 minh rằng:
m ≤ 2.e/v ≤ M
Lời giải:
Theo đề ra ta có:
M: bậc lớn nhất của đỉnh của G.
m: bậc nhỏ nhất của đỉnh của G.
Như vậy:
m ≤ deg(v
i
)

≤ M (với deg(v
i
)

: bậc của đỉnh v
i
)
v.m ≤ ∑deg(v
i

2
lần lượt là số phần tử của V
1
và V
2
.
n
1
+ n
2
= v
G là đồ thị phân đôi nên e đạt giá trị max khi G là đồ thị phân đôi đầy
đủ.Khi đó:
e = n
1
.n
2
Có nghĩa là trong trường hợp tổng quát thì:
e ≤ n
1
.n
2
Như vậy, để chứng minh e ≤ v
2
/4 chỉ cần chứng minh:
n
1
.n
2
≤ v

2
+ 2.n
1
.n
2
2
P(3,1)
P(2,1)
P(2,2)P(2,3)
P(3,2)P(3,3)
n
1
2
+ n
2
2
- 2.n
1
.n
2
≥ 0≤ v
2
/4
(n
1
- n
2
)
2


a) b)
1 2 3 1 2 0 1
2 0 4 2 0 3 0
3 4 0 0 3 1 1
1 0 1 0
c)
0 1 3 0 4
1 2 1 3 0
3 1 1 0 1
0 3 0 0 2
4 0 1 2 3
Lời giải:
a) b)
c)
V
1
V
3
V
2
4
V
4
V
3
V
1
V
2
V

a
21
a
22
...

a
2n
A= .........
a
n1
a
n2
... a
nn
*Nếu G là đồ thị vô hướng :
a
ij
là số cạnh nối đỉnh v
i
và v
j
-Tổng hàng i của ma trận A:
n
∑ a
ij
chính là bậc của đỉnh v
i
j=1
-Tổng cột j của ma trận A:

*Bài 6:
Tìm ma trận liền kề cho các ma trận sau:
a) K
n
b) C
n
c) W
n
d) K
m,n
e) Q
n
Lời giải:
5
a) Ma trận liền kề của đồ thị đầy đủ K
n
:
a
i1
a
i2
... a
ij
... a
in
a
1j
0 1 ... 1 ... 1
a
2j

ij-1
a
ij
a
ij+1
... a
in-1
a
in
a
1j
0 1 0 ... 0 0 0 ... 0 1
a
2j
1 0 1 ... 0 0 0 ... 0 0
a
3j
0 1 0 ... 0 0 0 ... 0 0
... ... ... ... ... ... ... ... ... ... ...
a
ij
0 0 0 ... 1 0 1 ... 0 0
... ... ... ... ... ... ... ... ... ... ...
a
nj
1 0 0 ... 0 0 0 ... 1 0
Viết cách khác:
Ma trận liền kề của đồ thị vòng C
n
là:

... a
ij-1
a
ij
a
ij+1
... a
in-1
a
in
a
in +1
a
1j
0 1 0 ... 0 0 0 ... 0 1 1
a
2j
1 0 1 ... 0 0 0 ... 0 0 1
... ... ... ... ... ... ... ... ... ... ... ...
a
ij
0 0 0 ... 1 0 1 ... 0 0 1... ... ... ... ... ... ... ... ... ... ... ...
a
nj
1 0 0 ... 0 0 0 ... 1 0 1
a
n+1j

như sau:
v
1
v
2
... v
m
v'
1
v'
2
... v'
n
v
1
0 0 ... 0 1 1 ... 1
v
2
0 0 ... 0 1 1 ... 1
... ... ... ... ... ... ... ... ...
v
m
0 0 ... 0 1 1 ... 1
v'
1
1 1 ... 1 0 0 ... 0
v'
2
1 1 ... 1 0 0 ... 0
... ... ... ... ... ... ... ... ...