TAILIEUCHUNG - Bài giảng Toán học tổ hợp - Chương 1: Đại cương về đồ thị

Bài giảng Toán học tổ hợp - Chương 1: Đại cương về đồ thị cung cấp cho người học những kiến thức như: 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. Mời các bạn cùng tham khảo! | Chương 1. ĐẠI CƯƠNG VỀ ĐỒ THỊ LVL @2020 1 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 1. Thành phố Königsberg Phổ nay là Kaliningrad Nga 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 2. 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 3. 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 4. 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à số phần tử của 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 i j Cạnh e kề với đỉnh i và đỉnh j hay đỉnh i và đỉnh j kề với cạnh e có thể viết tắt e ij Đỉnh i và đỉnh j được gọi là 2 đỉnh kề nhau Hai cạnh nối cùng một cặp đỉnh được gọi là hai cạnh song song. Cạnh có hai đỉnh trùng nhau gọi là một khuyên 9 Một số loại đồ thị vô hướng Định nghĩa. Cho G là đồ thị vô hướng. Khi đó G được gọi là a đơn đồ thị hay đồ thị đơn nếu G không có khuyên và không có cạnh song song b đa đồ thị nếu G không có khuyên cho phép có cạnh song song c giả đồ thị nếu G cho phép có cạnh song song và có khuyên 10 b c a b a d e h c k g d b a d c 11 Đỉnh kề Tập các đỉnh kề với đỉnh v được viết là v u V v u E Nhận xét. Đồ thị đơn G hoàn toàn được xác định nếu chúng ta biết v v V nên đồ thị đơn

• Toán học
• Bài giảng Toán học tổ hợp
• Toán học tổ hợp
• Đại cương về đồ thị
• Đẳng cấu đồ thị
• Biểu diễn đồ thị
• Đồ thị vô hướng
• Đồ thị lưỡng phân
• 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
• Cấu trúc rời rạc
• 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
• 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ố