Luận văn Thạc sĩ Toán học: Một số tính chất của ma trận và áp dụng vào đồ thị

ĐẠ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

Mục lục

Lời cảm ơn iii

Mở đầu 1

1 Kiến thức chuẩn bị

1.1.1 Khái niệm đồ thị 1.1.2 Phổ của đồ thị

1.1 Khái niệm của đồ thị và 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 . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 3 6 10 13

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ị . . . . . . . . . . . . . . . . . . . . . . . . 14 14 14 17 19 20 26

3 Áp dụng một số tính chất của ma trận vào đồ thị

3.1 Ứng dụng định lý Kirchhoff tìm số cây bao trùm của đồ thị . . . 3.2 Ứng dụng trong đếm số đồ thị con . . . . . . . . . . . . . . . . 3.3 Ứng dụng xác định bậc chính quy và tính hai phần . . . . . . . 32 32 33 36

Kết luận 41

Tài liệu tham khảo 42

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 = BT 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à định thức con chính thứ k của ma trận vuông L. • [L]k,k:

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

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¨onigsberg. 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ý

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.

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 (cid:54)= 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

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 }.

Hình 1.1: Đồ thị G

Khi đó biểu diễn của đồ thị vô hướng 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.

Hình 1.2: Mạng lưới xe bus

Ta có hình ảnh chính xác của đồ thị.

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 .

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.

Hình 1.3: Đồ thị có trọng số G

Khi đó biểu diễn của đồ thị có trọng số G:

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.

Hình 1.4: Một đồ thị được gán nhãn G và ma trận kề A của nó.

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.

v∼u

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ì (cid:88) (1.1) λxu = xv (u = 1, 2, . . . , n),

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.

i=1 λk

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ố nguyên k ≥ 0, moment phổ thứ k của G là (cid:80)n i 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ó:

(cid:88)

v∼u

|xu| ≤ |∆(G)||xu|. |λ||xu| ≤

Vì xu (cid:54)= 0, mệnh đề được chứng minh.

1 , . . . , µkm

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 µk1 m 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

PG(x) =

x −1 −1 0 −1 −1 0 −1 −1 −1 −1 −1

(cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)

(cid:12) 0 −1 −1 (cid:12) (cid:12) (cid:12) 0 −1 (cid:12) (cid:12) x −1 −1 (cid:12) (cid:12) x −1 (cid:12) (cid:12) x (cid:12)

= x5 − 8x3 − 8x2 = x2(x + 2)(x2 − 2x − 4).

√

√ √ 5) = (cid:104)x1(cid:105), ε(0) = (cid:104)x2, x3(cid:105), ε(1 −

5, λ2 = Giá trị riêng sắp xếp theo thứ tự không tăng lần lượt là λ1 = 1 + 5, λ5 = −2 với các véc tơ riêng độc lập tuyến tính 0, λ3 = 0, λ4 = 1 − √ 5)T , x2 = (0, 1, 0, −1, 0)T , x1, x2, x3, x4, x5, trong đó x1 = (1, 1, 1, 1, −1 + 5)T , x5 = (1, −1, 1, −1, 0)T . Chúng x3 = (1, 0 − 1, 0, 0, )T , x4 = (1, 1, 1, 1, 1 − ta có ε(1 + 5) = (cid:104)x4(cid:105) và ε(−2) = (cid:104)x5(cid:105), trong đó các ngoặc là ký hiệu không gian con sinh bởi mỗi véc tơ trong ngoặc.

n Ví dụ 1.1.11. Đồ thị Petersen (Hình 1.5) có phổ là 31, 15, (−2)4.

Hình 1.5: Đồ thị Petersen.

(với bội 2) nếu n lẻ. 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 bội 1) nếu n là chẵn và 2 cos (n−1)π

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.

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.

2(9 −

2(−1 +

√ √ √ 17) và các giá trị riêng Seidel là 3, 1

2(−1 + 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à (cid:32)

17), 3, 3, 1 √ 17). 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 17), −1, 2(9 + −1, 1

(cid:33)

, A(G) = AU BT B C

trong đó AU là ma trận kề của đồ thị con cảm sinh bởi U và BT là chuyển vị của B. Khi đó GU có ma trận kề

(cid:32)

(cid:33)

, A(GU ) = AU B 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.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 −1ST 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ư switching đối với (U \V ) ˙∪(V \U ). Ta thấy rằng switching xác định một quan 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

(cid:40)

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ẽ:

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 1 1 0 1 0 2 1 0 1 0 1 0    3 1 1 0 1 0 0   4 0 0 1 0 1 1   5 1 1 0 1 0 1  6 0 0 0 1 1 0

(cid:3)

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à

i, j = 1, 2, . . . , n. aij = aji,

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

ap ij, i, j = 1, 2, . . . , n

là các phần tử của ma trận tích

Ap = A · A . . . A (cid:125)

(cid:124)

(cid:123)(cid:122) p

Khi đó

ap ij, 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 1 1 0 0 0 2 0 0 0 0 0 0    3 0 1 0 1 0 0   4 0 0 0 0 0 0   5 0 0 0 1 0 1  6 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ó.

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 đó

nếu tồn tại {i, j}, i < j

−1 nếu tồn tại {i, j}, i > j bij =

nếu không tồn tại {i, j}.

 1   0

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.

Hình 1.8: Đồ thị vô hướng

Ví dụ 1.3.1. Xét đồ thị cho trên hình vẽ sau:





B =

  .

1 −1  1  1 0 0 −1 0 0 0 0 −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ị.

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

(cid:40) 1

khi {i, j} ∈ E, aij := 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:

(cid:40)

nếu i = j, deg (vi) aij := 0 nếu i (cid:54)= j.

Khi đó, ma trận Laplace của đồ thị G : LG được định nghĩa bởi

LG = DG − AG.

Hình 2.1: Đồ thị G

Ví dụ 2.1.2. Cho đồ thị G như hình vẽ

Khi đó:









AG = DG =

   

   

   

   

0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 3 0 0 0 0 2 0 0 0 0 3 0 0 0 0 2





. Suy ra LG =

   

   

3 −1 −1 −1 0 −1 2 −1 3 −1 −1 −1 2 −1 0 −1

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.

Bổ đề 2.1.5. ([2], [4]) Ma trận Laplace của hai đồ thị G và H bằng tổng trực tiếp của LG và LH

(cid:32)

(cid:33)

. LG∪H = LG ⊕ LH = LG 0 0 LH

Chứng minh. Xét đồ thị G ∪ v(H) = (VG ∪ VH, EG) và định nghĩa tương tự cho v(G) ∪ H.

Theo Nhận xét 2.1.3 ta có

(cid:32)

(cid:33)

. LG∪v(H) = và Lv(G)∪H = 0 LG 0 LH

(cid:32) 0 0 0 LH

Theo Nhận xét 2.1.4 ta có

(cid:32)

(cid:33)

. LG∪H = LG ⊕ LH = LG 0 0 LH

Điều này có nghĩa: ma trận Laplace bằng tổng trực tiếp của các ma trận Laplace của các thành phần liên thông.

Định lý 2.1.6. ([2], [4]). [Hợp của các phổ rời nhau]. Nếu LG có các tập vectơ riêng (v1, v2, . . . , vn) với các giá trị riêng (λ1, λ2, . . . , λn) và LH có các tập vectơ riêng (ω1, ω2, . . . , ωn) và các giá trị riêng (µ1, µ2, . . . , µn). Khi đó LG∪H có các vectơ riêng:

v1 ⊕ 0, v2 ⊕ 0 . . . , vn ⊕ 0, 0 ⊕ ω1, 0 ⊕ ω2, . . . , 0 ⊕ ωn

với các giá trị riêng:

λ1, λ2, . . . , λn, µ1, µ2, . . . , µn.

Chứng minh. Từ Bổ đề 2.1.5 ta có:

(cid:32)

(cid:33)

. LG∪H = LG ⊕ LH = LG 0 0 LH

suy ra

(cid:32)

(cid:33) (cid:32)

(cid:33)

(cid:32)

(cid:33)

= . LG∪H ∗ (v1 ⊕ 0) = v1 0 λ1v1 0 0 LG 0 LH

2.1.2 Ma trận Laplace của một cạnh

Định nghĩa 2.1.7. Cho đồ thị G = (V, E), e ∈ E. Lấy Le là ma trận Laplace của n đỉnh mà chỉ bao gồm một cạnh là e.

Hình 2.2: Đồ thị G

Ví dụ 2.1.8. Cho đồ thị G như hình vẽ với E = {v1, v2, . . . , vn}

Suy ra





Le =

...

     

     

1 −1 0 0 . . . 0 0 0 . . . 0 −1 0 0 . . . 0 0 ... ... ... . . . 0 0 . . . 0 0 1 0 ... 0

Do vậy, ta có biểu diễn Laplace của một cạnh e như sau:

(cid:32)

(cid:33)

⊕ 0. Le = 1 −1 1 −1

Bởi tính cộng tính LG được xác định bởi công thức

(cid:88)

e∈E

Le. LG =

Ví dụ 2.1.9. Cho đồ thị G = (V, E), E = {1, 2, 3, 4}, V = {(1, 2), (1, 3), (1, 4)} như hình vẽ:

Hình 2.3: Đồ thị G

Khi đó





, L(1,2) = L(1,3) =

   

   

   

   

1 −1 0 0 0 0 1 −1 0 0 0 0 0 0 0 0 0 −1 0 1 0 0 0 0 0 1 −1 0 0 0 0 0





L(1,4) =

   

   

0 0 −1 1 0 0 0 0 0 0 0 0 1 −1 0 0

Suy ra













(cid:88)

+ + Le = LG =

   

   

   

   

   

   

e∈E

1 −1 0 0 0 0 1 −1 0 0 0 0 0 0 0 0 0 −1 0 1 0 0 0 0 0 1 −1 0 0 0 0 0 0 0 −1 1 0 0 0 0 0 0 0 0 1 −1 0 0





. =

   

   

3 −1 −1 −1 0 −1 −1 0 1 0 −1 0 0 −1 0 −1

Nhận xét 2.1.10. L là nửa xác định dương. Thật vậy





(cid:32)

(cid:33)

(cid:32)

(cid:19)

(cid:16)

(cid:17)

− = . = 2 1 −1 Le =

 

 

(cid:18) 1 √ 2

1 √ 2 1 −1 1 −1 1 −1 − 1 √ 2 1 √ 2

(cid:19)T

, Vì vậy là vectơ riêng ứng với giá trị riêng 2.

(cid:18) 1 √ 2

−1 √ 2

Sự phân tích này cho ta hệ quả

(cid:33)

(cid:32)

(cid:33)

(cid:32)

(cid:17)

(cid:16)

(cid:17)

(cid:16)

1 −1 = (x1 − x2)2. xT Lex = x1, x2 1 −1 x1 x2

Chú ý 2.1.11. Ma trận Laplace là một dạng bình phương, cụ thể (cid:19)

(cid:88)

(cid:18) (cid:88)

e∈E

i,j∈E

e∈E

x = xT Lex = Le (xi − xj)2. xT LGx = xT

Điều này có nghĩa LG là nửa xác định dương.

2.1.3 Phân tích ma trận Laplace

Nhận xét 2.1.12.

LG = BT · B.

Chứng minh. Giả sử

(cid:88)

i=1.

= (Bij)n [BT B]ij = ( cột thứ i của B)( hàng thứ j của B) j=1 = (Bij)n

Điều này sẽ cho chúng ta ba trường hợp

• Khi i = j

(cid:88)

j=1)2 =

e liên thuộc vi

1 = deg(i). [BT B]ij = ((Bij)n

• Khi i (cid:54)= j và không tồn tại cạnh giữa vi và vj

(cid:88)

j=1(Bij)n

i=1 = 0,

[BT B]ij = (Bij)n

cũng như là mọi cạnh đều không liên thuộc tới ít nhất vi hoặc vj.

• Nếu i (cid:54)= j và tồn tại cạnh e(cid:48) giữa vi và vj

(cid:88)

[BT B]ij = (Be,vi)(Be,vj ) = (Be(cid:48),vi)(Be(cid:48),vj ) = −1.

2.1.4 Định lý Kirchhoff

n (cid:89)

Định lý 2.1.13. ([2], [4]). Giả sử L là một ma trận Laplace của một đơn đồ thị liên thông G với n đỉnh. Khi đó, số lượng cây bao trùm của G, kí hiệu t(G) được xác định bởi công thức

i=1

t(G) = hay λi tG = Ckk(L) 1 n

với λi là các giá trị riêng không âm của LG (ma trận Laplace của đồ thị G).

Nhận xét 2.1.14. Ta thấy rằng tổng của mọi phần tử trên mỗi hàng của ma trận Laplace G đều bằng 0. Do đó, vectơ [1, 1, . . . , 1]T là vectơ riêng của L với giá trị riêng 0. Do đó mọi giá trị riêng của L đều không âm và 0 phải là giá trị riêng nhỏ nhất của L.

2.1.4.1 Hạng của ma trận con của ma trận liên thuộc B

Chú ý rằng mỗi một cột của ma trận liên thuộc có chính xác một giá trị 1 và một giá trị (-1). Do đó, tổng các thành phần của mỗi cột bằng 0. Tên tổng của tất cả các vectơ hàng của ma trận bằng 0. Do đó nó phụ thuộc tuyến tính. Vậy hạng của ma trận B phải nhỏ hơn n. Do đó chúng ta có những điều sau đây.

Hệ quả 2.1.15. ([2], [4]). Nếu G liên thông và BG là ma trận liên thuộc của G thì rank(BG) ≤ n − 1.

Bây giờ chúng ta xem xét ma trận con H của G trên k < n đỉnh mà rank(BH) = k. Điều đó có nghĩa là mọi hàng của BH là độc lập tuyến tính. Do đó tồn tại ít nhất một cạnh e = (u, v) mà nối đỉnh của H với đỉnh không thuộc H. Nói một cách khác, H không thể là một thành phần liên thông của G. Do đó chúng ta có điều sau đây.

Hệ quả 2.1.16. ([2], [4]). Nếu hạng của ma trận liên thuộc BH là n − 1 với H là ma trận con (n − 1) đỉnh của G thì G liên thông.

Bổ đề 2.1.17. ([2], [4]). Định thức của mọi ma trận vuông (n − 1) × (n − 1) của B đều bằng 0 hoặc 1 hoặc (−1).

2.1.4.2 Hạng của ma trận B và tính liên thông của G.

Giả sử (cid:101)B là ma trận con cho bởi B bằng cách xóa đi chính xác một hàng của B. Chú ý rằng có ít nhất một cột của B có tổng các giá trị khác 0. Vậy các hàng của (cid:101)B sẽ độc lập tuyến tính và rank( (cid:101)B) sẽ lớn hơn hoặc bằng số lượng hàng của (cid:101)B. Đo đó, rank( (cid:101)B) ≥ n − 1.

Tuy nhiên, hạng của ma trận liên thuộc B phải lớn hơn hoặc bằng bất kỳ hạng của ma trận con của nó mà trong đó có (cid:101)B. Mà ở đây, ma trận con lớn nhất của B có n − 1 hàng.

Hệ quả 2.1.18. ([2], [4]). Nếu G liên thông và B là ma trận liên thuộc của G thì rank(B) ≥ n − 1.

Bổ đề 2.1.19. ([2], [4]). [Hạng của ma trận liên thuộc của ma trận liên thông]. Cho B là ma trận liên thuộc của đồ thị G. Khi đó G liên thông khi và chỉ khi rank B = n − 1.

Chứng minh. (⇒) Từ Hệ quả 2.1.15 và 2.1.18, ta thấy G liên thông thì (n−1) ≥ rank B ≥ (n − 1) điều này có nghĩa rank B = n − 1.

(⇐) Cho rank B = n − 1. Khi đó, tồn tại một ma trận con (n − 1) × m của B gọi là (cid:101)B, mà có hạng bằng n − 1. Giả sử (cid:101)B là ma trận liên thuộc của ma trận con H((cid:101)V , (cid:101)E) của G trên n − 1 đỉnh hạng của (cid:101)B khác với số hàng của (cid:101)B. Chúng ta gắn là Bổ đề 2.1.23 và ở đó G liên thông.

2.1.4.3 Sự liên hệ giữa cây bao trùm và ma trận liên thuộc

Ma trận con T (V, (cid:101)E) là cây bao trùm của đồ thị G(V, E) nếu có những tính

chất sau:

1. T có n đỉnh và n − 1 cạnh.

2. T liên thông.

3. Ma trận liên thuộc BT có n dòng và n − 1 cột.

Chúng ta xem xét BT là ma trận n × m ra. Ở đó T liên thông, theo Bổ đề 2.1.19 ta có rank(BT ) = n − 1, điều đó có nghĩa là tổng hàng của BT không bằng 0, và do đó bộ (n − 1) hàng của BT là độc lập tuyến tính. Do đó, mọi tập hàng (cid:101)B của BT bao gồm n − 1 hàng (và tất cả (n − 1) cột) sẽ có hạng n − 1. Bây giờ vì (cid:101)B là một ma trận vuông với (n − 1) hàng và (n − 1) cột với hạng (n − 1), nó có nghĩa det( (cid:101)B) (cid:54)= 0. Do đó, chúng ta chứng minh các bổ đề sau

Bổ đề 2.1.20. ([2], [4]). [Định thức của ma trận vuông bất kỳ (n − 1) của BT ]. Nếu BT là ma trận liên thuộc của cây bao trùm T của G thì mọi ma trận con, vuông cấp (n − 1) × (n − 1) của BT không suy biến.

Chứng minh. Do BT là ma trận liên thuộc của cây bao trùm G nên hạng của ma trận BT phải là (n − 1) và định thức của ma trận (n − 1) × (n − 1) của BT phải thỏa mãn det(BT ) (cid:54)= 0 do đó BT không suy biến.

Bổ đề 2.1.21. ([2], [4]). Cho G là đồ thị với n đỉnh và B là ma trận liên thuộc của nó. Lấy H là ma trận con của G với n − 1 cạnh và BH là ma trận liên thuộc của nó. Khi đó H là cây bao trùm của G khi và chỉ khi mọi ma trận con, vuông cấp (n − 1) × (n − 1) của BH là không suy biến.

Chứng minh. (⇒) Lấy G liên thông. Khi ấy G là đồ thị với n đỉnh và B là ma trận liên thuộc của nó. Lấy H là ma trận con của G với n − 1 cạnh và BH là ma trận liên thuộc của nó. Khi đó H là cây bao trùm của G. Vận dụng Bổ đề 2.1.20 ta có BH là không suy biến.

(⇐). Mọi ma trận vuông con cấp (n − 1) × (n − 1) của BH là không suy

biến. Thật vậy:

Nếu mọi ma trận con (cid:101)B cấp (n − 1) × (n − 1) của ma trận B là không suy biến điều đó có nghĩa là rank( (cid:101)B) = n − 1. Do đó áp dụng Hệ quả 2.1.16 chúng ta thấy H liên thông. Do đó H có đúng n − 1 cạnh với n đỉnh nên H phải là một cây. Do đó H là cây bao trùm.

Từ hai bổ đề trên ta thu được các hệ quả sau:

Hệ quả 2.1.22. ([2], [4]). Mối một ma trận vuông không suy biến của B tương ứng với một cây bao trùm cảm sinh bởi chính những cột của nó.

Chứng minh. Cho G = (V, E) là một đồ thị liên thông. Lấy Q là một ma trận con, vuông cấp (n − 1) × (n − 1) của B và lấy GQ(VQ, EQ) là ma trận con với mỗi Q là một ma trận liên thuộc. Không mất tính tổng quát ta giả sử

VQ = {v1, v2, . . . , vn−1} ở đó rank(Q) = n − 1 (bởi nó không suy biến), có ít nhất một cột có tổng hàng khác 0 và do đó có một cạnh liên thông với đỉnh u mà u ∈ V \VQ. Do đó ma trận con T (VQ ∪ {u}, EQ) liên thông có n đỉnh và n − 1 cạnh và do vậy nó là cây bao trùm của đồ thị G với cùng các cạnh tương ứng với các cột ở Q.

Hệ quả này dẫn chúng ta tới một kết quả quan trọng sau đây.

Bổ đề 2.1.23. ([2], [4]). [Số cây bao trùm và ma trận liên thuộc của B]. Giả sử (cid:101)Bk là ma trận con của ma trận B có được bằng cách xóa hàng thứ k từ B. Khi đó (cid:101)Bk có n − 1 hàng và m cột. Do đó số lượng cây bao trùm của G, ký hiệu t(G), bằng số lượng ma trận con không suy biến cấp (n − 1) × (n − 1) của (cid:101)Bk.

Chứng minh. Theo Hệ quả 2.1.22 mỗi một ma trận con Q không suy biến cấp (n − 1) × (n − 1) của (cid:101)Bk tương ứng cho một cây bao trùm. Tuy nhiên (cid:101)Bk có n − 1 hàng và m cột, mỗi Q có một bộ cạnh khác nhau. Do đó số cây bao trùm của G bằng số ma trận không suy biến (cid:101)Bk với số chiều (n − 1) × (n − 1).

2.1.4.4 Một số kết quả giải tích ma trận

F1: (cid:101)Bk là ma trận con cấp (n − 1) × m của ma trận liên thuộc B cấp n × m bằng cách xóa bỏ hàng thứ k. Khi đó phần bù đại số của phần tử đường chéo thứ k của ma trận Laplace được tính như sau:

(cid:32)

(cid:33) .

Ckk = det

(cid:101)Bk · (cid:101)BT k

F2: Công thức Cauchy - Binet

det(AB) = det A · det B.

F3: Phần phụ đại số thứ k đường chéo chính của ma trận vuông cấp (n × n)

bằng với định thức con chính thứ k. Nghĩa là

với 1 < k ≤ n. Ckk = [L]kk

F4: Tích của tất cả các giá trị riêng không âm của tổ hợp Laplace L bằng tích

n (cid:88)

của mọi định thức con chính của L. Nghĩa là

k=1

(λ2λ3 . . . λn) = [L]kk.

Chứng minh. Do [L]kk = Ckk mà Ckk là ma trận vuông cấp n với giá trị riêng λ2, . . . , λn.

n (cid:88)

Bởi vì giá gị riêng là n nghiệm của đa thức đặc trưng pL(λ)

p=0

(−1)n−pCn−pλp det(λIn − Ck) =

pA(λ) = (λ − λ2)(λ − λ3) . . . (λ − λn)

= λn−1 − (λ2 + λ3 + . . . + λn)λn−2 + . . . + (−1)nλ2λ3 . . . λn.

So sánh với hệ số của đa thức đặc trưng. Chúng ta có

C11 = trA = λ2 + λ3 + . . . + λn = [L]11 C(n−1)(n−1) = λ2λ3 . . . λn = [L](n−1)(n−1).

2.1.4.5 Chứng minh định lý Kirchhoff

n (cid:89)

Định lý 2.1.24. ([2], [4]). Cho 0 = λ1 ≤ λ2 ≤ λ3 ≤ . . . ≤ λn là n giá trị riêng của ma trận Laplace L của đồ thị G

k=1

t(G) = × λk. 1 n

Chứng minh. Bước 1: (Sử dụng F1) Lấy P là một ma trận con cấp (n − 1) × m của ma trận liên thuộc B bằng cách bỏ đi hàng thứ k của B.

Ckk = det(P · P T ).

Bước 2: Chúng ta xây dựng tất cả các ma trận con cấp (n − 1) × (n − 1) từ P như sau: Lấy s là một dãy bất kỳ từ n − 1 phần tử lấy từ 1, 2, 3, . . . , m sao cho Si < Si+1. Lấy S là bộ tất cả các dãy s. Bây giờ, xây dựng một dãy điển hình s, là Ps là ma trận con cấp (n − 1) × (n − 1) của P bao gồm bởi giữ chỉ những cột từ P mà những phần tử trong s.

Bước 3: (Sử dụng F2) Chúng ta muốn đánh giá từ bước 1 sử dụng công thức

Cauchy - Binet như sau:

s∈S (cid:88)

Ckk = det(P · P T ) (cid:88) = det(Ps) × det(P T s )

s ).

= do det(Ps)2 det(Ps) = det(P T

Bước 4: Ps phải bằng 0 hoặc 1 hoặc (-1), do đó phương trình ở trên có dạng

(cid:88)

s∈S

det(Ps)2 Ckk =

(cid:88)

s∈S,det Ps(cid:54)=0

s∈S,det Ps=0 (cid:88)

(±1)2 = 02 +

s∈S,det Ps(cid:54)=0

= 1

= ma trận vuông không suy biến cấp (n − 1) của P

= ma trận vuông không suy biến cấp (n − 1) của (cid:101)Bk.

Bước 5: Ta có số lượng cây bao trùm trong G tương đương với số lượng ma trận con không suy biến cấp (n − 1) × (n − 1) của B. Do đó phương trình trên trở thành:

Ckk = số lượng cây bao trùm của G = t(G).

Bước 6: Chú ý t(G) không phụ thuộc vào cách lấy k và do đó mỗi một phần

bù đại số đường chéo của tổ hợp Laplace Ct bằng t(G)

t(G) = C11 = C22 = . . . = Cnn.

n (cid:88)

Bước 7: (Sử dụng F4 và F5)

k=1 n (cid:88)

λ2λ3 . . . λn = [L]k,k (bởi F4)

k=1

= Ck,k (bởi F5)

= n × t(G) (bởi Bước 6).

Do đó chúng ta chứng minh được định lý.

2.2 Các phép toán đồ thị

Phần này được tham khảo chính từ [4] với việc trình bày lại cách xác định đa thức đặc trưng của các đồ thị được suy ra từ các đồ thị đơn giản hơn bằng các phép toán. Điển hình như chúng ta định nghĩa phép toán này trên các đồ thị G1, G2, . . . , Gn (n = 1, 2, . . .) để thu được đồ thị G, và sau đó mô tả quan hệ giữa phổ của G1, G2, . . . , Gn và phổ của G. Trong một số trường hợp quan trọng, phổ của G được xác định bởi phổ của G1, G2, . . . , Gn, trong các trường hợp khác, bất biến cộng tính của G1, G2, . . . , Gn là quan trọng trong dạng các góc đồ thị hoặc các hàm nhảy khái quát. Các phép toán được xem xét bao gồm cả việc xóa hay thêm đỉnh.

Các phép toán phần bù, hợp và nối liên hệ với nhau bằng hệ thức

G∇H = G ˙∪H.

Trước hết chúng ta khảo sát hợp (rời) của các đồ thị. Nếu G có ma trận kề A và H có ma trận kề B, thì ma trận kề của G ˙∪H là tổng trực tiếp

(cid:32)

(cid:33)

A + B = . A O O B

Khảo sát các định thức dẫn trực tiếp tới kết quả sau.

Định lý 2.2.1. ([4]) Đa thức đặc trưng của hợp rời hai đồ thị là

PG ˙∪H(x) = PG(x)PH(x).

Từ định lý ta có nếu G1, G2, . . . , Gs là các hợp phần của đồ thị G thì

PG(x) = PG1(x)PG2(x) . . . PGs(x).

Nếu G là một đồ thị chính quy thì đa thức đặc trưng PG(x) của phần bù G của G có thể được biểu diễn bởi PG(x) (và ngược lại). Quan hệ này được cho trong định lý sau.

Định lý 2.2.2. ([4]) Nếu G là một đồ thị chính quy bậc r với n đỉnh, thì

(2.1) PG(−x − 1), PG(x) = (−1)n x − n + r + 1 x + r + 1

tức là, nếu các giá trị riêng của G là λ1 = r, λ1, . . . , λn, thì các giá trị riêng của G là n − 1 − r, −λ2 − 1, . . . , −λn − 1.

Chứng minh. Nếu G có ma trận kề A thì G có ma trận kề J − I − A. Đặt x1, . . . , xn là một cơ sở trực giao của Rn gồm các véc tơ riêng của A với x1 = j. Khi đó chúng ta có Ax − 1 = rx1, (J − I − A)x1 = (n − 1 − r)x1 và (J − I − A)xi = (−1 − r)xi(i = 2, . . . , n).

Trong trường hợp tổng quát, phổ của đồ thị G không xác định phổ của G. Ví dụ các phần bù của các đồ thị cùng phổ C4 ˙∪K1, K1,4 là không cùng phổ. Tất nhiên phổ của G được xác định bởi phổ và góc chính của G.

Mệnh đề 2.2.3. ([4]) Cho đồ thị G với n đỉnh, phần bù G của G có đa thức đặc trưng

(cid:18)

(cid:19)

m (cid:88)

i=1

1 − n . (2.2) PG(x) = (−1)nPG(−x − 1) β2 i x + 1 + µi

Chứng minh. Chúng ta sử dụng khai triển định thức đa tuyến tính trong phép hội (conjunction) với sự phân hoạch phổ của A). Đa thức đặc trưng của G được cho bởi:

PG(x) = det((x + 1)I + A − J)

m (cid:88)

i=1

= det((x + 1)I + A) − jT adj((x + 1)I + A)j = (−1)nPG(−x − 1)(1 − jT ((x + 1)I + A)−1) (cid:18) (cid:19) 1 − n . (2.3) = (−1)nPG(−x − 1) β2 i x + 1 + µi

Chúng ta có thể áp dụng đúng lập luận tương tự với J − 2A − I để thu

được:

Mệnh đề 2.2.4. ([4]) Cho đồ thị G bất kỳ với n đỉnh, đa thức đặc trưng SG(x) của ma trận kề Seidel của G được xác định, bởi

(cid:18)

(cid:19)(cid:18)

(cid:19)

m (cid:88)

i=1

− (x + 1) 1 − n . (2.4) SG(x) = (−2)nPG 1 2 β2 i x + 1 + 2µi

Ta cũng có thể áp dụng lập luận tương tự cho G ˙∪H. Theo Định lý 2.2.1, giá trị riêng của G · ∪H là các giá trị riêng của G hoặc H (hoặc cả hai). Chúng

ta giả sử rằng G có n1 đỉnh và H có n2 đỉnh. Ma trận kề của G ˙∪H có phân tích phổ là

(cid:32)

(cid:33)

(cid:32)

(cid:33)

(cid:32)

(cid:33)

, = ξ1 + . . . + ξs A O O B P1 O O Q1 Ps O O Qs

trong đó Pi là phép chiếu trực giao Rn1 → εA(ξi) và Qi là phép chiếu trực giao Rn2 → εB(ξi) (i = 1, . . . , s). Ở đây εA(ξi) = {0} nếu ξi không là một giá trị riêng của G và εB(ξi) = {0} nếu ξi không là một giá trị riêng của H. Như trong Mệnh đề 2.2.3 chúng ta có

(cid:19)

s (cid:88)

, 1−n1 −n2

(cid:18) PG ˙∪H(x) = (−1)n1+n2PG ˙∪H(−x−1)

i=1

β2 i x + 1 + ξi γ2 i x + 1 + ξi

(2.5) trong đó các số βi, khác không chính là các góc chính khác không của G và các số γi khác không chính là các góc chính khác không của H. Lập luận này có thể mở rộng cho hợp rời của các đồ thị tùy ý bất kỳ. Chú ý rằng góc chính δi, của G ˙∪H được cho bởi

i = n1β2

i + n2γ2 i

(i = 1, . . . , s). (n1 + n2)δ2

Hệ trên được rút ra từ định nghĩa hoặc từ so sánh (2.2) và (2.5). Ta có thể viết lại Phương trình (2.2) sử dụng Mệnh đề 2.2.1 và 2.2.3 để thu được:

PG ˙∪H(x) = (−1)n2PG(x)PH(−x − 1) + (−1)n1PG(−x − 1)PH(x)

(2.6) − (−1)n1+n2PG(−x − 1)PH(−x − 1).

Thay G bởi G, H bởi H, ta thu được kết quả sau:

Định lý 2.2.5. ([4]) Cho G và H là các đồ thị có tương ứng n1, n2 đỉnh. Đa thức đặc trưng nối G∇H là

PG∇H(x) = (−1)n2PG(x)PH(−x − 1) + (−1)n1PH(x)PG(−x − 1)

(2.7) − (−1)n1+n2PG(−x − 1)PH(−x − 1).

Hệ quả 2.2.6. ([4]) Cho G và H là các đồ thị có tương ứng n1, n2 đỉnh. Khi đó

(cid:19)

(cid:18)

m (cid:88)

p (cid:88)

i γ2 β2 k (x − µi)(x − vk)

i=1

k=1

, 1 − n1n2 PG∇H(x) = PG(x)PH(x)

trong đó G có µ1, . . . , µm các giá trị riêng phân biệt với góc chính tương ứng β1, . . . , βm và H có v1, . . . , vm các giá trị riêng phân biệt với góc chính tương ứng γ1, . . . , γm.

Chứng minh. Chứng minh được suy ra từ Định lý 2.2.5 và Mệnh đề 2.2.3.

Từ Mệnh đề 2.2.3 và Định lý 2.2.5 chúng ta cũng có thể tìm thấy mở rộng cho đa thức đặc trưng của nón qua một đồ thị G (tức là đồ thị thu được từ G bằng cách thêm một đỉnh kề cho mọi đỉnh của G):

Mệnh đề 2.2.7. ([4]) Nón trên G có đa thức đặc trưng

(cid:18)

(cid:19)

m (cid:88)

i=1

x − . (2.8) PK1∇G(x) = PG(x) nβ2 i x − µi

Tiếp theo chúng ta thảo luận việc nối các đồ thị chính quy. Đầu tiên chúng

ta có thể đưa ra kết quả sau từ Mệnh đề 2.2.2 và Định lý 2.2.5.

Định lý 2.2.8. ([4]) Nếu G1 là đồ thị r1 chính quy với n1 đỉnh và G2 là đồ thị r2, chính quy với n2 đỉnh thì đa thức đặc trưng của đồ thị nối G1∇G2 được cho bởi

(2.9) ((x − r1)(x − r2) − n1n2). PG1∇G2(x) = PG1(x)PG2(x) (x − r1)(x − r2)

Chú ý rằng nếu G1∇G2 là đồ thị chính quy thì cả G1 và G2 là chính quy. Nói các khách, nếu G1 là đồ thị r1 chính quy với n1 đỉnh và G2 là đồ thị r2 chính quy với n2 đỉnh thì G1∇G2 là một đồ thị chính quy khi và chỉ khi r1 + n2 = r2 + n1. Trong trường hợp này,G1∇G2 có n(1) = n + 1 + n2 đỉnh và là chính quy bậc r(1) = r1 = n2 = r2 + n1. Vì vậy quan hệ n1 − r1 = r2 − r2 = n(1) − r(1) vẫn đúng và từ (2.9) ta có

. (2.10) PG1∇G2(x) = (x − r1)(x + n(1) − r(1)) PG1(x)PG2(x) (x − r1)(x − r2)

Phương trình này có thể được sử dụng để xác định P(G1∇G2)∇G3(x) từ PGi(x) (i = 1, 2, 3). Điều kiện cần để (G1∇G2)∇G3 chính quy (bậc r2 và n2 đỉnh) là n(1) − r(1) = n3 − r3 = n(2) − r(2); trong trường hợp này, từ (2.9) và (2.10) chúng ta có

. P(G1∇G2)∇G3(x) = (x−r(2))(x+n(1)−r(1))(x+n(2)−r(2)) PG1(x)PG2(x)PG3(x) (x − r1)(x − r2)(x − r3)

Tiếp theo chúng ta đến với kết quả sau (trong đó tính kết hợp của phép toán nối cho phép chúng ta bỏ qua dấu ngoặc đơn trong G1∇G2∇ . . . ∇Gk).

k (cid:89)

Định lý 2.2.9. ([4]) [FiGr] Cho G1, . . . , Gk là các đồ thị đều với Gi chính quy bậc ri và ni đỉnh (i = 1, 2, . . . , k), trong đó quan hệ n1 − r1 = n2 − r2 = . . . = nk − rk = s. Khi đó đồ thị G = G1∇G2∇ . . . ∇Gk có n = n1 + n2 + . . . + nk đỉnh và là đều bậc r = n − s. Vì vậy chúng ta có

i=1

(2.11) . PG(x) = (x − r)(x + n − r)k−1 PGi x − ri

∞ (cid:88)

Chúng ta kết thúc phần này với một vài chú ý trên các góc chính và các hàm bước đi tổng quát (walk generating functions). Từ Mệnh đề 2.2.3, 2.2.4 và 2.2.7 chúng ta thấy rằng, cho trước các giá trị riêng của G, sự hiểu biết về góc chính của G tương đương với sự hiểu biết về phổ của G hoặc phổ của ma trận Seidel của G hoặc phổ của nón qua G. Nói cách khác, cho trước các trị riêng của G, sự hiểu biết về góc chính của G tương đương với sự hiểu biết về hàm bước đi tổng quát

k=0

(2.12) HG(t) = n Nktk,

m (cid:88)

trong đó Nk là số bước đi độ dài k trong G. Sử dụng Định lý 1.3.5 chúng ta có

p=1

. (2.13) HG(t) = n β2 i 1 − tµp

Theo đó chúng ta có thể viết công thức (2.2) và (2.4) dưới dạng

PG(x) = (−1)nPG(−1 − x)(1 − (x + 1)−1HG(−1/(1 + x))),

SG(x) = (−1)n2nPG(−(x − 1)/2)(1 − (x + 1)−1HG(−2/(x + 1))).

Chúng ta cũng có thể sử dụng phương trình đầu tiên để biểu diễn hàm bước đi tổng quát theo đa thức đặc trưng:

(cid:27) .

− 1 (2.14) HG(t) = 1 t

(cid:26) (−1)n PG(− t+1 t ) PG( 1 t )

Điều này cho phép chúng ta biểu diễn HG theo HG, và HG1∇G2 theo HG1 và HG2:

Định lý 2.2.10. ([4])

HG(− t t+1 ) t+1−tHG( −t

t+1 )

; (i) HG(t)

(t) = HG1(t) + HG2(t); (ii) HG1 ˙∪G2

. (iii) HG1∇G2(t) = HG1(t) + HG2(t) + 2tHG1(t)HG2(t) 1 − t2HG1(t)HG2(t)

Chứng minh. Từ (2.14) chúng ta có

(cid:26)

(cid:27)

− 1 (2.15) HG(t) = 1 t (−1)n PG(− t+1 t ) PG( 1 t )

và

(cid:26)

(cid:27)

t )/PG( 1

) = − − 1 . (2.16) HG( −t t + 1 t + 1 t (−1)n PG( 1 t ) PG(− t+1 t )

Mối quan hệ trong (i) có được bằng các loại trừ PG(− t+1 t ) từ (2.15) và (2.16). Mối quan hệ trong (ii) được suy từ định nghĩa (2.12). Mối quan hệ thứ ba được suy ra từ (i) và (ii) khi chúng ta biểu diễn G1∇G2 như là phần bù của G1 ˙∪G2.

Chương 3

Áp dụng một số tính chất của ma

trận vào đồ thị

Trong chương này, ta xem xét một vài ứng dụng của phổ đồ thị trong việc xác định tính chất định tính của đồ thị như tìm số cây bao trùm của đồ thị, đếm số đồ thị con, tính chính quy đồ thị, tính liên thông và bài toán khoảng cách phổ đồ thị của Richard Brualdi. Tài liệu tham khảo [2], [4] - [6].

3.1 Ứng dụng định lý Kirchhoff tìm số cây bao trùm

của đồ thị

Như chúng ta đã biết, rất nhiều mô hình thực tế được giải quyết bằng các bài toán về đồ thị như mô hình mạng lưới giao thông trong một khu vực hay sơ đồ bộ máy công ty. Định lý Kirchhoff giúp chúng ta tính toán số cây bao trùm của đồ thị từ đó giải quyết các bài toán như: 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. Giả sử các ga tàu là một đỉnh và cần xây dựng đường đi sao cho đường đó đi qua tất cả các ga số đường cần phải xây dựng là ít nhất.

Vậy ma trận kề và ma trận bậc tương ứng của mô hình là









. DA = , AA =

   

   

   

   

0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0 2 0 0 0 0 3 0 0 0 0 3 0 0 0 0 2

Hình 3.1: Đồ thị G

Ma trận Laplace của mô hình:





. LA =

   

   

1 0 2 −1 3 −1 −1 −1 0 −1 −1 3 2 0 −1 −1

Tiếp theo, xây dựng ma trận Lkk bằng cách xóa bỏ bất cứ một hàng và 1 cột từ LA. Ví dụ ta xóa bỏ hàng 1 và cột 1, kết quả được ma trận





L11 =

 

  .

3 −1 −1 0 −1 3 2 −1 −1

Cuối cùng ta lấy định thức của Lkk:

det L11 = 18 − 1 − 1 − 3 − 2 − 3 = 8.

Vậy số cây bao trùm của mô hình là 8 tương ứng với số cách xây dựng mạng lưới đường sắt đúng yêu cầu.

3.2 Ứng dụng trong đếm số đồ thị con

Kết quả sau đây đóng vai trò căn bản trong đếm đồ thị con của một đồ thị

với phổ λ1 ≥ λ2 ≥ · · · ≥ λn.

n (cid:88)

Định lý 3.2.1. ([6]) Số bước đi (walk) đóng độ dài k trong một đồ thị G bằng sk, trong đó

i=1

(3.1) sk = λk i ,

là moment phổ thứ k của G.

Rõ ràng s1 = 0 (hay tương đương G không có khuyên (loop)). Nếu G có e cạnh và t tam giác, thì s2 = 2e và s3 = 6t. Để thấy được điều này, đầu tiên chú ý rằng một bước đi đóng có độ dài 2 đi qua một cạnh, trong khi một cạnh ij tính cho hai bước đi đóng độ dài 2, cụ thể iji và jij. Thứ hai, một bước đi đóng độ dài 3 đi qua một tam giác, và mỗi tam giác tính cho 6 bước đi độ dài 3 (có 3 cách chọn điểm bắt đầu và lựa chọn hướng).

Theo đó, ta có:

(i) Số định bằng với số giá trị riêng (tính cả bội);

2s2;

(ii) số cạnh bằng 1

2s2;

(iii) bậc trung bình (mean degree) là 1

6s3;

(iv) số tam giác bằng 1

2ns3.

(v) trung bình số tam giác chứa một đỉnh cho trước là 1

Các nhận xét bên trên giải thích tại sao đồ thị thường được sắp thứ tự từ điển bằng dãy (s0, s1, . . . , sn−1). (Nhắc lại rằng, s0, s1, . . . , sn−1 xác định phổ và do đó xác định tất cả các moment phổ khác).

Khi k ≥ 4, một bước đi đóng độ dài k có thể vết nhiều hơn một kiểu đồ thị con; ví dụ, khi k = 4 ta có 3 kiểu, cụ thể K2, P3 và C4. Ngoài ra, khi đi trên P3, số bước đi v − v có độ dài 4 phụ vào v. Để khảo sát vấn đề này, ta sử dụng góc đồ thị (là bất biến đồ thị liên hệ với các đỉnh): Phương trình (3.1) kéo theo bản sao “địa phương” sau đây của Định lý 3.2.1.

m (cid:88)

Định lý 3.2.2. ([6]) Số nk(j) bước đi đóng độ dài k bắt đầu (và kết thúc) tại đỉnh j của đồ thị G là

ijµk α2 i .

i=1

(3.2) nk(j) =

Một hệ quả trực tiếp của định lý là bậc của đỉnh bất kỳ, và số tam giác kề với một đỉnh bất kì có thể được suy ra từ các giá trị riêng và góc của đồ thị. Trong trường hợp như vậy, ta nói rằng tính bất biến tương ứng (corresponding invariant) là EA-tái tạo lại được (EA-reconstructible).

m (cid:88)

Định lý 3.2.3. ([6]) Bậc dj của đỉnh j, số tj các tam giác kề với đỉnh j của đồ thị G là

ijµ2 α2 j ,

ijµ3 α2 i .

i=1

dj = tj = 1 2

i=1

Chứng minh. Điều này được rút ra từ (3.2) vì n2(j) = dj và n3(j) = 2tj.

(cid:0)di 2

Nhận xét 3.2.4. Cho f là số đồ thị con của G đẳng cấu với P3. Đếm số cặp (cid:1). Từ Định lý 3.2.3 cạnh chứa một định cho trước, ta thấy rằng f = (cid:80)n suy ra f là EA-tái tạo lại được.

Hai kết quả tiếp theo chỉ ra rằng số tứ giác (4-chu trình), và số ngũ giác

(5-chu trình) cũng là EA-tái tạo lại được.

Định lý 3.2.5. ([6]) Số tứ giác q trong đồ thị G là

(cid:32)

(cid:33)

m (cid:88)

n (cid:88)

m (cid:88)

ijµ2 α2 i

hjµ2 α2 h

i=1

j=1

h=1

. q = µ2 i + 1 − 2 1 8

Chứng minh. Đầu tiên ta chứng minh s4 = 2e + 4f + 8q, trong đó f (giống bên trên) là số đường đi có độ dài 2 trong G. Để thấy điều này, chú ý rằng đồ thị con đi qua bởi một bước đi đóng có độ dài 4 là K2 hoặc P3 hoặc C4. Với mỗi một trong các đồ thị này, Hình 3.2 chỉ ra số bước đi đóng có độ dài 4 bắt đầu tại một định (và đi qua đồ thị). Tổng số bước đi đóng độ dài 4 đi qua đồ thị tương ứng là 2, 4 và 8.

Hình 3.2: Các đồ thị của Định lý 3.2.5.

Bây giờ e và s4 được xác định bởi phổ của G, trong khi f là EA-tái tạo lại được. Do đó, q là EA-tái tạo lại được, và công thức tường minh là vấn đề tính toán đại số.

Định lý 3.2.6. ([6]) Số ngũ giác p của đồ thị G là

(cid:32)

(cid:33)

m (cid:88)

n (cid:88)

m (cid:88)

hjµ2 α2 h

i=1

j=1

h=1

p = . α2 ijµ2 i 3 µ2 i + 5 − 5 1 10

Chứng minh. Lập luận như trong chứng minh bên trên, ta có s5 = 30t+ 10s + 10, trong đó t là số tam giác và s là số đồ thị con chứa tam giác một cạnh pendant. Chú ý rằng s = (cid:80)n j=1 tj(dj − 2), trong đó dj và tj xác định bởi Định lý 3.2.3. Từ đó kết được suy ra bằng tính toán thông thường.

3.3 Ứng dụng xác định bậc chính quy và tính hai

phần

Từ Chương 1 ta biết rằng bậc của đỉnh không được xác định bằng phổ của đồ thị (xem Hình 1.6). Mặt khác, từ phổ ta có thể nói tất cả bậc của đỉnh của G là giống nhau hay không, và nếu chúng giống nhau, ta có thể tìm bậc chính quy.

Định lý 3.3.1. ([6]) Cho λ1 là chỉ số của đồ thị G, gọi d và ∆ tương tứng là bậc trung bình và bậc lớn nhất. Khi đó

d ≤ λ1 ≤ ∆.

Ngoài ra, d = λ1 khi và chỉ khi G là chính quy. Với đồ thị liên thông G, λ1 = ∆ khi và chỉ khi G là chính quy.

Chứng minh. Với bất đẳng thức đầu tiên, ta nhắc lại chỉ số của G xác đỉnh bởi

λ1 = sup{xT Ax : x ∈ Rn, (cid:107)x(cid:107) = 1},

trong đó A là ma trận kề của G. Lấy x = 1√ n(1, 1, . . . , 1)T , ta được λ1 ≥ d. Ngoài ra, theo nguyên lý Rayleight, dấu bằng xảy ra khi và chỉ khi x = 1√ n(1, 1, . . . , 1)T là một véc tơ riêng của G. Nhưng x là véc tơ riêng khi và chỉ khi G là chính quy (Mệnh đề 1.1.8).

Bất đẳng thức thứ 2 rút ra từ Mệnh đề 1.1.7, trong khi theo Mệnh đề 1.1.8

nếu G là r-chính quy thì λ1 = r (= ∆).

Giả sử G liên thông và λ1 = ∆. Đặt x = (x1, x2, . . . , xn)T là véc tơ riêng tương ứng với λ1. Ta có thể giả sử tất cả các số của x đều dương. Đặt xu = maxi{xi}. Phương trình

(cid:88)

v∼u

(3.3) xv ∆xu =

chỉ ra deg(u) = ∆ và xv = vu với mọi v ∼ u. Lặp lại lập tương tự chỉ ra tất cả các đỉnh có bậc ∆ (và G nhận véc tơ 1 là véc tơ riêng).

Vì nd = tr(A2) ta thu được kết quả sau:

Hệ quả 3.3.2. ([6]) Đồ thị G là chính quy (bậc λ1) khi và chỉ khi

1 + λ2

2 + · · · + λ2 n.

nλ1 = λ2

Do đó ta có thể nhận ra tính chính quy từ phổ. Tiếp theo ta chứng minh rằng kết quả tương tự cũng đúng với tính hai phần. Nếu G là hai phần trên U ˙∪V , thì G có ma trận kề dạng

(cid:32)

(cid:33)

A = , O P Q O

trong đó Q = P T ; ở đây các số khác không của P tương ứng với các cạnh kề với đỉnh của U , các số khác không của Q tương ứng với các cạch kề với các đỉnh của V. Bây giờ, giả sử µ là một giá trị riêng của G, và

(cid:32)

(cid:33)

x = y z

mà một véc tơ riêng bất kỳ thuộc E(µ). Ta có P z = µy và Qy = µz. Xét véc tơ

(cid:32)

(cid:33)

x(cid:48) = . y −z

Ta có

(cid:32)

(cid:33) (cid:32)

(cid:33)

(cid:32)

(cid:33)

(cid:32)

(cid:33)

= = = −µx(cid:48). Ax(cid:48) = O P Q O y −z −P z Qy −µy µz

Điều này không chỉ suy ra −µ là một giá trị riêng của G, mà còn suy ra E(−µ) và E(µ) có cùng số chiều. Do đó ta đã chứng minh được phổ của đồ thị hai phần đối xứng qua điểm 0.

Bây giờ ta chứng minh điều ngược lại cũng đúng. Theo đó, cho G là đồ thị có phổ đối xứng qua điểm 0. Khi đó tất cả các moment phổ lẻ của G bằng 0; cụ thể, G không có chu trình độ dài lẻ (theo Định lý 3.2.1). Do đó G là hai phần, và ta có kết quả sau.

Định lý 3.3.3. ([6]) Đồ thị G là hai phần khi và chỉ khi phổ của nó là đối xứng qua gốc.

Đối với đồ thị liên thông chúng ta có kết quả mạnh hơn đáng kể sau đây:

Định lý 3.3.4. ([6]) Đồ thị liên thông G là hai phần khi và chỉ khi λ1 = −λn.

Chứng minh. Dựa theo Định lý 3.3.3, ta chỉ cần chứng minh rằng nếu λ1 = −λn thì G là hai phần. Điều này là hệ quả của một định lý của Frobenius, nhưng chúng ta vẫn chứng minh dưới đây.

1 và nó không phải là giá trị riêng đơn, khi đó A2 là khả quy, cụ thể với hai phần U ˙∪V ; thì G không có bước đi U -V có độ dài 2. Giả sử phản chứng U có hai đỉnh kể nhau u1 và u2, lấy v ∈ V . Gọi w0w1 · · · wm là đường ngắn nhất từ u1 tới v, gọi k là giá trị nhỏ nhất sao cho wk+1 ∈ V. Nếu k > 0 thì wk−1wkwk+1 là một bước đi U -V có độ dài 2. Nếu k = 0 thì u2w0w1 là một bước đi U -V độ dài 2, mâu thuẫn. Do đó, U là độc lập và V là độc lập. Suy ra điều phải chứng minh.

Giá trị riêng lớn nhất của A2 là λ2

Ta kết thúc phần này bằng việc thảo luận các chu trình độ dài ngắn nhất. Chúng ta định nghĩa chu vi chu trình lẻ của G (odd-girth), ký hiệu là og(G), là độ dài nhỏ nhất của chu trình lẻ.

Định lý sau đây được phát biểu theo đa thức đặc trưng PG(x). (Mặc dù hiểu biết về PG(x) tương đương với hiểu biết về phổ của G, nhưng tính toán trong thực hành lại khác nhau.)

2ch, với h = og(G).

Định lý 3.3.5. ([6]) Cho xn + c1xn−1 + c2xn−2 + · · · + cn−1x + cn là đa thức đặc trưng của đồ thị G. Khi đó chu vi chu trình lẻ của G bằng chỉ số của hệ số khác không đầu tiên của dãy c1, c3, c5, . . .; số chu trình có độ dài này bằng − 1

Chứng minh. Ta có

(cid:88)

H∈Hi

(−1)p(H)2c(H) (i = 1, 2, . . . , n), ci =

với Hi là tập tất cả các đồ thị con trên đỉnh i (đồ thị con của G có hợp phần (component) hoặc là chu trình hoặc là đẳng cấu với K2), p(H) là số hợp phần của H, và c(H) là số chu trình trong H.

Do đó nếu og(G) = 2k + 1 thì c2k+1 = 0 khi l < k bởi vì không có đồ thị con cơ sở có số lẻ đỉnh. Trường hợp k = l, một đồ thị con cơ sở phải là một chu trình lẻ, nên c2k+1 = −2s(G), trong đó (G) là số chu trình có độ dài og(G). Suy ra điều phải chứng minh.

Một câu hỏi tự nhiên phát sinh. Liệu có thể tìm được (từ đa thức đặc trưng) độ dài của một chu trình chẵn ngắn nhất, và tìm số chu trình như vậy? Câu trả lời là không. Để thấy điều này, một lần nữa ta xét cặp đồ thị nhỏ nhất đồng phổ trong Hình 1.6(a): K1,4 không có chu trình, trong khi C4 ˙∪K1 có một, và là một chu trình chẵn.

Tuy nhiên, đôi khi ta sử dụng định lý sau của Sachs. Đầu tiên thấy rằng

nếu G có chu vi chu trình (girth) g thì với i < g ta có

nếu i lẻ ci = nếu i = 2q,

(cid:40) 0 (−1)qbq

trong đó bq là số đồ thị con cơ sở chứa q bản sao rời nhau của K2.

Với i = g, các đồ thị con cơ sở có thể thuộc hai dạng, hoặc là các bản sao rời nhau của K2 (chỉ xảy ra khi g chẵn) hoặc một bản sao của Cg. Theo đó, ta định nghĩa

(cid:40)

nếu i lẻ (3.4) ˆci = nếu i = 2q ci ci − (−1)qbq

với i = 1, 2, . . . , n. Ta có ˆci = 0 nếu i < g và −ˆcg bằng hai lần số chu trình độ dài g. Do đó ta đã chứng minh được:

2 ˆcg.

Định lý 3.3.6. ([6]) Nếu ˆci được xác định như trong (3.4) thì chu vi chu trình của G bằng với chỉ số của hệ số khác không đầu tiên trong dãy ˆc1, ˆc2, ˆc3, . . .; số chu trình có độ dài này là − 1

Với đồ thị chính quy ta có thể biết nhiều thông tin hơn. Nếu G là r-chính quy có n đỉnh thì với q < g, bq có thể được biểu diễn theo q, n và r. Do đó ta có

Định lý 3.3.7. ([6]) Nếu G là đồ thị chính quy, thì chu vi chu trình của G được xác định bởi đa thức đặc trưng của nó (và do đó cả bởi phổ).

Với phân tích kỹ hơn, ta thu được kết quả sau.

Định lý 3.3.8. ([6]) Cho G là một đồ thị r-chính quy có n đỉnh và chu vi chu trình g. Nếu h ≤ min{n, 2g − 1} thì số chu trình trong G có độ dài h được xác định bởi r và các hệ số c1, c2, . . . , ch trong đa thức đặc trưng của G.

Kết luận

Thực hiện đề tài luận văn với mục đích là tìm hiểu về sự liên hệ giữa ma trận và đồ thị nhằm góp phần làm rõ mối quan hệ giữa đại số tuyến tính và lí thuyết đồ thị, tôi đã đề cập tới những nội dung chính sau:

- Ma trận Laplace của đồ thị.

- Định lí Kirchhoff về số cây bao trùm của đồ thị dựa trên việc tính định

thức Laplace.

- Nghiên cứu phổ của đồ thị và các phép toán từ đó nghiên cứu ứng dụng của phổ đồ thị trong đếm số đồ thị con, xác định bậc chính quy và tính hai phần.

Kết quả của luận văn không mới, nhưng việc thực hiện đề tài luận văn đã giúp cho tôi có được những hiểu biết sâu sắc về mối quan hệ giữa đại số tuyến tính – lý thuyết đồ thị và cũng hi vọng rằng trên nền tảng những hiểu biết này có điều kiện tôi sẽ có được những kết quả nghiên cứu thực sự ý nghĩa.