CHƯƠNG 1
MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ
Tôn Quang Toại Khoa CNTT, Đại học Ngoại ngữ - Tin học TP.HCM
Nội dung
Một số bài toán dẫn đến khái niệm đồ thị Định nghĩa đồ thị và Phân loại đồ thị Các thuật ngữ cơ bản Một số dạng đồ thị
MỘT SỐ BÀI TOÁN DẪN ĐẾN KHÁI NIỆM ĐỒ THỊ
Một số bài toán dẫn đến khái niệm đồ thị
Bài toán 1. Có cách nào xuất phát từ một vị trí, sau đó đi qua 7 cây cầu (mỗi cây cầu chỉ đi qua một lần) và trở về vị trí xuất phát?
Một số bài toán dẫn đến khái niệm đồ thị
Bài toán 2. Có thể vẽ hình phong bì thư sau bởi một nét bút hay không?
1
3 2
5 4
Một số bài toán dẫn đến khái niệm đồ thị
Bài toán 3. Một Sinh viên muốn đi từ nhà đến trường thì phải đi như thế nào? Cách đi nào là nhanh nhất?
ĐỊNH NGHĨA ĐỒ THỊ VÀ PHÂN LOẠI ĐỒ THỊ
Định nghĩa và phân loại đồ thị
Định nghĩa Đồ thị
Đồ thị là một mô hình toán học để biểu diễn tập các đối tượng (V) và mối quan hệ giữa các đối tượng đó (E). Đồ thị được định nghĩa bởi bộ (V, E) với: • V là tập các đỉnh (Vertices): V = {v1, v2, v3, …, vn} và n =
|V| gọi là bậc/cấp của đồ thị
• E là tập cạnh (Edges): E = {e1, e2, e3,… em} gồm một số cặp phần tử không có thứ tự (hay có thứ tự) của tập V và m = |E| gọi là kích thước của đồ thị.
Định nghĩa và phân loại đồ thị
Ký hiệu đồ thị:
G = (V, E)
Ký hiệu cạnh: Cạnh ek nối 2 đỉnh vi và vj được ký hiệu là:
ek = (vi, vj)
Định nghĩa và phân loại đồ thị
Phân loại đồ thị: dựa vào 2 tiêu chuẩn
Hướng của cạnh: • Đồ thị vô hướng • Đồ thị có hướng
Số cạnh nối 2 đỉnh: • Đơn đồ thị • Đa đồ thị
Định nghĩa và phân loại đồ thị
Đồ thị vô hướng: G=(V, E) là đồ thị vô hướng nếu tập cạnh E là tập các cặp không có thứ tự (các cạnh không có chiều).
Định nghĩa và phân loại đồ thị
Đồ thị có hướng: G=(V, A) là đồ thị có hướng nếu tập cung A là tập các cặp có thứ tự (các cạnh có chiều).
Biểu diễn đồ thị bằng hình học
Biểu diễn đỉnh:
Mỗi đỉnh: là 1 điểm, 1 vòng tròn nhỏ hay 1 biểu tượng nào đó trong mặt phẳng hay không gian. Dùng ký hiệu, tên hoặc số hiệu của đỉnh ghi bên điểm tương ứng
Biểu diễn cạnh (cung):
Nếu e=(u, v) là một cạnh thì nối điểm u đến điểm v bằng một đoạn thẳng hay đoạn cong không đi qua các điểm biểu diễn các đỉnh khác. Nếu e=(u, v) là một cung thì nối điểm u đến điểm v bằng một đoạn thẳng định hướng hay đoạn cong định hướng không đi qua các điểm biểu diễn các đỉnh khác
Biểu diễn đồ thị bằng hình học
x1
1 x2 x10
7 x3 x12 x1 1 5 x 9 6 x15 3
2 x4 x8 x14 x1 3
4
8 x7 x5 x6
CÁC THUẬT NGỮ CƠ BẢN
Kề và Liên thuộc
Cho cạnh e=(u, v)
u kề (adjacent) với v.
u có cạnh liên thuộc (incident) là e
v
e
u
Đỉnh đầu và Đỉnh cuối
Cho cung e=(u, v)
u là đỉnh đầu (start-vertex) v là đỉnh cuối (end-vertex) Cung e đi ra khỏi đỉnh u và đi vào đỉnh v
v
e
u
Khuyên, Đỉnh treo, Đỉnh cô lập
Khuyên/Vòng (self-loop): Là cạnh (hoặc cung) có 2 đỉnh đầu trùng nhau.
Đỉnh treo (pendant): Là đỉnh thuộc duy nhất một cạnh (hoặc cung).
Đỉnh cô lập (isolated): Là đỉnh không thuộc cạnh (hoặc cung) nào.
Bậc của đỉnh
Định nghĩa Bậc của đỉnh Cho đồ thị vô hướng G=(V, E) và đỉnh v ∈ V. Ta gọi bậc của v là số cạnh liên thuộc với đỉnh v (mỗi khuyên được tính 2 lần) Ký hiệu:
𝒅𝒅𝒅𝒅𝒅𝒅(𝒗𝒗)
Chú ý: • Đỉnh cô lập (isolated) v có • Đỉnh treo (pendant) v có
deg 𝑣𝑣 = 0 deg 𝑣𝑣 = 1
Bậc của đỉnh
Ví dụ:
1
7
5 6
3
2
4
8
i 1 2 3 4 5 6 7 8
deg(i)
Bậc của đỉnh
Định lý bắt tay – Handshaking Theorem: Cho đồ thị vô hướng G=(V, E), tổng bậc của các đỉnh sẽ bằng 2 lần số cạnh
deg(𝑣𝑣) = 2𝑚𝑚
� 𝑣𝑣∈𝑉𝑉
Bậc của đỉnh
Chứng minh:
Trong quá trình tính tổng bậc các đỉnh, mỗi cạnh được tính 2 lần.
Vậy, tổng bậc các đỉnh = 2 lần số cạnh (đpcm)
Bậc của đỉnh
Hệ quả: Mọi đồ thị vô hướng có số lượng các đỉnh bậc lẻ là 1 số chẵn
Chứng minh:
Bậc của đỉnh
Định nghĩa Bậc của đỉnh Cho đồ thị có hướng G=(V, E) và đỉnh v ∈ V.
Ta gọi bậc vào của v là số cung đi vào v Ta gọi bậc ra của v là số cung đi ra khỏi v Ta gọi bậc của v là số cung đi vào và đi ra khỏi v
Ký hiệu:
−
(𝑣𝑣)
𝑑𝑑𝑑𝑑𝑑𝑑 +
Bậc vào của v: Bậc ra của v: Bậc của v:
𝑑𝑑𝑑𝑑𝑑𝑑
(𝑣𝑣)
−
+
deg 𝑣𝑣 = 𝑑𝑑𝑑𝑑𝑑𝑑
𝑣𝑣 + 𝑑𝑑𝑑𝑑𝑑𝑑
(𝑣𝑣)
Bậc của đỉnh
Chú ý: 1 khuyên được tính 1 lần bậc vào và 1 lần bậc ra Ví dụ:
a
v deg−(v) deg+(v) deg(v)
b
b d
c
f
d
e
a
f
e c
Bậc của đỉnh
Định lý bắt tay – Handshaking Theorem: Cho đồ thị có hướng G=(V, E), tổng bậc vào bằng tổng bậc ra và bằng số cạnh
−
+
𝑑𝑑𝑑𝑑𝑑𝑑
𝑑𝑑𝑑𝑑𝑑𝑑
𝑣𝑣 =
𝑑𝑑𝑑𝑑𝑑𝑑 𝑣𝑣 = 𝑚𝑚
� 𝑣𝑣∈𝑉𝑉
𝑣𝑣 = � 𝑣𝑣∈𝑉𝑉
� 𝑣𝑣∈𝑉𝑉
1 2
Bài tập
Trong một bữa tiệc, mọi người bắt tay nhau. Chứng minh rằng số người bắt tay với 1 số lẻ người khác là 1 số chẵn Cho một đồ thị n đỉnh (n≥2), bao giờ cũng có ít nhất hai đỉnh cùng bậc Cho một đồ thị n đỉnh (n>2) có đúng 2 đỉnh cùng bậc, thì đồ thị có đúng 1 đỉnh bậc 0 hay đúng 1 đỉnh bậc n-1
MỘT SỐ DẠNG ĐỒ THỊ
Một số dạng đồ thị
Đồ thị đầy đủ (complete graph)
Đồ thị vô hướng n đỉnh gọi là đồ thị đầy đủ nếu 2 đỉnh bất kỳ được nối với nhau đúng 1 cạnh
K2 K1 K3 K4 K5 K6
Một số dạng đồ thị
Đồ thị bù (Complement graph)
:
′
̅𝐺𝐺 = (𝑉𝑉, 𝐸𝐸
Đồ thị bù của đồ thị G=(V, E) là đồ thị • Có cùng đỉnh với G ) • Có các cạnh là những cạnh mà ta phải bổ sung vào G để
G trở thành đồ thị đầy đủ
G
̅𝐺𝐺
Một số dạng đồ thị
Đồ thị vòng (cycle graph)
Đồ thị vô hướng n đỉnh gọi là đồ thị vòng nếu có duy nhất một chu trình đơn đi qua tất cả các đỉnh
C2 C1 C3 C4 C5 C6
Một số dạng đồ thị
Đồ thị bánh xe (cycle graph)
) là đồ thị thu được từ
bằng cách bổ sung thêm 1 đỉnh và nối
𝑛𝑛 ≥ 3
Đồ thị bánh xe n đỉnh ( đồ thị đỉnh này với các đỉnh của
𝐶𝐶𝑛𝑛
𝐶𝐶𝑛𝑛
W3 W4 W5 W6
Một số dạng đồ thị
Đồ thị hai phía (bipartite graph)
Đồ thị vô hướng G=(V, E) được gọi là đồ thị hai phía nếu tập đỉnh V có thể phần thành 2 tập X và Y sao cho: • • 𝑉𝑉 = 𝑋𝑋 ∪ 𝑌𝑌 (𝑋𝑋 ≠ ∅ 𝑣𝑣𝑣 𝑌𝑌 ≠ ∅) • Mỗi cạnh của G có một đỉnh 𝑋𝑋 ∩ 𝑌𝑌 = ∅ thuộc X và một đỉnh của Y
Một số dạng đồ thị
Đồ thị hai phía đầy đủ (bipartite graph)
Đồ thị vô hướng G=(V, E) được gọi là đồ thị hai phía đầy đủ nếu mọi đỉnh thuộc tập X đều nối các đỉnh thuộc tập Y và ngược lại
𝐾𝐾2,3
Một số dạng đồ thị
Đồ thị phẳng (planar graph)
Đồ thị được gọi là đồ thị phẳng nếu chúng ta có thể vẽ đồ thị trên một mặt phẳng mà các cạnh không cắt nhau.
Một số dạng đồ thị
Đồ thị con: Cho đồ thị G=(V, E). Đồ thị G’=(V’, E’) là đồ thị con của G nếu:
V’ ⊆ V E’ ⊆ E (u, v) ∈ E’ ⇒ u, v ∈ V’
Đặc biệt: Nếu V’=V thì G’ được gọi là đồ thị bộ phận hay đồ thị khung (spanning subgraph) của G
Tóm tắt chương 1
Một số khái niệm đồ thị Bậc của đỉnh Một số dạng đồ thị
