TAILIEUCHUNG - Bài giảng Cấu trúc rời rạc: Chương 5 - ĐH Công nghệ Thông tin (Phần 1)

Bài giảng "Cấu trúc rời rạc - Chương 5: Các khái niệm cơ bản của lý thuyết đồ thị" cung cấp cho người học các kiến thức: Các khái niệm cơ bản, biểu diễn đồ thị, một số đồ thị đặc biệt, sự đẳng cấu của các đồ thị, đồ thị có hướng, đường đi và chu trình, sự liên thông. | CHƯƠNG 5: CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ PHẦN 1: Các khái niệm cơ bản Biểu diễn đồ thị Một số đồ thị đặc biệt Sự đẳng cấu của các đồ thị Đồ thị có hướng Đường đi và chu trình Sự liên thông Các khái niệm cơ bản Đồ thị (Graph) G = (V, E) với V≠ V: tập các đỉnh E: tập các cạnh Cạnh e E ứng với 2 đỉnh v, w V v, w là 2 đỉnh kề (hay liên kết) với nhau, e liên thuộc với v và w Ký hiệu: e = vw ( ) v w : e được gọi là vòng (khuyên) tại v - Đồ thị dùng biểu diễn mối tương quan giữa 2 hay nhiều đối tượng Các khái niệm cơ bản Đồ thị (Graph) Cạnh bội (song song) Hai cạnh phân biệt cùng tương ứng với một cặp đỉnh Đơn đồ thị Đồ thị không có vòng và cạnh song song Đa đồ thị Các đồ thị không phải là đơn đồ thị - Đồ thị dùng biểu diễn mối tương quan giữa 2 hay nhiều đối tượng Các khái niệm cơ bản Đồ thị (Graph) Đồ thị đầy đủ Đồ thị mà mọi cặp đỉnh đều kề nhau Kn: đơn đồ thị đầy đủ Đồ thị con Đồ thị G’ = (V’, E’) V’ V, E’ E Đồ thị hữu hạn E và V hữu hạn Đồ thị vô hạn - Đồ thị dùng biểu diễn mối tương quan giữa 2 hay nhiều đối tượng Biểu diễn đồ thị Biểu diễn hình học Mỗi đỉnh một điểm Mỗi cạnh một đường (cong hoặc thẳng) nối 2 đỉnh liên thuộc với nó Biểu diễn bằng ma trận Thường được dùng để biểu diễn trên máy tính 2 cách biểu diễn thường dùng Ma trận kề Ma trận liên thuộc Biểu diễn đồ thị Biểu diễn bằng ma trận Ma trận kề Ma trận vuông cấp n (số đỉnh của đồ thị) Các phần tử được xác định bởi : Nếu là một cạnh của G : Nếu không là một cạnh của G Tính chất Phụ thuộc vào thứ tự liệt kê của các đỉnh Ma trận là đối xứng Một vòng được tính là một cạnh (akk = 1) Biểu diễn đồ thị Biểu diễn bằng ma trận Ma trận kề Ví dụ 1 Biểu diễn đồ thị Biểu diễn bằng ma trận Ma trận kề Ví dụ 2 Biểu diễn đồ thị Biểu diễn bằng ma trận Ma trận liên thuộc Ma trận M = ( )nxm Các phần tử được xác định bởi : Nếu cạnh liên thuộc với vi của G : : Nếu cạnh không liên thuộc với vi của G Tính chất Các cột tương ứng với các cạnh bội là giống nhau .

• Toán học
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Đồ thị có hướng
• Lý thuyết đồ thị
• Biểu diễn đồ thị
• Đồ thị đặc biệt
• Toán học rời rạc
• Đẳng cấu đồ thị
• Đại cương về đồ thị
• Bài giảng Toán học rời rạc
• Toán rời rạc
• bài giảng Toán rời rạc
• giáo trình Toán rời rạc
• bài tập Toán rời rạc
• đề cương Toán rời rạc
• Phương pháp đếm dùng hàm sinh
• Hệ số hàm sinh
• Hàm sinh mũ
• Sơ đồ Ven
• Nguyên lý bù trừ
• Kỹ thuật đếm
• Cây khung ngắn nhất
• Cây có gốc
• Phép duyệt cây
• Tìm đường đi ngắn nhất
• Đồ thị Euler
• Đồ thị Hamilton
• Khoa học máy tính
• Cấu trúc dữ liệu
• Set partitioning
• Bài toán đếm
• Đối tượng rời rạc
• Biểu diễn quan hệ
• Quan hệ tương đương
• tài liệu học đại học
• tài liệu toán rời rạc
• toán cao cấp
• học toán rời rạc
• Phép đếm
• Tổ hợp căn bản
• Tổ hợp lặp
• Khai triển lũy thừa
• Khai triển đa thức
• Propositional logic
• Phép toán logic
• Predicate logic
• Logic vị từ
• Hàm đơn ánh
• Độ tăng của hàm
• Thuật toán
• Thuật toán tìm kiếm
• Thuật toán sắp xếp nổi bọt
• Bài giảng Toán học tổ hợp và cấu trúc rời rạc
• Toán học tổ hợp
• Hàm và thuật toán
• Độ phức tạp của thuật toán
• Đường đi Euler
• Thuật ngữ về đồ thị
• Lý thuyết tập hợp
• Phép toán tập hợp
• Tích Descartes
• Các bài toán về đường đi
• Một số kỹ thuật đếm
• Sử dụng sơ đồ Ven
• Định nghĩa hàm sinh
• Tổ hợp cơ bản
• Khai triển luỹ thừa của đa thức