Xem mẫu
- 112 Lê Xuân Hùng
VỀ CHU TRÌNH HAMILTON TRONG ĐỒ THỊ TÁCH CỰC
ON HAMILTON CYCLES IN SPLIT GRAPHS
Lê Xuân Hùng
Trường Đại học Tài nguyên và Môi trường Hà Nội; Email: lxhung@hunre.edu.vn
Tóm tắt - Đồ thị G = (V , E ) được gọi là đồ thị tách cực nếu tồn Abstract - A graph G = (V , E ) is called a split graph if there
tại phân hoạch V = I K sao cho đồ thị con của G cảm sinh exists a partition V = I K such that the subgraphs of G
trên I là đồ thị rỗng và đồ thị con của G cảm sinh trên K là đồ thị induced by I and K are empty and complete, recpectively. We will
đầy đủ. Chúng ta ký hiệu đồ thị tách cực đó là S ( I K , E ) . Khái denote such a graph by S ( I K , E ) . The notion of split graphs
niệm đồ thị tách cực được định nghĩa vào năm 1977 bởi S. Foldes was introduced in 1977 by S. Foldes and P.L.Hammer. Attention
và P.L. Hammer. Các đồ thị này đã và đang được nghiên cứu nhiều has been paid to these graphs because of their connection with
bởi vì chúng có liên quan nhiều đến các vấn đề về tổ hợp. Mặt many combinatorial problems. Moreover, one of the fundamental
khác, một trong những vấn đề cơ bản của lý thuyết đồ thị là bài problems in graph theory is the hamiltonian problem. In this paper,
toán Hamilton. Trong bài báo này chúng ta sẽ nghiên cứu sự tồn we characterize Hamiltonian graphs in the class of split graphs with
tại chu trình Hamilton trong lớp đồ thị tách cực với 3
3 (G) (| I | −1) . We show that G has Hamilton cycle if and
(G) (| I | −1) và chứng minh được rằng đồ thị tách cực G 5
5 only if for every vK , G −v has a Hamilton path.
có chu trình Hamilton khi và chỉ khi khi với mọi vK , đồ thị
G − v có đường Hamilton.
Từ khóa - đồ thị tách cực; chu trình Hamilton; đường Hamilton; đồ Key words - split graph, Hamilton cycle, Hamilton path; non-
thị tách cực phi Hamilton tối đại; bậc cực tiểu. hamiltonian split graph; minimum degree.
độ bền bằng 2 đều có chu trình Hamilton, các tác giả
1. Đặt vấn đề Kratsch, Lehel và Muller [6] đã nghiên cứu mối quan hệ
Tất cả các đồ thị được nói tới trong bài báo này là những giữa độ bền với sự tồn tại chu trình Hamilton trong đồ thị
đơn đồ thị hữu hạn, vô hướng, không có khuyên và không tách cực.
có cạnh bội. Nếu G là một đồ thị, thì V(G) (hoặc V) được Trong bài báo này chúng tôi tiếp tục nghiên cứu sự tồn
gọi là tập đỉnh và E(G) (hoặc E) được gọi là tập cạnh. Tập tại chu trình Hamilton cho đồ thị tách cực G = S ( I K , E )
hợp tất cả các đỉnh là hàng xóm của tập con S V (G) 3
với (G) (| I | −1) và đã chứng minh được rằng đồ thị
được ký hiệu là NG (S ) (hoặc N(S)). Với mỗi đỉnh 5
v V (G) , ta gọi N G (v) là bậc của đỉnh v, ký hiệu là tách cực G có chu trình Hamilton khi và chỉ khi với mọi
v K , đồ thị G − v có đường Hamilton.
deg(v). Với đồ thị G = (V , E ) , số min deg(v) | v V
được gọi là bậc cực tiểu của G, ký hiệu là (G) . Đồ thị 2. Nội dung nghiên cứu
con của G cảm sinh trên tập U V (G) được ký hiệu là 2.1. Một số kết quả liên quan
G[U ] . Ngoài ra, một số khái niệm và ký hiệu khác được Giả sử C là một chu trình trong đồ thị G = (V , E ) . Ta
định nghĩa trong [1]. sẽ ký hiệu chu trình C với một chiều xác định là C và chu
Đồ thị G = (V , E ) được gọi là đồ thị tách cực nếu tồn trình C với chiều ngược lại là C . Nếu u, v V (C ) , thì ta
tại một phân hoạch V = I K sao cho đồ thị con G[I] là ký hiệu các đỉnh liên tiếp của C từ u tới v theo chiều đã xác
đồ thị rỗng và đồ thị con G[K] là đồ thị đầy đủ. Chúng ta định trên C là uCv và ký hiệu các đỉnh liên tiếp của C từ
ký hiệu đồ thị đồ thị tách cực là S ( I K , E) . Khái niệm u tới v theo chiều ngược lại xác định trên C là uCv . Ta sẽ
đồ thị tách cực được định nghĩa đầu tiên vào năm 1977 bởi coi uCv và uCv như là các đường và cũng như là các tập
Foldes và Hammer [4]. Các đồ thị này đã và đang được
đỉnh. Nếu u V (C ) , thì ta ký hiệu u + và u − lần lượt là
nghiên cứu nhiều bởi vì chúng có liên quan nhiều đến các
vấn đề về tổ hợp (xem [3], [5], [8]). các đỉnh đứng ngay sau và ngay trước đỉnh u trên C . Các
Năm 1980, Burkard và Hammer đã đưa ra một điều khái niệm tương tự như đã mô tả ở trên cho các chu trình
kiện cần nhưng không là điều kiện đủ để đồ thị tách cực cũng sẽ được sử dụng cho các đường. Nếu U V (G) , thì
G = S ( I K , E ) với | I || K | có chu trình Hamilton [2]. ta ký hiệu tập U NG (u) là NU (u) .
Các tác giả này cũng đặt ra một câu hỏi, cần bổ sung những
Giả sử G = S ( I K , E ) là đồ thị tách cực và G* là đồ
điều kiện gì để điều kiện cần trên cũng là điều kiện đủ. Đã
có một số tác giả giải quyết được một phần câu hỏi trên, đó thị 2 phần thu được từ đồ thị G bằng cách xóa đi tất cả các
là Peemoller [7], Ngô Đắc Tân và Lê Xuân Hùng [9], [10]. cạnh có cả hai đỉnh đầu mút đều thuộc K. Trong đồ thị G* ,
Liên quan đến giả thuyết của V.Chvatal rằng mọi đồ thị có các đỉnh thuộc tập I ta tô màu trắng, các đỉnh thuộc tập K
- TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG - SỐ 7(80).2014 113
ta tô màu đen. Các đường của đồ thị G có cả hai đỉnh đầu
*
thị G − v .
mút đều thuộc K ta gọi là B-đường. Bây giờ giả sử rằng G = S ( I K , E ) là đồ thị tách cực
Bổ đề 1 ([6]). Giả sử G = S ( I K , E ) là đồ thị tách cực với (G) | I | −2 và với mọi v K , đồ thị G − v có
với | I || K | . Khi đó G có chu trình Hamilton khi và chỉ khi đường Hamilton. Từ Bổ đề 3 ta có N ( I ' ) I ' với mọi
tập đỉnh của G* có thể phân hoạch thành các B-đường.
I ' I thỏa mãn I ' min | I |,| K | −1 . Do đó theo
Bổ đề 2 ([6]). Giả sử G = S ( I K , E ) là đồ thị tách
Định lý 5, hoặc G có chu trình Hamilton hoặc G là một
3
cực. Nếu với mọi tập con I I ta đều có N ( I ) I ' ,
' ' trong các đồ thị ngoại lệ liệt kê trong định lý. Nhưng dễ
2 dàng thấy rằng các đồ thị ngoại lệ này không thỏa mãn điều
thì tập đỉnh của G* có thể phân hoạch thành các B-đường. kiện với mọi v K , đồ thị G − v có đường Hamilton. Như
vậy, chỉ xảy ra trường hợp G có chu trình Hamilton. ■
Bổ đề 3. Giả sử G = S ( I K , E ) là đồ thị tách cực với
Bảng 1. Các đồ thị Gnm , Dn4 và Fn5
| I |= m, | K |= n và với mọi v K , đồ thị G − v có đường
Hamilton. Khi đó với mọi I ' I thỏa mãn Đồ thị Tập đỉnh Tập cạnh
G = (V , E ) V = I K E = E1 E2 E3
I ' min m, n − 1 ta luôn có N ( I ' ) I ' .
Gnm I = u1 ,..., um E1 = u1v1 , u2 v2 , u3v3
Chứng minh. Giả sử tồn tại tập con I ' I thỏa
3 m n K = v1 ,..., vn E2 = {ui v j | i = 1,..., m;
mãn I ' min m, n − 1 nhưng N ( I ' ) I ' . Giả sử
j = 4,..., m + 1}
v1 , v2 ,..., vk là các đỉnh của N ( I ' ) và giả sử P là đường E3 = {vi v j | i j;
Hamilton của G − v1 . Khi đó P − v1 , v2 ,..., vk có thể được i, j = 1,..., n}
phủ bởi k = N ( I ' ) đường rời nhau. Do đó G − N ( I ' ) D4
I = u1 ,..., u4 E1 = {u1v2 , u2 v1 , ui vi |
n
cũng có thể được phủ bởi k = N ( I ) đường rời nhau.
' 4n K = v1 ,..., vn i, j = 1, 2,3, 4}
Nhưng ta biết rằng số ít nhất các đường rời nhau của E2 = {ui v5 | i = 1,..., 4}
G − N ( I ' ) phủ được V (G − N ( I ' )) lớn hơn k = N ( I ' ) . E3 = {vi v j | i j;
Từ đó dẫn tới điều mâu thuẫn. ■ i, j = 1,..., n}
Bổ đề 4 ([9]). Giả sử G = S ( I K , E ) là đồ thị tách F n
5
I = u1 ,..., u5 E1 = {ui vi | i = 1,...,5}
cực phi-Hamilton tối đại. Khi đó với mỗi v K , hoặc 6n K = v1 ,..., vn E2 = {ui v j | i = 1,...,5;
N I (v) I − (G ) hoặc N I (v) = I . j = 6,7}
Định lý 5 ([9]). Giả sử G = S ( I K , E ) là đồ thị tách E3 = {vi v j | i j;
cực với | I |= m, | K |= n và (G) m − 2 . Khi đó G có chu i, j = 1,..., n}
trình Hamilton khi và chỉ khi m n và N ( I ) I ' '
với 3. Kết quả chính
mọi I I thỏa mãn I min m, n − 1 , ngoại trừ các
' ' Trong mục này chúng ta sẽ phát biểu và chứng minh
định lý dưới đây.
đồ thị dưới đây mà đối với chúng điều kiện đủ không đúng:
Định lý 7. Giả sử G = S ( I K , E ) là đồ thị tách cực
(i) m = 3 n và G là đồ thị Gn3 ;
3
(ii) m = 4 n và G là đồ thị con bao trùm của đồ thị với (G) (| I | −1) . Khi đó G có chu trình Hamilton khi
Dn hoặc đồ thị Gn4 ;
4 5
và chỉ khi với mọi v K , đồ thị G − v có đường Hamilton.
(iii) m = 4 n và G − u là đồ thị Gn3 với mỗi u I ;
Chứng minh. Nếu G có chu trình Hamilton và giả sử v
(iv) m = 5 n và G là đồ thị Fn5 hoặc là đồ thị con bao
là một đỉnh thuộc K, thì v+ Cv− là đường Hamilton của đồ
trùm của đồ thị Gn5 ; thị G − v .
(v) 6 m n và G là đồ thị con bao trùm của đồ thị Gnm . Bây giờ giả sử G = S ( I K , E ) là đồ thị phi Hamilton
Các đồ thị Gnm , Dn4 và Fn5 được định nghĩa trong Bảng 1. 3
Từ Định lý 5 ta suy ra hệ quả sau đây. tối đại thỏa mãn | I |= m, | K |= n, (G) (m − 1) và với
5
Hệ quả 6. Giả sử G = S ( I K , E ) là đồ thị tách cực mọi v K , đồ thị G − v có đường Hamilton. Đặt
với (G) | I | −2 . Khi đó G có chu trình Hamilton khi và 2m + 3
Ki = v K | N I (v) = i , t = .
chỉ khi với mọi v K , đồ thị G − v có đường Hamilton. 5
Chứng minh. Nếu G có chu trình Hamilton và giả sử v (Trong đó [a] là ký hiệu số nguyên lớn nhất nhỏ hơn
là một đỉnh thuộc K, thì v+ Cv− là đường Hamilton của đồ hoặc bằng a). Theo Bổ đề 4 dễ dàng thấy rằng
- 114 Lê Xuân Hùng
Kt +1 = ... = Km−1 = . u j = v −j N I ( vn ) với mọi j = 1, 2,..., k = deg ( u1 ) . Từ đó
Nếu tồn tại đỉnh v Km và giả sử P là đường Hamilton suy ra rằng
của G − v . Khi đó vPv là chu trình Hamilton của G, mâu Khẳng định 3.1. deg ( u1 ) = m − t và u1 , u2 ,..., um−t là
thuẫn với việc G là đồ thị phi Hamilton. Do đó Km = . tất cả các đỉnh của V(G) không kề với vn .
Ta xét hai trường hợp có thể xảy ra. Đặt:
Trường hợp 1: Kt = P1 = u1 Pu2− , P2 = u2 Pu3− , ..., Pm −t = um −t Pvn
Trong trường hợp này, Kt = Kt +1 = ... = Km = . Với Khi đó các khẳng định sau là đúng.
mọi I I ta có
N ( u j ) V ( Pi ) 1
'
Khẳng định 3.2. với mọi
' deg(u) 3 (m − 1) I ' 3 ' i, j 1, 2,..., m − t .
N ( I ) uI
'
5 = I .
t −1 2m + 3 Giả sử ngược lại rằng tồn tại i, j 1, 2,..., m − t sao
−1 2
cho N ( u j ) V ( Pi ) 2 . Giả sử vl và vl +1 là hai đỉnh khác
5
Theo Bổ đề 1 và Bổ đề 2, G có chu trình Hamilton,
mâu thuẫn. nhau của N ( u j ) V ( Pi ) , xuất hiện trên P theo thứ tự của
Trường hợp 2: Kt các chỉ số của chúng. Trước hết giả sử rằng j i . Khi đó
Theo Bổ với mọi u I
đề 3, ta có vl−+1 u1 , u2 ,..., um −t . Theo Khẳng định 3.1, vl−+1 N ( vn )
deg(u) = N (u ) u = 1 , do đó deg(u) 2 . Hơn nữa, . Do đó
nếu m 4 thì (G) 2 m − 2 . Theo Hệ quả 6, G có chu C ' = u j Pu1v j Pvl−+1vn Pvl +1u j là chu trình Hamilton của
trình Hamilton, mâu thuẫn. Do vậy m 5 . G, mâu thuẫn. Bây giờ ta giả sử rằng j i . Khi đó
Giả sử vn là một đỉnh của Kt . Vì I = m 5 và vl+ u1 , u2 ,..., um −t và tiếp tục theo Khẳng định 3.1 ta có
2m + 3 vl+ N ( vn ) . Do đó C ' = u j Pvl+ vn Pv j u1 Pvl u j là chu trình
N I ( vn ) = t = m , tồn tại đỉnh u1 I sao cho
5 Hamilton của G, mâu thuẫn.
u1 không kề với vn . Vì G là đồ thị tách cực phi Hamilton Khẳng định 3.3. Nếu v N ( u j ) V ( Pi ) và j i với
tối đại nên G + u1vn có chu trình Hamilton D. Do đó
i, j 1, 2,..., m − t , thì v − N ( vn ) .
P = D − u1vn là đường Hamilton của G với các đỉnh đầu
Nếu v = v j , thì ta đã chứng tỏ trong Khẳng định 3.1
mút là u1 và vn . Chú ý rằng u1 I , vn K và u1 không
rằng v − = v −j = u j N ( vn ) . Nếu v v j và v − N ( vn ) , thì
kề với vn . Giả sử P = u1 ...vn . Nếu vn− K và u N I ( vn ) ,
C ' = u j Pu1v j Pv − vn Pvu j là chu trình Hamilton của G, mâu
thì P ' = u1 Pu − vn− Puvn là đường Hamilton của G với các
thuẫn.
đỉnh đầu mút là u1 và vn . Nhưng trong P ' , vn− = u I .
Khẳng định 3.4. Nếu v N ( u j ) V ( Pi ) và j i với
Bằng việc xét P ' thay cho P nếu cần thiết, không mất tính
i, j 1, 2,..., m − t , thì v + N ( vn ) .
tổng quát ta có thể giả sử rằng vn− trong P là đỉnh um I .
Giả sử v1 , v2 ,..., vk là các đỉnh của N ( u1 ) xuất hiện lần Giả sử v + N ( vn ) . Khi đó
lượt trên P theo thứ tự của các chỉ số của chúng. Nếu tồn C ' = u j vPu1v j Pvn v + Pu j là chu trình Hamilton của G,
tại đỉnh u j N ( u1 ) sao cho v −j N ( vn ) , thì mâu thuẫn.
Từ Khẳng định 3.2 ta có deg ( u j ) m − t
−
C = u1 Pv v Pv j u1 là chu trình Hamilton của G, mâu
'
j n với
thuẫn. Do vậy v N ( vn ) với mọi j = 1, 2,..., k . Suy ra
−
j j 1, 2,..., m − t . Nhưng trong đồ thị G, theo giả thiết ta
v −j I với mọi j = 1, 2,..., k . Dễ dàng thấy rằng u1 = v1− . có deg ( u j ) m − t . Do đó deg ( u j ) = m − t với mọi
Đặt u j = v −j I với mọi j = 2,..., k và j 1, 2,..., m − t . Hơn nữa, theo Khẳng định 3.1, Khẳng
N I ( vn ) = I \ N I ( vn ) . Khi đó định 3.3 và Khẳng định 3.4 ta có
N ( u1 ) = v1 , v2 ,..., vm −t ,
N I ( vn ) = I − N I ( vn ) = m − t .
N ( u j ) = u2− , u3− ,..., u −j , v j , v j +1 ,..., vm −t
3 2m + 3
Nhưng deg ( u1 ) (m − 1) = m − , suy ra
5 5 Với j = 2,3,..., m − t .
deg ( u1 ) m − t (vì deg ( u1 ) là số nguyên dương) và Giả sử rằng u −j = v j −1 với mọi j 2,3,..., m − t . Khi
- TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG - SỐ 7(80).2014 115
đó với I = u1 , u2 ,..., um −t ta có
'
đề này vẫn chưa giải quyết được triệt để và rất cần được
tiếp tục nghiên cứu. Chính vì vậy, bài báo tiếp tục đề cập
N ( I ' ) = v1 , v2 ,..., vm −t . tới vấn đề tồn tại chu trình Hamilton cho một số lớp đồ thị
tách cực và đã đạt được một số kết quả mới, trong đó kết
Do đó N ( I ' ) = m − t = I ' , mâu thuẫn với Bổ đề 3. quả chính là Định lý 7 (định lý đã chỉ ra một điều kiện cần
và đủ cho một lớp đồ thị tách cực có chu trình Hamilton).
Như vậy, phải tồn tại j 2,3,..., m − t sao cho u −j v j −1 .
3(m − 1) 12 TÀI LIỆU THAM KHẢO
Vì m 5 nên deg ( u j ) với mọi
5 5 [1] M. Behazad and G. Chartrand, 1971. Introduction to the Theory of
j 1, 2,..., m − t , từ đó suy ra rằng deg ( u j ) 3 với mọi
graphs, Allyn and Bacon, Boston.
[2] R.E. Burkard and P.L. Hammer, 1980. “A note on Hamiltonian split
j 1, 2,..., m − t . Nếu um− −t vm −t −1 , thì graphs”. J. Combin. Theory B28, pp. 245 – 248.
[3] V. Chvatal and P.L. Hammer, 1977. “Aggregation of inequalities in
C ' = um −t um− −t −1 Pu1vm −t −1um −t −1vm −t Pvn vm+ −t −1 Pum −t integer programming”. Ann. Discrete Math. 1, pp. 145 – 162.
[4] S. Foldes and P.L. Hammer, 1977. “Split graphs”. In: Proceeding of
là chu trình Hamilton của G, mâu thuẫn. Tiếp theo, nếu the Eighth Southeastern Conference on Combinatorics, Graph
u2− v1 , thì Theory and Computing (Louisiana State University, Baton Rouge,
LA, 1977), Congressus Numerantium, vol. XIX, Utilitas
C ' = u1v2 Pum −t u2− u2 vm −t Pvn u2−− Pu1 Mathematics, Winnipeg, Man., pp. 311 – 315.
[5] S. Foldes and P.L. Hammer, 1978. “On a class of matroid-producing
là chu trình Hamilton của G, mâu thuẫn. Cuối cùng, nếu graphs”. In: Combinatorics (Proceeding of the Filth Hungarian
u −j v j −1 với j 2, m − t , thì Colloquium, Kesrthely, 1976), vol. 1, Colloquium Mathematical
Society, Jano’s Bolyai, vol. 18, North-Holland, Amsterdam, New
York, pp. 331 - 352.
C ' = u j −1v j Pum −t u −j u j vm −t Pvnu −−
j Pv j −1u1 Pu j −1
[6] D. Kratsch, J. Lehel, H. muller, 1996. “Toughness, hamiltonicity and
là chu trình Hamilton của G, mâu thuẫn. split graphs”, Discrete Math. 150, pp. 231 - 245.
[7] J. Peemoller, 1985. “Necessary conditions for Hamiltonian split
Như vậy, ta đã suy ra mâu thuẫn trong tất cả các trường graphs”. Discrete Math. 54, pp. 39 – 47.
hợp. Định lý 7 được chứng minh đầy đủ. ■ [8] U.N. Peled, 1975. Regular Boolean function and their polytope,
Ph.D. Thesis, Department of Combinatorics and Optimization,
4. Kết luận University of Waterloo, Chapter VI.
Vấn đề tồn tại hay không tồn tại chu trình Hamilton [9] Ngo Dac Tan, Le Xuan Hung, 2004. “Hamilton cycles in split graphs
trong đồ thị nói chung và lớp đồ thị tách cực nói riêng là with large minimum degree”. Discussiones Math. Graph Theory 24,
một bài toán khó và luôn là vấn đề thời sự của toán học. pp. 23 – 40.
Việc tìm điều kiện để một đồ thị tách cực có chu trình [10] Ngo Dac Tan, Le Xuan Hung, 2005. “On the Burkard-Hammer
codition for hamiltonian split graphs”. Discrete Math. 296, pp. 59–72.
Hamilton đã được một số nhà toán học quan tâm nghiên
cứu và đã đạt được một số kết quả nhất định. Tuy vậy vấn
(BBT nhận bài: 13/05/2014, phản biện xong: 03/06/2014)
nguon tai.lieu . vn
