Tài liệu Phổ đồ thị và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN PHẠM VĂN QUANG PHỔ ĐỒ THỊ VÀ ỨNG DỤNG Chuyên ngành: Phương pháp toán sơ cấp Mã số: 60460113 LUẬN VĂN THẠC SỸ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. LÊ ANH VINH HÀ NỘI−2017 2 LỜI CẢM ƠN Trước khi trình bày nội dung chính của khóa luận, em xin bày tỏ lòng biết ơn sâu sắc tới PGS. TS. Lê Anh Vinh, người đã tận tình hướng dẫn để em có thể hoàn thành luận văn này. Em cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong khoa Toán - Cơ - Tin học, Đại học Khoa Học Tự Nhiên, Đại Học Quốc Gia Hà Nội đã dạy bảo em tận tình trong suốt quá trình học tập tại khoa. Nhân dịp này em cũng xin gửi lời cảm ơn chân thành tới Trường Trung học phổ thông Khoa Học Giáo Dục - Đại học Khoa học Giáo dục - Đại học Quốc Gia Hà Nội đã tạo điều kiện giúp đỡ trong quá trình hoàn thành chương trình đào tạo và hoàn thiện luận văn này. Hà Nội, ngày 07 tháng 04 năm 2017 Học viên Phạm Văn Quang 1 Mục lục Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Chương 1. Phổ của đồ thị 1.1 Khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Một số khái niệm khác . . . . . . . . . . . . . . . . . . . . . . . 1.3 Một vài kết quả từ đại số tuyến tính . . . . . . . . . . . . . . . 3 3 8 13 Chương 2. Phổ và các phép toán đồ thị 25 2.1 Phần bù, hợp và nối các đồ thị . . . . . . . . . . . . . . . . . . 25 2.2 Phổ của các đồ thị đặc biệt . . . . . . . . . . . . . . . . . . . . 31 Chương 3. Một số ứng dụng của phổ đồ thị 35 3.1 Ứng dụng trong đếm số đồ thị con . . . . . . . . . . . . . . . . 35 3.2 Ứng dụng xác định bậc chính quy và tính hai phần . . . . . . . 38 3.3 Ứng dụng xác định tính liên thông . . . . . . . . . . . . . . . . 42 3.4 Ứng dụng của giá trị phổ lớn thứ 2 . . . . . 3.4.1 Giá trị riêng lớn thứ hai . . . . . . . 3.4.2 Giá trị riêng với môđun lớn thứ hai . 3.5 Phổ đồ thị và bài toán của Richard Brualdi 3.5.1 Đối phổ của đồ thị theo chuẩn `pn . . 3.5.2 Đối phổ của đồ thị hai phần đầy đủ . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 44 46 47 50 52 55 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2 LỜI NÓI ĐẦU Trong toán học và tin học, lý thuyết đồ thị là lĩnh vực nghiên cứu rất quan trọng và có nhiều ứng dụng. Trong thực tế có nhiều bài toán như mạng lưới liên kết website, mạng lưới giao thông, ... có thể biểu diễn bởi một cấu trúc đồ thị nào đó. Do vậy, sự phát triển của các thuật toán xử lý đồ thị là một trong các mối quan tâm chính của khoa học máy tính và toán học ứng dụng. Một trong những kết quả đầu tiên trong lý thuyết đồ thị xuất hiện trong bài báo của Leonhard Euler về Bảy cây cầu ở Königsberg, xuất bản năm 1736. Bài báo này cũng được xem như một trong những kết quả tôpô đầu tiên trong hình học, tức là, nó không hề phụ thuộc vào bất cứ độ đo nào. Nó diễn tả mối liên hệ sâu sắc giữa lý thuyết đồ thị và tôpô học. Năm 1852, Francis Guthrie đưa ra bài toán bốn màu về vấn đề liệu chỉ với bốn màu có thể tô màu một bản đồ bất kì sao cho không có hai nước nào cùng biên giới được tô cùng màu. Bài toán này được xem như đã khai sinh ra lý thuyết đồ thị, và chỉ được giải sau một thế kỉ vào năm 1976 bởi Kenneth Appel và Wolfgang Haken. Trong khi cố gắng giải quyết bài toán này, các nhà toán học đã tạo ra nhiều thuật ngữ và khái niệm nền tảng cho lý thuyết đồ thị. Việc ứng dụng rộng rãi trong khoa học kĩ thuật khiến cho lí thuyết định tính của đồ thị ngày càng phát triển hơn những năm sau đó. Lí thuyết phổ của đồ thị là một trong những khái niệm quan trọng cho biết được nhiều thông tin về đồ thị. Trong luận văn này, ta tập trung tìm hiểu khái niệm này với nội dung chính được tham khảo trong tài liệu [1], [11] và [12]. Bố cục luận văn gồm phần mở đầu, ba chương, phần kết luận và danh mục tài liệu tham khảo. Chương 1 dành để trình bày một vài khái niệm cơ bản về lí thuyết phổ của đồ thị. Chương 2 đề cập tới kết quả về phổ của đồ thị và các phép toán trên đồ thị. Chương 3 dành để nêu lại một số ứng dụng phổ của đồ thị trong việc xác định tính chất định tính của đồ thị đó. Hà Nội, ngày 07 tháng 11 năm 2017 Phạm Văn Quang 3 Chương 1 Phổ của đồ thị Mục đích chính của chương này nhằm giới thiệu một vài khái niệm cơ bản của lí thuyết đồ thị, đặc biệt là phổ của đồ thị.Các định nghĩa chính dưới đây của chương được tham khảo chủ yếu trong sách của D. Cvetkovic, P. Rowlinson, S. Simic [1]. 1.1 Khái niệm cơ bản Cho G là một đơn đồ thị vô hướng hữu hạn và không có khuyên. Giả sử các đỉnh của G được gán nhãn là 1, 2, . . . , n. Nếu đỉnh i và j được nối với nhau bởi một cạnh thì ta nói i và j kề nhau và viết i ∼ j. Trước hết ta xem xét ma trận kề A của đồ thị G được định nghĩa như sau: A = A(G) = (aij ), trong đó aij = 1 nếu i ∼ j và bằng 0 trong các trường hợp khác. Do đó A là ma trận đối xứng với các phần tử trên đường chéo chính bằng 0, các phần tử khác có thể lấy các giá trị là 0 và 1 trong trường hợp bất kỳ, tuy nhiên xuyên suốt luận văn này các phần tử được xem là các số thực. Một ví dụ về đồ thị và ma trận kề của nó được cho trong Hình 1.1. Hình 1.1: Một đồ thị được gán nhãn G và ma trận kề A của nó. Các giá trị riêng của A là các số thực λ thỏa mãn Ax = λx với véc tơ khác 4 không x ∈ Rn . Mỗi véc tơ x được gọi là một véc tơ riêng của ma trận A (hay của đồ thì được gán nhãn G) tương ứng với giá trị riêng λ. Quan hệ Ax = λx có thể được mô tả theo cách sau: nếu x = (x1 , x2 , . . . , xn )T thì X xv (u = 1, 2, . . . , n), (1.1) λxu = v∼u trong đó tổng lấy qua tất cả các đỉnh kề v của đỉnh u. Chúng ta chú ý hai hệ quả sau từ phương trình trên mà ta gọi là các phương trình giá trị riêng của G. Vì A là một ma trận đối xứng thực, các giá trị riêng là những số thực. Chúng ta thường ký hiệu các giá trị riêng là λ1 , λ2 , . . . , λn và trừ khi chúng ta chỉ ra trong những trường hợp khác, chúng ta giả sử rằng λ1 ≥ λ2 ≥ · · · ≥ λn . Khi cần, chúng ta sử dụng ký hiệu λi = λi (G) (i = 1, 2, . . . , n). Định nghĩa 1.1.1. Tập các giá trị riêng của ma trận kề A của đồ thị G được gọi là phổ của đồ thị G. Giá trị riêng lớn nhất λ1 (G) được gọi là chỉ số (index) của G. Với mọi số Pn nguyên k ≥ 0, moment phổ thứ k của G là i=1 λki ký hiệu bởi sk . Chú ý rằng sk là tổng đường chéo của Ak và n moment phổ đầu tiên xác định phổ của G. Mệnh đề 1.1.2. Nếu đồ thị G có bậc lớn nhất là ∆(G) thì |λ| ≤ ∆(G) với mọi giá trị riêng λ của G. Chứng minh. Với ký hiệu ở trên, đặt u là một đỉnh mà |xu | là cực đại. Sử dụng Phương trình (1.1), chúng ta có: X |λ||xu | ≤ |xu | ≤ |∆(G)||xu |. v∼u Vì xu 6= 0, mệnh đề được chứng minh. Mệnh đề 1.1.3. Đồ thị G là chính quy bậc r nếu và chỉ nếu tất cả các véc tơ 1 là một véc tơ riêng của G (với giá trị riêng tương ứng r). Nếu λ là một giá trị riêng của A thì tập {x ∈ Rn : Ax = λx} là một không gian con của Rn gọi là không gian riêng của λ và ký hiệu bởi ε(λ) hoặc εA (λ). Các không gian riêng của λ được gọi là các không gian riêng của G. Tất nhiên, việc gán nhãn các đỉnh của G sẽ dẫn đến một hoán vị của các tọa độ trong 5 véc tơ riêng (và các không gian riêng). Vì A là ma trận đối xứng nên nó có thể chéo hóa bởi một ma trận trực giao. Vì vậy không gian riêng là các trực giao từng đôi một và bằng cách ghép với các cơ sở trực chuẩn của các không gian riêng chúng ta thu được một cơ sở trực chuẩn của Rn gồm các véc tơ riêng. Ngoài ra, số chiều của εA (λ) bằng bội của λ như một nghiệm của PG (x). Nói cách khác, bội hình học (geometry multiplicity) của λ tương tự như bội đại số của λ; do đó chúng ta chỉ đề cập đến bội của λ. Một giá trị riêng đơn là một giá trị riêng có bội 1. Nếu G có các giá trị riêng phân biệt µ1 , . . . , µm tương ứng với các bội k1 , . . . , km , chúng ta sẽ viết µ1k1 , . . . , µkmm là phổ của G. (Chúng ta thường bỏ sót trường hợp Ki bằng 1). Ví dụ 1.1.4. Cho đồ thị G  x   −1  PG (x) =  0  −1  −1 trong Hình 1.1, ta có  −1 0 −1 −1  x −1 0 −1  −1 x −1 −1  0 −1 x −1  −1 −1 −1 x  = x5 − 8x3 − 8x2 = x2 (x + 2)(x2 − 2x − 4). √ Giá trị riêng sắp xếp theo thứ tự không tăng lần lượt là λ1 = 1 + 5, λ2 = √ 0, λ3 = 0, λ4 = 1 − 5, λ5 = −2 với các véc tơ riêng độc lập tuyến tính √ x1 , x2 , x3 , x4 , x5 , trong đó x1 = (1, 1, 1, 1, −1 + 5)T , x2 = (0, 1, 0, −1, 0)T , √ x3 = (1, 0 − 1, 0, 0, )T , x4 = (1, 1, 1, 1, 1 − 5)T , x5 = (1, −1, 1, −1, 0)T . Chúng √ √ ta có ε(1 + 5) = hx1 i, ε(0) = hx2 , x3 i, ε(1 − 5) = hx4 i và ε(−2) = hx5 i, trong đó các ngoặc là ký hiệu không gian con sinh bởi mỗi véc tơ trong ngoặc. Ví dụ 1.1.5. Các giá trị riêng của chu trình có độ dài n là 2 cos 2πj (j = n 0, 1, . . . , n − 1). Để thấy điều này, ta quan sát rằng một ma trận kề có dạng A = P + P −1 trong đó P là một ma trận hoán vị xác định bởi một hoán vị vòng độ dài n. Nếu ω căn bậc n của đơn vị thì (1, ω, ω 2 , . . . , ω n−1 )T là một véc tơ riêng của P với giá trị riêng tương ứng ω. Vì vậy các giá trị riêng của A là số ω + ω −1 trong đó ω n = 1. Vì vậy giá trị riêng lớn nhất là 2 (với bội 1) và giá trị riêng lớn thứ hai là 2 cos 2π (với bội 2). Giá trị riêng nhỏ nhất là −2 (với n bội 1) nếu n là chẵn và 2 cos (n−1)π (với bội 2) nếu n lẻ. n Ví dụ 1.1.6. Đồ thị Petersen (Hình 1.2) có phổ là 31 , 15 , (−2)4 . 6 Hình 1.2: Đồ thị Petersen. Chúng ta nói rằng hai đồ thị là đồng phổ nếu chúng có phổ giống nhau. Rõ ràng, các đồ thị đẳng cấu là đồng phổ (nói cách khác, phổ là bất biến đồ thị). Tuy nhiên các đồ thị có phổ giống nhau không nhất thiết là đẳng cấu: các đồ thị không đẳng cấu trong Hình 1.3(a) có phổ là 21 , 03 , (−2)1 . Đây là ví dụ với số đỉnh ít nhất. Hình 1.3(b) là đồ thị liên thông không đẳng cấu đồng phổ với số đỉnh ít nhất: đa thức đặc trưng của chúng là (x − 1)(x + 1)2 (x3 − x2 − 5x + 1). Các đồ thị khác nhau được đặc trưng bởi phổ của chúng hoặc cùng với các bất biến đại số của chúng. Hình 1.3: Hai cặp đồ thị đồng phổ không đẳng cấu. Cho đồ thị G với tập đỉnh 1, 2, . . . , n. Gọi D là ma trận đường chéo diag(d1 , . . . , dn ), trong đó di là bậc của đỉnh i (i = 1, . . . , n). Ma trận Laplacian của một đồ thị G là ma trận D − A và ma trận Laplacian không dấu là ma trận D + A. Ma trận Seidel của G là ma trận S = J − I − 2A, trong đó J là ma trận 1 kích thược n × n. Vì vậy phần tử ở vị trí (i, j) của S là 0 nếu i = j, −1 nếu i ∼ j và 0 trong các trường hợp khác. Giống như các đồ thị chính quy đã biết, có rất ít sự lựa chọn giữa các ma trận của nó từ quan điểm phổ đồ thị. Giả sử rằng G là đồ thị chính quy bậc r và A có các giá trị riêng xếp theo thứ tự không tăng λ1 , . . . , λn . Từ Mệnh đề 1.1.2 và 1.1.3, ta có λ1 = r và tất cả các véc tơ gồm toàn 1 có thể mở rộng tới một cơ sở trực giao của Rn gồm các véc tơ riêng của ma trận A, rI ± A và J − I − 2A. Khi đó D ± A có các giá 7 trị riêng r ± r, r ± λ2 , . . . , r ± λn , trong đó S có các giá trị riêng n − 1 − 2r, −1 − 2λ2 , . . . , −1 − 2λn . Với các đồ thị không chính quy, không có một liên hệ đơn giản giữa các phổ khác nhau; Định lý 1.3.15 sẽ cung cấp một số bất đẳng thức, nhưng bây giờ ta đưa ra một ví dụ rõ ràng. Ví dụ 1.1.7. Cho đồ thị như trong Hình 1.1. Các giá trị riêng của ma trận Laplacian là 5, 5, 3, 3, 0. Các giá trị riêng của ma trận Laplacian không dấu là √ √ √ 1 (9 + 17), 3, 3, 12 (9 − 17) và các giá trị riêng Seidel là 3, 12 (−1 + 17), −1, 2 √ −1, 21 (−1 + 17). Ma trận Seidel có liên quan đặc biệt tới graph switching (thường được gọi là Seidel switching): cho một tập con U các đỉnh của đồ thị G. Đồ thị GU thu được từ G như sau. Với u ∈ U, v ∈ / U các đỉnh u, v kề nhau trong GU nếu và chỉ nếu chúng không kề trong G. Giả sử rằng G có ma trận kề trong G là ! AU B T A(G) = , B C trong đó AU là ma trận kề của đồ thị con cảm sinh bởi U và B T là chuyển vị của B. Khi đó GU có ma trận kề ! T AU B A(GU ) = , B C trong đó B thu được từ B bằng cách thay 0 bởi 1. Khi G là chính quy thì công thức này dễ chỉ ra (Xem Ví dụ 1.1.4). Việc tìm kiếm một điều kiện cần và đủ trên U cho GU là chính quy như sau: Mệnh đề 1.1.8. Giả sử rằng G là chính quy với n đỉnh và bậc r. Khi đó GU là chính quy bậc r nếu và chỉ nếu U sinh ra một đồ thị con bậc k, trong đó |U | = n − 2(r − k). Chú ý rằng đồ thị switching đối với tập con U của tập các đỉnh giống như là đồ thị switching đối với các hợp phần của nó. Đồ thị switching được mô tả dễ dàng từ ma trận Seidel S của G: ma trận Seidel của GU là T −1 ST trong đó T là ma trận đường chéo với phần tử đường chéo thứ i là 1 nếu i ∈ U và −1 nếu i 8 không thuộc U . Ta dễ dàng thấy rằng đồ thị switching trên U và V giống như ˙ \U ). Ta thấy rằng switching xác định một quan switching đối với (U \V )∪(V hệ tương đương trên đồ thị. Chú ý ràng đồ thị tương đương switching có ma trận Seidel tương tự và vì vậy có phổ Seidel giống nhau. Xét quan hệ giữa phổ và phổ Seidel của các đồ thị chính quy, chúng ta có mệnh đề sau: Mệnh đề 1.1.9. Nếu và G và GU là chính quy và cùng bậc thì G và GU có phổ giống nhau. 1.2 Một số khái niệm khác Chúng ta thường ký hiệu Kn , Cn , Pn tương ứng là đồ thị đầy đủ, chu trình, đường trên n đỉnh. Một đồ thị liên thông với n đỉnh được gọi là unicyclic nếu có n cạnh và chứa duy nhất một chu trình. Nếu chu trình độ dài lẻ thì đồ thị được gọi là odd-unicyclic. Một đồ thị liên thông với n đỉnh và n + 1 cạnh được gọi là đồ thị bicyclic. Chu vi (girth) của đồ thị G là độ dài của một chu trình ngắn nhất trong G. Một đồ thị con đầy đủ của G được gọi là một clique của G, trong khi một coclique là một đồ thị con cảm sinh không có cạnh. Đồ thị hai phần đầy đủ kích thước mỗi phần m và n được ký hiệu là Km,n . Đồ thị K1,n được gọi là một n-claw. Hơn nữa, Kn1 ,n2 ,...,nk là đồ thị đầy đủ k-phần với các phần (các lớp mầu) kích thước n1 , . . . , nk . Siêu đường cong m chiều (hypercube) ký hiệu là Qm . Các đỉnh của nó là 2m m-bộ 0 và 1 và hai bộ là kề nhau nếu và chỉ nếu chúng chỉ khác tại một đỉnh nào đó. Các đỉnh hay các cạnh được gọi là độc lập nếu chúng không kề nhau từng đôi một. Khi viết, một tập các đỉnh độc lập thường được gọi là một tập ổn định. Một tập các cạnh độc lập trong G được gọi là một matching của G. Một matching của G được gọi là hoàn hảo nếu mỗi đỉnh của G là một đỉnh cuối của một cạnh từ matching; các matching hoàn hảo cũng được gọi là 1-factor. The cocktail party graph CP (n) là một đồ thị chính quy duy nhất với 2n đỉnh bậc 2n − 2; nó thu được từ đồ thị K2n bằng cách xóa một matching hoàn hảo. Bậc của một đỉnh v được ký hiệu là deg(v) hoặc dv . Bậc nhỏ nhất trong G được ký hiệu là δ(G), bậc lớn nhất được ký hiệu là ∆(G). Một cạnh chứa một đỉnh bậc 1 được gọi là một cạnh treo (pendant). Một đồ thị chính quy bậc r được gọi là r-chính quy và một đồ thị 3-chính quy được gọi là một đồ thị bậc ba (cubic graph). Một đồ thị chính quy mạnh 9 với tham số (n, r, e, f ) là một đồ thị r-chính quy với n đỉnh (0 < r < n − 1) sao cho hai đỉnh kề bất kỳ có e đỉnh chung và hai đỉnh không kề bất kỳ có f đỉnh chung. Ví dụ đồ thị Petersen (Hình 1.2) là đều mạnh với tham số (10, 3, 0, 1). Hạn chế 0 < r < n − 1 để loại trừ các đồ thị đầy đủ và các hợp phần của nó. Một đồ thị gọi là hai nhánh nửa chính quy (semi-regular bepartite) với tham số (n1 , n2 , r1 , r2 ) nếu nó là hai phần và cách đỉnh trong mỗi phần có bậc nhất (n1 đỉnh có bậc r1 và n2 đỉnh có bậc r2 , trong đó n1 r1 = n2 r2 ). Nếu B là tập hợp các tập con của tập S thì đồ thị liên thuộc (incidence graph) xác định bởi B và S là đồ thị hai phần GB với tập đỉnh B ∪ S và với một cạnh nối giữa x ∈ S và B ∈ B khi x ∈ B. Vì vậy nếu B có dạng v điểm và b khối, trong đó mỗi khối có k điểm và mỗi điểm nằm trong r khối thì GB là một đồ thị nửa chính quy với tham số (v, b, r, k). Trong trường hợp này, chúng ta gọi GB là đồ thị phác họa (the graph of the design). Nhắc lại rằng trọng một t-design với các tham số v, k, λ, điểm t bất kỳ nằm trên khối λ và một design đối xứng là một 2-design với b = v < k (tương đương r = k < v). Phần bù của một đồ thị G được ký hiệu bởi G trong khi mG ký hiệu cho đồ thị gồm m bản sao rời nhau của G. Đồ thị chia (subdivision graph) S(G) thu được từ G bằng cách thêm một đỉnh bậc 2 vào mỗi cạnh của G. Chúng ta ký hiệu V (G) là tập đỉnh của G và E(G) là tập cạnh. Ta nói rằng G là rỗng nếu V (G) = ∅, tầm thường nếu |V (G)| = 1 và null nếu E(G) = ∅. Một đồ thị con H với V (H) = V (G) được gọi là tạo bởi đồ thị con spanning của G (spanning subgraph of G). Một chu trình spanning được gọi là chu trình Hamilton và một đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton. Một tự đẳng cấu của G là một hoán vị π của V (G) sao cho u ∼ v nếu và chỉ nếu π(u) ∼ π(v). Rõ ràng, tự đẳng cấu của G là một nhóm (đối với hàm hợp). Chúng ta nói rằng G là vertex-transitive nếu với mọi u, v ∈ V (G), tồn tại một tự đẳng cấu π của G sao cho π(u) = v. ˙ Hợp của các bản sao rời nhau của các đồ thị G và H được ký hiệu là G∪H. Phép nối (join) G 5 H của các đồ thị rời nhau G và H là đồ thị thu được từ ˙ bằng cách nối mỗi đỉnh của G với mỗi đỉnh của H. Đồ thị K1 5 H được G∪H gọi là một nón qua H trong khi K2 5 H (= K1 5 (K1 5 H)) được gọi là nón kép qua H. Đồ thị K1 5 Cn (n ≤ 3) là wheel Wn+1 với n + 1 đỉnh. Vì vậy đồ thị trong Ví dụ 1.1.4 là wheel W5 . 10 Nếu uv là một cạnh của G, ta viết G − uv là các đồ thị thu được từ G bằng cách xóa cạnh uv. Tổng quát hơn, nếu E là một tập các cạnh của G, chúng ta viết G − E cho đồ thị thu được từ G bằng cách xóa các cạnh trong E. Với v ∈ V (G), G − v ký hiệu là đồ thị thu được từ G bằng cách xóa đỉnh v và tất cả các cạnh kề với v. Với U ⊆ V (G), ký hiệu G − U là đồ thị con của G sinh bởi V (G)\U . Nếu mỗi đỉnh G − U kề với một đỉnh của U thì U được gọi là một tập trội (dominating set) trong G. Nếu u, v là các đỉnh của đồ thị liên thông G thì khoảng cách giữa u và v, ký hiệu d(u, v) là độ dại ngắn nhất của đường nối u, v trong G. Định nghĩa 1.2.1. Đồ thị thẳng L(H) của một đồ thị H là một đồ thị mà các đỉnh là các cạnh của H, hai đỉnh trong L(H) kề nhau khi các cạnh tương ứng trong H có đúng một đỉnh chung. Nếu G = L(H) với mọi đồ thị H thì H được gọi là một root graph của G. Nếu E(H) = ∅ thì G là một đồ thị rỗng. Do đó, chúng ta lấy một đồ thị phẳng có nghĩa là một đồ thị L(H), trong đó E(H) khác rỗng. Chú ý rằng chúng ta có thể giả sử (nếu cần) rằng H không có đỉnh cô lập. Nếu H liên thông thì L(H) cũng vậy. Nếu H không liên thông thì mỗi hợp phần không tầm thường của H đưa tới một hợp phần liên thông của L(H). Mệnh đề 1.2.2. Nếu H là một đồ thị liên thông và L(H) là chính quy, thì H là chính quy hoặc hai nhánh nửa chính quy. Ma trận liên thuộc của đồ thị H là ma trận B có các hàng và các cột được đánh chỉ số bởi các đỉnh và các cạnh của H. Phần tử (v, e) của B là  0 nếu v không kề với e, bve = 1 nếu v kề với e. Do đó các cột của B là các véc tơ đặc trưng của các cạnh của H như các tập con của V (H). Chúng ta thấy rằng B T B = A(L(H)) + 2I. (1.2) Nếu A(L(H))x = λx thì (λ + 2)xT x = xT B T Bx ≥ 0. Vì vậy mọi giá trị riêng của L(H) lớn hơn hoặc bằng −2. Đây là một tính chất phổ đáng chú ý của các đồ thị phẳng. 11 Lớp các đồ thị với phổ trong khoảng [−2, ∞) cũng chứa đồ thị phẳng suy rộng được định nghĩa như sau. Đầu tiên, ta nói rằng một petal được thêm vào một đồ thị khi chúng ta thêm một cạnh treo (pendant edge) và sau đó lặp lại với một cạnh treo 2-chu trình. Một blossom Bk chứa k petal (k ≥ 0) được thêm vào mỗi đỉnh đơn. Vì vậy B0 là một đồ thị tầm thường. Một đồ thị với các blossom (có thể rỗng) tại mỗi đỉnh thì được gọi là một B-đồ thị. Bây giờ chứng ta mở rộng Định nghĩa 1.2.1 tới đồ thị phẳng của một B-đồ thị Ĥ: các đỉnh trong L(Ĥ) kề nhau nếu và chỉ nếu các cạnh tương ứng trong Ĥ có đúng một đỉnh chung. Trong trường hợp đặc biệt, cạnh lặp lại giữa hai đỉnh của Ĥ là không kề nhau trong L(Ĥ). Vì vậy L(Bk ) = CP (k). Nếu G = L(Ĥ) thì chúng ta gọi đa đồ thị Ĥ là một root graph của G. Định nghĩa 1.2.3. Cho H là một đồ thị với tập đỉnh (v1 , . . . , vn ) và đặt a1 , . . . , an là các số nguyên không âm. Đồ thị phẳng suy rộng G = L(H; a1 , . . . , an ) là đồ thị L(Ĥ), trong đó Ĥ là B-đồ thị H(a1 , . . . , an ) thu được từ H bằng cách thêm ai petal tại đỉnh vi (i = 1, . . . , n). Nếu tất cả các ai khác 0 thì G được gọi là một đồ thị phẳng suy rộng. Cách xây dựng đồ thị phẳng suy rộng được minh họa trong Hình 1.4. Hình 1.4: Xây dựng đồ thị phẳng suy rộng. Một ma trận liên thuộc C = (cve ) của Ĥ = H(a1 , . . . , an ) được định nghĩa cho H với ngoại lệ sau: Nếu e và f là các cạnh giữa v và w trong một petal tại 12 v thì cwe , cwf = −1, 1. (Chú ý rằng tất cả những phần tử khác trong hàng w là 0). Ví dụ, một ma trận liên thuộc của một đa đồ thị Ĥ trong Hình 1.4 là:   1 1 1 0 0 0 0 0 0 0    0 0 1 1 0 1 0 0 0 0    0 0 0 1 1 0 0 0 0 0      0 0 0 0 1 1 1 1 1 1    0 0 0 0 0 0 −1 1 0 0       0 0 0 0 0 0 0 0 −1 1  −1 1 0 0 0 0 0 0 0 0. Ở đây các hàng được đánh số bởi 1, 2, . . . , 7 và các cột là a, b, . . . , j. Với ma trận liên thuộc C định nghĩa ở trên, ta có A(L(Ĥ)) = C T C − 2I và vì vậy λ(L(Ĥ)) ≥ −2. Chú ý rằng giá trị riêng nhỏ nhất lớn hơn −2 nếu và chỉ nếu hạng của ma trận C là |V (Ĥ)|. Tuy nhiên không phải tất cả các đồ thị G với λ(G) ≥ −2 là các đồ thị phẳng suy rộng, ngoại trừ một số hữu hạn các đồ thị. Ví dụ 1.2.4. Nếu chúng ta quay (switch) đồ thị L(K4,4 ) đối với bốn đỉnh độc lập thì chúng ta thu được các đồ thị chính quy bậc 6 khác nhau trên 16 đỉnh, gọi là đồ thị Shrikhande. Nó là đồ thị chính quy mạnh với tham số (16, 6, 2, 2). Từ Mệnh đề 1.1.9, đồ thị này là đồng phổ với L(K4,4 ). Nếu chúng ta quay L(K4,4 ) đối với các đỉnh của một đồ thị con cảm sinh L(K4,2 ) thì chúng ta thu được một đồ thị đều bậc 10 với 16 đỉnh được gọi là đồ thị Clebsch, nó là đồ thị chính quy mạnh với tham số (16, 10, 6, 6). Các đồ thi này được minh họa trong Hình 1.5. Trong Hình 1.5(a), các đỉnh của L(K4,4 ) là các giao điểm của 4 đường nằm ngang với 4 đường thẳng đứng, hai đỉnh là kề nhau trong L(K4,4 ) khi và chỉ khi các điểm tương ứng là cộng tuyến. Trong Hình 1.5(b) và 1.5(c), các đỉnh màu trắng là đỉnh trong tập switching mà tương ứng là đồ thị Shrikhande và đồ thị Clebsch. Ví dụ 1.2.5. Nếu chúng ta quy một đồ thị G đối với tập các đỉnh kề của đỉnh v, chúng ta thu được một đồ thị H trong đó v là một đỉnh cô lập. Nếu G = L(Ks ) thì G − v là đồ thị đều bậc 16 trên 27 đỉnh, được gọi là đồ thị Schlafli Sch16 ; nó là đồ thị với các tham số (27, 16, 10, 8). 13 Hình 1.5: Xây dựng các đồ thị trong Ví dụ 1.2.4 Ví dụ 1.2.6. Cho S1 , S2 , S3 là tập các đỉnh của L(K8 ) mà tương ứng cảm sinh ˙ 3 và C8 . Các đồ thị Ch1 , Ch2 , Ch3 tương các đồ thị con đẳng cấu với 4K1 , C5 ∪C ứng thu được từ L(K8 ) bằng cách switching đối với S1 , S2 , S3 được gọi là đồ thị Chang. Đồ thị L(K8 ), Ch1 , Ch2 , Ch3 đều có bậc 12 và chúng là đồng phổ theo Mệnh đề 1.1.9. Từng cặp đồ thị không đẳng cấu, chúng đều là chính quy mạnh với tham số (28, 12, 6, 4). 1.3 Một vài kết quả từ đại số tuyến tính Đầu tiền chúng ta chú ý rằng một đồ thị được xác định bởi các giá trị riêng và các véc tơ riêng tương ứng theo cách sau. Cho A là ma trận kề của một đồ thị G với các đỉnh 1, 2, . . . , n và các giá trị riêng λ1 ≤ λ2 ≤ . . . ≤ λn . Nếu x1 , . . . , x2 là các véc tơ riêng độc lập tuyến tính tương ứng với các giá trị riêng λ1 ≤ λ2 ≤ . . . ≤ λn của A. Nếu X = (x1 | x2 | xn ) và nếu E = diag(λ1 , . . . , λn ) thì AX = XE, do đó A = XEX −1 . Vì G được xác định bởi A, chúng ta có kết quả cơ bản sau: Định lý 1.3.1. Một đồ thị bất kỳ được xác định bởi các giá trị riêng của nó và một cơ sở các véc tơ riêng tương ứng. Vì A là ma trận thực đối xứng nên tồn tại một ma trận trực giao U sao cho U AU = E. Ở đây, cột của U là các véc tơ riêng là các cơ sở trực giao của Rn . T Nếu cơ sở này được xây dựng cùng với cơ sở trực giao của không gian riêng của A thì E = µ1 E1 + . . . + µm Em , trong đó µ1 , . . . , µm là các giá trị riêng phân biệt của A và mỗi Ei có phân tích phổ A = µ1 P1 + . . . + µm Pm (1.3) 14 trong đó Pi = U Ei E T (i = 1, . . . , m). Cho i cố định, nếu ε(µi ) có x1 , . . . , xd như một cơ sở trực giao thì Pi = x1 xT1 + . . . + xd xTd (1.4) và Pi thay thế phép chiếu trực giao của Rn vào trong ε(µi ) đối với cơ sở trực Pm giao chuẩn (e1 , . . . , en ) ∈ Rn . Xa hơn i=1 Pi = I, Pi2 = PiT (i = 1, . . . , m) và Pi Pj = O (i 6= j). Chúng ta cũng quan sát rằng với đa thức bất kỳ f , ta có f (A) = f (µ1 )P1 + . . . + f (µm )Pm . Trong trường hợp đặc biệt, Pi là một đa thức trong vành A với mỗi i. Rõ ràng Pi = fi (A), trong đó Q s6=i (x − µs ) . (1.5) fi (x) = Q s6=i (µi − µs ) Tiếp theo chúng ta đề cập đến kỹ thuật véc tơ riêng thường được sử dụng để tìm kiếm các đồ thị với chỉ số min, max trong một lớp các đồ thị cho trước. Một thương Reyleight của A là một đại lượng vô hướng dạng yT Ay/yT y trong đó y là một véc tơ khác véc tơ không trong Rn . Cận trên của tập là giá trị riêng lớn nhất λ1 của A, hay tương đương với λ1 = sup{xT Ax : x ∈ Rn , kxk = 1}. (1.6) Điều này được suy ra trực tiếp từ nhận xét rằng nếu {x1 , . . . , xn } là một cơ sở trực chuẩn gồm các véc tơ riêng của A và nếu x = α1 x1 + · · · + αn xn thì α12 + · · · + αn2 = 1, cùng với xT Ax = λ1 α12 + · · · + λn αn2 , (1.7) trong đó Axi = λi xi (i = 1, . . . , n). Chú ý rằng với y 6= 0, ta có yT Ay/yT y ≤ λ1 . Dấu “=” xảy ra nếu và chỉ nếu Ay = λ1 y. Tổng quát hơn, nguyên lý Rayleight có thể phát biểu như sau: nếu 0 6= y ∈ hxi , . . . , xn i thì λi ≥ yT Ay/yT y, trong đó dấu “=” xảy ra khi và chỉ khi Ay = λi y. Ngoài ra, mỗi giá trị riêng λi (i = 1, 2, . . . , n) có thể được đặc trưng bởi các không gian con của Rn như sau. Cho U U là một không gian con n − i + 1 chiều của Rn sao cho hxi , . . . , xn i ∩ U 6= {0}. Nếu x là một véc tơ đơn vị thuộc 15 giao của xT Ax ≥ từ (1.7), α1 = . . . có các không gian con này thì αi+1 = . . . = αn = 0 và vì vậy theo (1.7) λi . Từ đó ta có sup{xT Ax : x ∈ U, kxk = 1} ≥ λi . Mặt khác cũng chặn dưới đạt được khi U = hxi , . . . , xn i bởi vì trong trường hợp này = αi−1 = 0 với mọi véc tơ trong U . Vì vậy, với mỗi i ∈ {1, . . . , n} ta λi = inf{sup{xT Ax : x ∈ U, kxk = 1} : U ∈ Un−i+1 }, (1.8) trong đó Un−i+1 là tập tất cả các không gian con (n − i + 1) chiều trong Rn . Một ma trận đối xứng M cấp n × n được gọi là nửa xác định dương nếu tất cả các giá trị riêng là không âm, tức là xT M x ≥ 0 với mọi x ∈ Rn . Định lý 1.3.2. Cho M là một ma trận nửa xác định dương với các giá trị riêng λ1 ≥ λ2 ≥ . . . ≥ λn . Khi đó λ1 + λ2 + . . . + λr = sup{uT1 M u1 + . . . uTr M ur } (r = 1, 2, . . . , n), trong đó cận trên được lấy qua tất cả các véc tơ trực giao u1 , u2 , . . . , ur . Trong trường hợp đặc biệt, λ1 + λ2 + . . . + λr bị chặn dưới bằng tông của r phần tử trực giao lớn nhất của M . Chứng minh. Đặt M xi = λi xi (i = 1, 2, . . . , n), trong đó x1 , . . . , xn là trực chuẩn. Đặt U = (u1 | u2 | . . . | ur ), X = (x1 | x2 | . . . | xn ) và uj = Pn i=1 cij xi (j = 1, . . . , r). Khi đó U = XC, trong đó C = (cij ), ngoài ra I = U T U = C T C. Sử dụng Phương trình (1.7), ta có ! r r X n n r X X X X uTj M uj = c2ij λi = c2ij λi . j=1 j=1 i=1 i=1 j=1 Pr Chú ý rằng j=1 c2ij = bi , trong đó bi là thành phần đường chéo chính thứ i của CC T . Tiếp theo CC T và C T C có các giá trị riêng khác 0 như nhau nên phổ của CC T là 1r , 0n−r . Lại từ (1.7) ta có bi = eTi CC T ei ≤ 1 (i = 1, 2, . . . , n). Khi đó chúng ta có r X j=1 uTj M uj = n X i=1 bi λi , 0 ≤ bi ≤ 1, n X bi = tr(CC T ) = r, i=1 Pr Pr và j=1 uTj M uj ≤ i=1 λj . Dấu “=” xảy ra khi ui = xi (i = 1, . . . , r). Khi đó phần đầu của định lý được chứng minh. Với phần thứ hai, không mất tính tổng quát, ta có thể giả sử r phần tử trên đường chéo lớn nhất của M là r phần tử 16 trên đường chéo đầu tiên. Khi đó khẳng định thứ hai có được bằng cách lấy ui = ei (i = 1, 2, . . . , r). Nếu M là ma trận nửa xác định dương với hạng r thì tồn tại một ma trận trực giao U sao cho   θ1   ...       θ  r  UTMU =     0    ...    0 trong đó θ1 ≥ θ2 ≥ . . . ≥ θr > 0. đó √ θ1  X=  0 0 Ma trận này có thể viết thành X T X, trong ... ... 0 0 ... 0   0 0 . . . 0 , ... √ θr 0 . . . 0 cấp n × n. Vì vậy M = QT Q, trong đó Q = XU T . Nếu Q = (1 | . . . | n) thì mỗi cột qi nằm trong Rr và phần từ (i, j) của M là tích vô hướng qTi qj . Ma trận QT Q được gọi là ma trận Gram của các véc tơ q1 , . . . , qn . Chúng ta thường sử dụng ma trận Gram trong trường hợp M = AλI và λ là giá trị riêng nhỏ nhất của G. Trong trường hợp này bội của λ là −r. Vì trong trường hợp tổng quát, một đồ thị không thể xác định bởi các giá trị riêng của nó. Lẽ tự nhiên là chúng ta cố gắng tìm kiếm nhiều hơn các bất biến đại số, những đại lượng mà có thể dùng để phân biệt các đồ thị đồng phổ không đẳng cấu. Chú ý rằng {e1 , . . . , en } là một cơ sở trực chuẩn của Rn . mn số αi,j = kPi ej k được gọi là các góc của G, chúng là cosin của góc (nhọn) hợp bởi các trục với các không gian riêng. Chúng ta giả sử rằng µ1 ≥ . . . ≥ µn . Nếu chúng ta cũng để các cột của ma trận (αij ) theo thứ tự thì ma trận này là một bất biến đồ thị được gọi là ma trận góc của G. Chúng ta sẽ thấy ở trong chương tiếp theo rằng phổ của các đồ thị con xóa đỉnh G − j được xác định bởi phổ của G và góc αij , . . . , αmj . Cơ sở của mối quan hệ giữa các góc được thể hiện qua mệnh đề sau: 17 Mệnh đề 1.3.3. Các góc αij của một đồ thị thỏa mãn đẳng thức n X 2 αij = dim E(µi ), j=1 m X 2 αij = 1. (1.9) i=1 2 2 2 Chứng minh. Chúng ta có αi,j = kPi ej k2 = eTj Pi ej và vì vậy αi1 , . . . , αin xuất Pn 2 hiện trên đường chéo của Pi . Khi đó i=1 αij = tr(Pi ) = tr(Ei ) = dim E(µi ), Pm 2 Pm và i=1 αij = 1 vì i=1 Pi = I. Tiếp theo chúng ta thảo luận về mối quan hệ giữa các giá trị riêng, góc và bước đi trong một đồ thị. Một bước đi (walk) độ dài k trong một đồ thị là một dãy bất kỳ các đỉnh v0 , v1 , . . . , vk (không nhất thiết khác nhau) sao cho với mỗi i = 1, 2, . . . , k có một cạnh từ vi−1 đến vi . Bước đi là đóng nếu vk = v0 . Kết quả sau đây có thể chứng minh bằng quy nạp theo k. Mệnh đề 1.3.4. Nếu A là một ma trận kề của một đồ thị thì phần tử ở vị trí (k) (i, j) là aij của ma trận Ak bằng số bước đi độ dài k bắt đầu ở đỉnh i và kết thúc tại đỉnh j. Từ Mệnh đề 1.3.4 ta có số bước đi đóng độ dài k bằng số số moment phổ Pn Pn (k) thứ k vì j=1 ajj = tr(Ak ) = j=1 λkj . Từ sự phân tích phổ của A chúng ta có Ak = µk1 P1 + µkm Pm (1.10) Pm (k) 2 và vì ajj = i=1 µki αij , trong đó αij là các góc của G. Trong trường hợp đặc (2) biệt, bậc của đỉnh ajj được xác định bởi phổ và góc. Chúng ta viết j (hoặc jn ) cho các véc tơ gồm toàn 1 trong Rn và j⊥ cho không gian con trực giao của j. Từ (1.10) ta suy ra số bước đi độ dài k Nk trong G được xác định bởi Nk = X u,v a(k) uv T k =j A j= n X µki kPi jk2 . (1.11) i=1 √ Số βi = kPi jk/ n (i = 1, . . . , m) được gọi là các góc chính của G; chúng là giá Pm trị cosin của các góc giữa các không con riêng với j. Chú ý rằng i=1 βi2 = 1 bởi Pm vì j = i=1 Pi j. Giá trị riêng µi được gọi là giá trị riêng chính nếu E(µi ) 6⊆ j⊥ , hay Pi j 6= 0. Từ (1.11) ta có kết quả sau. 18 Định lý 1.3.5. Tổng số Nk các bước đi độ dài k trong đồ thị G là Nk = n trong đó tổng P0 0 X µki βi2 , (1.12) được lấy qua tất cả các giá trị riêng chính µi . Trong Chương 2 ta sẽ thấy rằng phổ của phần bù G, phổ của nón K1 5 G và phổ Seidel của G đều được xác định bằng phổ và các góc chính của G. Bây giờ ta quay trở lại một số kết quả tổng quát hơn từ lý thuyết ma trận mà kéo theo phổ của đồ thị. Một ma trận đối xứng M là khả quy ! (reducible) nếu tồn tại ma trận hoán X O vị P sao cho P −1 M P có dạng , trong đó X, Y là các ma trận vuông. O Y Nếu ngược lại, M được gọi là bất khả quy (irreducible). Nếu M = (mij ) cấp n×n thì chúng ta định nghĩa đồ thị GM như sau. Các đỉnh của GM là 1, 2, . . . , n và hai đỉnh phân biệt i và j kề nhau khi và chỉ khi mij 6= 0. Vì vậy GM là liên thông khi và chỉ khi M là bất khả quy. Định lý 1.3.6. Cho M là ma trận đối xứng bất khả quy với các phần tử không âm. Khi đó giá trị riêng lớn nhất λ1 của M là đơn, với véc tơ riêng tương ứng có có tất cả các phần tử đều dương. Ngoài ra, |λ| ≤ λ1 với mọi giá trị riêng λ của M . Chứng minh. Đặt x = (x1 , . . . , xn )T là một véc tơ riêng ứng với giá trị riêng λ1 . Đặt (y1 , . . . , yn )T , trong đó yi = |xi | (i = 1, . . . , n). Khi đó yT y = 1 và yT M y ≤ xT M x = λ1 . Vì vậy y cũng là một véc tơ riêng ứng với giá trị riêng λ1 . Chúng ta thấy rằng không có yi nào (và vì vậy không có xi ) bằng 0 bằng cách xem xét tính chất kề trong GM . Phương trình giá trị riêng có thể viết: X λ1 yi = mii yi + mij yj (i = 1, . . . , n). (1.13) j∼i Nếu yi = 0 thì theo (1.10), yj = 0 với mọi j ∼ i. Vì GM là liên thông, yj = 0 với mọi j, mâu thuẫn. Với λ1 là một giá trị riêng đơn, nếu dim E(λ1 ) > 1 được tạo bởi y (và x = ±y). Cuối cùng, nếu M z = λz, trong đó zT z = 1 và z = (z1 , . . . , zt )T thì X X |λ| = |zM z| = | zi mij zj | ≥ |z|mij |zj | ≥ λ1 . i,j i,j