Tài liệu Một số tính chất của ma trận và áp dụng vào đồ thị (Luận văn thạc sĩ)

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– MẠC ANH VĂN MỘT SỐ TÍNH CHẤT CỦA MA TRẬN VÀ ÁP DỤNG VÀO ĐỒ THỊ LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên, 10/2018 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– MẠC ANH VĂN MỘT SỐ TÍNH CHẤT CỦA MA TRẬN VÀ ÁP DỤNG VÀO ĐỒ THỊ LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp toán sơ cấp Mã số: 8460113 NGƯỜI HƯỚNG DẪN KHOA HỌC GS. TSKH. NGUYỄN VĂN MẬU Thái Nguyên, 10/2018 i Mục lục Lời cảm ơn iii Mở đầu 1 Kiến thức chuẩn bị 1.1 Khái niệm của đồ thị và phổ của đồ 1.1.1 Khái niệm đồ thị . . . . . . 1.1.2 Phổ của đồ thị . . . . . . . 1.2 Ma trận kề. Ma trận trọng số . . . 1.3 Ma trận liên thuộc . . . . . . . . . 1 thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Tính chất của ma trận biểu diễn đồ thị và các phép toán đồ thị 2.1 Tính chất của ma trận biểu diễn đồ thị . . . . . . . . . . . . . . 2.1.1 Ma trận Laplace của đồ thị và một số tính chất cơ bản . 2.1.2 Ma trận Laplace của một cạnh . . . . . . . . . . . . . . 2.1.3 Phân tích ma trận Laplace . . . . . . . . . . . . . . . . . 2.1.4 Định lý Kirchhoff . . . . . . . . . . . . . . . . . . . . . . 2.2 Các phép toán đồ thị . . . . . . . . . . . . . . . . . . . . . . . . 3 Áp 3.1 3.2 3.3 3 3 3 6 10 13 14 14 14 17 19 20 26 dụng một số tính chất của ma trận vào đồ thị 32 Ứng dụng định lý Kirchhoff tìm số cây bao trùm của đồ thị . . . 32 Ứng dụng trong đếm số đồ thị con . . . . . . . . . . . . . . . . 33 Ứng dụng xác định bậc chính quy và tính hai phần . . . . . . . 36 Kết luận 41 Tài liệu tham khảo 42 ii Danh mục các ký hiệu, các chữ viết tắt • G: Đồ thị n đỉnh, m cạnh. • A: Ma trận kề n × n của G có đường chéo chính bằng 0. • L = D − A: Ma trận Laplace của G. • B: Ma trận liên thuộc n × m · L = B T B. • Ckk : Là phần bù đại số của phần tử thứ k của đường chéo chính của ma trận vuông L. • [L]k,k : Là định thức con chính thứ k của ma trận vuông L. iii Lời cảm ơn Luận văn được thực hiện tại trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của GS. TSKH. Nguyễn Văn Mậu. Thầy đã hướng dẫn và tạo điều kiện tốt nhất để cho tác giả hoàn thành luận văn này. Nhân dịp này, tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới thầy. Tác giả cũng được xin bày tỏ lòng cảm ơn sâu sắc tới các thầy giáo, cô giáo đã tham gia giảng dạy các lớp cao học Toán K10Q, trường Đại học Khoa học - Đại học Thái Nguyên, khoa Toán - Tin đã tạo điều kiện thuận lợi nhất cho tác giả trong suốt quá trình học tập tại trường. Cuối cùng, tác giả cũng xin gửi lời cảm ơn chân thành tới tập thể lớp cao học toán K10Q, gia đình, bạn bè, lãnh đạo đơn vị công tác và đồng nghiệp đã giúp đỡ, động viên và tạo điều kiện tốt nhất cho tác giả khi học tập và nghiên cứu. Mặc dù bản thân đã có nhiều cố gắng nhưng do điều kiện thời gian ngắn, trình độ và kinh nghiệm nghiên cứu khoa học còn hạn chế, nên luận văn không tránh khỏi những thiếu sót. Tác giả rất mong nhận được những đóng góp của các thầy cô và các bạn đồng nghiệp để tác giả có thể tiếp tục nghiên cứu tốt hơn. Thái Nguyên, tháng 10 năm 2018 Người viết luận văn Mạc Anh Văn 1 Mở đầu Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã hình thành và phát triển từ khá lâu nhưng lại có nhiều ứng dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị đã xuất hiện từ những năm 30 của thế kỷ XVIII bởi nhà toán học lỗi lạc người Thụy Sĩ Leonhard Euler. Chính ông là người đã đề xuất mô hình đồ thị và sử dụng nó để giải bài toán nổi tiếng về cây cầu ở thành phố Königsberg. Từ đó, lý thuyết đồ thị ngày càng khẳng định được vị trí quan trọng trong việc áp dụng để giải quyết nhiều bài toán trên mọi lĩnh vực. Đồ thị mô tả các quan hệ hai ngôi trên tập hợp một cách trực quan sinh động: giúp chúng ta mô ta các bài toán phức tạp trở lên cụ thể, đơn giản hơn. Sơ đồ biểu diễn một hệ thống các tuyến bay của một hãng hàng không là một hình ảnh của đồ thị. Các đối tượng là các sân bay, mỗi đường bay thẳng sẽ biểu diễn mối liên hệ giữa 2 sân bay đầu cuối của tuyến. Các tính chất của đồ thị có thể được biểu diễn bằng ngôn ngữ đại số tuyến tính và những kết quả của đại số tuyến tính sẽ được thể hiện trực quan bằng đồ thị. Ma trận là một khái niệm của Đại số tuyến tính. Ma trận có ứng dụng trong hầu hết các lĩnh vực khoa học. Ma trận có vai trò khá quan trọng trong lý thuyết đồ thị. Có thể nói ma trận là một công cụ kết nối giữa lý thuyết đồ thị và đại số tuyến tính. Trong phạm vi của luận văn tốt nghiệp thạc sĩ chuyên ngành phương pháp toán sơ cấp từ sự đề xuất hướng nghiên cứu và trực tiếp hướng dẫn của GS.TSKH. Nguyễn Văn Mậu, chúng tôi xác định đề tài là “Một số tính chất của ma trận và áp dụng vào đồ thị”. Với đề tài này, tôi hy vọng rằng sẽ làm rõ mối liên hệ giữa đại số tuyến tính và lý thuyết đồ thị dựa trên các biểu diễn ma trận của nó, từ đó tìm ra được ứng dụng. Kết quả của đề tài cũng là sự thể hiện quá trình tập dượt nghiên cứu của tôi. Mục tiêu của luận văn là tìm hiểu sự liên hệ giữa ma trận và đồ thị, phổ của đồ thị, từ đó góp phần làm rõ mối quan hệ giữa đại số tuyến tính với lý 2 thuyết đồ thị. Nhiệm vụ nghiên cứu được đặt ra trong khuôn khổ luận văn này là nghiên cứu lợi ích khi biểu diễn đồ thị dưới dạng ma trận, từ đó sử dụng các công cụ đại số nhằm tìm ra các ứng dụng thực tế của ma trận đồ thị. Đối tượng nghiên cứu của luận văn xoay quanh đồ thị hữu hạn và các biểu diễn của đồ thị dưới dạng ma trận là: ma trận kề, ma trận liên thuộc, ma trận có trọng số và ma trận Laplace (xem [1-2], [4-6]). Ngoài phần Mở đầu, Kết luận và Tài liệu tham khảo, luận văn được chia làm 3 chương: Chương 1. Kiến thức chuẩn bị. Trong chương này, tôi trình bày cách xây dựng một đồ thị về ma trận đại số và khái niệm phổ của đồ thị. Chương 2. Tính chất của ma trận biểu diễn đồ thị và các phép toán đồ thị. Trên cở sở các loại ma trận của đồ thị hướng đến chứng minh định lí Kirchhoff. Rõ ràng, việc tính số cây bao trùm của một đồ thị trực quan thường mất thời gian và dễ gây nhầm lẫn, thiếu xót nhưng với định lí Kirrchoff từ công cụ đại số tác giả xây dựng nên cách tính số cây bao trùm của một đồ thị một cách chính xác và khoa học hơn bằng phần bù đại số của ma trận Laplace. Tiếp theo là các phép toán đồ thị để đếm số đồ thị con và xác định bậc chính quy và tính hai phần. Chương 3. Áp dụng một số tính chất của ma trận vào đồ thị. Tác giả trình bày 3 ứng dụng sử dụng tính chất đã nêu ở chương hai. Ứng dụng đầu tiên sử dụng định lý kirchhoff nhằm giải quyết bài toán xây dựng mạng lưới đường sắt tàu hỏa một cách kinh tế và tối ưu nhất. Ứng dụng thứ hai và thứ ba sử dụng tính chất phổ của đồ thị để đếm số đồ thị con và xác định bậc chính quy và tính hai phần. 3 Chương 1 Kiến thức chuẩn bị Trong chương này, chúng tôi trình bày một số kiến thức cơ sở cho chương sau. Trước tiên là trình bày khái niệm đồ thị có hướng và đồ thị vô hướng, từ đó biểu diễn đồ thị dưới dạng ma trận và ý nghĩa. 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ị. Kiến thức trong chương này sử dụng tài liệu [1], [2] và [4]. 1.1 Khái niệm của đồ thị và phổ của đồ thị 1.1.1 Khái niệm đồ thị Định nghĩa 1.1.1. Một đồ thị vô hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập hữu hạn; còn E là tập với các phần tử là các tập con hai phần tử trên V , E ⊆ {{u, v}|u, v ∈ V, u 6= v}. Các phần tử của V được gọi là các đỉnh, tập đỉnh của G được ký hiệu là V (G). Các phần tử của E được gọi là các cạnh, tập cạnh của đồ thị vô hướng G được ký hiệu là E(G). Nhưng để đơn giản hơn ta có thể viết “đỉnh v ∈ V ” hay “cạnh e ∈ E”. Cho a, b ∈ V , nếu tồn tại e ∈ {a, b} thì khi đó e là một cạnh của G với hai đỉnh đầu mút là a, b hay a, b là hai đỉnh liên thuộc với e. Cạnh e = {a, b} thường được ký hiệu ngắn gọn là ab hay ba. Trong luận văn này, ta chỉ xét tới đơn đồ thị, không xét tới đồ thị có khuyên và đa đồ thị. Do vậy khi nhắc đến đồ thị, ta ngầm hiểu là đơn đồ thị vô hướng. Có thể biểu diễn một đồ thị một cách trực quan như sau: Các đỉnh của V được biểu diễn bằng các vòng tròn nhỏ (rỗng hoặc đặc), còn các cạnh được 4 biểu diễn bằng một đường cong (đường thẳng) nối 2 đầu mút của cạnh. Ví dụ 1.1.2. Cho G = (V, E) với V = {a, b, c, d, f, g}; E = {ad, db, dc, bc, cf, cg, gf }. Khi đó biểu diễn của đồ thị vô hướng G: Hình 1.1: Đồ thị G Giả sử một mạng lưới giao thông gồm các trạm xe bus và đường đi giữa chúng, giữa 2 trạm luôn chỉ có không quá một đường đi trực tiếp, không có đường quay vòng từ một trạm tới chính nó. Ta biểu diễn mạng lưới giao thông này bằng mô hình đồ thị như sau: mỗi trạm đỗ xe là một đỉnh, mỗi đường đi trực tiếp giữa hai trạm là 1 cạnh. Ta có hình ảnh chính xác của đồ thị. Hình 1.2: Mạng lưới xe bus Các đường giao thông đôi khi chỉ được chạy theo một chiều. Chúng ta có thể dùng đồ thị có hướng để mô hình hóa những mạng như thế. Định nghĩa 1.1.3. Một đồ thị có hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập hữu hạn, còn E là một tập con của tích Đề các V × V . 5 Các phần tử của V được gọi là các đỉnh, còn các phần tử của E được gọi là các cung của đồ thị vô hướng G. Nếu (a, b) ∈ E thì (a, b) được gọi là cung của G với đỉnh đầu là a, đỉnh cuối là b và có hướng từ a tới b. Khi đã cho G = (V, E) là đồ thị có hướng, cung (a, b) ∈ E thường được ký hiệu ngắn gọn là ab với a là đỉnh đầu và b là đỉnh cuối; ba là cạnh với b là đỉnh đầu, a là đỉnh cuối. Biểu diễn một đồ thị có hướng trên mặt phẳng trực quan tương tự như biểu diễn đồ thị vô hướng: Các đỉnh của V được biểu diễn bằng các vòng tròn nhỏ (rỗng hoặc đặc), còn các cung được biểu diễn bằng một đường cong có hướng (với mũi tên) từ đỉnh đầu tới đỉnh cuối. Định nghĩa 1.1.4. Đồ thị có hướng hoặc vô hướng G = (V, E) được gọi là đồ thị có trọng số (hay thường gọi tắt là trọng đồ) nếu có ít nhất một trong hai hàm: f : V → WV và g : E → WE được xác định. Ở đây Wv và WE là các tập số. Giá trị f (v) cho v ∈ V được gọi là trọng số của đỉnh v, còn giá trị g(e) cho e ∈ E được gọi là trọng số của cung hay cạnh e. Người ta cũng thường ký hiệu trọng đồ bằng G = (V, E, f ) hay hay G = (V, E, f, g) tùy thuộc vào việc chỉ một hàm f , chỉ một hàm g hay cả hai hàm f và g được xác định. Trong khuôn khổ luận văn này, chúng ta chỉ sử dụng tới G = (V, E, g). Biểu diễn một đồ thị G = (V, E, g) có trọng số trên mặt phẳng ta biểu diễn đồ thị có hướng và gắn giá trị trọng số tương ứng lên trực tiếp sát phía bên cạnh của cung mang giá trị đó. Ví dụ 1.1.5. Cho đồ thị có hướng có trọng số với V = {a, b, c, d, f, g}, E = {ad, db, dc, bc, cf, cg, gf }, g(ad) = g(dc) = g(gf ) = 3, g(db) = g(bc) = 2, g(cf ) = g(cg) = 4. Khi đó biểu diễn của đồ thị có trọng số G: Hình 1.3: Đồ thị có trọng số G 6 1.1.2 Phổ của đồ thị 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.4. Hình 1.4: 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 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ì λxu = X xv (u = 1, 2, . . . , n), (1.1) 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.6. 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. 7 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ố P nguyên k ≥ 0, moment phổ thứ k của G là ni=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.7. ([2], [4]). 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ó: |λ||xu | ≤ X |xu | ≤ |∆(G)||xu |. v∼u Vì xu 6= 0, mệnh đề được chứng minh. Mệnh đề 1.1.8. ([2], [4]). Đồ 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 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 µk11 , . . . , µ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.9. Cho đồ thị G trong Hình 1.4, ta có    x −1 0 −1 −1   −1 x −1 0 −1     PG (x) =  0 −1 x −1 −1   −1 0 −1 x −1   −1 −1 −1 −1 x  8 = 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.10. Các giá trị riêng của chu trình có độ dài n là 2 cos 2πj n (j = 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π n (với bội 2). Giá trị riêng nhỏ nhất là −2 (với (n−1)π bội 1) nếu n là chẵn và 2 cos n (với bội 2) nếu n lẻ. Ví dụ 1.1.11. Đồ thị Petersen (Hình 1.5) có phổ là 31 , 15 , (−2)4 . Hình 1.5: Đồ 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.6(a) có phổ là 21 , 03 , (−2)1 . Đây là ví dụ với số đỉnh ít nhất. Hình 1.6(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. 9 Hình 1.6: 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.7 và 1.1.8, 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á 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í dụ 1.1.12. Cho đồ thị như trong Hình 1.4. 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 1 1 (9 + 17), 3, 3, (9 − 17) và các giá trị riêng Seidel là 3, (−1 + 17), −1, 2 2 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à A(G) = AU B BT ! 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 A(GU ) = AU B B C ! , 10 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.9). 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.13. ([2], [4]). 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 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.14. ([2], [4]). 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 Ma trận kề. Ma trận trọng số Xét đồ thị vô hướng G = (V, E) với tập đỉnh V = {1, 2, . . . , n} và tập cạnh E = {e1 , e2 , . . . , em }. Ta gọi ma trận kề của đồ thị G là (0;1) - ma trận A = {aij : i, j = 1, 2, . . . , n} với các phần tử được xác định theo quy tắc sau đây ( aij = 0, nếu {i, j} ∈ /E aij = 1, nếu {i, j} ∈ E, i, j = 1, 2, . . . , n. Ví dụ 1.2.1. Cho đồ thị như hình vẽ: 11 Hình 1.7: Đồ thị vô hướng G và đồ thị có hướng G1 Lời giải. Ma trận kề của đồ thị vô hướng G là: 1 2 3 4 5 6  1 0 2 1  3 1  4 0  5 1 6 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 1  0 0   0 . 1  1 0  Các tính chất của ma trận kề. 1) Rõ ràng ma trận kề của đồ thị vô hướng là đối xứng, tức là aij = aji , i, j = 1, 2, . . . , n. Ngược lại mỗi (0,1) - ma trận đối xứng cấp n sẽ tương ứng, chính xác đến cách đánh số đỉnh (còn nói là: chính xác đến đẳng cấu), với một đồ thị vô hướng n đỉnh. 2) Tổng các phần tử trên dòng i (cột j) của ma trận kề của đồ thị vô hướng chính bằng bậc của đỉnh i (đỉnh j). 3) Nếu ký hiệu apij , i, j = 1, 2, . . . , n là các phần tử của ma trận tích Ap = A | · A{z. . . A} p 12 Khi đó apij , i, j = 1, 2, . . . , n cho ta số đường đi khác nhau từ đỉnh i tới đỉnh j qua p − 1 đỉnh trung gian. Ma trận kề của đồ thị có hướng được định nghĩa hoàn toàn tương tự. Ví dụ 1.2.2. Đồ thị có hướng G1 cho trong Hình 1.7 có ma trận kề là ma trận sau 1 2 3 4 5 6  1 0 2 0  3 0  4 0  5 0 6 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1  0 0   0  0  1 0 Lưu ý rằng ma trận của đồ thị có hướng chưa chắc là ma trận đối xứng. Trong trường hợp đồ thị có trọng số cạnh hoặc cung, thay vì ma trận kề, để biểu diễn đồ thị ta sử dụng ma trận trọng số C = cij : i, j = 1, 2, . . . , n, với cij = cji , nếu (i, j) ∈ E và cij = θ, nếu (i, j) ∈ /E trong đó số θ, tùy từng trường hợp cụ thể, có thể được đặt bằng một trong các giá trị sau: 0, −∞, +∞. Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề (hoặc ma trận trọng số) là để trả lời câu hỏi: Hai đỉnh u, v có kề nhau trên đồ thị hay không, chúng ta chỉ phải thực hiện một phép so sánh. Nhược điểm lớn nhất của phương pháp này là không phụ thuộc vào số cạnh của đồ thị, ta luôn phải sử dụng n2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó. 13 1.3 Ma trận liên thuộc Xét G = (V, E), (V = {1, 2, . . . , n}, E = {e1 , e2 , . . . , em }) , là đồ thị có hướng. Xây dựng ma trận B = (bij , i = 1, 2, . . . , n, j = 1, 2, . . . , m), trong đó bij =    1 nếu tồn tại {i, j}, i < j   0 nếu không tồn tại {i, j}. −1 nếu tồn tại {i, j}, i > j Ma trận B xây dựng như quy tắc vừa nêu được gọi là ma trận liên thuộc đỉnh cung. Ví dụ 1.3.1. Xét đồ thị cho trên hình vẽ sau: Hình 1.8: Đồ thị vô hướng   1 −1 0 0  0 −1 0  . 1 0 0 −1  B = 1 Ma trận liên thuộc là một trong những cách biểu diễn rất hay được sử dụng trong các bài toán liên quan đến đồ thị có hướng mà trong đó phải xử lý các cung của đồ thị. 14 Chương 2 Tính chất của ma trận biểu diễn đồ thị và các phép toán đồ thị Trong chương này, tôi trình bày khái niệm ma trận Laplace của đồ thị, ma trận Laplace của một cạnh, ứng dụng của định lý Kirchhoff về đếm số cây bao trùm thông qua các giá trị riêng của ma trận Laplace của đồ thị cùng các kết quả liên quan đếm bài toán đếm, sau cùng là một phép toán trên đồ thị. Tôi tham khảo từ tài liệu [2], [4] - [6]. 2.1 Tính chất của ma trận biểu diễn đồ thị 2.1.1 Ma trận Laplace của đồ thị và một số tính chất cơ bản Định nghĩa 2.1.1. Cho một đồ thị vô hướng G = (V, E) với tập đỉnh V và tập hợp cạnh E. + Ma trận kề AG = aij của đồ thị G được xác định bởi ( aij := 1 khi {i, j} ∈ E, 0 khi {i, j} ∈ / E. + Ma trận bậc DG = aij là một ma trận đường chéo được định nghĩa: ( aij := deg (vi ) nếu i = j, 0 nếu i 6= j. 15 Khi đó, ma trận Laplace của đồ thị G : LG được định nghĩa bởi LG = DG − AG . Ví dụ 2.1.2. Cho đồ thị G như hình vẽ Hình 2.1: Đồ thị G Khi đó:  0 1  AG =  1 1  1 0 1 0 1 1 0 1  1  0  1 0  3 0  DG =  0 0 0 2 0 0 0 0 3 0  0  0  0 2  3 −1 −1 −1 −1 2 −1 0    Suy ra LG =  . −1 −1 3 −1 −1 0 −1 2 Nhận xét 2.1.3. Nếu một đỉnh i ∈ G là đỉnh cô lập thì hàng và cột tương ứng của ma trận Laplace đều bằng 0. [LG ]ij = 0, ∀i [LG ]ji = 0, ∀j. Nhận xét 2.1.4. Nếu G và H là hai đồ thị với cùng một tập đỉnh và tập cạnh rời nhau thì LG∪H = LG + LH .