intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Lý thuyết đồ thị: Chương 6 - Tôn Quang Toại

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST
Báo xấu
8
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết đồ thị: Chương 6 Cây, cung cấp cho người đọc những kiến thức như: Khái niệm Cây; Các tính chất cơ bản của Cây; Cây khung của đồ thị; Cây khung nhỏ nhất. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 6 - Tôn Quang Toại

  1. CHƯƠNG 6 CÂY Tôn Quang Toại Khoa CNTT, Đại học Ngoại ngữ ‐ Tin học TP.HCM
  2. Nội dung Khái niệm Cây Các tính chất cơ bản của Cây Cây khung của đồ thị Cây khung nhỏ nhất
  3. Khái niệm cây Định nghĩa Cây (Tree): Cây là  Đồ̀ thị vô hướng,  liên thông và  không có chu trình B E F B E F A A C D C D G1 G2
  4. Khái niệm cây Định nghĩa Rừng (Forest): Rừng là đồ thị không có chu trình B G I L J A C F K D E H • Nhận xét: Rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây.
  5. Các tính chất cơ bản của Cây Định lý: Cho đồ̀ thị vô hướng G=(V, E) có n đỉnh. Các mệnh đề̀  sau tương đương: (1) G là 1 cây (2) G không chứa chu trình và có n-1 cạnh (3) G liên thông và có n-1 cạnh (4) G liên thông và mỗi cạnh của nó điều là cầu (5) Giữa hai đỉnh bất kỳ của G được nối với nhau bởi đúng một đường đi duy nhất (6) G không chứa chu trình nhưng khi thêm vào một cạnh ta thu được đúng một chu trình
  6. Các tính chất cơ bản của Cây Sơ đồ chứng minh: Chứng minh: :
  7. Các tính chất cơ bản của Cây Chứng minh
  8. Các tính chất cơ bản của Cây Chứng minh
  9. Các tính chất cơ bản của Cây Chứng minh
  10. Các tính chất cơ bản của Cây Chứng minh
  11. Các tính chất cơ bản của Cây Chứng minh
  12. Cây khung của đồ thị Định nghĩa Cây khung (spanning tree) của đồ̀  thị: Một cây T gọi là cây khung (cây bao trùm)  của đồ thị G=(V, E) nếu  C D T = (V,E’) F E’  E  A C D B E C D A F A F B E B E
  13. Cây khung của đồ thị Định lý Cayley Số cây khung của đồ thị  là a n=4, số cây khung là: 4 16 d f b Ví dụ: abc, bcd, cda, dab c e abf, acf, bdf, ... A n=5, Số cây khung là: 5 125 B C D E
  14. Cây khung của đồ thị Bài toán: Cho G là đồ thị vô hướng, liên thông, hãy tìm 1 cây khung của đồ thị Lời giải Thuật toán tìm kiếm theo chiều sâu (DFS) Thuật toán tìm kiếm theo chiều rộng (BFS)
  15. Cây khung của đồ thị Tìm cây khung theo DFS void SpanningTree_DFS(int u) { 1. Đánh dấu u đã viếng thăm 2. Xét mọi đỉnh v chưa được viếng thăm và kề u, với từng đỉnh v đó { T = T  {(u, v)} DFS(v); } }
  16. Cây khung của đồ thị Tìm cây khung theo BFS void SpanningTree_BFS() { - Đánh dấu mọi đỉnh chưa viếng thăm - Đánh dấu u=0 đã viếng thăm - q.Enqueue(u) while (q!=) { - u = q.Dequeue(); - Tìm tất cả đỉnh v chưa viếng thăm và kề u { + T = T  {(u, v)} + Thăm đỉnh v + q.Enqueue(v) } } }
  17. Cây khung nhỏ nhất Phát biểu bài toán Cây khung nhỏ nhất  (Minimum Spanning Tree – MST):  Cho G=(V, E) là đồ thị vô hướng, liên thông và có trọng số. Hãy tìm 1 cây khung T=(V, E’) của đồ thị G sao cho tổng trọng số các cạnh của T là nhỏ nhất. Hay nói cách khác: Tìm E’ sao cho độ dài của cây T, , đạt giá trị nhỏ nhất 𝑤 𝑇 𝑤 𝑢, 𝑣 , ∈
  18. Cây khung nhỏ nhất Thuật toán tìm cây khung nhỏ nhất Có nhiều thuật toán xây dựng cây khung nhỏ nhất: • Thuật toán Boruvka • Thuật toán Kruskal • Thuật toán Jarnik – Prim • Phương pháp Dijkstra • Thuật toán Cheriton – Tarjan • Thuật toán Chazelle • … 
  19. Cây khung nhỏ nhất Thuật toán tìm cây khung nhỏ nhất Thuật toán Kruskal:  Ý tưởng của thuật toán Kruskal:  • Ban đầu cây T=(V, Ø) (Cây rỗng) • Lần lược chọn đủ (n‐1) cạnh có trọng số từ nhỏ đến lớn  vào cây T sao cho không được tạo thành chu trình Thuật toán Jarnik – Prim: Ý tưởng của thuật toán Jarnik – Prim:  • Ban đầu cây T chỉ có 1 đỉnh.  • Lần lược chọn thêm (n‐1) đỉnh vào cây T sao cho đỉnh  được chọn vào cây có cạnh đến một trong các đỉnh của  cây là là nhỏ nhất
  20. Cây khung nhỏ nhất Thuật toán Kruskal Input: G=(V, E) Output: Danh sách cạnh cay[] Bước 1 (Sắp xếp) Sắp xếp các cạnh có trọng số tang dần Bước 2 (Chọn n‐1 cạnh) Xét các cạnh theo thứ tự đã sắp xếp (cạnh nhỏ chọn trước). Chọn (n-1) cạnh theo quy tắc: • Cạnh được chọn và cùng các cạnh đã chọn trước đó không tạo thành chu trình
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
3=>0