Bài giảng Toán rời rạc - Bài 12: Đồ 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 2018 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. 2 / 34 Nội dung Định nghĩa và ví dụ Đồ thị thi đấu Đị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 4 / 34 Đồ thị có hướng v1 v2 v3 Đồ thị có hướng G = (V,E): V = {v1, v2, v3} E = {v1 → v1, v1 → v2, v1 → v3, v2 → v3, v3 → v2} 5 / 34 Bậc vào & bậc ra v1 v2 v3 Đỉnh indeg outdeg v1 1 3 v2 2 1 v3 2 1 5 5 6 / 34 Mệnh đề ∑ v∈V indeg(v) = ∑ v∈V outdeg(v) = |E| v1 v2 v3 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 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 aij = { 1 nếu vi → vj 0 ngược lại. Ví dụ v1 v2 v3 A = 1 1 10 0 1 0 1 0  9 / 34 Định lý Xét G = (V,E) là đồ thị có hướng với n đỉnh V = {v1, v2, . . . , vn}. và A = (aij) là ma trận kề của G. Xét (p(k)ij ) là số hành trình có hướng từ vi tới vj. Khi đó Ak = (p(k)ij ). 10 / 34 Ví dụ v1 v2 v3 A = 1 1 10 0 1 0 1 0  A2 = 1 2 20 1 0 0 0 1  A3 = 1 3 30 0 1 0 1 0  11 / 34 Chứng minh ▶ Bằng quy nạp theo độ dài hành trình. ▶ Ta ký hiệu a(k)ij là phần tử ở hàng i cột j của ma trận Ak. ▶ Ta đặt P(k) := ∀i, j a(k)ij = p(k)ij ▶ Bước cơ sở: k = 1. 3 Tại sao? 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 vi k; vh → vj ▶ với vi k; 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. 13 / 34 Chứng minh: Bước quy nạp (tiếp) p(k+1)ij = ∑ h: vh→vj p(k)ih = n∑ h=1 p(k)ih · ahj = n∑ h=1 a(k)ih · ahj (giả thiết quy nạp) = a(k+1)ij (quy tắc nhân ma trận) 3 14 / 34 Định nghĩa Một đồ thị có hướng G = (V,E) là liên thông mạnh nếu với mọi u, v ∈ V, tồn tại một đường đi có hướng từ u tới v trong G. 15 / 34 Định nghĩa Một đồ thị có hướng được là phi chu trình (DAG) nếu nó không chứa chu trình có hướng. v1 v2 v3 v4 v5 16 / 34 Nội dung Định nghĩa và ví dụ Đồ thị thi đấu Định nghĩa ▶ Một đồ thị định hướng của một đồ thị (vô hướng) G = (V,E) là một đồ thị có hướng thu được từ G bằng cách chọn một hướng x→ y hoặc y→ x cho mỗi cạnh xy ∈ E. ▶ Đồ thị thi đấu là một đồ thị định hướng của một đồ thị đầy đủ nào đó. 18 / 34 Ví dụ ▶ Đồ thị định hướng của đồ thị đầy đủ cho phép mô hình hóa các giải đấu thể thao kiểu “round-robin”. ▶ Giải đấu gồm n đội và mỗi đội thi đấu với tất cả các đội khác. ▶ Với mỗi cặp u, v, ta có cạnh u→ v nếu u thắng v. ▶ Cuối giải ta có một đồ thị định hướng của Kn. ▶ “Điểm số” của mỗi đội chính là bậc ra của đội đó, là số lần thắng. 19 / 34 Đội nào vô địch? 20 / 34 Định nghĩa Một đường đi Hamilton có hướng là hành trình đi qua mỗi đỉnh của G đúng một lần. 21 / 34 Có phải mọi đồ thị thi đấu đều có đường Hamilton? 22 / 34 Định lý Mọi đồ thị thi đấu đều chứa một đường đi Hamilton. 23 / 34 Chứng minh ▶ Bằng quy nạp theo số đỉnh n của đồ thị. Đặt P(n) := “Mọi đồ thị thi đấu với n đỉnh đều chứa đường đi Hamilton”. ▶ Bước cơ sở: n = 1 3 ▶ Bước quy nạp: Giả sử P(n) đúng. ▶ Xét đồ thị thi đấu n+ 1 đỉnh. ▶ Bỏ đi một đỉnh v bất kỳ, ta còn đồ thị thi đấu n đỉnh: {v1, v2, . . . , vn}. ▶ Theo quy nạp ta có đường đi v1 → v2 → · · · → vn. 24 / 34 Trường hợp 1 Nếu v→ v1, vậy ta có đường Hamilton v→ v1 → v2 → · · · → vn 25 / 34 Trường hợp 2 Nếu v1 → v và tồn tại i nhỏ nhất sao cho v→ vi. v1 v2 . . . vi−1 vi . . . vn v 26 / 34 Trường hợp 3 Nếu v1 → v và với mọi i, vi → v. Vậy ta có đường Hamilton v1 → v2 → · · · → vn → v 3 27 / 34 Trò chơi chọi gà ▶ Hoặc con gà u thắng con gà v: u→ v ▶ Hoặc con gà v thắng con gà u: v→ u ▶ Con gà u gọi là gần thắng con gà v nếu u→ v hoặc { u→ w w→ v ▶ Một vua gà là con gà gần thắng mọi con gà khác. 28 / 34 Ví dụ Hãy tìm các vua gà. v1 v2 v3v4 29 / 34 Câu hỏi Có phải mọi đồ thị thi đấu đều có vua gà? 30 / 34 Định lý Con gà với bậc ra cao nhất là một vua. 31 / 34 Chứng minh Ta chứng minh bằng phản chứng. Xét u có bậc ra cao nhất và u không là vua. Vậy tồn tại v thỏa mãn: 1. v→ u, và 2. Với mọi w: ¬(u→ w)︸ ︷︷ ︸ w→u hoặc ¬(w→ v)︸ ︷︷ ︸ v→w 32 / 34 Nhắc lại tương đương logic ¬P ∨Q ≡ P⇒ Q 33 / 34 Chứng minh Ta chứng minh bằng phản chứng. Xét u có bậc ra cao nhất và u không là vua. Vậy tồn tại v thỏa mãn: 1. v→ u, và 2. Với mọi w: ¬(u→ w)︸ ︷︷ ︸ w→u hoặc ¬(w→ v)︸ ︷︷ ︸ v→w Khẳng định 2 tương đương với Nếu u→ w vậy v→ w. Kết hợp với khẳng định 1 ta được outdeg(v) ≥ outdeg(u) + 1 7. 34 / 34