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

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

1 / 34

Ngày 24 tháng 7 năm 2018

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.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

2 / 34

▶ Douglas B. West. Introduction to Graph Theory. 2nd Edition, 2000.

Nội dung

Định nghĩa và ví dụ

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

Đồ 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 (cid:2) 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) 2 E thì (a; b) được gọi là cung của G với đỉnh đầu là a và đỉnh cuối là b,

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

4 / 34

▶ và ta viết a ! b

Đồ thị có hướng

v2 Đồ thị có hướng G = (V; E):

v1

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

5 / 34

V = fv1; v2; v3g E = fv1 ! v1; v1 ! v2; v1 ! v3; v2 ! v3; v3 ! v2g v3

Bậc vào & bậc ra

v2

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

6 / 34

v1 Đỉnh v1 v2 v3 indeg 1 2 2 5 outdeg 3 1 1 5 v3

v2

Mệnh đề

v2V

v2V

∑ ∑ v1 indeg(v) = outdeg(v) = jEj

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

7 / 34

v3

Hành trình có hướng và đường đi có hướng

Hành trình Hành trình đơn Đường đi 7 3

3 3

7 7

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

8 / 34

Lặp cạnh Lặp đỉnh

Định nghĩa Xét G = (V; E) là đồ thị có hướng với V = fv1; v2; : : : ; vng. 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ụ

v2

1 0

v1 A @ A = 1 1 1 0 0 1 0 1 0

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

9 / 34

v3

Định lý Xét G = (V; E) là đồ thị có hướng với n đỉnh

ij ) là số hành trình có

V = fv1; v2; : : : ; vng:

và A = (aij) là ma trận kề của G. Xét (p(k) hướng từ vi tới vj. Khi đó

ij ):

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

10 / 34

Ak = (p(k)

Ví dụ

1 0 v2

A @ A = 1 1 1 0 0 1 0 1 0 v1 1 0 1 0

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

11 / 34

@ @ A A2 = A A3 = v3 1 2 2 0 1 0 0 0 1 1 3 3 0 0 1 0 1 0

Chứng minh

là phần tử ở hàng i cột j của ma trận Ak.

ij = p(k)

ij

▶ Bằng quy nạp theo độ dài hành trình. ▶ Ta ký hiệu a(k) ij ▶ Ta đặt P(k) := 8i; j a(k)

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

12 / 34

▶ Bước cơ sở: k = 1. 3 Tại sao?

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; vh ! vj

k; vh là một hành trình độ dài k từ vi tới vh

vi

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

13 / 34

▶ với vi ▶ và h : vh ! vj là một cạnh trong G.

Chứng minh: Bước quy nạp (tiếp)

n∑

h: vh!vj

h=1 n∑

∑ = (cid:1) ahj p(k+1) ij p(k) ih = p(k) ih

= (giả thiết quy nạp) (cid:1) ahj a(k) ih

h=1 = a(k+1) ij

(quy tắc nhân ma trận)

3

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

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 2 V, tồn tại một đường đi có hướng từ u tới v trong G.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

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

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

16 / 34

v3

Nội dung

Định nghĩa và ví dụ

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

Đồ 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 2 E.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

18 / 34

▶ Đồ thị thi đấu là một đồ thị định hướng của một đồ thị đầy đủ nào đó.

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”.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

19 / 34

▶ 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.

Đội nào vô địch?

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

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.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

21 / 34

Có phải mọi đồ thị thi đấu đều có đường Hamilton?

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

22 / 34

Định lý Mọi đồ thị thi đấu đều chứa một đường đi Hamilton.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

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:

fv1; v2; : : : ; vng:

▶ Theo quy nạp ta có đường đi

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

24 / 34

v1 ! v2 ! (cid:1) (cid:1) (cid:1) ! vn:

Trường hợp 1

Nếu v ! v1, vậy ta có đường Hamilton

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

25 / 34

v ! v1 ! v2 ! (cid:1) (cid:1) (cid:1) ! vn

Trường hợp 2

Nếu v1 ! v và tồn tại i nhỏ nhất sao cho v ! vi.

vi(cid:0)1 vi vn v1 v2 : : : : : :

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

26 / 34

v

Trường hợp 3

Nếu v1 ! v và với mọi i, vi ! v. Vậy ta có đường Hamilton

3

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

27 / 34

v1 ! v2 ! (cid:1) (cid:1) (cid:1) ! vn ! v

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

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

28 / 34

▶ Một vua gà là con gà gần thắng mọi con gà khác.

Ví dụ Hãy tìm các vua gà.

v1 v2

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

29 / 34

v4 v3

Câu hỏi Có phải mọi đồ thị thi đấu đều có vua gà?

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

30 / 34

Định lý Con gà với bậc ra cao nhất là một vua.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

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:

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

32 / 34

1. v ! u, và 2. Với mọi w: :(u ! w) } | hoặc :(w ! v) } | {z w!u {z v!w

Nhắc lại tương đương logic

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

33 / 34

(cid:17) :P _ Q P ) Q

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) } | hoặc :(w ! v) } | {z w!u {z 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

7:

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

34 / 34

outdeg(v) (cid:21) outdeg(u) + 1