1
TOÁN RỜI RẠC
ỨNG DỤNG TRONG TIN HỌC

Giảng viên:

Cao Thanh Tình (Email: )

Bộ môn Toán Lý – ĐHCNTT – ĐHQGTPHCM
Chương 1. Đại cương về đồ thị
2
Nội dung môn học

Phần 1: Lý thuyết đồ thị

Đại cương về đồ thị

Các bài toán về đường đi

Đồ thị phẳng và bài toán tô màu đồ thị

Cây

Phần 2: Đại số Boole

Đại số Boole

Cổng logic

Cực tiểu hóa hàm Boole
Chương 1. Đại cương về đồ thị


Hai cạnh phân biệt
cùng tương ứng với
một cặp đỉnh

Đơn đồ thị

Đồ thị không có vòng
và cạnh song song

Đa đồ thị

Các đồ thị không phải
là đơn đồ thị
x
y
z
A
B
C
D
Chương 1. Đại cương về đồ thị
5
Các khái niệm cơ bản

Đồ thị (Graph)

Đồ thị đầy đủ

Đồ thị mà mọi cặp đỉnh

Thường được dùng để biểu diễn trên máy tính

2 cách biểu diễn thường dùng

Ma trận kề

Ma trận liên thuộc
Chương 1. Đại cương về đồ thị
7
Biểu diễn đồ thị

Biểu diễn bằng ma trận

Ma trận kề

Ma trận vuông cấp n (số đỉnh của đồ thị)

Các phần tử a
ij
được xác định bởi

a
ij
= 1: Nếu v
i
v
j
là một cạnh của G

a


Ma trận kề

Ví dụ 2
A
B
C
D
E
E 0 1 2 2 0
D 0 1 1 1 2
C 1 1 0 1 2
B 1 0 1 1 1
A 0 1 1 0 0
A B C D E
Chương 1. Đại cương về đồ thị
10
Biểu diễn đồ thị

Biểu diễn bằng ma trận

Ma trận liên thuộc

Ma trận M = (m
ij
)
nxm

Các phần tử m
ij


Ma liên thuộc

Ví dụ
Chương 1. Đại cương về đồ thị
12
Biểu diễn đồ thị

Biểu diễn bằng bảng
(danh sách liền kề)

Lưu trữ các đỉnh liền kề
với một đỉnh

Ví dụ
a
b
c
d
e
Đỉnh Đỉnh liền kề
a b, c, e
b a
c a, c, d, e
d c, e
e a, c, d
Chương 1. Đại cương về đồ thị
13
Các khái niệm cơ bản


Bậc của đỉnh

Định lý 1.1

Trong mọi đồ thị G = (V, E), tổng số bậc của các đỉnh
của G bằng 2 lần số cạnh của nó

Hệ quả

Trong mọi đồ thị G = (V, E) ta có

Số đỉnh bậc lẻ là một số chẵn

Tổng bậc của đỉnh bậc lẻ là một số chẵn
Chương 1. Đại cương về đồ thị
15
Các khái niệm cơ bản

Bậc của đỉnh

Định lý 1.2

Trong mọi đồ thị G = (V, E), nếu số đỉnh nhiều hơn 1
thì tồn tại ít nhất hai đỉnh cùng bậc

Định lý 1.3

Trong mọi đồ thị G = (V, E), nếu số đỉnh nhiều hơn 2
và có đúng hai đỉnh cùng bậc thì hai đỉnh này không
đồng thời bằng 0 hoặc n-1

nhất 2 đại biểu tham gia trở lên, luôn có ít nhất
hai đại biểu mà họ có số người quen bằng nhau
trong các đại biểu đến dự họp
Chương 1. Đại cương về đồ thị
18
Các khái niệm cơ bản

Một số bài toán ví dụ
Chứng minh rằng số người mà mỗi người đã có một
số lẻ lần bắt tay nhau trên trái đất là một con số
chẵn.
Chương 1. Đại cương về đồ thị
19
Một số đồ thị đặc biệt

Đồ thị đầy đủ K
n

Đơn đồ thị

Số đỉnh: |V| = n

Bậc: deg(v) = n – 1 ∀v ∈V

Số cạnh: |E| = n(n - 1) / 2
K
5
K
4
K

Nối các đỉnh của C
n
với một đỉnh mới u ta được W
n

Số đỉnh: |V| = n + 1
≥
3

Bậc: deg(v) = 3 ∀v ∈V \ {u}; deg(u) = n

Số cạnh: |E| = 2n
Chương 1. Đại cương về đồ thị
22
Một số đồ thị đặc biệt

Đồ thị đều

Nối các đỉnh của C
n
với một đỉnh mới u ta được W
n

Số đỉnh: |V| = n + 1
≥
3

Bậc: deg(v) = 3 ∀v ∈V \ {u}; deg(u) = n

Số cạnh: |E| = 2n

Ký hiệu: G’ = G
Chương 1. Đại cương về đồ thị
25
Một số đồ thị đặc biệt

Đồ thị lưỡng phân

Một đồ thị G được gọi là đồ thị lưỡng phân nếu tập các
đỉnh của G có thể phân thành 2 tập hợp không rỗng, rời
nhau sao cho mỗi cạnh của G nối một đỉnh thuộc tập này
đến một đỉnh thuộc tập kia.

Ký hiệu: K
m,n