TÔ MÀU ĐỒ THỊ CÂY VÀ ỨNG DỤNG

BÀI BÁO CÁO
cao đẳng sư phạm đăklăk_
diemhuongtin35
TÔ MÀU ĐỒ THỊ
CÂY VÀ ỨNG DỤNG
NỘI DUNG BÁO CÁO
A. Tô màu đồ thị
Mở đầu
Các định nghĩa, định lý
Thuật toán
Ứng dụng bài toán Tô màu đồ thị : Lập lịch thi
B. Cây và ứng dụng
Mở đầu
Khái niệm – Tính chất
Phương pháp duyệt cây
C. Kết luận




A. Tô màu đồ thị
Mở đầu
Các định nghĩa, định lý
Thuật toán
Ứng dụng bài toán Tô màu đồ thị : Lập lịch thi
B. Cây và ứng dụng
Mở đầu
Khái niệm – Tính chất
Phương pháp duyệt cây
C. Kết luận

Tô màu đồ thị - Mở đầu
1. Mở đầu
Để phân biệt các miền có chung biên giới trên bản đồ, người ta phải tô màu chúng bằng các màu tùy ý khác nhau. Một bài toán thực tế được đặt ra là : Cần có ít nhất bao nhiêu màu để tô màu một bản đồ bất kỳ sao cho các miền kề nhau không cùng một màu? Ta có thể xét ví dụ sau:
B
D
C
A
E
G
F
A
D
C
B
E
G1
G2
Bản đồ G1 phải dùng ít nhất 4 màu
Bản đồ G2 phải dùng ít nhất 5 màu
Tô màu đồ thị - Mở đầu(tt)
Mỗi miền trên bản đồ được biểu diễn bằng một đỉnh, hai hình trên đồ thị được nối với nhau bằng một cạnh, nếu các miền được biểu diễn bằng hai đỉnh này có biên giới chung nhau. Đồ thị nhận được bằng cách như vậy gọi là đồ thị đối ngẫu.
Hình sau biểu diễn các đồ thị đối ngẫu với các bản đồ cho trên hình 1.
Tô màu đồ thị - Mở đầu(tt)
A
G
E
D
C
B
F
B
A
D
C
D
Các đồ thị đối ngẫu của các bản đồ trên hình 1
Tô màu đồ thị - Các định nghĩa, định lý
2. Định nghĩa – Định lý
2.1. Định nghĩa
Định nghĩa 1: Tô màu đơn đồ thị là sự gán màu cho các đỉnh của nó sao cho không có hai đỉnh liền kề được gán cùng một màu.
Định nghĩa 2: Số màu ( Sắc số) của một đồ thị là một số tối thiểu các màu cần thiết để tô màu cho đồ thị này.


Tô màu đồ thị - Các định nghĩa, định lý(tt)
2.2 . Định lý
Định lý 5 màu : Mọi đồ thị phẳng đều có thể tô đúng bằng 5 màu.

Định lý 4 màu : Mọi đồ thị phẳng đều có thể tô đúng bằng 4 màu.
Tô màu đồ thị - Thuật toán
Thuật toán
Input: Cho đồ thị G(V,E)
Output: Các đỉnh được tô màu
Các bước:
Bước 1:  Lập danh sách các đỉnh của đồ thị E’:=[v1,v2,…,vn] được sắp xếp theo thứ tự bậc giảm dần: d(v1) ≥ d(v2) ≥ … ≥ d(vn) Đặt i := 1

Tô màu đồ thị - Thuật toán (tt)
‚Bước 2: Tô màu i cho đỉnh đầu tiên trong danh sách. Duyệt lần lượt các đỉnh tiếp theo và tô màu i cho đỉnh không kề đỉnh đã được tô màu i.
Bước 3: ƒ Nếu tất cả các đỉnh đã được tô màu thì kết thúc, đồ thị được tô bằng i màu. Ngược lại, sang bước 4 „.
Bước 4: „ Loại khỏi E’ các đỉnh đã tô màu. Sắp xếp lại các đỉnh trong E’ theo thứ tự bậc giảm dần. Đặt i := i + 1 và quay lại bước 2 ‚.
Tô màu đồ thị - Thuật toán (tt)
Ví dụ: Xác định số màu của đồ thị G và H cho trên hình sau ?


b
a
c
f
g
e
d
b
a
c
f
g
e
d
G
H
Tô màu đồ thị - Ứng dụng
Lập lịch thi : Hãy lập lịch thi trong trường đại học sao cho không có sinh viên nào phải thi đồng thời hai môn cùng một lúc.
Giải
Ví dụ có 7 môn thi cần xếp lịch. Giả sử các môn học được đánh số từ 1 đến 7, và các cặp môn thi sau có chung sinh viên: 1 và 2, 1 và 3, 1 và 4, 1 và 7, 2 và 3, 2 và 4, 2 và 5, 2 và 7, 3 và 4, 3 và 7, 4 và 5, 4 và 6, 5 và 7, 6 và 7.
Tô màu đồ thị - Ứng dụng (tt)
Đợt thi Môn thi

I 1,6
II 2
III 3,5
IV 4,7
. Tô màu đồ thị
Mở đầu
Các định nghĩa, định lý
Thuật toán
Ứng dụng bài toán Tô màu đồ thị : Lập lịch thi
B. Cây và ứng dụng
Mở đầu
Khái niệm – Tính chất
Phương pháp duyệt cây
C. Bài tập ứng dụng
D. Kết luận


Cây và ứng dụng – Mở đầu
1. Mở đầu
- Một đồ thị liên thông và không có chu trình đơn được gọi là cây.
- Năm 1957, Arthur Cayley, nhà toán học người Anh, lần đầu tiên đã sử dụng cây để xác định các dạng khác nhau của hợp chất hóa học.
-Từ đó, Cây được ứng dụng trong nhiều lĩnh vực.
Cây và ứng dụng – Khái niệm
Định nghĩa 1:
Cây là một đồ thị vô hướng sao cho giữa hai đỉnh bất kỳ luôn có một đường đi đơn duy nhất nối chúng với nhau
Một đồ thị vô hướng không chứa chu trình và có ít nhất hai đỉnh gọi là một rừng. Trong một rừng, mỗi thành phần liên thông là một cây.
Ví dụ:
Xét các đồ thị trong hình sau
Cây và ứng dụng – Khái niệm(tt)
a
b
c
d
e
a
b
d
c
e
f
a
b
d
c
e
f
c
e
b
a
f
d
G1
G2
G3
G4
G1 và G2 là cây, G3 và G4 không là cây
Cây và ứng dụng – Khái niệm(tt)
Thuật ngữ
- Một đỉnh đặc biệt của cây được gọi là gốc.
- Định hướng mỗi cạnh bằng hướng từ gốc đi ra.
- Cây cùng với gốc sinh ra một đồ thị có hướng gọi là cây có gốc.
- Chuyển cây không có gốc thành cây có gốc bằng cách chọn một đỉnh bất kỳ làm gốc. Do đó việc chọn gốc khác nhau sẽ tạo ra các cây có gốc khác nhau.
Cây và ứng dụng – Khái niệm(tt)
Vẽ cây có gốc cho gốc ở phía trên của đồ thị và có thể bỏ mũi tên chỉ hướng của các cạnh vì việc chọn gốc đã xác định hướng của các cạnh.
Đỉnh u là đỉnh cha của đỉnh v nếu có một cạnh hướng từ u đến v. Đỉnh v được gọi là đỉnh con của đỉnh u. Đỉnh cha u là duy nhất của đỉnh v.
Các đỉnh cùng cha được gọi là anh em. Tổ tiên của một định khác với gốc là các đỉnh trên đường đi từ gốc tới đỉnh này.
Các đỉnh của cây gọi là lá nếu nó không có con. Các đỉnh có con được gọi là đỉnh trong.
Cây và ứng dụng – Khái niệm(tt)
T
Với gốc a
Với gốc c
Hình 2: Cây và các cây có gốc
f
g
d
e
b
a
c
a
b
f
g
e
c
d
c
a
b
f
g
d
e
Ví dụ: Hình 2 biểu diễn các cây có gốc khác nhau được tạo ra từ đồ thị T
Bằng cách chọn a và sau đó là c làm gốc
Cây và ứng dụng – Khái niệm(tt)
Định nghĩa 2: Cây nhị phân là một cây gốc, trong đó mỗi con của đỉnh hoặc là con bên trái hoặc là con bên phải, không có đỉnh nào nhiều hơn một con bên trái hay nhiều hơn một con bên phải. Cây nhị phân được gọi là đầy đủ, nếu mỗi đỉnh của nó hoặc là không có con hoặc là có đúng hai con
Cây và ứng dụng – Khái niệm(tt)
Định nghĩa 3: Cây tìm kiếm nhị phân là một cây nhị phân, trong đó mỗi đỉnh được gán một khóa sao cho mỗi giá trị khóa xác định chỉ một đỉnh và khóa của đỉnh lớn hơn khóa của tất cả các đỉnh con bên trái đồng thời nhỏ hơn khóa của tất cả các đỉnh con bên phải của nó.
Cây và ứng dụng – Khái niệm(tt)

Ví dụ: Tạo cây tìm kiếm nhị phân cho dãy sau :11,8,7,10,12,16,14,17
Giải: Cây tìm kiếm nhị phân cho dảy số trên được cho trên hình 3


Dãy số:11,8,7,10,12,16,14,17
11
8
16
12
14
17
10
7
Hình 3
Cây và ứng dụng – Tính chất
Định lý: Cho T là một đồ thị có n đỉnh. Khi đó các khẳng định sau là tương đương:
a) T là một cây.
b) T là đồ thị liên thông không có chu trình.
c) T là đồ thị liên thông có n – 1 cạnh.
d) T là đồ thị không có chu trình và có n – 1 cạnh
Cây và ứng dụng - Phương pháp duyệt cây
Hệ địa chỉ phổ dụng:
Định nghĩa: Hệ địa chỉ phổ dụng của một cây có gốc và được sắp là một cách sắp thứ tự toàn bộ các đỉnh của cây bằng phương pháp truy hồi như sau:
1. Gán nhãn cho gốc bằng số nguyên 0. Sau đó k đỉnh co của nó( ở mức 1) từ trái sang phải được gán nhãn là 1, 2, 3, …, k.
2. Với mọi đỉnh v ở mức n có nhãn A, thì kv đỉnh con của nó từ trái qua phải được gán nhãn là A.1,…, A.n
Cây và ứng dụng - Phương pháp duyệt cây (tt)
Các thuật toán duyệt cây
Các thủ tục viếng thăm một cách có hệ thống tất cả các đỉnh của một cây có gốc và được sắp thứ tự gọi là các thuật toán duyệt cây.
Các thuật toán duyệt cây :
Duyệt tiền thứ tự
Duyệt trung thứ tự
Duyệt hậu thứ tự
Cây và ứng dụng - Phương pháp duyệt cây (tt)
Duyệt tiền thứ tự
Thuật toán:
1. Thăm gốc r.
2. Duyệt cây con T(r1) của T(r) theo tiền thứ tự.
3. Duyệt cây con T(r2) của T(r) theo tiền thứ tự.
...
n+1. Duyệt cây con T(rn) của T(r) theo tiền thứ tự.
T1
T2
Tn
r
Bước 1: Duyệt r
Bước 2: Duyệt T1
Kiểu tiền thứ tự
Bước 3: Duyệt T2
Kiểu tiền thứ tự
Bước n + 1: Duyệt Tn
Kiểu tiền thứ tự
Duyệt cây theo kiểu tiền thứ tự
a
e
c
d
b
j
m
g
k
i
o
n
f
p
l
h
a
e
c
d
b
j
m
g
k
i
o
n
f
p
l
h
Ví dụ:Xác định trình tự viếng thăm các đỉnh của cây có gốc và được sắp xếp trên hình 3 bằng cách duyêt tiền thứ tự
e
d
b
j
m
g
k
o
n
p
l
h
a
e
c
d
b
j
m
g
k
i
o
n
f
p
h
j
m
g
k
o
n
p
l
a
e
c
d
b
j
m
g
k
i
o
n
f
p
h
g
k
o
n
l
a
e
c
d
b
j
m
i
o
f
p
h
g
k
n
l
a
e
c
d
b
j
m
i
o
f
p
h
Vậy thứ tự duyệt các đỉnh trên của cây T theo kiểu tiền thứ tự là :
a, b, e, j, k, n, o, p, f, c, d, g, l, m, h, i
Duyệt trung thứ tự
Thuật toán:
1. Duyệt cây con T(r1) của T(r) theo trung thứ tự.
2. Thăm gốc r.
3. Duyệt cây con T(r2) của T(r) theo trung thứ tự.
4. Duyệt cây con T(r3) của T(r) theo trung thứ tự.
...
n+1. Duyệt cây con T(rn) của T(r) theo trung thứ tự.

T1
T2
Tn
r
Bước 2: Duyệt r
Bước 1: Duyệt T1
Kiểu trung thứ tự
Bước 3: Duyệt T2
Kiểu trung thứ tự
Bước n + 1: Duyệt Tn
Kiểu trung thứ tự
Duyệt cây theo kiểu trung thứ tự
Ví dụ:Xác định trình tự viếng thăm các đỉnh của cây có gốc và được sắp xếp trên hình sau bằng cách duyêt trung thứ tự
a
e
c
d
b
j
m
g
k
i
o
n
f
p
l
h
a
e
c
d
b
j
m
g
k
i
o
n
f
p
l
h
a
e
c
d
b
m
g
k
i
o
n
f
p
l
h
a
c
d
b
j
m
g
k
i
o
n
f
p
l
h
e
c
d
b
m
g
o
f
l
h
a
c
d
b
j
m
g
k
i
n
f
p
l
h
e
d
m
g
o
h
a
c
b
j
m
g
k
i
n
f
p
l
h
e
d
o
a
c
b
j
m
g
k
n
f
p
l
h
i
Vậy thứ tự duyệt các đỉnh trên của cây T theo kiểu trung thứ tự là :
j, e, n, k, o, p, b, f, a, c, l, g, m, d, h, i
DUYỆT KIỂU HẬU THỨ TỰ

T1
T2
Tn
r
Bước n: Duyệt r
Bước 1: Duyệt T1
Kiểu hậu thứ tự
Bước 2: Duyệt T2
Kiểu hậu thứ tự
Bước n : Duyệt Tn
Kiểu hậu thứ tự
Duyệt cây theo kiểu hậu thứ tự
Ví dụ: xác định trình tự viếng thăm các đỉnh của cây có
gốcvà được sắp trên hình saubằng cách duyệt hậu thứ
tự.
a
e
c
d
b
j
m
g
k
i
o
n
f
p
l
h
a
e
c
d
b
j
m
g
k
i
o
n
f
p
l
h
Theo thuật toán duyệt hậu thứ tự, trình tự duyệt các đỉnh của T là:
J, n, o, p, k, e, f, b, c, l, m, g, h, I, d, a
a
c
f
b
e
j
n
o
p
k
l
m
h
i
d
g
Cách dễ nhớ các cách duyệt cây theo các kiểu tiền, trung, hậu thứ tự
A. Tô màu đồ thị
Mở đầu
Các định nghĩa, định lý
Thuật toán
Ứng dụng bài toán Tô màu đồ thị : Lập lịch thi
B. Cây và ứng dụng
Mở đầu
Khái niệm – Tính chất
Phương pháp duyệt cây
C. Kết luận

A.Tô màu đồ thị
1. Các định nghĩa, định lý
- Định lý 5 màu
- Định lý 4 màu
2. Thuật toán
3. Ứng dụng bài toán Tô màu đồ thị : Lập lịch thi
B. Cây và ứng dụng
1. Khái niệm – Tính chất
2. Phương pháp duyệt cây
- Duyệt tiền thứ tự
- Duyệt trung thứ tự
- Duyệt hậu thứ tự
C. Bài tập ứng dụng
C. Kết luận
Thank you for your attention!