Bài giảng Toán rời rạc: Chương 6

CHƯƠNG 6

CÂY

Nguyễn Quỳnh Diệp diepnq@tlu.edu.vn

Nguyễn Quỳnh Diệp

NỘI DUNG

• Các định nghĩa và tính chất

• Các ứng dụng của cây

• Cây khung

• Cây khung nhỏ nhất

Nguyễn Quỳnh Diệp

Toán rời rạc

6.1. CÁC ĐỊNH NGHĨA VÀ TÍNH CHẤT

Nguyễn Quỳnh Diệp

Toán rời rạc

CÂY

Định nghĩa 1:

Cây là một đồ thị vô hướng, liên thông và không có chu trình đơn

Ví dụ:

Nguyễn Quỳnh Diệp

Toán rời rạc

CÂY

Ví dụ: Đồ thị nào sau đây là cây?

Nguyễn Quỳnh Diệp

Toán rời rạc

Đồ thị không có chu trình đơn và không liên thông gọi là rừng.

CÂY

Định lí 1:

Một đồ thị vô hướng là một cây nếu giữa mọi cặp đỉnh của nó luôn tồn tại đường đi đơn duy nhất.

Định nghĩa 2:

Nguyễn Quỳnh Diệp

Toán rời rạc

Cây có gốc là cây có một đỉnh được gọi là gốc và mọi cạnh có hướng từ gốc đi ra.

CÂY

Ví dụ:

Nguyễn Quỳnh Diệp

Toán rời rạc

MỘT SỐ THUẬT NGỮ

Nguyễn Quỳnh Diệp

Toán rời rạc

Nếu v là đỉnh khác gốc, Cha của v là đỉnh u duy nhất sao cho có 1 cạnh hướng từ u đến v. Khi đó u gọi là cha của v; v gọi là con của u. Các đỉnh có cùng cha gọi là anh em.

MỘT SỐ THUẬT NGỮ

Nguyễn Quỳnh Diệp

Toán rời rạc

Tổ tiên của một đỉnh khác gốc là các đỉnh trên đường đi từ gốc tời đỉnh này (tức là cha của nó, ông của nó,…cho tới khi đến gốc). Con cháu của đỉnh v là các đỉnh có v như tổ tiên

MỘT SỐ THUẬT NGỮ

Nguyễn Quỳnh Diệp

Toán rời rạc

Các đỉnh của cây gọi là lá nếu nó không có con Các đỉnh có con gọi là đỉnh trong

MỘT SỐ THUẬT NGỮ

Nguyễn Quỳnh Diệp

Toán rời rạc

Nếu a là đỉnh của 1 cây, thì cây con với gốc a là đồ thị con của cây đang xét, bao gồm a và các con cháu của nó cùng với các cạnh liên thuộc với các con cháu của a.

CÂY m-phân

Định nghĩa 3:

• Cây có gốc được gọi là cây m-phân nếu tất cả các đỉnh trong của

• Cây được gọi là m-phân đầy đủ nếu mọi đỉnh trong có đúng m

nó không có hơn m con.

con.

Nguyễn Quỳnh Diệp

Toán rời rạc

• Khi m = 2 ta có cây nhị phân

CÂY CÓ GỐC

Cây có gốc được sắp:

Cây có gốc, được sắp (có thứ tự) là cây có gốc mà trong đó các con của mỗi đỉnh trong được sắp xếp theo một thứ tự nhất định.

Nguyễn Quỳnh Diệp

Toán rời rạc

VÍ DỤ VỀ CÂY

Tổ chức trong công ty

Nguyễn Quỳnh Diệp

Toán rời rạc

VÍ DỤ VỀ CÂY

Cấu trúc thư mục

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC TÍNH CHẤT CỦA CÂY

Định lí 2:

Cây với n đỉnh có đúng (n-1) cạnh

Định lí 3:

Cây m-phân đầy đủ với i đỉnh trong sẽ có tất cả n = m.i + 1 đỉnh.

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC TÍNH CHẤT CỦA CÂY

Định lí 4:

Cây m-phân đầy đủ với

lá

(i) n đỉnh có 𝒊 =

đỉnh trong và 𝒍 =

𝒎−𝟏 𝒏+𝟏 𝒎

𝒏−𝟏 𝒎

(ii) i đỉnh trong, có n= m.i + 1 đỉnh và l = (m – 1) .i +1 lá

đỉnh trong

(iii) l lá, có 𝒏 =

đỉnh và 𝒊 =

𝒍 −𝟏 𝒎 −𝟏

𝒎𝒍 −𝟏 𝒎−𝟏

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC TÍNH CHẤT CỦA CÂY

Ví dụ: Trò chơi viết thư dây chuyền. Ban đầu có một người nhận được một bức thư và giả sử rằng khi nhận được một bức thư hoặc sẽ viết thư cho bốn người khác hoặc không viết cho ai. Hỏi có bao nhiêu người nhận được thư kể cả người đầu tiên nếu không có ai nhận được nhiều hơn một bức và trò chơi kết thúc khi có 100 người nhận thư mà ko viết cho ai?

Giải: • Trò chơi biểu diễn bằng cây tứ phân. • Có 100 không viết thư nên số lá của cây là l = 100 • Số người nhận thư là n = (4.100 -1 )/(4-1) = 133 • Số các đỉnh trong là i = (100-1)/(4-1) = 33 đỉnh, tức 33 người

viết thư

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC TÍNH CHẤT CỦA CÂY

• Mức của đỉnh v trong cây là độ dài của đường đi duy nhất

từ gốc tới nó. Gốc có mức 0

• Độ cao của cây là mức cao nhất của tất cả các đỉnh

• Cây m-phân có độ cao h được gọi là cân đối nếu tất cả các

lá đều ở mức h và (h-1)

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC TÍNH CHẤT CỦA CÂY

Định lí 5:

Có nhiều nhất mh lá trong cây m-phân với độ cao h

Nguyễn Quỳnh Diệp

Toán rời rạc

6.2. CÁC ỨNG DỤNG CỦA CÂY

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC ỨNG DỤNG CỦA CÂY

• Cây tìm kiếm nhị phân

• Cây quyết định

• Các mã tiền tố

Nguyễn Quỳnh Diệp

Toán rời rạc

TÌM KIẾM NHỊ PHÂN

Cây nhị phân:

• Là cây có một cây con trái và một cây con phải • Mỗi đỉnh được gán một nhãn sao cho:

• Lớn hơn nhãn của tất cả các đỉnh thuộc cây con trái của nó • Nhỏ hơn nhãn của tất cả các đỉnh thuộc cây con bên phải của

Nguyễn Quỳnh Diệp

Toán rời rạc

nó

TÌM KIẾM NHỊ PHÂN

Xây dựng cây tìm kiếm nhị phân: • Bắt đầu cây có đúng 1 đỉnh (gốc) • Thêm một phần tử mới:

 So sánh với nhãn của đỉnh, bắt đầu từ gốc  Đi sang trái nếu nó nhỏ hơn  Đi sang phải nếu nó lớn hơn  Tạo đỉnh mới là con bên trái nếu phần tử nhỏ hơn nhãn của

đỉnh và đỉnh không có con trái

đỉnh và đỉnh không có con phải

Nguyễn Quỳnh Diệp

Toán rời rạc

 Tạo đỉnh mới là con bên phải nếu phần tử lớn hơn nhãn của

TÌM KIẾM NHỊ PHÂN

Ví dụ: Tạo cây tìm kiếm nhị phân cho các từ sau: mathematics,

physics,geography, zoology, meteology, geology, psychology, chemistry

Physics > Mathemetics

Geography < Mathemetics

Zoology > Mathemetics Zoology > Physics

Geology < Mathemetics Geology > Geography

Meteorology > Mathemetics Meteorology < Physics

Chemistry < Mathemetics Chemistry < Geography

Psychology > Mathemetics Psychology > Physics Psychology < Zoology

Nguyễn Quỳnh Diệp

Toán rời rạc

TÌM KIẾM NHỊ PHÂN

Thuật toán tìm kiếm nhị phân: • Định vị phần tử x trong cây tìm kiếm nhị phân nếu nó là

nhãn của một đỉnh

• Nếu x không là nhãn của đỉnh nào, thêm mới x vào cây

Nguyễn Quỳnh Diệp

Toán rời rạc

TÌM KIẾM NHỊ PHÂN

THUẬT TOÁN : Thuật toán tìm kiếm nhị phân

Procedure insertion(T: cây tìm kiếm nhị phân, x: phần tử) v := gốc của T { đỉnh không có trong T sẽ có giá trị bằng null } while v  null và label(v)  x begin

if x < label(v) then

if con bên trái của v  null then v := con bên trái của v else thêm đỉnh mới là con trái của v và đặt v := null

else

if con bên phải của v  null then v := con bên phải của v else thêm đỉnh mới là con phải của v và đặt v := null

end if gốc của T = null then thêm đỉnh v vào cây và gán cho nó nhãn là x else if v = null hoặc label(v)  x then gán nhãn cho đỉnh mới là x và đặt v là đỉnh mới này { v = vị trí của x }

Nguyễn Quỳnh Diệp

Toán rời rạc

6.3. CÁC PHƯƠNG PHÁP DUYỆT CÂY

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC PHƯƠNG PHÁP DUYỆT CÂY

• Duyệt tiền thứ tự (thứ tự trước)

• Duyệt trung thứ tự (thứ tự giữa)

Nguyễn Quỳnh Diệp

• Duyệt hậu thứ tự (thứ tự sau) Toán rời rạc

DUYỆT TIỀN THỨ TỰ

Định nghĩa 1:

Giả sử T là một cây được sắp thứ tự với gốc r. Nếu T chỉ có nút gốc thì r là duyệt tiền thứ tự của cây T. Ngược lại, thì gọi T1 , T2 …, Tn là các cây con của T từ trái qua phải. Duyệt tiền thứ tự là:

• Thăm r • Duyệt T1 theo kiểu tiền thứ tự • Duyệt T2 theo kiểu tiền thứ tự • ….. • Duyệt Tn theo kiểu tiền thứ tự

Nguyễn Quỳnh Diệp

Toán rời rạc

DUYỆT TIỀN THỨ TỰ

Ví dụ: Cách duyệt tiền thứ tự sẽ thăm các đỉnh của cây

theo thứ tự nào?

Nguyễn Quỳnh Diệp

Toán rời rạc

DUYỆT TIỀN THỨ TỰ

THUẬT TOÁN : Duyệt kiểu tiền thứ tự

Procedure Preorder (T: cây có gốc được sắp) r := gốc của T Liệt kê r for mỗi cây con c của r từ trái sang phải begin

T(c) := cây con với gốc c Preorder(T(c))

end

Nguyễn Quỳnh Diệp

Toán rời rạc

DUYỆT TRUNG THỨ TỰ

Định nghĩa 2:

Giả sử T là một cây được sắp thứ tự với gốc r. Nếu T chỉ có nút gốc thì r là duyệt trung thứ tự của cây T. Ngược lại, thì gọi T1 , T2 …, Tn là các cây con của T từ trái qua phải. Duyệt trung thứ tự là:

• Duyệt T1 theo kiểu trung thứ tự • Thăm r • Duyệt T2 theo kiểu trung thứ tự • ….. • Duyệt Tn theo kiểu trung thứ tự

Nguyễn Quỳnh Diệp

Toán rời rạc

DUYỆT TRUNG THỨ TỰ

Ví dụ: Cách duyệt trung thứ tự sẽ thăm các đỉnh của

cây theo thứ tự nào?

Nguyễn Quỳnh Diệp

Toán rời rạc

DUYỆT TRUNG THỨ TỰ

THUẬT TOÁN : Duyệt kiểu trung thứ tự

Procedure Inorder (T: cây có gốc được sắp) r := gốc của T if r là lá then liệt kê r else begin l := con đầu tiên từ trái sang phải của r T(l) := cây con với gốc l Inorder(T(l)) Liệt kê r for mỗi cây con c của r từ trái sang phải trừ l

T(c) := cây con với gốc c Inorder(T(c))

Nguyễn Quỳnh Diệp

Toán rời rạc

end

DUYỆT HẬU THỨ TỰ

Định nghĩa 3:

Giả sử T là một cây được sắp thứ tự với gốc r. Nếu T chỉ có nút gốc thì r là duyệt trung thứ tự của cây T. Ngược lại, thì gọi T1 , T2 …, Tn là các cây con của T từ trái qua phải. Duyệt hậu thứ tự là:

• Duyệt T1 theo kiểu hậu thứ tự • Duyệt T2 theo kiểu hậu thứ tự • ….. • Duyệt Tn theo kiểu hậu thứ tự • Thăm r

Nguyễn Quỳnh Diệp

Toán rời rạc

DUYỆT TRUNG THỨ TỰ

Ví dụ: Cách duyệt hậu thứ tự sẽ thăm các đỉnh của cây theo

Nguyễn Quỳnh Diệp

Toán rời rạc

thứ tự nào?

DUYỆT HẬU THỨ TỰ

THUẬT TOÁN : Duyệt kiểu hậu thứ tự

Procedure Postorder (T: cây có gốc được sắp) r := gốc của T for mỗi cây con c của r từ trái sang phải begin

T(c) := cây con với gốc c Postorder(T(c))

end Liệt kê r

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC KÍ PHÁP TRUNG TỐ, TIỀN TỐ VÀ HẬU TỐ

• Có thể dùng để biểu diễn biểu thức phức tạp:

• Mệnh đề phức hợp • Tập hợp • Biểu thức số học

• Biểu diễn bằng cây có gốc và được sắp, trong đó:

• đỉnh trong biểu thị các phép toán • lá biểu thị các số hay các biến

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC KÍ PHÁP TRUNG TỐ, TIỀN TỐ VÀ HẬU TỐ

Ví dụ: Tìm cây có gốc biểu diễn biểu thức

𝒙 + 𝒚 ↑ 𝟐 + (

)

𝒙 − 𝟒 𝟑

Biểu thức có đầy đủ dấu ngoặc đơn gọi là dạng trung tố Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC KÍ PHÁP TRUNG TỐ, TIỀN TỐ VÀ HẬU TỐ

• Biểu thức được viết dưới dạng tiền tố gọi là kí pháp Ba

Lan

• Khi duyệt biểu thức dạng tiền tố, ta làm như sau:

• Đi từ phải sang trái

• Gặp một toán tử thực hiện phép toán tương ứng với hai toán

hạng đi liền bên phải của toán tử

Ví dụ 1: Tính giá trị biểu thức tiền tố

+ - * 2 3 5 / ↑ 2 3 4

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC KÍ PHÁP TRUNG TỐ, TIỀN TỐ VÀ HẬU TỐ

• Biểu thức được viết dưới dạng hậu tố gọi là kí pháp Ba

Lan ngược

• Khi duyệt biểu thức dạng hậu tố, ta làm như sau:

• Đi từ trái sang phải

• Thực hiện phép toán khi có một toán tử đi sau hai toán hạng

Ví dụ 2: Tính giá trị biểu thức hậu tố

7 8 + 2 ↑ 7 4 – 3 / +

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC KÍ PHÁP TRUNG TỐ, TIỀN TỐ VÀ HẬU TỐ

Ví dụ 3:

a). Hãy biểu diễn biểu thức ((x+2)^3)*((y-(3+x))-5) bằng cây nhị

phân.

b). Hãy viết thứ tự duyệt cây dưới dạng: tiền tố, hậu tố, trung tố

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC KÍ PHÁP TRUNG TỐ, TIỀN TỐ VÀ HẬU TỐ

Ví dụ 4:

Hãy vẽ cây ứng với

a. + * + - 5 3 2 1 4

b. ^ + 2 3 – 5 1

c. * / 9 3 + * 2 4 – 7 6

Nguyễn Quỳnh Diệp

Toán rời rạc

CÁC KÍ PHÁP TRUNG TỐ, TIỀN TỐ VÀ HẬU TỐ

Ví dụ 5:

Hãy tính giá trị các biểu thức sau

a. 5 2 1 - - 3 1 4 + + *

b. + - ^ 3 2 ^ 2 3 / 6 – 4 2

c. 9 3 / 5 + 7 2 - *

d. * + 3 + 3 ^ 3 + 3 3 3

e. 3 2 * 2 ^ 5 3 – 8 4 / * -

Nguyễn Quỳnh Diệp

Toán rời rạc

6.4. CÂY KHUNG

Nguyễn Quỳnh Diệp

Toán rời rạc

CÂY KHUNG

Bài toán giao thông ở Maine:

Nguyễn Quỳnh Diệp

Toán rời rạc

• Chính quyền địa phương muốn cào tuyết một số ít nhất các con đường sao cho luôn luôn có đường thông suốt nối hai thành phố bất kì

CÂY KHUNG

Định nghĩa 1:

Cho G là một đơn đồ thị. Một cây được gọi là cây khung của G nếu nó là một đồ thị con của G và chứa tất cả các đỉnh của G.

Các cách tìm cây khung của đồ thị:

 Xóa đi các cạnh tạo ra chu trình

 Bằng phương pháp tìm kiếm theo chiều rộng

Nguyễn Quỳnh Diệp

Toán rời rạc

 Bằng phương pháp tìm kiếm theo chiều sâu

XÓA CÁC CẠNH TẠO CHU TRÌNH

Nguyễn Quỳnh Diệp

Toán rời rạc

TÌM KIẾM THEO CHIỀU SÂU

• Chọn tùy ý 1 đỉnh của đồ thị làm gốc

• Xây dựng đường đi từ đỉnh này bằng cách ghép nối tiếp các

cạnh vào đường đi, cho đến khi không thể ghép được nữa.

• Nếu đường đi chưa đi qua tất cả các đỉnh thì lùi lại một

bước và xây dựng đường đi mới qua các đỉnh chưa thuộc

đường đi.

• Tiếp tục lùi lại cho đến khi không thực hiện được nữa

Tìm kiếm ưu tiên chiều sâu cũng được gọi là thủ tục quay lui

Nguyễn Quỳnh Diệp

Toán rời rạc

TÌM KIẾM THEO CHIỀU SÂU

THUẬT TOÁN : Tìm kiếm theo chiều sâu

Procedure DFS(G: đồ thị liên thông với các đỉnh v1 , v2… vn) T := cây chỉ chứa một đỉnh v1 Visit(v1)

thêm đỉnh w và cạnh (v, w) vào T Visit(w)

Procedure Visit(v: đỉnh của G) for mỗi đỉnh w liền kề với v và chưa có trong T begin

Nguyễn Quỳnh Diệp

Toán rời rạc

end

TÌM KIẾM THEO CHIỀU SÂU

Ví dụ:

Bắt đầu từ đỉnh f

Nguyễn Quỳnh Diệp

Toán rời rạc

TÌM KIẾM THEO CHIỀU RỘNG

• Chọn tùy ý một đỉnh của đồ thị làm gốc

• Ghép vào tất cả các cạnh liên thuộc với đỉnh này. Đỉnh

ghép vào là đỉnh mức 1 của cây khung

• Với mỗi đỉnh mức 1, ghép tất cả các cạnh liên thuộc với

nó vào cây mà không tạo ra chu trình, ta được các đỉnh

mức 2.

• Tiếp tục cho đến khi tất cả các đỉnh được ghép vào cây

Nguyễn Quỳnh Diệp

Toán rời rạc

TÌM KIẾM THEO CHIỀU RỘNG

Ví dụ: Dùng thuật toán tìm kiếm theo chiều rộng, tìm cây

khung của đồ thị với đỉnh xuất phát là e

Nguyễn Quỳnh Diệp

Toán rời rạc

TÌM KIẾM THEO CHIỀU RỘNG

THUẬT TOÁN : Tìm kiếm theo chiều rộng

Procedure BFS(G: đồ thị liên thông với các đỉnh v1 , v2… vn) T := cây chỉ chứa một đỉnh v1 L := danh sách rỗng Đặt v1 vào danh sách L gồm các đỉnh không xử lí while L khác rỗng begin Xóa đỉnh đầu tiên, v, khỏi L for mỗi đỉnh liền kề w của v

if w chưa nằm trong L và không thuộc T then begin

thêm đỉnh w vào cuối danh sách L thêm w và cạnh {v, w} vào T

end

Nguyễn Quỳnh Diệp

Toán rời rạc

BÀI TẬP

Nguyễn Quỳnh Diệp

Toán rời rạc

 Bài 1: Tìm cây khung của đồ thị bằng cách xóa đi các cạnh

BÀI TẬP

 Bài 2: Tìm cây khung của đồ thị bằng kĩ thuật tìm kiếm theo

Nguyễn Quỳnh Diệp

Toán rời rạc

chiều sâu. Chọn a làm gốc của cây.

6.5. CÂY KHUNG NHỎ NHẤT

Nguyễn Quỳnh Diệp

Toán rời rạc

CÂY KHUNG NHỎ NHẤT

Định nghĩa 1:

Nguyễn Quỳnh Diệp

Toán rời rạc

Cây khung nhỏ nhất trong một đồ thị liên thông có trọng số là một cây khung có tổng trọng số trên các cạnh của nó là nhỏ nhất

CÂY KHUNG NHỎ NHẤT

Thuật toán tìm cây khung nhỏ nhất:

 Thuật toán Prim

 Thuật toán Kruskal

Nguyễn Quỳnh Diệp

Toán rời rạc

THUẬT TOÁN PRIM

• Do Robert Prim đưa ra năm 1957

• Thuật toán:

 Chọn một cạnh bất kì có trọng số nhỏ nhất, đặt vào

khung

 Ghép vào cây các cạnh có trọng số nhỏ nhất, liên thuộc

với 1 đỉnh của cây và không tạo ra chu trình

 Dừng khi có (n-1) cạnh được ghép vào cây

Nguyễn Quỳnh Diệp

Toán rời rạc

THUẬT TOÁN PRIM

Ví dụ: Tìm cây khung nhỏ nhất

Trọng số

Lần chọn

Cạnh

Tổng cộng : 24

Nguyễn Quỳnh Diệp

Toán rời rạc

THUẬT TOÁN PRIM

THUẬT TOÁN : Thuật toán Prim

Procedure Prim(G: đồ thị liên thông có trọng số với n đỉnh) T := cạnh có trọng số nhỏ nhất for i:= 1 to n-2 begin

e := cạnh có trọng số tối thiểu, liên thuộc với một đỉnh trong

T và không tạo ra chu trình trong T nếu ghép nó vào T

T := T với e được ghép vào

end { T là cây khung nhỏ nhất của G }

Nguyễn Quỳnh Diệp

Toán rời rạc

THUẬT TOÁN PRIM

Ví dụ: Tìm cây khung nhỏ nhất

4

a b

2

3

1

c d

2

Nguyễn Quỳnh Diệp

Toán rời rạc

THUẬT TOÁN PRIM

• Cây khung nhỏ nhất gồm các cạnh: {E, C} ; {E, D}; {E, B} ;

{D, A}

• Tổng trọng số nhỏ nhất của cây khung là: 7

4

a b

2

3

1

2

Nguyễn Quỳnh Diệp

Toán rời rạc

THUẬT TOÁN KRUSKAL

• Do Joseph Kruskal đưa ra năm 1956

• Thuật toán:

 Chọn một cạnh bất kỳ có trọng số nhỏ nhất, đặt vào

khung

 Ghép vào cây các cạnh có trọng số nhỏ nhất và không

tạo ra chu trình

 Dừng khi có (n-1) cạnh được ghép vào cây

Nguyễn Quỳnh Diệp

Toán rời rạc

THUẬT TOÁN KRUSKAL

THUẬT TOÁN : Thuật toán Kruskal

Procedure Kruskal(G: đồ thị n đỉnh, liên thông, có trọng số) T := đồ thị rỗng for i:= 1 to n-1 begin

e := cạnh bất kì của G với trọng số nhỏ nhất và không tạo ra

chu trình trong T khi ghép vào T T := T với e được ghép vào

end { T là cây khung nhỏ nhất của G }

Nguyễn Quỳnh Diệp

Toán rời rạc

THUẬT TOÁN KRUSKAL

Ví dụ: Tìm cây khung nhỏ nhất

Trọng số

Lần chọn

Cạnh

Tổng cộng : 24

Nguyễn Quỳnh Diệp

Toán rời rạc

THUẬT TOÁN PRIM

Ví dụ: Tìm cây khung nhỏ nhất

4

a b

2

3

1

c d

2

Nguyễn Quỳnh Diệp

Toán rời rạc

BÀI TẬP

Nguyễn Quỳnh Diệp

Toán rời rạc

 Bài 2: Tìm cây khung nhỏ nhất dùng thuật toán Prim và Kruskal

BÀI TẬP

Nguyễn Quỳnh Diệp

Toán rời rạc

 Bài 2: Tìm cây khung nhỏ nhất dùng thuật toán Prim và Kruskal

Nguyễn Quỳnh Diệp

Bài giảng Toán rời rạc: Chương 6 - Nguyễn Quỳnh Diệp