Bài giảng Toán rời rạc - Chương: Đồ 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
 Đồ thị có hướng G =
 v2
 (V, E):
 V = {v1, v2, v3}
 v1
 E = {v1 → v1, v1 → v2, v1 → v3,
 v2 → v3, v3 → v2}
 v3
 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
 v3
 6 / 34
 v2
Mệnh đề
 ∑ ∑ v1
 indeg(v) = outdeg(v) = |E|
 v∈V v∈V
 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   
 Lặp đỉnh   
 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
 v
 1 A = 0 0 1
 0 1 0
 v3
 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 (k)
 A = (pij ).
 10 / 34
Ví dụ
 v2  
 1 1 1
 A = 0 0 1
 0 1 0
 v1    
 1 2 2 1 3 3
 A2 = 0 1 0 A3 = 0 0 1
 v3 0 0 1 0 1 0
 11 / 34
Chứng minh
 ▶ Bằng quy nạp theo độ dài hành trình.
 ▶ (k) k
 Ta ký hiệu aij là phần tử ở hàng i cột j của ma trận A .
 ▶ Ta đặt
 ∀ (k) (k)
 P(k) := i, j aij = pij
 ▶ Bước cơ sở: k = 1.  Tại sao?
 12 / 34
Chứng minh: Bước quy nạp
 ▶ Giả sử P(k) 
 ▶
 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.
 13 / 34
Chứng minh: Bước quy nạp (tiếp)
 ∑ ∑n
 (k+1) (k) (k) ·
 pij = pih = pih ahj
 h: vh→vj h=1
 ∑n
 (k) ·
 = aih ahj (giả thiết quy nạp)
 h=1
 (k+1)
 = aij (quy tắc nhân ma trận)
 
 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.
 v2
 v1 v4 v5
 v3
 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 
 ▶ 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 
 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 → w
 u → v hoặc
 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
 v4 v3
 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{z w}) hoặc | (w{z v})
 w→u 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{z w}) hoặc | (w{z v})
 w→u 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 .
 34 / 34