Đang chuẩn bị liên kết để tải về tài liệu:
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 CuuDuongThanCong.com https fb.com tailieudientucntt 1 57 Tài liệu tham khảo Norman L. Biggs Discrete Mathematics Oxford University Press 2002. CuuDuongThanCong.com https fb.com tailieudientucntt 2 57 CuuDuongThanCong.com https fb.com 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 CuuDuongThanCong.com https fb.com 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 CuuDuongThanCong.com https fb.com 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 CuuDuongThanCong.com https fb.com 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 CuuDuongThanCong.com https fb.com 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 CuuDuongThanCong.com https fb.com 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 CuuDuongThanCong.com https fb.com tailieudientucntt Đồ thị đầy đủ 10.2 Graph Terminology and Special Types of Grap Định nghĩa Đồ thị đầy đủ5 gồm EXAMPLE n đỉnh Complete