tailieunhanh - Bài giảng Toán rời rạc: Đồ thị - Trần Vĩnh Đức

Bài giảng Toán rời rạc: Đồ thị cung cấp cho người học những nội dung kiến thức như: Đồ thị và biểu diễn, một số đồ thị đặc biệt, đẳng cấu, bậc, đường đi và chu trình. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết. | Đồ thị Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 https tailieudientucntt 1 57 Tài liệu tham khảo Norman L. Biggs Discrete Mathematics Oxford University Press 2002. https tailieudientucntt 2 57 https tailieudientucntt 3 57 Nội dung Đồ thị và biểu diễn Một số đồ thị đặc biệt Đẳng cấu Bậc Đường đi và chu trình https tailieudientucntt Định nghĩa Một đồ thị G là một cặp có thứ tự G V E ở đây V là một tập còn E là tập với các phần tử là các tập con hai phần tử của V. Các phần tử của V được gọi là các đỉnh còn các phần tử của E gọi là các cạnh của G. Ví dụ a Xét đồ thị G V E trong đó z b V a b c d z E a b a d b z c d d z . d c https tailieudientucntt 5 57 Định nghĩa Hai đỉnh x và y gọi là kề nhau hay hàng xóm nếu x y là một cạnh của đồ thị. Ta biểu diễn đồ thị G V E bởi danh sách kề trong đó mỗi đỉnh v giữ một danh sách các đỉnh kề với v. Ví dụ a z b a b c d z b a d a b d z c d z d c https tailieudientucntt 6 57 Bài tập Có ba ngôi nhà A B C mỗi ngôi nhà đều kết nối với cả ba nhà cung cấp ga nước và điện G W E. 1. Hãy viết danh sách kề cho đồ thị biểu diễn bài toán này và vẽ nó. 2. Liệu bạn có thể vẽ đồ thị này trên mặt phẳng để không có cạnh cắt nhau không https tailieudientucntt 7 57 Ví dụ GS Mc Brain và vợ là bà April tới một bữa tiệc ở đó có 4 đôi vợ chồng khác. Có một vài cặp bắt tay nhau nhưng không ai bắt tay với vợ hoặc chồng mình. GS hỏi mọi người khác xem họ bắt tay bao nhiêu người và ông ấy nhận được 9 con số khác nhau. Hỏi có bao nhiêu người đã bắt tay April https tailieudientucntt 8 57 Nội dung Đồ thị và biểu diễn Một số đồ thị đặc biệt Đẳng cấu Bậc Đường đi và chu trình https tailieudientucntt Đồ thị đầy đủ Graph Terminology and Special Types of Grap Định nghĩa Đồ thị đầy đủ5 gồm EXAMPLE n đỉnh Complete

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Đồ thị đầy đủ
• Đồ thị vòng
• Đồ thị bánh xe
• Đồ thị hai phần
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Câu hỏi Toán rời rạc
• Bài tập Toán rời rạc
• Hệ thức truy hồi
• Quan hệ chia để trị Toán rời rạc
• Nguyên lý toán rời rạc
• Cấu hình tổ hợp
• Cấu hình toán rời rạc
• Bài giảng môn học Toán học rời rạc
• Toán học rời rạc
• Môn Toán học rời rạc
• Tập hợp và logic mệnh đề
• lý thuyết toán rời rạc
• đề cương Toán rời rạc