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

Lý thuyết đồ thị - Phần 3

Chia sẻ: Hoàng Danh Long | Ngày: | Loại File: PPT | Số trang:9

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

Đồ thị vô hướng (có hướng) G=(V,E) được gọi là đồ thị có trong số nếu mỗi cạnh (cung) ...

Chủ đề:

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

Lưu

Nội dung Text: Lý thuyết đồ thị - Phần 3

  1. 3.3. Đường đi trong đồ thị 3.3.1. Định nghiã đường đi. 3.3.2. Tính liên thông. 3.3.3. Chu trình Euler và đường đi Euler. 3.3.4. Tìm đường đi ngắn nhất. Oct 1, 2010 3.3. Đường đi trong đồ thị 1
  2. 3.3.4. Tìm đường đi ngắn nhất  Đồ thị có trọng số  Định nghĩa 1.  Đồ thị vô hướng (có hướng) G =(V,E) được gọi là đồ thị có trọng số  nếu mỗi cạnh (cung) e∈E được đặt tương ứng với một số thực  w(e). Số thực w(e) được gọi là trọng số của cạnh (cung) e.  Định nghĩa 2.  Ma  trận  trọng  số  của  đơn  đồ  thị  G  =(V,E)  là  ma  trận  W=[wi,k]  trong đó  wi,k là trọng số của cạnh (cung) nối đỉnh thứ i với đỉnh thứ k  (nếu có);  wi,k=∞  nếu không có cạnh (cung) nối đỉnh thứ i với đỉnh thứ  k. Oct 1, 2010 3.3. Đường đi trong đồ thị 2
  3. 3.3.4. Tìm đường đi ngắn nhất  Theo định nghiã trên:   các phần tử của ma trận trọng só có thể là các số âm.   Một đơn đồ thị bất kỳ cũng có thể xem là đồ thị có trọng số nếu  mỗi cạnh (cung) đều gắn trọng số là 1 (như định nghĩa đường đi  độ  dài  1  trong  mục  trước)  và  khi  đó  ma  trận  trọng  số  chính  là  ma trận 0­1.  Ví dụ:   xét  một  mạng  hàng  không,  khi  đó  mạng  này  có  thể  coi  là  các  đồ thị có trọng số với các kiểu trọng số sau đây:  Độ dài cung đường bay  Giá cước vận chuyển cho một đơn vị vận chuyển  thời gian thực hiện chuyến bay giữa hai sân bay Oct 1, 2010 3.3. Đường đi trong đồ thị 3
  4. 3.3.4. Tìm đường đi ngắn nhất Ví dụ: Ma trận trọng số của đồ thị trên là 0 15 20 0 20 14  15 0 11 18 0 24    20 11 0 13 22 0 W=  0 18 13 0 16 21  20 0 22 16 0 12    14  24 0 21 12 0 Oct 1, 2010 3.3. Đường đi trong đồ thị 4
  5. 3.3.4. Tìm đường đi ngắn nhất  Bài toán được đặt ra là:   tìm đường đi ngắn nhất trong đồ thị có trọng số G  =(V,E) từ  đỉnh x đến đỉnh y cho trước.  Ý tưởng giải thuật là:   ta  sẽ  lần  lượt  duyệt  và  xác  định  độ  dài  của  đường  đi  ngắn  nhất từ đỉnh x đến các đỉnh lân cận, cho đến khi đỉnh đích y  được duyệt.   Ở  mỗi  bước  duyệt,  mỗi  đỉnh  v  sẽ  được  gắn  nhãn,  là  cặp  (l(v);t(v)) trong đó:   l(v)  là  độ  dài  của  đường  đi  tìm  được  từ  đỉnh  đầu  x  đến  đỉnh  v  cho đến thời điểm đang xét;   t(v) là đỉnh trước đỉnh v trong đường đi đó. Oct 1, 2010 3.3. Đường đi trong đồ thị 5
  6. 3.3.4. Tìm đường đi ngắn nhất  Từ đó ta có thuật toán sau đây Dijkstra (Hà lan­1930­2002):  Bước khởi đầu: Với mọi đỉnh v ∈ V,  l(v):= ∞; t(v):=‘’; L(x):=0; {độ dài đường đi từ x đến x bằng 0} S:=∅; {S là tập đỉnh đã được duyệt}  Bước lặp: Khi y∉S thực hiện: Tìm u trong tập các đỉnh chưa được duyệt (u∈V\S) sao cho l(u) bé nhất; S:=S∪{u}; Với mọi đỉnh v thuộc tập các đỉnh chưa được duyệt và có cạnh (cung) từ u đến  v, thực hiện  Nếu l(u) + wuv 
  7. 3.3.4. Tìm đường đi ngắn nhất  Ví dụ: Bước  A1 A2 A3 A4 A5 A6 khởi đầu Tìm đường đi ngắn           0      ∞      ∞      ∞      ∞      ∞ nhất từ A1 đến A4 Bước 1 0 15,A1 20,A1 ∞ 20,A1 14, A1 A1 Bước 2 0 15,A1 20,A1 35,A6 20,A1 14, A1 A6 Bước 3 0 15,A1 20,A1 33,A2 20,A1 14, A1 A2 Bước 4 0 15,A1 20,A1 33,A2 20,A1 14, A1 A3 Bước 5 0 15,A1 20,A1 33,A2 20,A1 14, A1 A5 Bước 6 0 15,A1 20,A1 33,A2 20,A1 14, A1 A4 Oct 1, 2010 3.3. Đường đi trong đồ thị 7
  8. 3.3.4. Tìm đường đi ngắn nhất  Giới thiệu chương trình 2 6 4 8 1 5 6 1 3 7 2 9 3 4 5 Oct 1, 2010 3.3. Đường đi trong đồ thị 8
  9. 3.3.4. Tìm đường đi ngắn nhất  Edsger Wybe Dijkstra   (sinh ngày 11  tháng 5, 1930 tại Rotterdam  – mất ngày 6 tháng 8, 2002 tại Nuenen).   Là nhà khoa học máy tính Hà Lan.   Ông được nhận giải thưởng Turing cho các  đóng  góp  có  tính  chất  nền  tảng  trong  lĩnh  vực ngôn ngữ lập trình.  Không lâu trước khi chết, ông đã được nhận  giải  Bài  báo  ảnh  hưởng  lớn  trong  lĩnh  vực  tính  toán  phân  tán  của  ACM  dành  cho  bài  báo  đã  khởi  đầu  cho  ngành  con  Self­ stabilization.   Sau  khi  ông  qua  đời,  giải  thưởng  thường  niên này đã được đổi tên thành giải thưởng  Edsger Dijkstra  ACM Edsger W. Dijkstra.  (ảnh của Brian Randell)  Oct 1, 2010 3.3. Đường đi trong đồ thị 9
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
2=>2