Luận văn này có mục đích tìm hiểu và trình bày các kiến thức cơ bản về đồ thị và các kết quả lý thuyết, các định lý liên quan đến tính liên thông, các tính chất về bậc của đồ thị vô hướng và một số ví dụ ứng dụng cơ bản. | ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC o0o NGUYỄN THỊ PHƯƠNG TÍNH LIÊN THÔNG ĐỈNH LIÊN THÔNG CẠNH VÀ CÁC TÍNH CHẤT VỀ BẬC CỦA ĐỒ THỊ VÔ HƯỚNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2018 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC o0o NGUYỄN THỊ PHƯƠNG TÍNH LIÊN THÔNG ĐỈNH LIÊN THÔNG CẠNH VÀ CÁC TÍNH CHẤT VỀ BẬC CỦA ĐỒ THỊ VÔ HƯỚNG Chuyên ngành Toán ứng dụng Mã số 8 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC . TRẦN VŨ THIỆU THÁI NGUYÊN 5 2018 iii Mục lục Danh mục các ký hiệu 1 Danh mục các hình vẽ 3 Mở đầu 5 1 KIẾN THỨC CHUẨN BỊ 8 . KHÁI NIỆM ĐỒ THỊ . . . . . . . . . . . . . . . . . . . . . 8 . Định nghĩa và các ký hiệu . . . . . . . . . . . . . . . 8 . Phép toán trên đồ thị . . . . . . . . . . . . . . . . . 11 . Đồ thị đẳng cấu . . . . . . . . . . . . . . . . . . . . . 12 . Bậc của đỉnh trong đồ thị . . . . . . . . . . . . . . . 13 . ĐƯỜNG ĐI VÀ CHU TRÌNH . . . . . . . . . . . . . . . . . 14 . TÍNH LIÊN THÔNG CỦA ĐỒ THỊ . . . . . . . . . . . . . 17 . MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT . . . . . . . . . . . . 20 . Đồ thị rỗng và đồ thị không . . . . . . . . . . . . . . 20 . Rừng và cây . . . . . . . . . . . . . . . . . . . . . . . 20 . Đồ thị đầy đủ . . . . . . . . . . . . . . . . . . . . . . 21 . Đồ thị vòng đồ thị đường và đồ thị bánh xe . . . . . 21 . Đồ thị đều đồ thị chính qui . . . . . . . . . . . . . 22 . Đồ thị hai phần . . . . . . . . . . . . . . . . . . . . . 23 . Phần bù của đơn đồ thị . . . . . . . . . . . . . . . . 23 iv 2 LIÊN THÔNG ĐỈNH VÀ LIÊN THÔNG CẠNH CỦA ĐỒ THỊ 25 . LIÊN THÔNG CẤP k GIỮA HAI ĐỈNH . . . . . . . . . . . 25 . ĐỒ THỊ k - LIÊN THÔNG . . . . . . . . . . . . . . . . . . 30 . ĐỈNH KHỚP . . . . . . . . . . . . . . . . . . . . . . . . . . 32 . LIÊN THÔNG CẠNH CẤP GIỮA HAI ĐỈNH . . . . . . . 34 3 CÁC TÍNH CHẤT VỀ BẬC CỦA ĐỒ THỊ 39 . DI CHUYỂN TRÊN ĐỒ THỊ . . . . . . . . . . . . . . . . . 39 . ĐỒ THỊ ĐỒNG BẬC . . . . . . . . . . . . . .
