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.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Đồ thị có hướng - Trần Vĩnh Đức Đồ thị có hướng Trần Vĩnh Đức Ngày 24 tháng 7 năm 2018CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 34 Tài liệu tham khảo ▶ Eric Lehman, F Thomson Leighton & 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 đấuCuuDuongThanCong.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 → bCuuDuongThanCong.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 } v3CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 34 Bậc vào & bậc ra v2 Đỉnh indeg outdeg v1 1 3 v1 v2 2 1 v3 2 1 5 5 v3CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 34 v2 Mệnh đề ∑ ∑ v1 indeg(v) = outdeg(v) = |E| v∈V v∈V v3CuuDuongThanCong.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 7CuuDuongThanCong.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 v3CuuDuongThanCong.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 0CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 34 Chứng minh ▶ Bằng quy nạp theo độ dài hành trình. ▶ Ta ký hiệu aij(k) là phần tử ở hàng i cột j của ma trận Ak . ▶ Ta đặt (k) (k) P(k) := ∀i, j aij = pij ▶ Bước cơ sở: k = 1. 3 Tại sao?CuuDuongThanCong.com https://fb.com/tailieudientucntt 12 / 34 Chứng minh: Bước quy nạp ▶ Giả sử P(k) 3 ▶ Hành trình độ dài k + 1 từ vi đến vj có thể tách thành k vi ; vh → vj k ▶ với vi ; vh là một hành trình độ dài k từ vi tới vh ▶ và h : vh → vj là một cạnh trong G.CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 34 ...