tailieunhanh - 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ị

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ố Konigsberg. 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. | ĐẠ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 1 Kiến thức chuẩn bị 3 Khái niệm của đồ thị và phổ của đồ thị . . . . . . . . . . . . . . 3 Khái niệm đồ thị . . . . . . . . . . . . . . . . . . . . . . 3 Phổ của đồ thị . . . . . . . . . . . . . . . . . . . . . . . 6 Ma trận kề. Ma trận trọng số . . . . . . . . . . . . . . . . . . . 10 Ma trận liên thuộc . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Tính chất của ma trận biểu diễn đồ thị và các phép toán đồ thị 14 Tính chất của ma trận biểu diễn đồ thị . . . . . . . . . . . . . . 14 Ma trận Laplace của đồ thị và một số tính chất cơ bản . 14 Ma trận Laplace của một cạnh . . . . . . . . . . . . . . 17 Phân tích ma trận Laplace . . . . . . . . . . . . . . . . . 19 Định lý Kirchhoff . . . . . . . . . . . . . . . . . . . . . . 20 Các phép toán đồ thị . . . . . . . . . . . . . . . . . . . . . . . . 26 3 Áp 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 .