Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Luận văn đồ thị nhìn thấy và các vấn đề liên quan...

Tài liệu Luận văn đồ thị nhìn thấy và các vấn đề liên quan

.PDF
46
378
52

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA TOÁN - TIN ĐỖ THỊ TUẤN MINH ĐỒ THỊ NHÌN THẤY VÀ CÁC VẤN ĐỀ LIÊN QUAN Luận văn tốt nghiệp thạc sĩ toán học Chuyên ngành: Hình học và tô pô Mã số: 60.46.01.05 Hà Nội - 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA TOÁN - TIN ĐỖ THỊ TUẤN MINH ĐỒ THỊ NHÌN THẤY VÀ CÁC VẤN ĐỀ LIÊN QUAN Luận văn tốt nghiệp thạc sĩ toán học Chuyên ngành: Hình học và tô pô Cán bộ hướng dẫn: TS. Phạm Hoàng Hà Hà Nội - 2017 LỜI CẢM ƠN Trước khi trình bày nội dung chính của luận văn, tôi xin bày tỏ lòng biết ơn sâu sắc tới TS. Phạm Hoàng Hà người đã trực tiếp hướng dẫn và tận tình chỉ bảo tôi trong suốt quá trình thực hiện luận văn này. Tôi cũng xin bày tỏ lòng biết ơn chân thành, và gửi lời kính chúc sức khỏe đến toàn thể các thầy cô giáo trong khoa Toán - Tin, trường Đại học sư phạm Hà Nội − đã dạy bảo tôi tận tình trong suốt quá trình học tập tại khoa. Nhân dịp này tôi cũng xin được gửi lời cảm ơn chân thành tới gia đình, người thân, bạn bè đã luôn ở bên, cổ vũ, động viên, giúp đỡ tôi trong suốt quá trình học tập và thực hiện luận văn tốt nghiệp. Hà Nội, ngày 15 tháng 03 năm 2017 Học viên Đỗ Thị Tuấn Minh Mục lục 1 2 3 Đồ thị nhìn thấy 7 1.1 Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Một số kết quả . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Đồ thị k-liên thông . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Tính liên thông của đồ thị nhìn thấy 17 2.1 Cạnh liên thông . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Bổ đề cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 Đỉnh liên thông . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 Đỉnh liên thông với giới hạn cộng tuyến . . . . . . . . . . . . . . . 31 Một số vấn đề liên quan đến đồ thị nhìn thấy 39 3.1 Giả thuyết Dirac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 Định lý Beck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 KẾT LUẬN 45 TÀI LIỆU THAM KHẢO 46 4 LỜI MỞ ĐẦU Hình học tổ hợp nghiên cứu sự phân bố, sắp xếp giữa các đối tượng hữu hạn của hình học như sắp xếp các điểm, các đường thẳng, các siêu phẳng... trong không gian Euclid. Hình học tổ hợp có liên quan mật thiết đến các vấn đề khác như các bài toán tô màu, các bài toán tối ưu... Để nghiên cứu hình học tổ hợp, chúng ta cần nắm rõ các kiến thức cơ bản về tôpô, lý thuyết đồ thị, lý thuyết số và các ngành khác. Một trong các nội dung nghiên cứu của hình học tổ hợp là lý thuyết đồ thị, một trường hợp đặc biệt là đồ thị nhìn thấy, nó có rất nhiều ứng dụng trong lĩnh vực hình học tổ hợp và hình học rời rạc. Đồ thị nhìn thấy của một tập hữu hạn các điểm trong mặt phẳng gồm các điểm được gọi là các đỉnh và các đoạn thẳng nối giữa hai đỉnh là các cạnh sao cho nếu đoạn thẳng nối giữa hai đỉnh của đồ thị không chứa các đỉnh khác. Gần đây với việc nhiên cứu đồ thị nhìn thấy, David R. Wood và các đồng sự đã đưa ra được rất nhiều kết quả có giá trị như một khẳng định cho giả thuyết Dirac yếu, các bài toán tô màu... Với mục đích tìm hiểu sâu sắc hơn về đồ thị nhìn thấy, tôi chọn đề tài: " Đồ thị nhìn thấy và các vấn đề liên quan". Luận văn trình bày chi tiết các kết quả nghiên cứu gần đây về đồ thị nhìn thấy và một số ứng dụng của nó trong một số bài toán hình học tổ hợp. Nội dung chính của luận văn bao gồm: Chương 1: Đồ thị nhìn thấy. Trong chương này, tôi trình bày những kiến thức cơ sở lý thuyết đồ thị và đồ thị nhìn thấy như: Các khái niệm về đỉnh, cạnh, bậc của đỉnh, đồ thị vô hướng, có hướng, tính liên thông và các phép toán về đồ thị ... Chương 2: Tính liên thông của đồ thị nhìn thấy. Trong chương này, tôi trình bày chi tiết các kết quả nghiên cứu gần đây về tính liên thông của đồ thị nhìn thấy như: đỉnh- và cạnh- liên thông, giới hạn tốt nhất có thể của đỉnh- và cạnh-liên thông. 5 Chương 3: Một số vấn đề liên quan đến đồ thị nhìn thấy. Trong chương này, tôi trình bày chi tiết các kết quả nghiên cứu gần đây về giả thuyết Dirac và định lý Beck. Mặc dù đã cố gắng hết sức nhưng do thời gian thực hiện luận văn không nhiều nên trong luận văn không thể tránh khỏi những hạn chế và thiếu sót. Tôi rất mong nhận được những góp ý và sự chỉ bảo của các thầy giáo, cô giáo cũng như các anh chị nghiên cứu sinh, các anh chị và các bạn học viên. Tôi xin chân thành cảm ơn! Hà Nội, ngày 15 tháng 03 năm 2017 Học viên Đỗ Thị Tuấn Minh 6 Chương 1 Đồ thị nhìn thấy Trong chương này trình bày hệ thống các kiến thức cơ bản và quan trọng nhất cần sử dụng trong nội dung chính của luận văn như: Các khái niệm về đỉnh, cạnh, bậc của đỉnh, đồ thị vô hướng, có hướng, tính liên thông và các phép toán về đồ thị và đồ thị nhìn thấy nói riêng ... 1.1. Các khái niệm cơ bản Chúng ta bắt đầu bằng việc định nghĩa một số khái niệm sẽ được sử dụng trong toàn luận văn: + Mặt phẳng đề cập tới là mặt phẳng Euclid trong R2 . + Tập hợp hữu hạn các điểm trong mặt phẳng được ký hiệu là P . + Một đường thẳng được gọi là xác định bởi P nếu nó chứa hai điểm thuộc P . + Tập các điểm được gọi là thẳng hàng nếu nó thuộc cùng một đường thẳng, ngược lại ta nói chúng không thẳng hàng. Ta cũng giới thiệu một số kiến thức cơ sở về lý thuyết đồ thị. Định nghĩa 1.1. Đồ thị G = (V, E) bao gồm V là một tập hữu hạn các đỉnh cùng với E là tập hợp gồm 2 phần tử của V gọi là cạnh. Định nghĩa 1.2. Hai đỉnh được gọi là kề nhau nếu chúng được nối bởi một cạnh. 7 Định nghĩa 1.3. Đồ thị được gọi là phẳng nếu trong hình vẽ của nó không có hai cạnh nào cắt nhau (trừ các cạnh chung đỉnh). Định nghĩa 1.4. Cho P là tập hợp hữu hạn điểm. Hai điểm phân biệt v và w là nhìn thấy trong P nếu không có điểm nào thuộc P nằm trong khoảng mở vw. Đồ thị nhìn thấy của P có tập hợp đỉnh là P , 2 đỉnh lúc đó là kề nhau nếu và chỉ nếu nó nhìn thấy trong P . Hình 1.1 là đồ thị nhìn thấy của tập các đỉnh P = { A; B; C; D; E; F } và các cặp đỉnh kề nhau là {( A, B); ( A, D ); ( A, E); ( A, C ); ( F, B); ( F, D ); ( F, E); ( F, C ); ( A, F ); ( B, D ); ( D, E); ( E, C )}. Định nghĩa 1.5. Đồ thị G (V, E) được gọi là đơn đồ thị nếu giữa 2 đỉnh phân biệt u, v của V có nhiều nhất một cạnh trong E nối u và v. Đồ thị G (V, E) được gọi là đa đồ thị nếu giữa 2 đỉnh phân biệt u, v của V có thể có nhiều hơn một cạnh trong E nối u và v (ở đây ta thừa nhận đa đồ thị có thể có vòng). Định nghĩa 1.6. Hai đồ thị G, G’ được gọi là đẳng cấu nếu có một song ánh ϕ : V(G) −→ V(G’) sao cho xy ∈ E( G ) nếu và chỉ nếu ϕ( x ) ϕ(y) ∈ E( G 0 ). Một đồ thị H là đồ thị con của G, ký hiệu H ⊂ G, nếu có một đồ thị H’ đẳng cấu với H sao cho V(H’)⊂ V(G) và E(H’)⊂ E(G). Định nghĩa 1.7. Cho G = (V, E), v ∈ V, ta đặt: N (V ) = {w ∈ V : vw ∈ E} là tập tất cả các đỉnh kề với v (không kể v). Khi đó d(v)=| N (v)| là bậc của v. Ký hiệu δ( G ) là bậc nhỏ nhất của các đỉnh trong G, ∆( G ) là bậc lớn nhất của các đỉnh trong G. 8 Định nghĩa 1.8. Đồ thị G được gọi là liên thông nếu giữa hai đỉnh phân biệt bất kỳ của đồ thị luôn có một đường nối 2 đỉnh ấy. Thành phần liên thông của G là đồ thị con liên thông lớn nhất trong G chứa thành phần ấy. Định nghĩa 1.9. Dưới đây ta nêu ra một số loại đồ thị thường gặp: , Pn có n cạnh và n+1 đỉnh; ta gọi n • Đường của đồ thị Pn có dạng là độ dài của đường. • Chu trình Cn là đồ thị có dạng . Đồ thị Cn có n cạnh và n đỉnh. Bậc của mỗi đỉnh đều bằng 2. Ta gọi n là độ dài của chu trình. • Đồ thị đầy đủ Kn là đồ thị có n đỉnh, tất cả các đỉnh đều là đỉnh kề của nhau. Kn có (n2 ) cạnh. Ví dụ K4 là . • Đồ thị hai phần (bipartite) nếu có một sự phân chia V ( G ) = X ∪ Y sao cho với mỗi cạnh của G có một đỉnh trong X và một đỉnh trong Y; chúng ta gọi sự phân chia đó là sự phân chia hai phần (bipartition). • Đồ thị hai phần đầy đủ Ks,t là đồ thị có V(Ks,t )=X∪ Y. Với |X|=s, |Y|=t, sao cho mỗi đỉnh trong X đều kề với tất cả các đỉnh của Y. Không có cạnh nằm trong X hoặc Y. Ks,t có st cạnh. Ví dụ K2,3 là . 1.2. Một số kết quả Trong phần này, chúng tôi sẽ chứng minh một số kết quả cơ bản về đồ thị. Mệnh đề 1.10. Trong bất kỳ đồ thị nào ta đều có ∑v∈V (G) d(v) = 2| E( G )| Chứng minh. Chúng ta đếm số cặp (v, e) ∈ V ( G ) × E( G ) sao cho v ∈ e. Khi đó, một đỉnh v cho ta d(v) cặp như trên. Nên tổng số cặp trong đồ thị G là ∑v∈V (G) d(v). Mặt khác, mỗi cạnh cho chúng ta 2 cặp (v, e) như trên. Do vậy số cặp tính theo số cạnh bằng 2| E( G )|. Vậy ∑v∈V (G) d(v) = 2| E( G )|. 9 Mệnh đề 1.11. Một đồ thị G với bậc nhỏ nhất δ( G ) > 2 chứa một đường có độ dài ít nhất bằng δ( G ) và một chu trình có độ dài ít nhất bằng δ( G ) + 1. Chứng minh. Lấy v1 v2 . . . vk là đường lớn nhất trong G, theo nghĩa: đường này không thể mở rộng thêm. Khi đó tất cả các đỉnh kề với v1 đều phải nằm trên đường này, nếu không thì chúng ta có thể mở rộng nó. Từ v1 có ít nhất δ( G ) đỉnh kề, nên tập {v2 , v3 ,. . . , vk } chứa ít nhất δ( G ) thành phần. Do đó k > δ( G ) + 1. Vì vậy đường trên có độ dài ít nhất bằng δ( G ). Làm tương tự với cách chứng minh trên với chu trình. Đỉnh kề với v1 , đỉnh mà xa nhất thuộc đường phải là vi với i > δ( G ) + 1. Như vậy v1 v2 . . . vi v1 là chu trình có độ dài ít nhất bằng δ( G ) + 1. Mệnh đề 1.12. Bất kỳ đồ thị G nào đều chứa một đồ thị con hai phần H với | E( H )| > | E( G )|/2. Chứng minh. Chúng ta chứng minh kết quả mạnh hơn là: G có một đồ thị con hai phần với V ( H ) = V ( G ) và d H (v) > dG(v) /2 cho tất cả các đỉnh v ∈ V ( G ). Bắt đầu với một sự phân chia tùy ý V ( G ) = X ∪ Y (việc phân chia này không cần là sự phân chia hai phần (bipartition) của G), chúng ta thực hiện theo phương pháp sau. Chúng ta quy cho X và Y như những "đường". Với bất kỳ đỉnh v ∈ V ( G ), chúng ta xem đỉnh đó có nhiều cạnh tới X hay tới Y hơn; nếu có nhiều cạnh kết nối nó với các đỉnh trong cùng một thành phần hơn các cạnh tới thành phần khác, thì chúng ta di chuyển đỉnh đó tới thành phần khác. Chúng ta lặp lại việc này cho tới khi không còn đỉnh nào bị di chuyển. Có nhiều nhất |V ( G )| các bước liên tiếp mà không có đỉnh nào bị di chuyển, từ đó nếu không đỉnh nào có thể bị di chuyển, thì chúng ta đã hoàn thành. Chúng ta di chuyển một đỉnh từ phần này sang phần khác và làm tăng lên số cạnh giữa X và Y (chú ý rằng một đỉnh có thể di chuyển trở lạị và ra giữa X và Y, nhưng vẫn làm tăng tổng số cạnh giữa X và Y trong mỗi bước). Điều này chỉ ra rằng thuật toán có tính dừng vì số cạnh trong đồ thị là hữu hạn. Khi thuật toán dừng, mỗi đỉnh của X có ít nhất nửa số cạnh của nó tới Y, và tương tự, với mỗi đỉnh trong Y 10 có ít nhất nửa số cạnh của nó tới X. Như vậy, đồ thị H với V(H)=V(G) và E(H)= { xy ∈ E( G ) : x ∈ X, y ∈ Y } có tính chất | E( H )| > | E( G )|/2. Mệnh đề 1.13. Một đồ thị là hai phần nếu và chỉ nếu nó không chứa chu trình lẻ (với chu trình lẻ là chu trình có độ dài lẻ). Chứng minh. Giả sử G là đồ thị hai phần với sự phân chia hai phần V ( G ) = X ∪ Y, và v1 . . . vk v1 là một chu trình của G, với v1 ∈ X. Ta phải có vi ∈ X với tất cả các i lẻ và vi ∈ Y với tất cả các i chẵn. Do vk kề với v1 nên nó phải thuộc Y, vì vậy k là số chắn và chu trình này là không lẻ. Giả sử rằng chúng ta có một đồ thị G liên thông, không có chu trình lẻ. Chúng ta có thể thiết lập được một sự phân chia hai phần bằng cách sử dụng thuật toán sau. Bắt đầu với X, Y là các tập rỗng. Đặt một đỉnh tùy ý x0 vào trong X. Đặt tất cả các đỉnh kề với x0 vào trong Y. Với mỗi đỉnh y ∈ Y, đặt vào trong X tất cả những đỉnh kề với y, những đỉnh mà chưa đươc chỉ định. Sau đó với mỗi x ∈ X, đặt trong Y tất cả các đỉnh kề với nó (những đỉnh mà chưa được chỉ định). Lặp lại điều này cho tới khi tất cả các đỉnh trong G đều được xác định nằm trong hoặc X hoặc Y. Thuật toán này là đúng đắn bởi vì không có đỉnh nào được chỉ định nhiều hơn một lần (vì trong thuật toán chỉ xem xét đối với những đỉnh chưa được chỉ định). Điều còn lại cần chỉ ra rằng thuật toán là dừng (nghĩa là nó không tiến hành một cách vô tận), và kết quả thu được thực sự là sự phân chia hai phần của V ( G ). Thuật toán này có tính dừng vì G là liên thông (theo giả sử). Thậy vậy, điều này có nghĩa rằng với mỗi y ∈ Y có một đường yv1 . . . vk x0 tới x0 , và với mỗi bước có ít nhất một đỉnh khác từ đường này phải được chỉ định. Tiếp theo, chúng ta chỉ ra rằng V ( G ) = X ∪ Y là một sự phân chia hai phần. Giả sử rằng có hai đỉnh x1 , x2 ∈ X là liền kề. Theo cách xây dựng, có một đường P từ x1 tới x0 chỉ chứa các cạnh giữa X và Y, và tương tự, có một đường P0 từ x2 tới x0 ; chú ý rằng các đường này có thể giao nhau, vì vậy hợp của chúng không phải một đường. Lấy x3 là đỉnh đầu tiên mà P giao với P0 (có thể là x0 ). Sau đó 11 chúng ta lấy đường P” từ x1 qua x3 tới x2 , đường này cũng có tính chất là tất cả các cạnh của nó đều là cạnh giữa X và Y. Từ đó, đường này đi từ X vào X chỉ chứa các cạnh giữa X và Y, nó phải có số cạnh chẵn. Như vậy, nếu ta phối hợp với cạnh x1 x2 chúng ta có một chu trình lẻ, điều này mâu thuẫn. Tương tự, nếu y1 , y2 ∈ Y liền kề. Điều này chỉ ra rằng tất cả các cạnh trong G đều là cạnh giữa X và Y, vì vậy G là đồ thị hai phần. Chúng ta đã giả sử rằng G là liên thông. Nếu G không liên thông, chúng ta có thể áp dụng chứng minh trên cho từng thành phần liên thông của G, và kết hợp tùy ý sự phân chia hai phần của các thành phần liên thông đó cho ta sự phân chia hai phần của G. 1.3. Đồ thị k-liên thông Trước khi nghiên cứu về đồ thi k- liên thông, chúng ta chứng minh một công cụ quan trong, là chìa khóa cho các tính chất chung này. Đó là định lý của Menger. Định nghĩa 1.14. Cho hai tập hợp điểm A,B ⊂ V ( G ), chúng ta gọi một AB-đường nếu một đỉnh cuối của nó nằm trong A, đỉnh cuối còn lại nằm trong B, và không có đỉnh nào khác nằm trong A hoặc B. Nếu x ∈ A ∩ B thì ta xem như bản thân x cũng là một AB-đường. Chúng ta gọi một tập S ⊂ V ( G ) sao cho mọi AB- đường đều giao với S là một AB-separator. Định lý 1.15. (Menger). Cho G là một đồ thị và A, B ⊂ V ( G ). Số lượng tối đa của các AB-đường rời nhau bằng lực lượng nhỏ nhất của tập S ⊂ V ( G ) sao cho mọi AB-đường chứa 1 đỉnh của S. Chứng minh. Gọi s là lực lượng nhỏ nhất của một AB-separator. Với bất kỳ tập các AB-đường rời nhau chứa nhiều nhất s đường, vì nếu không thì một separator lực lượng s không thể cắt tất cả các đường. Chúng ta phải chỉ ra rằng tồn tại một tập hợp gồm s AB-đường rời nhau. Chúng ta sẽ chứng minh bằng quy nạp theo 12 | E( G )|. Khi | E( G )| = 0 thì AB-separator nhỏ nhất chỉ là bản thân A ∩ B, vì vậy, ta có s = | A ∩ B| và s đỉnh trong A ∩ B là s AB-đường rời nhau. Giả sử rằng | E( G )| > 1 và lấy xy là cạnh bất kỳ trong E( G ). Chúng ta khẳng định rằng nếu G không có s AB-đường rời nhau thì G có một AB-separator lực lượng s chứa cả x và y. Đầu tiên chúng ta chứng minh định lý dựa vào khẳng định này, sau đó chúng ta sẽ chứng minh khẳng định đó. Xét đồ thị G-xy, trong đó S là một AB-separator. Xét một AS-separator R trong G-xy. Nhận thấy rằng, mọi AB-đường trong G chứa một AS-đường trong G-xy (điều này có thể sai nếu ta không có x, y ∈ S), do R cũng là một AB-separator trong G, ngụ ý rằng | R| > s. Nó cho thấy rằng lực lượng nhỏ nhất của một ASseparator trong G-xy ít nhất bằng s. Bằng quy nạp, điều này chỉ ra rằng G-xy có s AB-đường rời nhau. Các AS-đường và SB-đường không giao nhau ngoài S, từ đó ta nhận được một AB-đường tránh S. Do |S|=s, ta có thể liên kết s AS-đường với s SB-đường được s AB-đường rời nhau. Việc còn lại là chứng minh khẳng định: Nếu G không có s AB-đường rời nhau thì G có một AB-separator S lực lượng bằng s chứa cả x và y. Ta liên kết xy để có được đồ thị G-xy. Điều này có nghĩa là chúng ta bỏ xy và định nghĩa x và y như một đỉnh v xy . Chính xác hơn, chúng ta loại bỏ x,y và tất cả các cạnh kề với nó, thêm vào đỉnh mới v xy , và ta liên kết v xy với tất cả các đỉnh trước đây kề với x hoặc y (hoặc cả hai). Sau đó ta đặt A’=(A\{ x, y}) ∪ {v xy }. Ta làm tương tự với tập B để nhận được tập B’. Một A’B’-đường P trong G-xy tương ứng với một hoặc nhiều AB-đường trong G. Nếu v xy không nằm trên P thì P là một AB-đường trong G; Nếu v xy nằm trên P thì có thể có nhiều hơn một cách sửa đổi P thành một AB-đường trong G. Ngược lại, một AB-đường trong G tương ứng với một A’B’-đường trong G-xy. Cũng chú ý rằng các A’B’-đường rời nhau trong G-xy tương ứng với các AB-đường rời nhau trong G. Theo Giả thiết, G không có s AB-đường rời nhau, vì vậy G-xy cũng không 13 có s A’B’-đường rời nhau. Bằng phương pháp quy nạp (cho cả định lý, không phải chỉ cho khẳng định trên). Điều này chỉ ra rằng lực lượng nhỏ nhất của một A’B’-separator trong G-xy nhiều nhất bằng s-1, vì vậy G-xy có một A’B’-separator S’ có lực lượng nhiều nhất bằng s-1. Ta phải có v xy ∈ S0 , mặt khác S’ là một ABseparator trong G mà nhỏ hơn AB-separator nhỏ nhất (do mỗi AB-đường trong G cho tương ứng một A’B’-đường trong G-xy). Đặt S = (S0 \{v xy }) ∪ { x, y}, S là một AB-separator trong G lực lương bằng s và chứa x,y. Hệ quả 1.16. Cho G là một đồ thị và x, y ∈ V ( G ) là 2 điểm phân biệt sao cho xy ∈ / E( G ). Số lượng lớn nhất các đường bên trong rời nhau từ x tới y bằng lực lượng nhỏ nhất của tập S ⊂ V ( G )\{ x, y} thỏa mãn tính chất mọi đường từ x đến y chứa một đỉnh của S. Chứng minh. Áp dụng định lý 1.15 với A=N(x), B=N(y) (với N(x), N(y) lần lượt là tập tất cả các đỉnh kề với x,y). Chú ý rằng việc thêm đỉnh x,y vào AB-đường cho ta một đường từ x tới y, nhưng việc loại bỏ x và y từ một đường giữa x và y có thể không cho ta một AB-đường, bởi vì một đường giữa x và y có thể qua nhiều hơn một đỉnh kề của x hoặc y. Tuy nhiên, mỗi đường giữa x và y chứa một đường con là một AB-đường, vì vậy số lượng lớn nhất của các đường bên trong rời nhau từ x đến y bằng số AB-đường rời nhau. Theo định lý 1.15, số lượng lớn nhất các đường bên trong rời nhau từ x tới y bằng lực lượng nhỏ nhất của tập hợp S ⊂ V ( G ) sao cho mọi AB-đường đều giao với S. Bất kỳ tập S nào đều có tính chất mọi đường từ x tới y đều chứa một đỉnh của S. Việc còn lại là chỉ ra rằng tập bé nhất S này không chứa x hoặc y. Giả sử S chứa x và mọi AB-đường đều giao với S, khi đó ta cũng có điều tương tự với tập S\{ x }, từ đó đường đi từ B đến A qua x chứa một đường con từ B đến A không chứa x, và đường con này phải chứa một vài đỉnh khác của S. Cho đồ thị G, S ⊂ G, G − S là đồ thị con của G có được bằng cách bỏ đi những đỉnh thuộc S và tất cả các cạnh là kề với bất cứ đỉnh nào của S. 14 Định nghĩa 1.17. Một đồ thị G được gọi là k-liên thông nếu |V ( G )| ≥ k và với mỗi tập S ⊂ V ( G ) mà |S| = k − 1 thì G-S là liên thông. Chú ý rằng đồ thi 1-liên thông là liên thông, trừ trường hợp |V ( G )| = 1. Định lý 1.18. Một đồ thị G là k- liên thông nếu và chỉ nếu với bất kỳ hai đỉnh phân biết x,y ∈ V ( G ) có k đường liên kết nội bộ từ x đến y trong G. Chứng minh. Nếu G có k đường liên kết nội bộ giữa hai đỉnh bất kỳ, thế thì ta phải có |V ( G )| ≥ k, và sau khi bỏ đi k-1 đỉnh, với hai đỉnh bất kỳ vẫn liên thông bởi một trong k đường, vì vậy G là k-liên thông. Ngược lại, Giả sử G là k-liên thông và G chứa hai điểm x,y mà chúng không được liên kết bởi k đường bên trong rời nhau. Nếu xy ∈ / E( G ), theo hệ quả 1.16 có k-1 đỉnh, những đỉnh mà loại bỏ liên kết x với y, mâu thuẫn với định nghĩa k-liên thông. Như vậy chúng ta có thể giả sử rằng xy ∈ E( G ). Theo giả thiết, bất kỳ tập các đường bên trong rời nhau liên kết giữa x và y có lực lượng nhiều nhất bằng k-1. Hơn nữa, bất kỳ tập lớn nhất nào như vậy đều chứa đường xy, vì nếu không chúng ta có thể cộng thêm vào nó. Như vậy G-xy có nhiều nhất k-2 đường bên trong rời nhau từ x tới y. Theo hệ quả 1.16, có một tập S ⊃ V ( G )\{ x, y} lực lượng bằng k-2 sao cho mọi đường từ x tới y đều giao với S. Chúng ta có |S ∪ { x, y}| = k và |V ( G )| > k, vì vậy tồn tại một đỉnh z ∈ / S ∪ { x, y}. Trong G-xy, S phải tránh z tới hoặc x hoăc y, mặt khác có một đường từ x tới y tránh S. Điều đó nói rằng S tránh z từ x; thì S ∪ {y} là tập của nhiều nhất k-1 đỉnh mà chúng tránh z từ x trong G, mâu thuẫn với tính k-liên thông của G. Định nghĩa 1.19. Đặc trưng liên thông conn(G) của một đồ thị G là số lớn nhất k sao cho G là k-liên thông. Chúng ta có conn(Cn )=2, conn(Kn )=n-1 với n > 3, conn(GP )=3 với GP là đồ thị Petersen (đồ thị có 10 đỉnh, 15 cạnh, mỗi cạnh có bậc bằng 3, đường kính bằng 2 và chu trình nhỏ nhất bằng 5). Chú ý rằng conn(G)6 δ( G ), từ đó nếu x là một 15 đỉnh có d( x ) = δ( G ), thì N ( x ) là tập gồm δ( G ) đỉnh sao cho G − N ( x ) là không liên thông. 16 Chương 2 Tính liên thông của đồ thị nhìn thấy Trong chương này chúng tôi nghiên cứu về cạnh- và đỉnh-liên thông của đồ thị nhìn thấy. Đồ thị G với ít nhất k+1 đỉnh là k-đỉnh-liên thông (k-cạnh-liên thông) nếu G giữ nguyên tính liên thông mỗi khi ít hơn k đỉnh (cạnh) bị xóa đi. Như đã biết trong chương 1, định lý của Menger nói rằng điều này tương đương với sự tồn tại của k đường gồm các đỉnh-rời nhau (cạnh- rời nhau) giữa mỗi cặp đỉnh. Đặt κ(G) và λ(G) là đỉnh- và cạnh-liên thông của đồ thị G. Với δ(G) là bậc nhỏ nhất của G, khi đó κ ( G ) 6 λ( G ) 6 δ( G ). Nếu một đồ thị nhìn thấy G có n đỉnh, với nhiều nhất ` đỉnh thẳng hàng thì δ( G ) > n −1 `−1 . Chúng ta sẽ chỉ ra cả cạnh- và đỉnh-liên thông ít nhất bằng (định lý 2.4 và hệ quả 2.15). Từ đó ta có đồ thị nhìn thấy với δ = n −1 `−1 n −1 `−1 là giới hạn dưới tốt nhất có thể. Chúng ta đề cập tới đồ thị nhìn thấy mà các đỉnh của nó không phải tất cả thẳng hàng là đồ thị nhìn thấy không-cộng tuyến. Đồ thị nhìn thấy không-cộng tuyến có đường kính bằng 2[4] (với đường kính của một đồ thị là độ dài đường đi ngắn nhất giữa hai đỉnh xa nhất của đồ thị), và được biết rằng đồ thị có đường kính bằng 2 có cạnh-liên thông bằng bậc nhỏ nhất của chúng. Chúng ta củng cố kết quả này để chỉ ra rằng nếu một đồ thị có đường kính bằng 2 thì với bất kỳ 2 đỉnh v và w mà deg(v) 6 deg(w), có deg(v) cạnh-rời nhau vw-đường với độ dài nhiều nhất bằng 4 (định lý 2.2). Chúng ta cũng mô tả cạnh cắt tối thiểu của đồ thị nhìn thấy như tập các cạnh kề với một đỉnh có bậc nhỏ nhất (định lý 2.6). 17 Với việc quan tâm tới đỉnh-liên thông, kết quả chính của chúng ta là κ > δ 2 đối với tất cả đồ thị nhìn thấy không cộng tuyến (định lý 2.11). Giới hạn này mạnh hơn giới hạn κ > n −1 `−1 . Trong trường hợp đặc biệt có nhiều nhất 4 điểm thẳng hàng chúng ta cải tiến giới hạn này tới κ > đoán rằng κ > 2δ+1 3 2δ+1 3 (định lý 2.18). Chúng ta phỏng đối với mọi đồ thị nhìn thấy. Giới hạn này là tốt nhất có thể vì với mỗi số nguyên k, có một đồ thị nhìn thấy với kích thước đỉnh cắt bằng 2k+1, nhưng bậc nhỏ nhất bằng 3k+1. Bởi vậy đỉnh-liên thông nhiều nhất bằng 2k+1= 2δ3+1 . Hình 2.1 chỉ ra trong trường hợp k=4. Hình 2.1: Một đồ thị nhìn thấy với đỉnh-liên thông 2δ+1 3 . Các đỉnh đen là tập đỉnh bị cắt bỏ. Bậc nhỏ nhất δ = 3k + 1 là đạt được, với ví dụ này, tại tất cả các đỉnh phía trên bên trái. Không phải tất cả các cạnh được vẽ. Một công cụ quan trọng trong chương này, cái mà cũng được quan tâm độc lập, là một loại đồ thị nhìn thấy hai phần. Cho A và B là 2 tập hợp các điểm rời nhau trong mặt phẳng. Đồ thị nhìn thấy hai phần B( A, B) của A và B có tập đỉnh là A ∪ B, ở đây một đỉnh v ∈ A và w ∈ B được gọi là kề nhau nếu và chỉ nếu chúng là nhìn thấy trong mối quan hệ A ∪ B. Quan sát dưới đây được sử dụng 18 vài lần trong chương này và nhấn mạnh tầm quan trong của đồ thị nhìn thấy hai phần. Quan sát 2.1. Cho G là một đồ thị nhìn thấy. Lấy { A, B, C } là một sự phân chia của V(G) sao cho C tách rời A và B. Nếu B( A, B) gồm t cặp cạnh không giao nhau, thì |C | > t bởi vì phải có một đỉnh riêng biệt trong C trên mỗi cạnh đó. Cuối cùng, một bổ đề giữ vị trí đặc biệt được quan tâm độc lập. Bổ đề 2.7 nói rằng với bất kỳ đồ thị hình học không có giao điểm với tính chất 2 màu chúng được tách bởi một đường thẳng (trừ một vài trường hợp suy biến), tồn tại một cạnh ra nhập chúng sao cho sự hợp nhất này là đồ thị hình học không có giao điểm được tô màu thực sự. 2.1. Cạnh liên thông Định lý 2.2. Cho G là đồ thị với đường kính bằng 2. Khi đó cạnh-liên thông của đồ thị G bằng bậc nhỏ nhất của nó. Hơn nữa, với 2 đỉnh phân biệt v và w trong G, nếu d := min{deg(v), deg(w)} thì có d cạnh-rời nhau vw-đường có độ dài nhiều nhất bằng 4, bao gồm ít nhất một đường có chiều dài nhiều nhất bằng 2. Chứng minh. Đầu tiên giả sử v, w là các đỉnh không liền kề. Đặt C là tập các đỉnh chung kề với v và w. Với mỗi đỉnh c ∈ C, lấy đường (v, c, w). Đặt A là tập gồm d − |C | các đỉnh kề với v không nằm trong C. Đặt B là tập gồm d − |C | đỉnh kề với w không nằm trong C. Đặt M1 là đồ thị con 2 phần lớn nhất tao ra bởi A và B. Gọi các đỉnh tương ứng của M1 từ A, B là A1 và B1 . Với mỗi cạnh ab ∈ M1 , lấy đường (v, a, b, w). Đặt A2 , B2 tương ứng là tập con của A, B chứa các đỉnh còn lại. Đặt D := V ( G )\( A2 ∪ B2 ∪ {v, w}). Đặt M2 là cặp đỉnh tùy ý trong A2 và B2 . Với mỗi cặp ab ∈ M2 , lấy đường (v, a, x, b, w), ở đây x là đỉnh kề chung của a và b (điều này tồn tại vì G có đường kính bằng 2). Từ x liền kề với a, x 6= w, và do tính lớn nhất của M1 nên x ∈ / B2 . Tương tự x 6= v và x ∈ / A2 , vì vậy x ∈ D . Như vậy có 3 loại đường (v, C, w), (v, A1 , B1 , w), (v, A2 , D, B2 , w). Các đường 19 trong mỗi loại có cạnh-rời nhau. Mặc dù D chứa A1 , B1 , các cạnh giữa mỗi cập các tập từ { A1 , B1 , A2 , B2 , C, D, {v}, {w}} xảy ra ở nhiều nhất một loại, và tất cả các cạnh được tạo bởi các tập phân biệt của các tập hợp trên. Tổng số đường là |C | + | A1 | + | A2 | = d. Điều này kết thúc chứng minh định lý trong trường hợp v, w không liền kề. Nếu G chứa cạnh vw thì làm lại như trên sau khi chúng ta loại bỏ cạnh vw, ta tìm được d − 1 đường. Chú ý rằng độ dài các đường tìm thấy trong định lý 2.2 không thể cải thiện thêm, ví dụ sau sẽ chỉ ra điều đó. Cho các số nguyên γ > 2 và δ > 3, lấy G là đồ thị dạng 5-chu trình (v, w, x, y, z) và thay thế x bởi một tập X gồm δ − 1 điểm, thay thế y bởi một tập gồm γ điểm, thay thế z bởi một tập Z gồm δ − 1 điểm. Thay thế các cạnh giữa các đỉnh đó bằng đồ thị con hai phận đầy đủ giữa các tập đỉnh tương ứng. Mỗi đỉnh trong X liền kề với w và mọi đỉnh trong Y, mỗi đỉnh trong Z là liền kề với v và mọi định trong Y. Như vậy G có bậc nhỏ nhất bằng δ và đường kính bằng 2. Chú ý rằng deg(v) = deg(w) = δ. Thực tế ta có thể chọn γ lớn để chỉ các đỉnh v, w có bậc bằng δ còn các đỉnh khác bậc đều lớn hơn δ. Xét tập S gồm δ đường có các cạnh-rời nhau giữa v và w. Một đường trong S là cạnh vw, trong khi đó các đường còn lại có độ dài ít nhất bằng 4. Như vậy các đường được tìm thấy trong định lý 2.2 là tốt nhất có thể. Một ví dụ thêm nữa, trong trường hợp v, w không liền kề, có thể được xây dựng bởi hai tập gồm (δ + 1)-đỉnh rời nhau và xác định một đỉnh trong mỗi tập. Khi đó có δ − 1 vw-đường có độ dài bằng 4 và một đường có độ dài bằng 2. Cách khác, có thể lấy δ − 2 vw-đường có độ dài bằng 4 và 2 đường có độ dài bằng 3. Định lý 2.2 cho ta hệ quả sau đối với đồ thị nhìn thấy. Hệ quả 2.3. Cho G là đồ thị nhìn thấy với đường kính bằng 2. Khi đó cạnh-liên thông của đồ thị G bằng bậc nhỏ nhất của nó. Hơn nữa, với 2 đỉnh phân biệt v và w trong G, nếu d := min{deg(v), deg(w)} thì có d cạnh-rời nhau vw-đường có độ dài nhiều nhất bằng 4, bao gồm ít nhất một đường có chiều dài nhiều nhất bằng 2. 20
- Xem thêm -

Tài liệu liên quan