Toán rời rạc 7- cây

Giáo dục đại cương,Toán rời rạc
  Đánh giá    Viết đánh giá
 38      448      0
Phí: Tải Miễn phí
Mã tài liệu
2wuntq
Danh mục
Giáo dục đại cương,Toán rời rạc
Thể loại
Toán rời rạc,tin học đại cương
Ngày đăng
20/12/2013
Loại file
pdf
Số trang
29
Dung lượng
1.46 M
Lần xem
448
Lần tải
38
  DOWNLOAD

Chọn một đỉnh tùy ý của đồ thị làm gốc. Xây dựng đường đi từ đỉnh này bằng cách lượt ghép các cạnh sao cho mỗi cạnh mới ghép sẽ nối đỉnh cuối cùng trên đường đi với một đỉnh còn chưa thuộc đường đi.Tiếp tục ghép thêm cạnh vào đường đi chừng nào không thể thêm được nữa. Nếu đường đi qua tất cả các đỉnh của đồ thị thì cây do đường đi này tạo nên là cây khung. Nếu chưa thì lùi lại đỉnh trước đỉnh cuối cùng của đường đi và xây dựng đường đi mới xuất phát từ đỉnh này đi qua các đỉnh còn chưa thuộc đường đi. Nếu điều đó không thể làm được thì lùi thêm một đỉnh nữa trên đường đi, tức là lùi hai đỉnh trên đường đi và thử xây dựng đường đi mới

HƯỚNG DẪN DOWNLOAD TÀI LIỆU

Bước 1:Tại trang tài liệu thuvienmienphi bạn muốn tải, click vào nút Download màu xanh lá cây ở phía trên.
Bước 2: Tại liên kết tải về, bạn chọn liên kết để tải File về máy tính. Tại đây sẽ có lựa chọn tải File được lưu trên thuvienmienphi
Bước 3: Một thông báo xuất hiện ở phía cuối trình duyệt, hỏi bạn muốn lưu . - Nếu click vào Save, file sẽ được lưu về máy (Quá trình tải file nhanh hay chậm phụ thuộc vào đường truyền internet, dung lượng file bạn muốn tải)
Có nhiều phần mềm hỗ trợ việc download file về máy tính với tốc độ tải file nhanh như: Internet Download Manager (IDM), Free Download Manager, ... Tùy vào sở thích của từng người mà người dùng chọn lựa phần mềm hỗ trợ download cho máy tính của mình  

NỘI DUNG TÀI LIỆU

Toán rời rạc 7- cây

 

HÌNH ẢNH DEMO
Tài liệu Toán rời rạc 7- cây slide 1

Tài liệu Toán rời rạc 7- cây slide 2

Tài liệu Toán rời rạc 7- cây slide 3

Tài liệu Toán rời rạc 7- cây slide 4

Tài liệu Toán rời rạc 7- cây slide 5


Chỉ xem 5 trang đầu, hãy download Miễn Phí về để xem toàn bộ

Cây
Cây
1.
ĐN và tính chất
Biên soạn: TS.Nguyễn Viết Đông
2.
Cây khung ngắn nhất
3.
Cây có gốc
4.
Phép duyệt cây
2
Định nghĩa và tính chất
Định nghĩa và tính chất
Định nghĩa Cây.
1
a)
)
Cho G là đồ thị vô hướng. G được gọi là một
cây nếu G liên thông và không có chu trình
sơ cấp.
Rừng là đồ thị mà mỗi thành phần liên
thông của nó là một cây.
11
5
12
2
13
6
14
3
7
8
4
9
15
10
16
17
3
4
1
với nhau
T không có chu trình sơ cấp và nếu thêm vào một cạnh giữa
1
Định nghĩa và tính chất
Định nghĩa và tính chất
Điều kiện cần và đủ.
Cho T là đồ thị vô hướng có n đỉnh. Các phát biểu sau đây
1
là tương đương:
i. T là cây.
ii. T liên thông và có n-1 cạnh.
iii. T không có chu trình sơ cấp và có n-1 cạnh .
5
2
6
3
7
8
4
9
10
iv. T liên thông và mỗi cạnh là một cầu.
11
12
13
14
15
16
17
v.
Giữa hai.đỉnh bất kỳ có đúng một đường đi sơ cấp nối chúng
vi. hai đỉnh không kề nhau thì có một chu trình sơ cấp duy nhất.
5
6
Định nghĩa và tính chất
Định nghĩa cây khung.
Breadth-first Search Algorithm .Thuật toán ưu tiên
chiều rộng
Cho G là đồ thị liên thông với tập đỉnh {v1, v2, …, vn}
Bước 0:thêm v1 như là gốc của cây rỗng.
Cho G = (V,E) là đồ thị vô hướng.
Bước 1: thêm vào các đỉnh kề v làm con của nó và các
cạnh nối v1 với chúng.
T là đồ thị con khung của G.
Nếu T là một cây thì T được gọi là cây khung(hay
cây tối đại, hay cây bao trùm) của đồ thị G.
Những đỉnh này là đỉnh mức 1 trong cây.
Bước 2: đối với mọi đỉnh v mức1, thêm vào các cạnh
kề với v vào cây sao cho không tạo nên chu trình đơn.
Thu được các đỉnh mức 2.
Thuật toán tìm cây khung.
…………………………………………………….
Tiếp tục quá trình này cho tới khi tất cả các đỉnh của đồ
thị được ghép vào cây.
CâyT thu được là cây khung của đồ thị.
7
2
f
d
Ví dụ. Xét đồ thị liên thông G.
c l
a
e
a
c
l
e
d
h
e
i
f
j
g
Chọn elàm gốc
d
f
i
d
h
m
e
i
k
f
j
g b d f
a c h
g
Thêm avà clàm con của b,
j
i
k
m
k
Các đỉnh kề với elà con của nó.
h là con duy nhất của d,
gvà jlà con của f,
Các đỉnh mức 1 là: b, d, f, i
k là con duy nhất của i,
Các đỉnh mức 2 là: a, c, h, g, j, k
Depth-firstSearch Algorithm
a
c
l
e
(Thuật toán ưu tiên chiều sâu)
Cho G là đồ thị liên thông với tập đỉnh{v1, v2, …, vn}
e f
d g
h a c h
i j g
m k l
Cuối cùng thêm lvà mlà con của gvà ktương
ứng
Các đỉnh mức 3 là: l, m
j
i
k
m
Chọn một đỉnh tùy ý của đồ thị làm gốc. Xây dựng
đường đi từ đỉnh này bằng cách lượt ghép các cạnh sao
cho mỗi cạnh mới ghép sẽ nối đỉnh cuối cùng trên
đường đi với một đỉnh còn chưa thuộc đường đi.Tiếp tục
ghép thêm cạnh vào đường đi chừng nào không thể thêm
được nữa. Nếu đường đi qua tất cả các đỉnh của đồ thị
thì cây do đường đi này tạo nên là cây khung. Nếu chưa
thì lùi lại đỉnh trước đỉnh cuối cùng của đường đi và xây
dựng đường đi mới xuất phát từ đỉnh này đi qua các đỉnh
còn chưa thuộc đường đi. Nếu điều đó không thể làm
được thì lùi thêm một đỉnh nữa trên đường đi, tức là lùi
hai đỉnh trên đường đi và thử xây dựng đường đi mới.
3

Nguồn: thuvienmienphi

 

Bạn phải gởi bình luận/ đánh giá để thấy được link tải

Nếu bạn chưa đăng nhập xin hãy chọn ĐĂNG KÝ hoặc ĐĂNG NHẬP
 
 

BÌNH LUẬN


Nội dung bậy bạ, spam tài khoản sẽ bị khóa vĩnh viễn, IP sẽ bị khóa.
Đánh giá(nếu muốn)
 BÌNH LUẬN

ĐÁNH GIÁ


ĐIỂM TRUNG BÌNH

0
0 Đánh giá
Tài liệu rất tốt (0)
Tài liệu tốt (0)
Tài liệu rất hay (0)
Tài liệu hay (0)
Bình thường (0)
Thành viên
Nội dung đánh giá

 
LINK DOWNLOAD

Toan-roi-rac-7-cay.pdf[1.46 M]

File đã kiểm duyệt
     Báo vi phạm bản quyền
Pass giải nén (Nếu có):
thuvienmienphi.com
DOWNLOAD
(Miễn phí)

Tài liệu tương tự