MR_”Di ’ collection
LÝ THUYẾT ĐỒ THỊ

Email:

2/63
MỞ ĐẦU
- Lý thuyết Đồ thị là một trong những ngành khoa học
ra đời khá sớm.
- Lý thuyết Đồ thị giúp mô tả hình học và giải quyết
nhiều bài toán thực tế phức tạp liên quan đến các khái
niệm như: đường đi, chu trình, tập ổn định, chu số, sắc
số, duyệt đồ thị, đường đi ngắn nhất, tâm đồ thị, luồng
vận tải, đồ thị phẳng, cây bao trùm, cây biểu thức, cây
mã tối ưu …bằng các thuật toán ngắn gọn và lý thú.
- Lý thuyết Đồ thị đã gắn kết nhiều ngành khoa học
với nhau.
3/63
MỞ ĐẦU (tiếp)
Bài giảng điện tử “Lý thuyết Đồ thị” này bao gồm:
- 11 chương
- phân thành 20 bài học
trình bày những vấn đề cốt lõi nhất của lý thuyết đồ thị
cùng các thuật toán tiêu biểu; giúp người học có thể
cài đặt trên máy tính và ứng dụng trong thực tế.
4/63
CHƯƠNG 1
ĐẠI CƯƠNG VỀ ĐỒ THỊ
5/63
NỘI DUNG


- Đỉnh b kề với đỉnh a
-
Hai đỉnh a và b cùng kề với cạnh (a,b).
Hai cạnh kề nhau: là hai cạnh có ít nhất một đỉnh
chung.
9/63
ĐỊNH NGHĨA ĐỒ THỊ (tiếp)

Định nghĩa 1.2
Đồ thị là một cặp G = (V, F), trong đó:
- V là tập hợp các đỉnh,
- F : V → 2
V
, được gọi là ánh xạ kề.

Sự tương đương của hai định nghĩa:
∀ x, y ∈ V : (x, y) ∈ E ⇔ y ∈ F(x).
10/63
VÍ DỤ 1.2
Ánh xạ kề của đồ thị trên hình vẽ:
F(a) = {b, c} , F(b) = {c} , F(c) = ∅ ,
F(d) = {b, c} và F(e) = {a, b, d} .
Hình 1.1: Đồ thị hữu hạn
a
b
e d
c
11/63
ĐỒ THỊ VÔ HƯỚNG VÀ CÓ HƯỚNG
