Ảnh hưởng của tính chất đồ thị lên ràng buộc giữa các bất biến trong cây và đồ thị phẳng

TẠP CHÍ KHOA HỌC ĐẠI HỌC TÂN TRÀO 
SỐ 02 – THÁNG 3 NĂM 2016 
 30 
ẢNH HƯỞNG CỦA TÍNH CHẤT ĐỒ THỊ LÊN RÀNG BUỘC 
GIỮA CÁC BẤT BIẾN TRONG CÂY VÀ ĐỒ THỊ PHẲNG 
Influences of graph’s quality on the invariables’ relationship in tree and plane graph 
ThS. Khổng Chí Nguyện* 
ThS. Vũ Thị Khánh Trình* 
ThS. Nguyễn Văn Dân* 
TÓM TẮT 
Lý thuyết đồ thị là một ngành Toán học có nhiều ứng dụng quan trọng trong Tin học và trong 
thực tế. Những ý tưởng cơ bản được đề ra bởi nhà toán học Thuỵ sĩ Leonhar Euler (1707-1783). 
Ông đã dùng đồ thị để giải quyết bài toán nổi tiếng về 7 chiếc cầu ở Konigsberg. Bằng mô hình đồ 
thị, chúng ta có thể giải quyết được nhiều bài toán thực tế như: tìm cách để tham quan một triển lãm 
sao cho mỗi một hành lang đi qua đúng một lần, tìm số mầu ít nhất để tô mầu bản đồ, biểu diễn sự 
ảnh hưởng lẫn nhau giữa các cá nhân trong một tổ chức hay sự cạnh tranh giữa các loài trong môi 
trường tự nhiên... 
Giữa tính chất của đồ thị và các bất biến trong đồ thị có mối liên hệ ràng buộc chặt chẽ với 
nhau. Bài báo này chỉ trình bày một số kết quả về ảnh hưởng của tính chất của đồ thị lên ràng buộc 
giữa các bất biến trong cây và đồ thị phẳng. 
Từ khóa: đồ thị; cây; đồ thị phẳng; cạnh; đỉnh. 
ABSTRACT 
Graph Theory is a Mathematic field which has many important applications in Informatics 
and in reality. The basic ideas were proposed by the Swiss Mathematician - Leonhar Euler (1707-
1783). He used graphs to solve the famous problem of 7 brigdes in Konigsberg. By using graph 
models, we can solve many factual problems such as looking for a way to visit an exhibition so that 
each corridor is passed only once, finding the fewest numbers of colours to colour a map, showing 
an mutual effects among individuals in a group or a competition among species in natural 
environment 
There is a close relationship between graph’s features and the invariables in graph. This paper 
only presents some results of the effects of the former on the relationship among the latter in tree 
and plane graphs. 
Key word: graph; tree; plane graph; vertex; edge. 
I. Đặt vấn đề∗ 
Mối liên hệ giữa tính chất của đồ thị và 
ràng buộc của một số bất biến trong đồ thị 
được nghiên cứu cùng với sự hình thành và 
phát triển của lý thuyết đồ thị. Các kết quả 
này được trình bày rải rác trong nhiều tài 
∗
 Trường Đại học Tân Trào 
liệu của các tác giả khác nhau về lý thuyết 
đồ thị, cũng như các tài liệu có liên quan. 
Bài báo này tập hợp các kết quả đó và trình 
bày chúng theo chủ đề: “Ảnh hưởng của tính 
chất đồ thị lên ràng buộc giữa các bất biến 
trong cây và đồ thị phẳng”. Một số phát hiện 
mới của tác giả cũng sẽ được trình bày. 
TẠP CHÍ KHOA HỌC ĐẠI HỌC TÂN TRÀO 
SỐ 02 – THÁNG 3 NĂM 2016 31
II. Nội dung nghiên cứu 
1. Một số khái niệm cơ bản 
1.1. Đồ thị 
Đồ thị vô hướng là cặp ( , )G V E= , trong 
đó V là tập hợp nào đó, còn E là tập con của 
tập , ) | , ,{( }u v u v V u v∈ ≠ , v V∈ được gọi là các 
đỉnh, còn các phần tử của E được gọi là các 
cạnh của đồ thị G. Cạnh ( , )u v E∈ được ký 
hiệu đơn giản là uv hay vu. Như vậy, các đồ thị 
ta xét ở đây là các đồ thị vô hướng, không có 
khuyên và không có cạnh bội. Ta còn gọi 
những đồ thị này là đơn đồ thị vô hướng. 
Tập đỉnh và tập cạnh của đồ thị G cũng 
thường được ký hiệu tương ứng là ( )V G và 
( )E G . Ta gọi số đỉnh của đồ thị G là cấp của 
đồ thị G, ký hiệu là | |V hay | ( ) |V G ; còn số 
cạnh của đồ thị G được gọi là cỡ của đồ thị G, 
ký hiệu là | |E hay | ( ) |E G . Nếu cạnh 
( )e uv E G= ∈ , thì ta nói rằng u và v là hai đỉnh 
kề nhau trong G, hay cạnh e liên thuộc với hai 
đỉnh u và v. 
Đồ thị ( , )G V E= có cấp | |V n= và cỡ 
2| | nE m C= = được gọi là đồ thị đầy đủ cấpn, ký 
hiệu là 
n
K . Nói cách khác đồ thị đầy đủ là một 
đồ thị trong đó mọi cặp đỉnh của nó kề nhau. 
Đồ thị ( , )G V E= có cấp 0n≠ và cỡ 
0m=
 được gọi là đồ thị rỗng cấp n, ký hiệu là 
n
E hay 
n
O . Nói cách khác đồ thị rỗng là đồ thị 
trong đó không có cặp đỉnh nào là kề nhau. 
Đồ thị 1 1K E= được gọi là đồ thị 
tầm thường. 
Giả sử x là một đỉnh tuỳ ý của đồ thị 
( , )G V E= . 
Ta gọi tập ( ) | ,{ }N x y V y x xy E= ∈ ≠ ∈ là 
tập các đỉnh kề của x (hay còn gọi là tập các đỉnh 
láng giềng của x). Số | ( ) |N x được gọi là bậc của 
đỉnhx trong đồ thị G và ký hiệu là ( )deg x . Nếu 
( ) 0deg x = thì x được gọi là đỉnh cô lập. 
1.3. Đồ thị con 
Ta nói đồ thị ( , )G V E′ ′ ′= được gọi là đồ 
thị con của đồ thị ( , )G V E= và ký hiệu là 
G G′ ⊆ nếu V V′ ⊆ và E E′ ⊆ . Nếu G G′ ⊆ và 
'G chứa tất cả các cạnh của G mà nối hai đỉnh 
của 'V, thì 'G được gọi là đồ thị con cảm sinh 
bởi G lên tập đỉnh con 'Vvà được ký hiệu là 
[ ']G V . Nếu G G′ ⊆ và V V′ = thì G' được gọi là 
đồ thị con bao trùm của đồ thị G. Nếu W V⊆ 
thì [ ]G W G V W− = − là đồ thị nhận được từ G 
bằng cách xoá đi tất cả các đỉnh của W và tất 
cả các cạnh liên thuộc với các đỉnh đó. Tương 
tự, nếu E E′ ⊆ thì ( , )G E G V E E′ ′− = − . Nếu 
, ( )x y V G∈ là hai đỉnh không kề nhau trong G 
thì G xy+ là đồ thị nhận được từ G bằng cách 
thêm cạnh nối x với y. 
1.2. Liên thông trong đồ thị 
Hai đỉnh phân biệt x và y của đồ thị 
( , )G V E= được gọi là liên thông, nếu có một 
đường từ x đến y trong ( , )G V E= .Đồ thị G 
được gọi là liên thông nếu mọi cặp đỉnh phân 
biệt trong G đều liên thông với nhau. Đồ thị 
con liên thông cực đại của G được gọi là thành 
phần liên thông của đồ thị đó. Như vậy một đồ 
thị liên thông là một thành phần liên thông của 
chính nó. 
Một đỉnh ( )x V G∈ được gọi là đỉnh cắt 
nếu G x− có nhiều thành phần liên thông hơn 
đồ thị G. Tương tự, cạnh ( )e E G∈ được gọi là 
cầu nếu G e− có nhiều thành phần liên thông 
hơn đồ thị G 
Giả sử ( , )G V E= là một đồ thị liên 
thông, còn W V⊆ thoả mãn G W−
là không liên 
thông, thì tập đỉnh W được gọi là tách đượcđồ 
thị G. Nếu hai đỉnh s và t của G thuộc hai 
thành phần liên thông khác nhau của đồ thị 
G W−
thì ta nói W tách được s với t. Tương tự, 
nếu E E′ ⊆ thoả mãn G E′− là không liên 
thông, thì tập cạnh E' được gọi là tách được đồ 
thị G, và nếu hai đỉnh s và t của G thuộc hai 
thành liên thông khác nhau của G E′− thì ta nói 
E' tách được s với t. 
Đồ thị ( , )G V E= được gọi là k- liên 
thông ( 2k ≥ ) nếu G là đồ thị đầy đủ 
1kK + , hoặc 
TẠP CHÍ KHOA HỌC ĐẠI HỌC TÂN TRÀO 
SỐ 02 – THÁNG 3 NĂM 2016 
 32 
G có ít nhất 2k +
đỉnh và không có bất kỳ tập 
1k −
 đỉnh nào tách nó. 
Giá trị cực đại k để đồ thị G là k - liên 
thông được gọi là độ liên thông của G và ký 
hiệu là ( )Gκ . Tương tự giá trị cực đại k để đồ 
thị là k- liên thông cạnh được gọi là độ liên 
thông cạnh của G và ký hiệu là ( )Gλ . 
2. Một số kết quả về ảnh hưởng của 
tính chất đồ thị lên ràng buộc giữa các bất 
biến trong lớp đồ thị phẳng và cây 
2.1. Cây 
Đồ thị vô hướng liên thông, không có 
chu trình được gọi là cây, và ký hiệu là 
( , )T V E= . Một đồ thị không có chu trình, 
không nhất thiết liên thông được gọi là rừng. 
Như vậy mỗi một thành phần liên thông của 
rừng là một cây. 
Định lý 1 [3]. Giả sử ( , )T V E= là đồ thị 
vô hướng có cấp n và cỡ m . Khi đó các mệnh 
đề sau là tương đương: 
(i) T là cây; 
(ii) T là đồ thị liên thông không có chu 
trình và 1m n= − ; 
(iii) T là đồ thị liên thông và 1m n= − . 
Chứng minh. 
1.1 (i) → (ii). Giả sử ( , )T V E= là cây. 
Khi đó T không có chu trình. Ta sẽ chứng 
minh 1m n= − bằng qui nạp theo n. Với n = 1, 
khẳng định là hiển nhiên. Vì 0 1 1 1m n= = − = − . 
Giả sử khẳng định đã được chứng minh 
là đúng cho những cây có số đỉnh nhỏ hơn n. 
Xét cây ( , )T V E= với | |V n= và ( )e E T∈ là 
một cạnh bất kỳ. Khi đó đồ thị T e− là không 
liên thông, vì trong trường hợp ngược lại T sẽ 
có ít nhất một chu trình chứa cạnh e. Mâu 
thuẫn với T là cây. Suy ra T e− có đúng 2 
thành phần liên thông, không có chu trình là 
1 1 1( , )T V E= và 2 2 2( , )T V E= . Thật vậy, nếu T e− 
có nhiều hơn 2 thành phần liên thông thì T sẽ 
không liên thông. Mâu thuẫn với T là cây. Khi 
đó ta có: 
1 2 1 2à | | | | v | | | | 1 .n V V m E E= + = + + 
1T và 2T là những cây có số đỉnh nhỏ hơn 
n. Theo giả thiết qui nạp, ta có | | | | 1i iE V= − với 
i = 1, 2. Suy ra: 
1 2 1 2| | | | 1 (| | 1) (| | 1) 1 1.m E E V V n= + + = − + − + = − 
1.2 (ii) → (iii). Để chứng minh (iii) ta chỉ 
cần chứng minh T là liên thông. Ta cũng chứng 
minh bằng qui nạp theo n. Với n = 1, khẳng 
định đúng. Giả sử khẳng định đã được chứng 
minh cho những đồ thị có cấp nhỏ hơn n. 
 Nếu ( , )T V E= là không liên thông, thì T 
có 2k ≥ thành phần liên thông là 
( , ), 1i i iT V E i k= ≤ ≤ . Mỗi thành phần 
,iT 1, 2,...,i k∈ , là một đồ thị liên thông, không 
có chu trình. Do đó , 1iT i k≤ ≤ là các cây, và vì 
thế | | | | 1, 1i iE V i k= − ≤ ≤ . Khi đó ta có: 
1 1
| | (| | 1) , 2.
k k
i i
i i
m E V n k k
= =
= = − = − ≥∑ ∑ 
Mâu thuẫn với giả thiết 1m n= − . Vậy T 
là liên thông. 
1.3 (iii) → (i). Giả sử T không là cây. Khi 
đó T có chu trình, chẳng hạn C. Lấy ( )e E C∈ 
là một cạnh bất kỳ và xét đồ thị T e− . Ta có 
T e−
 là đồ thị liên thông. Nếu T e− không là 
cây thì T e− chứa chu trình 'C và đồ thị 
( )T e e ′− − , ( )e E C′ ′∈ , là đồ thị liên thông. 
Thực hiện quá trình này cho tới khi ta thu 
được cây *T . Theo chứng minh ở 1.1(i) → (ii), 
*T có n - 1 cạnh và n đỉnh. Điều này suy ra 
không có cạnh nào trong T bị xoá. Vậy T là 
cây. Định lý được chứng minh xong.■ 
Hệ quả 2 [4]. Một cây cấp n thì có cỡ là 
n - 1. Một rừng cấp n và k thành phần liên 
thông thì có cỡ là n - k. ■ 
Trong lớp đồ thị cây, cây có gốc có 
nhiều ứng dụng trong thực tế, đặc biệt là trong 
TẠP CHÍ KHOA HỌC ĐẠI HỌC TÂN TRÀO 
SỐ 02 – THÁNG 3 NĂM 2016 33
quản lý dữ liệu máy tính hay việc mô hình hoá 
hệ thống cơ cấu tổ chức... Để tìm hiểu về cây 
có gốc, công nhận định lý sau. 
Định lý 3 [3]. Một đồ thị là cây nếu giữa 
mọi cặp đỉnh của nó luôn tồn tại một đường 
duy nhất. ■ 
Trong cây ( , )T V E= , xét một đỉnh đặc 
biệt, ( )r V T∈ , được gọi là gốc của T. Khi định 
rõ gốc ta có thể gán cho mỗi cạnh một hướng 
duy nhất từ gốc đi ra. Cây ( , )T V E= cùng với 
gốc ( )r V T∈ sinh ra một đồ thị có hướng gọi 
là cây có gốc. Như vậy từ một cây bất kỳ ta 
luôn chuyển nó thành cây có gốc bằng cách 
chọn một đỉnh tuỳ ý làm gốc. 
Giả sử ( , )T V E= là cây có gốc ( )r V T∈ . 
Cha của một đỉnh ( ),v V T v r∈ ≠ , là một đỉnh 
duy nhất ( )u V T∈ sao cho có đúng một cạnh 
từ u đến v, u có thể trùng với r. Nếu đỉnh u là 
cha của đỉnh v, thì đỉnh v được gọi là con của 
đỉnh u. Các đỉnh có cùng cha được gọi là anh 
em. Tổ tiên của một đỉnh ( ),x V T x r∈ ≠ là tất 
cả các đỉnh trên đường từ gốc r tới x, còn dòng 
dõi của một đỉnh ( )x V T∈ là tất cả các đỉnh 
coi x như là tổ tiên. Những đỉnh mà không có 
con được gọi là đỉnh lá, còn những đỉnh khác 
được gọi là đỉnh trong, đỉnh gốc ( )r V T∈ là 
một đỉnh trong. Khi | ( ) | 1V T = thì { }V r= và 
lúc này r được gọi là đỉnh lá. 
Nếu ( )a V T∈ là một đỉnh của cây, thì 
cây con gốc a, là đồ thị con cảm sinh của cây 
đang xét bởi tập đỉnh bao gồm a và các dòng 
dõi của nó. 
Một cây có gốc được gọi là cây m - phân 
nếu tất cả các đỉnh trong của nó có không quá 
m con. Cây m - phân được gọi là đầy đủ nếu 
mọi đỉnh trong của nó có đúng m con. Cây m - 
phân với 2m= được gọi là cây nhị phân. Chú 
ý rằng nếu ( )x V T∈ là một đỉnh trong thì 
( )deg x m≤ . 
Sau đây ta xét một số kết quả quan trọng 
về cây m - phân. Ta ký hiệu n, t và l tương 
ứng là số đỉnh, số đỉnh trong và số đỉnh lá của 
cây m - phân. 
Định lý 4 [3]. Giả sử ( , )T V E= là cây m- 
phân đầy đủ cấp n với t đỉnh trong. Khi đó 
1n mt= + . 
Chứng minh. Với mọi ,x V x r∈ ≠ , x luôn 
là một đỉnh con của một đỉnh trong nào đó. 
Trong t đỉnh trong này, mỗi đỉnh có đúng m 
con. Do đó có mt đỉnh khác gốc r. Suy ra cây 
m- phân đầy đủ có 1n mt= + đỉnh. ■ 
Định lý 5 [3]. Giả sử cây m - phân đầy 
đủ ( , )T V E= có cấp n, t đỉnh trong và n đỉnh 
lá. Khi đó nếu biết một trong 3 đại lượng này 
thì 2 đại lượng kia cũng sẽ được xác định. Cụ 
thể là: 
(i) Nếu T có cấp n thì 
1 ( 1) 1
 ;
n m n
t v l
m
à
m
+ − +
= = 
(ii) Nếu T có t đỉnh trong thì 1n mt= + và 
( 1) 1;l m t= − + 
(iii) Nếu T có l đỉnh lá thì 
1
.
1 1
1
 à
ml
n v t l
m m
−
= = −
− −
Chứng minh. Giả sử cây ( , )T V E= có cấp 
n. Ta cũng giả sử t là số đỉnh trong, l là số đỉnh 
lá của T. Vì trong cây có gốc chỉ có hai loại 
đỉnh, đó là đỉnh lá và đỉnh trong. Do đó ta luôn 
có đẳng thức .n t l= + 
Bây giờ ta chứng minh các khẳng định 
(i), (ii) và (iii) của định lý. 
(i) Theo định lý 4 ta có 1n mt= + . Suy 
ra: 1nt
m
−
= và l n t= − 1 1( 1)n n n m
m m
− −
= = − + . 
(ii) Giả sử cây m- phân đầy đủ có t đỉnh 
trong. Khi đó theo định lý 3 và đẳng thức 
TẠP CHÍ KHOA HỌC ĐẠI HỌC TÂN TRÀO 
SỐ 02 – THÁNG 3 NĂM 2016 
 34 
n t l= + , ta suy ra 1t l mt+ = + . Do đó: 
( 1) 1.l m t= − + Hiển nhiên 1n mt= + (định lý 4). 
(iii) Giả sử cây m - phân đầy đủ ( , )T V E= 
có l đỉnh lá. Khi đó theo định lý 4 và đẳng thức 
n t l= + , ta suy ra: 
1 1n nm n
l n t n
m m
− − +
= − = − =
1
1 .
1
ml
ml nm n n
m
−
⇔ = − + ⇔ =
−
Do đó ta có: 1 1 .
1 1
ml l
t n l l
m m
− −
= − = − =
− −
■ 
Ta xét một tham số khác là chiều cao của 
cây có gốc. Ta định nghĩa mức của một đỉnh 
v V∈
 làđộ dài của đường từ gốc r V∈ tới v và 
ký hiệu là ( )vµ . Như vậy ( ) ( , )v d r vµ = với 
( )v V T∈ . Chiều cao của cây có gốc T, ký hiệu 
là ( ) max ( ).
x V
h h T vµ
∈
= = 
Cây m - phân có chiều cao h được gọi là 
cân đối nếu các lá của nó đều ở mức h hoặc h - 
1. Cây m - phân hoàn toàn là cây m - phân đầy 
đủ trong đó mọi lá ở cùng mức. Định lý sau 
đây nêu lên mối quan hệ giữa số lá và chiều 
cao của cây. 
Định lý 6 [3]. Giả sử ( , )T V E= là cây m 
- phân có chiều cao h, số lá l. Khi đó hl m≤ . 
Chứng minh. Ta chứng minh khẳng định 
này bằng qui nạp theo h. 
Trước hết ta xét cây m - phân có chiều 
cao 1h = . Những cây dạng này chỉ gồm đỉnh 
gốc và đỉnh con. Do đó mỗi con của nó là một 
đỉnh lá. Vì vậy có không quá 1m m= lá trong 
cây m - phân chiều cao 1h = . 
Giả sử khẳng định được chứng minh là 
đúng cho cây m - phân có chiều cao h. Ta xét 
cây m - phân ( , )T V E= có chiều cao nhỏ hơn 
h. Xoá tất cả các cạnh nối từ gốc đến các đỉnh 
mức 1. Ta sẽ thu được không quá m cây con m 
- phân của gốc có chiều cao 1h = . Theo giả 
thiết qui nạp số các đỉnh lá của mỗi cây con 
này là không quá 1hm − đỉnh. Do đó tổng số các 
đỉnh lá của những cây con này là không quá 
1
.
h h
m m m
−
= . Mặt khác rõ ràng là các đỉnh lá của 
cây m - phân T có chiều cao h chính là các 
đỉnh lá của những cây con m - phân chiều cao 
1h =
 nói trên của T. Vì vậy, số các đỉnh lá của 
T là .hl m≤ ■ 
Nhận xét 7 [3]. Nếu ( , )T V E= là cây m - 
phân hoàn toàn thì ( )deg u m= với mọi đỉnh 
trong u và với mọi đỉnh lá , ( ) ( )v V v h h Tµ∈ = = . 
Khi đó, số các đỉnh lá của cây T là hl m= . Từ 
đây ta xác định được cấp của T và số các đỉnh 
trong của cây T nhờ định lý 5(iii). 
2.2. Đồ thị phẳng 
Đồ thị ( , )G V E= được gọi là đồ thị 
phẳng, nếu ta có thể biểu diễn nó trên mặt 
phẳng sao cho các cạnh của G hoặc không 
giao nhau hoặc giao nhau chỉ ở đỉnh chung của 
chúng. Ta đồng nhất đồ thị phẳng G với một 
biểu diễn phẳng như vậy của nó trên mặt 
phẳng. 
Trong đồ thị phẳng ( , )G V E= , một miền 
là phần mặt phẳng được giới hạn bởi các cạnh 
của G và không bị chia thành các phần nhỏ bởi 
các cạnh khác. Ký hiệu bằng F là tập các miền 
của một đồ thị phẳng, số | |F f= là số các 
miền của đồ thị phẳng, 1f ≥ . 
Ảnh hưởng của tính chất của đồ thị lên 
ràng buộc giữa các bất biến được thể hiện 
tương đối rõ nét qua qua các định lý sau đây 
trong đồ thị phẳng. 
Định lý 8 [1]. Giả sử ( , )G V E= là đồ thị 
phẳng, liên thông có n đỉnh, m cạnh và f 
miền. Khi đó: 2n m f− + = . 
Chứng minh. Ta chứng minh khẳng định 
trên bằng qui nạp theo số miền f. 
Với 1f = , thì G không có chu trình. Vì 
đồ thị G là liên thông, nên G là cây. Theo hệ 
quả 2 ta có 1m n= − . Do vậy, 
TẠP CHÍ KHOA HỌC ĐẠI HỌC TÂN TRÀO 
SỐ 02 – THÁNG 3 NĂM 2016 35
( 1) 1 2n m f n n− + = − − + = . Khẳng định đúng 
cho trường hợp 1f = . 
Giả sử khẳng định đã được chứng minh 
là đúng cho những đồ thị phẳng có số miền 
nhỏ hơn , 2f f ≥ . Ta xét đồ thị phẳng liên thông 
( , )G V E= có 2f ≥ miền. Khi đó, trong G có 
ít nhất một chu trình, chẳng hạn C. Nếu xy là 
một cạnh thuộc tập ( )E C , thì xy sẽ liên thuộc 
với cả hai miền trong G. Suy ra G xy− là đồ thị 
phẳng có 1m− cạnh, 1f − miền và n đỉnh. 
Theo giả thiết qui nạp ta có: 
( 1) ( 1) 2 2.n m f n m f− − + − = ⇔ − + = ■ 
Định lý 1 được gọi là công thức Euler 
cho đồ thị phẳng. 
Định lý 9.12 [4]. Giả sử ( , )G V E= là đồ 
thị phẳng có n đỉnh, m cạnh, f miền và k thành 
phần liên thông. Khi đó n m f− + 1.k= + 
Chứng minh. Giả sử ( , )i i iG V E= với 
1 i k≤ ≤ là những thành phần liên thông của đồ 
thị G. Mỗi thành phần ,1iG i k≤ ≤ , là một đồ thị 
phẳng, liên thông. Ký hiệu | |, | |i i i in V m E= = và 
| |,1i if F i k= ≤ ≤ . Theo định lý 1, ta có 
2,i i in m f− + = 1 .i k≤ ≤ Vì với mọi 
,1 , , i ji j i j k V V≠ ≤ ≤ ∩ = ∅ , nên 
1
k
i
i
n n
=
=∑ và 
1
.
k
i
i
m m
=
=∑ 
Ta nhận xét thấy rằng các đồ thị phẳng, 
liên thông ,1iG i k≤ ≤ có chung một miền ngoài 
cùng, tức là miền có biên không giới hạn. Vì 
vậy miền này sẽ được đếm k lần trong 
1
k
i
i
f
=
∑ . 
Do đó: 
1
1.
k
i
i
f f k
=
= − +∑ Suy ra: 
1
( ) 1
k
i i i
i
n m f n m f k
=
− + = − + − +∑
1
2 1 2 1 1.
k
i
k k k k
=
= − + = − + = +∑ ■ 
Giả sử đồ thị ( , )G V E= có chu trình. 
Chu vi nhỏ nhất của đồ thịG, ký hiệu là ( )g G 
hay g, là độ dài của chu trình ngắn nhất trong 
G. Chu vi lớn nhất của G, ký hiệu là ( )c G hay 
c, là độ dài của chu trình lớn nhất trong G. 
Nếu đồ thị không có chu trình, thì ta qui ước 
g c= = +∞ . Như vậy với mọi đồ thị ( , )G V E= 
ta có 3 ( ) ( )g G c G≤ ≤ ≤ +∞ . 
Định lý 10 [4], [1].Giả sử đồ thị phẳng, 
liên thông ( , )G V E= có n đỉnh, m cạnh, f miền 
và chu vi nhỏ nhất g thoả mãn 3 g≤ < +∞ . Khi 
đó 
(i) ( 2)
2
g
m n
g
≤ −
−
 (Bất đẳng thức cạnh - 
đỉnh), 
(ii) 3 2f m≤ (Bất đẳng thức cạnh - miền). 
Chứng minh. Giả sử 
1 2{ , , ... }, mE e e e= , 
1 2{ , ,..., }.fF R R R= Ta thành lập ma trận cạnh - 
miền ( )ij mfX x= , trong đó: 
ij 1x = nếu ie là một cạnh trên biên của jR ; 
ij 0x = nếu ie không là một cạnh trên biên 
của jR ; 
 cho mọi 1,2,...,i m= và 1, 2, ...,j f= . Vì 
mỗi cạnh ở trên biên của nhiều nhất 2 miền, 
nên mỗi hàng có nhiều nhất 2 chữ số 1. Mặt 
khác có ít nhất 3 cạnh ở trên biên của một 
miền tạo thành một chu trình, nên số các chữ 
số 1 trên mỗi cột ít nhất là 3g ≥ . Gọi N là số 
các chữ số 1 trong ma trận X. Khi đó ta có 
2gf N m≤ ≤ . Vì 3g ≥ nên 3 f gf≤ và như vậy 
ta có bất đẳng thức cạnh - miền 3 2 .f m≤ 
Mặt khác, theo công thức Euler cho đồ 
thị phẳng ta có: f = 2.m n− + Suy ra: 
( 2) 2 ( 2) ( 2)g m n m g m g n− + ≤ ⇔ − ≤ −
( 2).
2
g
m n
g
⇔ ≤ −
−
■ 
Từ công thức Euler cho đồ thị phẳng và 
các bất đẳng thức cạnh - miền, cạnh - đỉnh ta 
có các hệ quả sau đây về quan hệ cạnh - đỉnh 
trong một số lớp đồ thị phẳng cụ thể. 
TẠP CHÍ KHOA HỌC ĐẠI HỌC TÂN TRÀO 
SỐ 02 – THÁNG 3 NĂM 2016 
 36 
Hệ quả 11 [3]. Giả sử ( , )G V E= là đồ 
thị phẳng, liên thông có n đỉnh, m cạnh và f 
miền. Khi đó: 
(i) Nếu 3n≥ thì 3( 2)m n≤ − ; 
(ii) Nếu 3n≥ và không có chu trình độ 
dài 3, thì 2( 2);m n≤ − 
(iii) Nếu 4n≥ và không có chu trình độ 
dài 3 và 4, thì 5 ( 2)
3
m n≤ − . 
Chứng minh. (i) Nếu G không có chu 
trình, thì vì G là liên thông nên G là cây. Do 
vậy 1f = . Theo định lý 11 ta có 2,n m f− + = 
nên
2 1 2 ( 2) ( 2) 2( 2).m n f n n n n= + − = + − ≤ − + − = −
Suy ra 3( 2)m n< − . Khẳng định đúng nếu G 
không có chu trình. 
Giả sử G có chu trình thì 3 g≤ < +∞ . 
Theo định lý 13 ta có: 
( 2) ( 2) 2 .
2
g
m n g m n m
g
≤ − ⇔ − + ≤
−
 Suy ra 3( 2) 2 3( 2).m n m m n− + ≤ ⇔ ≤ − 
(ii) Nếu G không có chu trình, thì vì G 
liên thông, nên G là cây và do đó 1f = . Theo 
định 1 ta suy ra: 
1 2 1m n n= + − = − =
2 1 2 3 1 2( 2).n n n n− − ≤ − − = − Vậy khẳng định 
đúng nếu G không có chu trình. 
Giả sử G có chu trình. Khi đó 
4 g≤ < +∞ . Theo chứng minh định lý 10 và 
công thức Euler cho đồ thị phẳng, ta có: 
2 4( 2) 2 2( 2).gf m m n m m n≤ ⇔ − + ≤ ⇔ ≤ − 
(iii) Nếu G không có chu trình, G liên 
thông. Suy ra G là cây. Do đó 1f = . Theo định 
lý 1, ta có 2 1m n f n= + − = − hay 
3 3 3 5 2 3 5 2.4 3 5 10.m n n n n n= − = − − ≤ − − < −
Vì vậy khẳng định đúng, nếu G không có 
chu trình. 
Giả sử G có chu trình. Khi đó 
5 g≤ < +∞ . Theo định lý 3 ta có 2gf m≤ hay: 
5( 2) 2 3 5( 2).m n m m n− + ≤ ⇔ ≤ − ■ 
Hệ quả 12 [3]. Nếu ( , )G V E= là đồ thị 
phẳng 2 - phần, liên thông với 3n≥ đỉnh và m 
cạnh thì 2( 2)m n≤ − . 
Chứng minh. Vì G là đồ thị 2- phần, nên 
G không có chu trình độ dài lẻ. Nói riêng G 
không có chu trình độ dài 3. Sử dụng hệ quả 
4(ii), ta có điều phải chứng minh. ■ 
Hệ quả 12 chỉ là một trường hợp riêng 
của định lý 16. 
3. Kết quả nghiên cứu chính 
Tập con I V⊆ của đồ thị ( , )G V E= 
được gọi là tập độc lập nếu đồ thị con cảm 
sinh G[I] là đồ thị rỗng. Tập con độc lập với số 
đỉnh nhiều nhất của G, được gọi là tập độc lập 
đỉnh củaG. Ký hiệu bằng ( )Gα số đỉnh của tập 
độc lập đỉnh lớn nhất và gọi là số độc lập đỉnh 
của đồ thị G. 
Định lý 13. Giả sử ( , )T V E= là cây m - 
phân có chiều cao h và ( )Tα là số độc lập đỉnh 
của T. Khi đó: 
(i) Nếu h chẵn 
thì 2 4( ) 1 ... ;hT m m mα ≤ + + + + 
(ii) Nếu h lẻ thì 3 5( ) .... hT m m m mα ≤ + + + + 
Chứng minh. (i) Ta ký hiệu r là đỉnh gốc 
và I là tập độc lập đỉnh lớn nhất của T. Ký 
hiệu: ( ) | ( ) , 0 , 2 , . ., .}.{kI x V T x k k hµ= ∈ = = 
Rõ ràng đồ thị con cảm sinh 
[ ], 0, 2, 4, ...,kT I k h= là đồ thị rỗng. Mặt khác, 
theo định lý 3, ta suy ra mỗi đỉnh của kI 
không kề với bất kỳ đỉnh nào của 
kI ′ với 
k k′≠
 và , 0, 2, 4,...,k k h′ = . Do đó đồ thị con cảm 
sinh 
0 2[ ... ]hT I I I∪ ∪ ∪ là đồ thị rỗng. Hơn nữa 
0 2 ... kI I I∩ ∩ ∩ = ∅ , nên ta có: 
0 2| | | | | | ... | | .hI I I I= + + + 
Bây giờ ta tính | |kI với 0, 2, 4,...,k h= . 
 Ký hiệu 
kT là đồ thị con cảm sinh của 
cây m - phân ( , )T V E= lên tập các đỉnh mức k 
TẠP CHÍ KHOA HỌC ĐẠI HỌC TÂN TRÀO 
SỐ 02 – THÁNG 3 NĂM 2016 37
và các tổ tiên của chúng. Như vậy 
kT là cây m- 
phân có chiều cao k, và 
kI là tập các đỉnh lá của 
nó. Khi đó, theo định lý 6 ta có: 
| | , 0,2,4,..., .kkI m k h≤ = Suy ra: 
0 2 4( ) | | ... .hT I m m m mα = ≤ + + + + 
(ii) Giả sử h lẻ và r là gốc của ( , )T V E= . 
Xét một cây con T' của gốc r. Khi đó 
( ) 1h T h′ = − là số chẵn. Theo chứng minh (i), 
ta có: 2 4( ) 1 ... 1 .hT m m mα ′ ≤ + + + + − 
Mặt khác, có không quá m cây con kiểu 
T'. Suy ra 
2 4( ) ( ) (1 ... 1)hT m T m m m mα α ′≤ ≤ + + + + −
3 5
... .
h
m m m m= + + + + ■ 
Cây Fibonacci
n
T được định nghĩa một 
cách đệ qui như sau: 
(i) 1T và 2T là cây có gốc chỉ gồm 1 đỉnh; 
(ii) Với 3,4,...n = cây 
n
T là cây có gốc r 
với 
1nT − là cây con bên trái và 2nT − là cây con 
bên phải. 
Như vậy cây Fibonacci là cây nhị phân. 
Theo định lý 5(iii), nếu biết số lá của cây 
n
T là 
( )
n n
l l T= thì số đỉnh trong 1( )n nt T l −= còn cấp 
1| ( ) | 2n nV T l −= . Vì vậy ta chỉ cần xác định được 
số lá của cây , 3
n
T n ≥ . 
Theo định nghĩa cây Fibonacci, 
1T và 2T 
có số lá bằng 1. Để xác định số lá của 
3T ta tính 
tổng số lá của hai cây 
1T và 2T . Ta có: 
3 3 1 2( ) 1 1 2.l T l l l= = + = + = 
Tiếp tục, cây Fibonacci thứ n có số lá: 
1 2( ) ( ) ( )n n nl T l T l T− −= + hay: 1 2 .n n nl l l− −= + 
Như vậy dãy số { }
n
l thoả mãn hệ thức 
truy hồi: 
1 2n n nl l l− −= + , với 3n≥ cùng với điều 
kiện ban đầu 
1 21, 1l l= = . Vậy số đỉnh lá của 
cây 
n
T chính là số Fibonacci thứ n. Ta có định 
lý sau. 
Định lý 14 [3]. Giả sử ( , ), 3
n n n
T V E n= ≥ 
là cây Fibonacci thứ n . Ký hiệu ( )
n
l T là số 
đỉnh lá của nó. Khi đó ( )
n n
l T l= , trong đó l n là 
số Fibonacci thứ n được cho bởi hệ thức truy 
hồi sau: 1 2 1 21, 1, n n nl l l l l− −= = = + với 
3.n ≥ ■ 
Ký hiệu ( )h h Tn n= là chiều cao của cây 
Fibonacci , 3
n
T n ≥ . 
Định lý 15 [3]. ( ) 2 , 3
n n
h h T n n= = − ≥ . 
Chứng minh. Ta chứng minh khẳng định 
này bằng qui nạp theo n. Với 3n= ta có 
3 1, 2 3 2 1.h n= − = − = Khẳng định đúng cho 
3n= . 
Giả sử khẳng định đã được chứng minh 
là đúng cho mọi cây Fibonacci 
kT với 3 k n≤ < . 
Khi đó cây 
n
T được xây dựng từ 2 cây 
Fibonacci 
1nT − và 2nT − bằng cách lấy một đỉnh 
tuỳ ý 
1 2( ) ( )n n nr V T V T− −∉ ∪ và nối nr với gốc 1nr − 
của 
1nT − và gốc 2nr − của 2nT − . Rõ ràng theo định 
nghĩa của cây Fibonacci, ta 
có:
1( ) ( ) 1 .n nh T h T −= + 
Theo giả thiết qui nạp 
1( ) ( 1) 2 3nh T n n− = − − = − . Suy 
ra:
n
h = ( ) ( 3) 1 2 .
n
h T n n= − + = − Vậy khẳng định 
đúng cho cây 
nT . ■ 
Định lý 16.Giả sử ( , )G V E= là đồ thị 
phẳng k - phần, liên thông với 2, 3k n≥ ≥ đỉnh 
và m cạnh. Khi đó: 2( 1)( ).m k n k≤ − − 
Chứng minh. Giả sử đồ thị phẳng, liên 
thông, k - phần 
1 2( ... , )kG V V V E= ∪ ∪ ∪ trong đó 
2, i jk V V≥ ∩ =∅ cho mọi ,1 ,i j i j k≠ ≤ ≤ và 
| | ,1i iV n i k= ≤ ≤ . Với mỗi cặp iV và 
,jV 1 , ,i j k i j≤ ≤ ≠ , đồ thị con cảm sinh 
TẠP CHÍ KHOA HỌC ĐẠI HỌC TÂN TRÀO 
SỐ 02 – THÁNG 3 NĂM 2016 
 38 
[ ]i jG V V∪ là một đồ thị con 2 - phần, ta ký hiệu 
là: 
( , ),ij i j ijG V V E= ∪ | | .ij ijE m= 
ijG là đồ thị phẳng 2 - phần, liên thông. 
Sử dụng hệ quả 12, ta có: 2( ) 4.ij i jm n n≤ + − Tổng 
có 2kC đồ thị con 2 - phần ijG , ,1 , )i j i j k≠ ≤ ≤ , 
và rõ ràng tập cạnh của chúng là rời nhau. 
Ta có: 
1
,ij
i j k
m m
≤ < ≤
=∑ 
1 2
1
( ) ( 1) ( 1) ... ( 1)
≤ < ≤
+ = − + − + + −∑ i j k
i j k
n n k n k n k n
1 2 ( 1)( ... ) ( 1) .= − + + + = −kk n n n k n 
Suy ra: 
1
ij
i j k
m
≤ < ≤
∑
1
[ ]2( ) 4i j
i j k
n n
≤ < ≤
≤ + −∑
1
[ ]2 ( ) 2i j
i j k
n n
≤ < ≤
= + −∑ 
hay 2[( 1) ( 1)] 2( 1)( ).m k n k k k n k≤ − − − = − − ■ 
III. Kết luận 
Bài báo trình bày một số kết quả trong 
các tài liệu khác nhau về sự ảnh hưởng cuả 
tính chất của đồ thị lên ràng buộc giữa các bất 
biến trong lớp đồ thị phẳng và cây. Phần lớn 
các kết quả đều liên quan đến số cạnh và số 
đỉnh của đồ thị. Định lý 13 và Định lý 16 là 
những kết quả mới. 
TÀI LIỆU THAM KHẢO 
1. B. Bollobas, Graph Theory an Introductory Course, New York - Heidelberg - 
Berlin, 1979; 
2. R. J. McElice, R.B. Ash, C. Ash, Introduction to Discrete Mathematics, McGraw - 
Hall Book Company, 1989; 
3. K. H. Rosen, Dicrete Mathematics and Its Application, 2, McGraw - Hill Book 
Company, 1991; 
4. R. Wilson, Introduction to Graph Theory, Longman,1975. 
5. B. Bollobas et all (Editors), Proceeding of Symposia in Applied Mathematics, 14, 
Probability Combinators and Its Applications, American Mathematical Society, 1991; 
6. O. Ore, Theory of Graphs, American Mathemetican Society, Province, XXXVIII, 
1962.