tailieunhanh - Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 4 - Lê Văn Luyện

Bài giảng "Toán học tổ hợp và cấu trúc rời rạc - Chương 4: Đại cương về đồ thị" cung cấp cho người học các kiến thức: Giới thiệu, các khái niệm cơ bản, biểu diễn đồ thị, đẳng cấu đồ thị, đường đi, chu trình. nội dung chi tiết. | Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 4 - Lê Văn Luyện Chương 4. ĐẠI CƯƠNG VỀ ĐỒ THỊ lvluyen@ FB: Nội dung 1. Giới thiệu 2. Các khái niệm cơ bản 3. Biểu diễn đồ thị 4. Đẳng cấu đồ thị 5. Đường đi, chu trình 2 1. Giới thiệu Bài toán. Thành phố Königsberg, Đức nằm trên một con sông, có hai hòn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu. Bài toán đặt ra là có thể đi theo một tuyến đường mà đi qua mỗi cây cầu đúng một lần rồi quay lại điểm xuất phát hay không? 3 Năm 1736, nhà toán học Leonhard Euler đã chứng minh rằng điều đó là không thể được. 4 Bài toán 1. Có thể vẽ hình phong bì thư bởi một nét bút hay không? Nếu có hãy chỉ ra tuần tự các nét vẽ 1 2 3 4 5 5 Bài toán 2. Một đoàn kiểm tra chất lượng các con đường. Để tiết kiệm thời gian, đoàn kiểm tra muốn đi qua mỗi con đường đúng 1 lần. Kiểm tra xem có cách đi như vậy không? 4 7 5 1 8 6 2 3 6 Bài toán 3. Một sinh viên muốn đi từ nhà đến trường thì phải đi như thế nào? Cách đi nào là ngắn nhất? 7 2. Các khái niệm cơ bản Định nghĩa. Một đồ thị vô hướng (undirected graph) G=(V, E) được định nghĩa bởi: • Tập hợp V ≠ ∅ được gọi là tập các đỉnh (vertex) và n = |V| gọi là cấp của đồ thị; • Tập hợp E là tập các cạnh (edge) của đồ thị; Mỗi cạnh e∈E được liên kết với một cặp đỉnh {i, j}, không phân biệt thứ tự 8 Đỉnh kề Định nghĩa. Trên đồ thị vô hướng, xét cạnh e được liên kết với cặp đỉnh

• Toán học
• Bài giảng Toán học tổ hợp
• Toán học tổ hợp
• Cấu trúc rời rạc
• Đại cương về đồ thị
• Biểu diễn đồ thị
• Đẳng cấu đồ thị
• Tổ hợp cơ bản
• Nguyên lý cộng
• Nguyên lý Dirichlet
• Tổ hợp lặp
• Khai triển lũy thừa của đa thức
• Bài giảng Hình học tổ hợp
• Hình học tổ hợp
• Bài toán về Hình học tổ hợp
• Định lý Pal
• Ôn tập chuyên đề Hình học tổ hợp
• Tổ hợp căn bản
• Khai triển lũy thừa
• Khai triển đa thức
• Bài toán tồn tại tổ hợp
• Bài toán liệt kê tổ hợp
• Công thức toán học
• Mô hình toán
• Toán kinh tế
• Lý thuyết tổ hợp
• Bài giảng Toán học tổ hợp và cấu trúc rời rạc
• Khai triển luỹ thừa của đa thức
• Các bài toán về đường đi
• Đồ thị Hamilton
• Đồ thị Euler
• Ma trận khoảng cách
• Bài giảng Nhập môn mạch số
• Nhập môn mạch số
• Mạch tổ hợp
• Mạch tính toán số học
• Mạch logic tổ hợp
• Mạch logic tổ hợp phức tạp
• Bài toán về đường đi
• Tìm đường đi ngắn nhất
• Phương pháp đếm dùng hàm sinh
• Bài toán đệ quy
• Hệ số hàm sinh
• Tải trọng và tác động
• Bài giảng Tải trọng và tác động
• Nguyên lý tính toán tổ hợp tải trọng
• Tổ hợp tải trọng
• Tính toán tổ hợp tải trọng
• Khái niệm về tổ hợp
• Phép duyệt cây
• Cây khung ngắn nhất
• Cây khung của đồ thị
• Thuật toán tìm cây
• Một số kỹ thuật đếm
• Sử dụng sơ đồ Ven
• Nguyên lý bù trừ
• Cây có gốc
• Định nghĩa hàm sinh
• Hàm sinh mũ
• Kỹ thuật đếm
• Đồ thị vô hướng
• Đồ thị lưỡng phân
• Phương pháp sơ đồ Ven
• Đa thức quân xe
• Số đếm nâng cao
• Công thức truy hồi
• Số Stirling loại hai
• Tam giác Bell
• Bài giảng Điện tử số
• Điện tử số
• Digital Electronics
• Mô hình toán học
• Thiết kế mạch tổ hợp
• Phân tích mạch tổ hợp
• Bài giảng Toán học
• Phương pháp giải toán số học
• Bài toán về ước và bội
• Bồi dưỡng học sinh giỏi Toán
• Chuyên đề số học
• Chuyên đề tổ hợp
• Số nguyên tố