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
