TAILIEUCHUNG - 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 https 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. https tailieudientucntt 2 34 Nội dung Định nghĩa và ví dụ Đồ thị thi đấu https 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 https 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 https 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 https tailieudientucntt 6 34 v2 Mệnh đề v1 indeg v outdeg v E v V v V v3 https 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 https 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 https 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 . https 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 https

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Đồ thị có hướng
• Đồ thị thi đấu
• Đường đi Hamilton
• Đồ thị định hướng
• 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