Xem mẫu
- Đồ thị có hướng
Trần Vĩnh Đức
Ngày 24 tháng 7 năm 2018
CuuDuongThanCong.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 đấu
CuuDuongThanCong.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 → b
CuuDuongThanCong.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 }
v3
CuuDuongThanCong.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
v3
CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 34
- v2
Mệnh đề
∑ ∑ v1
indeg(v) = outdeg(v) = |E|
v∈V v∈V
v3
CuuDuongThanCong.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 7
CuuDuongThanCong.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
v3
CuuDuongThanCong.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 0
CuuDuongThanCong.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
- Chứng minh: Bước quy nạp (tiếp)
(k+1)
∑ (k)
∑
n
(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)
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 ∈ 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
v3
CuuDuongThanCong.com https://fb.com/tailieudientucntt 16 / 34
- Nội dung
Định nghĩa và ví dụ
Đồ thị thi đấu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Đị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 đó.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 19 / 34
- Đội nào vô địch?
CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 34
nguon tai.lieu . vn
