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

Bài giảng về Lý thuyết đồ thị

Chia sẻ: Vu Dinh Duong Duong | Ngày: | Loại File: PPT | Số trang:78

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

Trong toán học và tin học, lý thuyết đồ thị nghiên cứu các tính chất của đồ thị. Một cách không chính thức, đồ thị là một tập các đối tượng được gọi là các đỉnh (hoặc nút) nối với nhau bởi các cạnh (hoặc cung). Cạnh có thể có hướng hoặc vô hướng. Đồ thị thường được vẽ dưới dạng một tập các điểm (các đỉnh nối với nhau bằng các đoạn thẳng (các cạnh). Đồ thị biểu diễn được rất nhiều cấu trúc, nhiều bài toán thực tế có thể được biểu diễn bằng đồ thị. Ví dụ, cấu...

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 về Lý thuyết đồ thị

  1. Đơn đồ thị, đa đồ thị Đồ thị G = (V,E) gọi là đa đồ thị nếu nó có • ít nhất một cặp đỉnh được nối với nhau bởi hai cạnh trở lên và không có khuyên C5 C2 C1 C7 C4 C6 C3 Ở mạng này có nhiều kênh thoại nối giữa hai máy. Mô hình mạng trên là một đa đồ thị.
  2. Giả đồ thị Giả đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh, E là tập các cặp không có thứ tự gồm hai phần tử (không nhất thiết khác nhau) của V gọi là các cạnh. • Các e được gọi là khuyên nếu có dạng e=(u,u) C5 • Ví dụ: C1 C2 C7 C4 C6 C3 Mạng máy tính có đường điện thoại từ một máy tính đến chính nó. Mô hình trên là một giả đồ thị vô hướng.
  3. Đồ thị có hướng G = (V,E) là đồ thị có hướng nếu với mọi cạnh e=(x,y) ∈ E có phân biệt thứ tự các đỉnh x và y, có hướng x đến y, hay (x,y) ≠ (y,x) x y Đối với một cung e = (x, y): x là đỉnh đi (gốc,đầu) • y là đỉnh đến(ngọn, cuối) • Cung e đi từ x và đến y • Lý thuyết đồ thị 3
  4. Đồ thị có hướng Song song Khuyên 1 G = (V, E) 6 4 V = {1, 2, 3, 4, 5, 6} 2 E = { (1,4), (1,6), (2,1), (2,3), 5 3 (3,2), (4,3), (4,5), (4,6), (5,3), (6,1), (6,5),(5,3)} (1, 4) = 1→4 Đỉnh Kề Cạnh Kề Lý thuyết đồ thị 4
  5. Đồ thị có hướng • Cho G=(V,E) là môt đồ thị có hướng và ̣ e=(vi,vj)∈E : – vj được gọi là đinh sau của vi ̉ – vi là môt đinh trước cua vj ̣̉ ̉ • Tập các đỉnh sau và đinh trước của vi lân ̉ ̀ lượt được kí hiêu là Γ (vi) và Γ-1(vi) ̣ Γ (x) = {y ∈ V | (x,y) ∈E} • G=(V,E) = (V, Γ) Lý thuyết đồ thị 5
  6. Đồ thị có hướng Lý thuyết đồ thị 6
  7. Đồ thị vô hướng G = (V,E) là đồ thị vô hướng nếu với • mọi cạnh e=(x,y) ∈ E không phân biệt thứ tự các đỉnh x và y, tức là từ x đến y không kể hướng, hay (x,y) = (y,x) x y Lý thuyết đồ thị 7
  8. Đồ thị vô hướng 3 1 G = (V, E) 2 V = {1, 2, 3, 4, 5} E = {(1,2), (1,3), (1,4), (2,3), (3,5), (4,5)} 4 5 • cạnh song song, khuyên? • Γ (x) = {y ∈ V | (x,y) ∈E} Lý thuyết đồ thị 8
  9. Đồ thị có trọng số • Môt đồ thị G = (V,E) goi là có trong lượng hay trong sô ́ ̣ ̣ ̣ ̣ nêu môi canh(hoăc cung) được gan 1 sô, ́ ̃ ̣ ̣ ́ ́ • nghia là có môt anh xạ ω: E R. ̃ ̣́ • Khi đó ω(e) goi là trong lượng cua e. ̣ ̣ ̉ 40 3 1 20 60 10 2 70 4 50 5 Lý thuyết đồ thị 9
  10. 3.2. Các thuật ngữ cơ bản Kề nhau Cho G = (V,E) và e =(x,y) ∈ E là một • cạnh nối đỉnh x và y. Khi đó ta nói e là cạnh chứa đỉnh x,y hoặc x,y là các đỉnh thuộc cạnh e. Khi đó x,y được gọi là hai đỉnh kề nhau Hai cạnh kề nhau nếu giữa chúng có • đỉnh chung. Ví dụ với u=(x,y) và v =(y,z) thì u,v là hai – cạnh kề nhau Lý thuyết đồ thị 10
  11. Khái niệm X2 và X3 là  hai đỉnh kề  nhau X1 và X2 là  hai đỉnh kề  nhau x2 x3 x1 x4 X1 và X4 là  hai đỉnh kề  x5 nhau Lý thuyết đồ thị 11
  12. Bậc của đỉnh • G=(V,E) có hướng và vi ∈V – nửa bâc trong(nửa bậc vào) = số các cung kết ̣ thúc tại (hay đi vào) vi : deg- (vi)= | Γ -1(vi) | – nửa bâc ngoai (nửa bậc ra) = số các cung khởi ̣ ̀ đầu từ(hay đi ra từ) vi : deg+ (vi)= | Γ (vi) | ̣ ̉ – bâc cua vi : deg(vi) =deg- (vi) + deg+ (vi) 3 1 Nửa Bậc vào của 1 là 3 2 Nửa Bậc ra của 1 là 1 4 5 Lý thuyết đồ thị 12
  13. Bậc của đỉnh • G=(V,E) vô hướng và vi ∈V – bâc cua vi : deg(vi) = số canh kề với vi, trong ̣ ̉ ̣ đó môt khuyên được đêm là 2 ̣ ́ • Đỉnh có bậc = 0 được gọi là đỉnh cô lập • Đỉnh có bậc = 1 được gọi là đỉnh treo và cung (cạnh) tới của nó được gọi là cạnh treo Lý thuyết đồ thị 13
  14. Bậc của đỉnh Đỉnh cô lập Đỉnh treo d(a) = 1, d(b) = 4, d(c) = 4, d(d) = 1, d(e) = 3, d(f) = 3, Cạnh treo d(g) = 0 Lý thuyết đồ thị 14
  15. Bậc của đỉnh vi d-( vi) d+( vi) d( vi) a 1 3 4 b 2 1 3 c 2 1 2 d 2 2 4 e 2 2 4 Lý thuyết đồ thị 15
  16. Bậc của đỉnh K Lý thuyết đồ thị 16
  17. Bậc của đỉnh • Sự liên hệ giữa đinh và canh ̉ ̣ ∑ d − (vi ) = ∑ d + (vi ) – Nêu G có hướng thì m = ́ 2m = ∑ d (vi ) vi ∈V vi ∈V – vi ∈V – Số đinh bâc lẻ là số chăn ̉ ̣ ̃ Lý thuyết đồ thị 17
  18. 3.3.Một số dạng đồ thị đặc biệt Đồ thị đủ (vô hướng) Kn • Là đơn đồ thị câp n và giữa 2 đinh bât kỳ đêu có ́ ̉ ́ ̀ môt canh(mỗi đỉnh của đồ thị được nối đến tất cả ̣ ̣ các đỉnh khác trong đồ thị) n(n − 1) có 2 • Một đồ thị đủ có n đỉnh sẽ cạnh • Môt đồ thị có hướng G goi là đủ nêu đồ thị vô ̣ ̣ ́ hướng tương ứng cua nó là đây đủ ̉ ̀
  19. • Cho G=(V,E) là đồ thị có hướng. Ta bao ̉ – Đồ thị đối xứng : (x,y) ∈ E  (y,x) ∈ E Đồ thị phan xứng : (x,y) ∈ E  (y,x) ∉ E. ̉ – G là đối xứng đủ nêu G đơn và giữa 2 đinh có 2 ́ ̉ cung ngược chiêu nhau ̀ G là phan xứng đủ hay 1 vong thi đâu nêu G đơn ̉ ̀ ́ ́ và giữa 2 đinh có đung 1 cung. Kí hiêu Tn ̉ ́ ̣ – G là giả đôi xứng hay cân băng nêu deg-(vi) = deg+ ́ ̀ ́ (vi), ∀vi ∈ V – G là k-đêu nêu G đơn và ̀ ́ deg-(vi) = deg+(vi)=k, ∀vi ∈ V
  20. • Cho G=(V,E) là đồ thị vô hướng. Ta bao ̉ – G là k-đêu nêu G đơn và deg(vi) =k,  ∀vi ∈ V ̀ ́ – Chu trình (vòng) Cn , với n ≥ 3, là một đồ thị có n đỉnh v1, v2,…,vn và các cạnh {v1, v2}, {v2, v3}, …, {vn − 1, vn} và {vn, v1}
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