Về chu trình Hamilton trong đồ thị tách cực

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

18
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Khái niệm đồ thị tách cực được định nghĩa vào năm 1977 bởi S. Foldes và P.L. Hammer. Các đồ thị này đã và đang được 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. Mặt khác, một trong những vấn đề cơ bản của lý thuyết đồ thị là bài toán Hamilton.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Về chu trình Hamilton trong đồ thị tách cực

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 vK , G −v has a Hamilton path. có chu trình Hamilton khi và chỉ khi khi với mọi vK , đồ 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. ' 4n 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 6n 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 )  uI ' 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)