Lý thuyết đồ thị định nghĩa và phân loại

1. ĐỊNH NGHĨA ĐỒ THỊ
1.1. Đồ thị vô hướng
Đồ thị vô hướng G = (V, E). Trong đó:
+ V là tập hợp, các phần tử của nó được gọi
là đỉnh.
+ E là tập hợp, mỗi phần tử là một cặp
không thứ tự (v, w) của 2 đỉnh thuộc V.
(v, w) được gọi là cạnh nối v và w.
⇒ (v, w ) ≡ (w, v)
1. ĐỊNH NGHĨA ĐỒ THỊ
1.1. Đồ thị vô hướng
Ví dụ: Đồ thị cạnh tranh trong sinh thái học
Mỗi loài là được biểu diễn bằng một đỉnh.
Nếu hai loài cạnh tranh thức ăn với nhau thì hai
đỉnh tương ứng có cạnh nối
chuột
chuột trù
sóc
chim quạ
cú
cắt
1. ĐỊNH NGHĨA ĐỒ THỊ
1.2. Đồ thị có hướng
Ví dụ: Cho tập V = {2, 3, 4, 5,6}. Hãy biểu diễn
quan hệ: aRb ⇔ a là ước của b và a ≠ b
2
3
4
5
6
1. ĐỊNH NGHĨA ĐỒ THỊ
1.2. Đồ thị có hướng
Đồ thị có hướng G = [V, E]. Trong đó:
+ V là tập hợp, các phần tử của nó được
gọi là đỉnh.
+ E là tập hợp, mỗi phần tử là một cặp
có thứ tự [v, w] của hai đỉnh của tập V.
[v, w] gọi là cung từ v đến w.
⇒ [v, w ] ≠ [w, v]
1. ĐỊNH NGHĨA ĐỒ THỊ
1.2. Đồ thị có hướng
Ví dụ: Đồ thị thi đấu vòng tròn.
[a, b] có nghĩa là đội a thắng đội b
Đội 1
Đội 2
Đội 3
Đội 4 Đội 5
3
2
4
5
1
1. ĐỊNH NGHĨA ĐỒ THỊ
Một số thuật ngữ: Cạnh e=(v,w)∈E, v∈V, w∈V,
khi đó:
+ e là cạnh liên thuộc v, w.
+ v, w được gọi là kề nhau
+ v, w gọi là đỉnh đầu mút của cạnh e.
+ Nếu e=[v,w] thì v gọi là đỉnh đầu (đỉnh xuất
phát), w là đỉnh cuối (đỉnh đích) của cung e.
+ Nếu v ≡ w thì e được gọi là khuyên.
+ Nếu có e’ = (v,w) thì e và e’ được gọi là hai
cạnh song song (cùng liên thuộc một cặp đỉnh).
1. ĐỊNH NGHĨA ĐỒ THỊ
Ví dụ:
+ Cạnh a liên thuộc 2 đỉnh 1
và 2.
+ Đỉnh 1 và 2 gọi là hai đỉnh
kề nhau.
+ Cạnh c là khuyên
+ Cạnh d và e song song
2
1
3
a
b
d
c
e
2
1
3
a
b
d
c
e
2. PHÂN LOẠI ĐỒ THỊ
Phân loại theo tính chất cạnh của đồ thị:
+ Đồ thị vô hướng là đồ thị mà tất cả các cạnh là
cạnh vô hướng.
+ Đồ thị có hướng là đồ thị mà tất cả các cạnh là
có hướng.
+ Đồ thị hỗn hợp là đồ thị có cả cạnh vô hướng
và cạnh có hướng.
2. PHÂN LOẠI ĐỒ THỊ
Ví dụ: Đồ thị hỗn hợp
Một bản đồ giao thông cùa Hà Nội là một đồ thị
hỗn hợp. Trong đó:
+ Các đỉnh biểu diễn các nút giao thông (ngã ba,
ngã tư đường…)
+ Các cạnh biểu diễn các con đường nối các nút
giao thông đó.

Cạnh có hướng nếu là đường một chiều

Cạnh vô hướng nếu là đường hai chiều.
2. PHÂN LOẠI ĐỒ THỊ
Ngoài ra, ta còn có:
+ Đồ thị đơn là đồ thị mà không có khuyên và
cạnh song song.
+ Đồ thị điểm là đồ thị chỉ có một đỉnh và
không có cạnh nào.
+ Đồ thị rỗng là đồ thị không có đỉnh và không
có cạnh.

Xem chi tiết: Lý thuyết đồ thị định nghĩa và phân loại