funnystar_hana
New Member
Download miễn phí Giáo trình Đại số lý thuyết đồ thị
3.3. CÁC DẠNG CỦA BÀI TOÁN:TỪ MỘT ĐỈNH ĐẾN CÁC ĐỈNH
CÒN LẠI.
Bài toán này còn được gọi là bài toán tìm đường đi ngắn nhất từ gốc duy nhất. Nhiều
bài toán khác cũng có thể dùng thuật toán này để giải :
- Đường đi ngắn nhất đến đích duy nhất.
- Đường đi ngắn nhất từ cặp đỉnh cho trước.
- Đường đi ngắn nhất cho mọi cặp đỉnh (thuật toán gốc duy nhất từ mỗi đỉnh).
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
(n 2 – 3n + 6) /2 thì G là một đồ thị Hamilton.Chứng minh. Aùp dụng định lý 2.
Simpo PDF Merge and Split Unregistered phiên bản -
Chương 2. Cấu trúc Cây.
Trương Mỹ Dung 18
CHƯƠNG 2.
CẤU TRÚC CÂY.
2.1 ĐỊNH NGHĨA & THÍ DỤ.
2.1.1 CÂY.
Cây là một đồ thị không định hướng, liên thông và không có chu trình.
THÍ DỤ.
FIG. 2.1. Cây.
Chiều dài của đường nối hai đỉnh lại với nhau được gọi là khoảûng cách giữa hai đỉnh.
TÍNH CHẤT.
Giữa hai đỉnh bất kỳ của một cây sẽ có duy nhất một dây chuyền nối chúng lại với
nhau.
Một cây n đỉnh sẽ có n –1 cạnh. Cộng thêm vào cây một cạnh giữa hai đỉnh bất kỳ sẽ
tạo nên một chu trình duy nhất.
2.1.2 RỪNG.
Là một đồ thị không định hướng và không có chu trình (Không liên thông mạnh) Mỗi
thành phần liên thông của một rừng là một cây.
Simpo PDF Merge and Split Unregistered phiên bản -
Chương 2. Cấu trúc Cây.
Trương Mỹ Dung 19
2.1.3 CẤU TRÚC CÂY (CÂY CÓ GỐC).
Là một đồ thị có định hướng sao cho mỗi đỉnh đều có một đỉnh trước trừ một phần tử duy
nhất không có , được gọi là GỐC. Với mọi đỉnh x thì có duy nhất một đường từ gốc đi
đến x.
Xét một đỉnh x của một cây T có gốc là r :
Một đỉnh y bất kỳ nằm trên đường hướng từ gốc đến x, đươc gọi là các ĐỈNH
TRƯỚC (ANCETRE ) của x, và x được là ĐỈNH SAU (DESCENDANT) của y.
Nếu (x,y) là một cạnh của T, ta gọi x là CHA của y và y là CON của x. Hai đỉnh
cùng cha được gọi là ANH EM. Một đỉnh không có con được gọi là LÁ. Những đỉnh
không là LÁ được gọi là ĐỈNH TRONG.
Chiều dài của đường từ gốc đến đỉnh được gọi là độ sâu của đỉnh đó.
Mức (Niveau) của một đỉnh trong T là khoảng cách từ gốc đến x.
Mức của nút gốc = 0.
Mức của nút khác gốc = Mức của cây con nhỏ nhất chứa nó + 1.
Chiều cao hay độ sâu (Hauteur, profondeur) của cây là giá trị lớn nhất của mức của
các đỉnh trong cây.
Nếu mỗi đỉnh trong cây có tối đa hai con, thì ta gọi đó là cây nhị phân.
Bậc của nút & bậc của cây (Degrée).
Bậc của nút là số cây con của nút đó.
Bậc của cây là bậc lớn nhất của các nút của cây. Nếu cây có bậc là n, ta gọi là
cây n-cành.
THÍ DỤ . Cây 3 – cành có gốc,với 8 đỉnh và có độ cao là 4.
-------------------------------------------- d(1) = 3--------------------Mức 0.
---------------------- d(4)=2 ------- ---------- d(3)=0 -----Mức 1.
d( 2)=0
-------------d(5)=2 ---------- ------------------------------------------Mức 2.
d(9)=0
d(6)=0 ------- d(7) =1 ----------------------------------------- Mức 3.
--------d(8)=0 --------------------------------------------------------Mức 4.
FIG.2.2. Cây có gốc.
2.1.4. THÍ DỤ.
2
3
1
4
5 9
6 7
8
Simpo PDF Merge and Split Unregistered phiên bản -
Chương 2. Cấu trúc Cây.
Trương Mỹ Dung 20
Đôi khi ta có thể biểu diễn một quan hệ bao hàm thức của nhiều tập hợp bằng một
cấu trúc cây.
Thí dụ. Bao hàm của các tập hợp sau có thể biểu diễn thành cấu trúc cây như sau :
B, C, D ⊂ A. A
E, F, G, H ⊂ B.
M, N ⊂ D. D C B
I ⊂ E.
J,K ⊂ F. M N E F G H
L ⊂ H. I J K L
Một Biến có cấu trúc có thể biểu diễn dưới dạng cây.
SINH VIÊN
TRƯỜNG CMNN
CAO ĐẲNG ĐẠI HỌC HỌ TÊN SINH
NGÀY NOI
N T N TP Q
Biểu thức số học. Biểu thức +
X = (x – (2* y) +((x+(y+z)) *z) - *
có thể biểu diễn thành hình cây x * + z
như sau : 2 y x +
y z
Vòng loại trong một cuộc thi đấu bóng bàn.
Vòng 1. J đấu với T, F đấu với M, L đấu với P. J
Vòng 2. J đấu với M, L đấu với Ph J Ph
Vòng 3. J đấu Ph. J M L Ph
Cuối cùng J thắng.
J T F M P L
Câu trong ngôn ngữ tự nhiên (hay trong ngôn ngữ lập trình)
Ferme
Đối với câu « Le Pilote ferme la porte » Pilote porte
Có thể biểu diễn dưới dạng Le la
Tự điễn có thể tổ chức theo hình cây. .
Chẳng hạn tự điễn gồm các từ ART, ART COU
ARTICLE, ASTISTE, COU, COUR,
COUTEAU, COUVE, COUVENT, * I * R TEAU VE
COUVER có thể biểu diễn theo
hình vẽ sau. Ký tự «*» chỉ chấm dứt CLE STE * * * NT R
một từ. Chú ý, thứ tự ALPHABET
theo thứ tự từ phải sang trái. * * * *
Simpo PDF Merge and Split Unregistered phiên bản -
Chương 2. Cấu trúc Cây.
Trương Mỹ Dung 21
2.2 TÍNH CHẤT CƠ BẢN.
2.2.1 ĐỊNH LÝ 1.
Cho G là một cây bậc n > 1. Các tính chất sau đây tương đương với nhau :
1. G liên thông và không có chu trình.
2. G liên thông và có n –1 cạnh.
3. G không có chu trình và có n – 1 cạnh.
4. G không có chu trình và nếu thêm vào một cạnh giữa hai đỉnh không kề sẽ
tạo một chu trình duy nhất giữa chúng.
5. G liên thông tối thiểu(có nghĩa là nếu xóa đi một cạnh bất kỳ thì G không còn
liên thông nữa)
6. Mọi cặp đỉnh có duy nhất dây chuyền nối chúng.
CHỨNG MINH. Bài tập.
2.2.2 ĐỊNH LÝù 2.
Một đồ thị G = (X,U) là một đồ thị có chứa một đồ thị riêng phần nếu và chỉ nếu
G liên thông.
CHỨNG MINH. Bài tập.
2.2.3 ĐỊNH LÝ 3.
Mọi Cấu trúc cây là một cây.
CHỨNG MINH. Bài tập.
Simpo PDF Merge and Split Unregistered phiên bản -
Chương 2. Cấu trúc Cây.
Trương Mỹ Dung 22
2.3 CÂY NHỊ PHÂN.
2.3.1. ĐỊNH NGHĨA (THEO ĐỆ QUI).
Một cây nhị phân B hoăc là ∅ hay có dạng :
B = trong đó :
O : gốc,
B1 : cây con trái và
B2 : cây con phải.
2.3.2. BIỂU DIỄN CÂY NHỊ PHÂN.
THÍ DỤ.
SỬ DỤNG BẢNG. Có thể định nghĩa kiểu dữ liệu như sau :
Type Arbtab = Array [1..n] of Record v : t ;
G : integer ;
D : integer ;
End ;
Với thí dụ ở trên, ta có :
Trái Phải
1
2 d 0 8
3 a 5 6
4 e 0 9
5 b 2 0
6 c 4 0
7
8 f 0 0
9 g 0 0
10
SỬ DỤNG CON TRỎ. Có thể định nghĩa kiểu dữ liệu như sau :
Type Pt = ^nut ;
nut = Record
G : Pt ;
Val : t ;
D : Pt ;
End ;
e
a
b
d
c
f g
Simpo PDF Merge and Split Unregistered phiên bản -
Chương 2. Cấu trúc Cây.
Trương Mỹ Dung 23
2.3.3. DUYỆT MỘT CÂY NHỊ PHÂN.
Có 3 cách duyệt một cây nhị phân (phụ thuộc theo gốc).
1. THỨ TỰ TRƯỚC (PREFIXÉ).
Xử lý gốc.
Duyệt cây con trái.
Duyệt cây con phải.
2. THỨ TỰ GIỮA (INFIXÉ).
Duyệt cây con trái.
Xử lý gốc.
Duyệt cây con phải.
3. THỨ TỰ SAU (POSTFIXÉ).
Duyệt cây con trái.
Duyệt cây con phải.
Xử lý gốc.
THÍ DỤ. Theo cây ở thí dụ trên , ta có :
Trước : a b d f c e g.
Giửa : d f b a e g c.
Sau : f d b g e c a.
2.4 CÂY PHỦ.
2.4.1. ĐỊNH NGHĨA.
Cho một đồ thị vô hướng G. Một cây H gọi là cây phủ của G nếu H là cây riêng
phần của G chứa mọi đỉnh của G.
2.4.2. ĐỊNH LÝ.
Đồ thị G có cây phủ nếu và chỉ nếu G liên thông.
Simpo PDF Merge and Split Unregistered phiên bản -
Chương 2. Cấu trúc Cây.
Trương Mỹ Dung 24
2.4.3. GIẢI THUẬT TÌM CÂY PHỦ.
Xét một đồ thị G.
GIẢI THUẬT.
Bước 1. Chọn tùy ý một đỉnh của G đặt vào H.
Bước 2. Nếu mọi đỉnh của G đều nằm trong H thì dừng.
Bưức 3. Nếu không, tìm một đỉnh của G không nằm trong H mà nó có thể nối
nó với một đỉnh của H bằng một cạnh. Thêm đỉnh và cạnh này vào H. Quay
về bước 2.
THÍ DỤ . Cho đồ thị G theo hình vẽ sau :
x3 x2
x1
x6
x4 x5
FIG. 2.3.
Khởi từ x1. T= ∅.
Bước 1. Chọn x2, T = {(x1,x2)}.
Bước 2. Chọn x3, T = {(x1,x2), (x2,x3)}.
Bước 3. Chọn x4, T = {(x1,x2), (x2,x3), (x3,x4)}.
Bước 4. Chọn x5, T = {(x1,x2), (x2,x3), (x3,x4), (x4,x5)}.
Bước 5. Chọn x6, T = {(x1,x2), (x2,x3), (x3,x4), (x4,x5), (x5,...