Đ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ị có hướng - Trần Vĩnh Đức

Bài giảng Toán rời rạc: Đồ thị có hướng cung cấp cho người học những nội dung kiến thức như: Định nghĩa và ví dụ, đồ thị định hướng, đồ thị thi đấu, đường đi Hamilton. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết. | Đồ thị có hướng Trần Vĩnh Đức Ngày 24 tháng 7 năm 2018 CuuDuongThanCong.com https fb.com tailieudientucntt 1 34 Tài liệu tham khảo Eric Lehman F Thomson Leighton amp Albert R Meyer Mathematics for Computer Science 2013 Miễn phí Ngô Đắc Tân Lý thuyết Tổ hợp và Đồ thị NXB ĐHQG Hà Nội 2004. Douglas B. West. Introduction to Graph Theory. 2nd Edition 2000. CuuDuongThanCong.com https fb.com tailieudientucntt 2 34 Nội dung Định nghĩa và ví dụ Đồ thị thi đấu CuuDuongThanCong.com https fb.com tailieudientucntt Định nghĩa Một đồ thị có hướng là một cặp có thứ tự G V E ở đây V là một tập còn E là một tập con của tích đề các V V tức E là một quan hệ hai ngôi trên V. Các phần tử của V thường được gọi là các đỉnh. Các phần của E gọi là các cung. Cụ thể hơn nếu a b E thì a b được gọi là cung của G với đỉnh đầu là a và đỉnh cuối là b và ta viết a b CuuDuongThanCong.com https fb.com tailieudientucntt 4 34 Đồ thị có hướng v2 Đồ thị có hướng G V E V v1 v2 v3 v1 E v1 v1 v1 v2 v1 v3 v2 v3 v3 v2 v3 CuuDuongThanCong.com https fb.com tailieudientucntt 5 34 Bậc vào amp bậc ra v2 Đỉnh indeg outdeg v1 1 3 v1 v2 2 1 v3 2 1 5 5 v3 CuuDuongThanCong.com https fb.com tailieudientucntt 6 34 v2 Mệnh đề v1 indeg v outdeg v E v V v V v3 CuuDuongThanCong.com https fb.com tailieudientucntt 7 34 Hành trình có hướng và đường đi có hướng Hành trình Hành trình đơn Đường đi Lặp cạnh 3 7 7 Lặp đỉnh 3 3 7 CuuDuongThanCong.com https fb.com tailieudientucntt 8 34 Định nghĩa Xét G V E là đồ thị có hướng với V v1 v2 . . . vn . Ma trận kề A aij của G định nghĩa bởi 1 nếu vi vj aij 0 ngược lại. Ví dụ v2 1 1 1 v1 A 0 0 1 0 1 0 v3 CuuDuongThanCong.com https fb.com tailieudientucntt 9 34 Định lý Xét G V E là đồ thị có hướng với n đỉnh V v1 v2 . . . vn . k và A aij là ma trận kề của G. Xét pij là số hành trình có hướng từ vi tới vj . Khi đó k Ak pij . CuuDuongThanCong.com https fb.com tailieudientucntt 10 34 Ví dụ v2 1 1 1 A 0 0 1 v1 0 1 0 1 2 2 1 3 3 A2 0 1 0 A3 0 0 1 v3 0 0 1 0 1 0 CuuDuongThanCong.com https fb.com