zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán rời rạc: Đồ thị - ThS. Hoàng Thị Thanh Hà

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

Báo xấu

20
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc - Đồ thị được biên soạn gồm các nội dung chính sau: các định nghĩa và ví dụ; biểu diễn đồ thị bằng ma trận; bậc của đỉnh; đẳng cấu; đồ thị con; đường đi, chu trình, đồ thị liên thông; những đơn đồ thị đặc biệ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 Toán rời rạc: Đồ thị - ThS. Hoàng Thị Thanh Hà

Toán rời rạc (3): ĐỒ THỊ Ths. Hoàng Thị Thanh Hà Khoa Thống kê –Tin học Trường Đại học Kinh tế Đại học Đà Nẵng 27 September 2012 1 Nội dung 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ 2. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN 3. BẬC CỦA ĐỈNH 4. ĐẲNG CẤU 5. ĐỒ THỊ CON 6. ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG 7. NHỮNG ĐƠN ĐỒ THỊ ĐẶC BIỆT 27 September 2012 2 1
1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh (vô hướng hoặc có hướng) nối các đỉnh đó. Người ta phân loại đồ thị tùy theo đặc tính và số các cạnh nối các cặp đỉnh của đồ thị. Lý thuyết đồ thị giải quyết các bài toán sau: – Tìm đường đi ngắn nhất – Tìm cây bao trùm tối thiểu – Chu trình đường đi Euler, Hamilton – … 27 September 2012 3 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ ĐN1: Đồ thị vô hướng G=(V,E) là một bộ gồm 2 tập hợp: i. Tập V tập khác rỗng chứa các đỉnh ii. Tập E chứa các cạnh (đó là các cặp không có thứ tự của các đỉnh). Cạnh e nối 2 đỉnh v, w kí hiệu là e=(v,w) – Mỗi đỉnh được biểu diễn bằng 1 điểm, mỗi cạnh là một đoạn thẳng hoặc đường cong nối giữa 2 điểm đó – Nếu e=(v,w) thì đỉnh v và w gọi là kề nhau hay v, w liên thuộc cạnh e hay e liên thuộc cạnh v và w – Hai cạnh song song khi chúng liên thuộc cùng với 1 cặp đỉnh – Cạnh có 2 đầu mút trùng nhau gọi là khuyên 27 September 2012 4 2
1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ – Nếu e=(v,w) thì đỉnh v và w gọi là kề nhau hay v, w liên thuộc cạnh e hay e liên thuộc cạnh v và w – Hai cạnh song song khi chúng liên thuộc cùng với 1 cặp đỉnh – Cạnh có 2 đầu mút trùng nhau gọi là khuyên 27 September 2012 5 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ ĐN2: Đồ thị vô hướng không có cạnh song song, không có khuyên gọi là Đơn đồ thị vô hướng 27 September 2012 6 3
1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ ĐN3: Đồ thị vô hướng có cạnh song song nhưng không có khuyên gọi là Đa đồ thị vô hướng – Đơn đồ thị là đa đồ thị 27 September 2012 7 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ ĐN4: Đồ thị vô hướng có cạnh song song và có khuyên gọi là Giả đồ thị vô hướng 27 September 2012 8 4
1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ Đồ thị vô hướng: Giả đồ thị Đa đồ thị Đơn đồ thị 27 September 2012 9 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ ĐN5: Đa đồ thị có hướng G=(V,E) là một bộ gồm 2 tập hợp: i. Tập V tập khác rỗng chứa các đỉnh ii. Tập E chứa các cung, đó là các cặp có thứ tự hai đỉnh. Cung e nối 2 đỉnh v, w kí hiệu là e=(v,w), ta nói cung e đi từ v đến w – Mỗi đỉnh được biểu diễn bằng 1 điểm, mỗi cung là một đoạn thẳng hoặc đường cong có hướng nối giữa 2 điểm 27 September 2012 10 5
1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ – Nếu e=(v,w) thì đỉnh v và w gọi là kề nhau hay v, w liên thuộc cung e hay e liên thuộc cung v và w, v là đỉnh gốc (đầu), w là đỉnh ngọn (cuối) – Hai cung song song khi chúng có cùng gốc và ngọn – Cung có gốc và ngọn trùng nhau gọi là khuyên ĐN6: Đồ thị có hướng không chứa các cạnh song song gọi là đồ thị có hướng 27 September 2012 11 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ Đồ thị Cạnh Cạnh song song Khuyên Đơn đồ thị vô Vô hướng Không Không hướng Đa đồ thị vô hướng Vô hướng Có Không Giả đồ thị vô Vô hướng Có Có hướng Đồ thị có hướng Có hướng Không Có Đa đồ thị có hướng Có hướng có có 27 September 2012 12 6
2. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN ĐN1: Ma trận liền kề (ma trận kề): – Cho đồ thị G = (V,E) với V = {1,2,…n}, ma trận kề của G là ma trận A(n*n) với aij= số cạnh nối từ đỉnh i đến đỉnh j – Như vậy, ma trận liền kề của một đồ thị vô hướng là ma trận vuông đối xứng trong khi ma trận liền kề của một đồ thị có hướng không có tính đối xứng. 27 September 2012 13 2. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN Ví dụ: Ma trận liền kề của đồ thị v1 v2 0 3 0 2   3 0 1 1 0 1 1 2   2 1 2 0 v4 v3   27 September 2012 14 7
2. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN Ma trận liền kề với thứ tự các đỉnh v1, v2, v3, v4, v5 v1 1 1 0 1 1   0 1 2 1 0 v5 v2 1 0 0 1 0   0 0 2 0 1 1 1 0 1 0 v4 v3   27 September 2012 15 2. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN ĐN2: Ma trận liên thuộc: Cho đồ thị vô hướng G=(V,E), v1, v2, ..., vn là các đỉnh và e1, e2, ..., em là các cạnh của G. Ma trận liên thuộc của G theo thứ tự trên của V và E là ma trận M= ( mij )1≤i ≤n ∈ M ( n × m, Z ) 1≤ j ≤m mij = 1 nếu cạnh ej nối với đỉnh vi và bằng 0 nếu cạnh ej không nối với đỉnh vi. 27 September 2012 16 8
2. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN Ví dụ ma trận liên thuộc với thứ tự các đỉnh v1, v2, v3, v4, v5 và các cạnh e1, e2, e3, e4, e5, e6 là: 1 1 0 0 0 0 v3   e6 v1 v2 e3 0 0 1 1 0 1 e4  1 e1 e5  0 0 0 0 1  e2 1 0 1 0 0 0 v4 v5 0 1 0 1 1 0   27 September 2012 17 3. BẬC CỦA ĐỈNH ĐN: cho đồ thị vô hướng G = (V,E), bậc của đỉnh v, kí hiệu là deg(v) là số cạnh kề với v. Một khuyên tại một đỉnh được đếm 2 lần cho bậc của đỉnh đó. – Đỉnh v gọi là đỉnh treo nếu deg(v)=1 và gọi là đỉnh cô lập nếu deg(v)=0 27 September 2012 18 9
3. BẬC CỦA ĐỈNH v1 v2 v3 v4 v5 v6 v7 Ta có deg(v1)=7, deg(v2)=5, deg(v3)=3, deg(v4)=0, deg(v5)=4, deg(v6)=1, deg(v7)=2. Đỉnh v4 là đỉnh cô lập và đỉnh v6 là đỉnh treo. 27 September 2012 19 3. BẬC CỦA ĐỈNH Mệnh đề: Cho đồ thị G = (V, E). Khi đó: 2|E|= ∑ deg(v) v∈V Chứng minh: Rõ ràng mỗi cạnh e = (u,v) được tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh. 27 September 2012 20 10
3. BẬC CỦA ĐỈNH Hệ quả: Số đỉnh bậc lẻ của một đồ thị là một số chẵn. Chứng minh: Gọi V1 và V2 tương ứng là tập các đỉnh bậc chẵn và tập các đỉnh bậc lẻ của đồ thị G = (V, E). Khi đó: 2|E| = ∑ deg(v) + ∑ deg(v) v∈V1 v∈V2 Vế trái là một số chẵn và tổng thứ nhất cũng là một số chẵn nên tổng thứ hai là một số chẵn. Vì deg(v) là lẻ với mọi v ∈ V2 nên |V2| là một số chẵn. 27 September 2012 21 3. BẬC CỦA ĐỈNH Mệnh đề: Trong một đơn đồ thị, luôn tồn tại hai đỉnh có cùng bậc. Chứng minh: Xét đơn đồ thị G=(V,E) có |V|=n. Khi đó phát biểu trên được đưa về bài toán: trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau (Định lý Dirichlet) 27 September 2012 22 11
3. BẬC CỦA ĐỈNH ĐN: cho đồ thị có hướng G = (V,E), v ∈ V, – bậc vào của v, kí hiệu là degt(v) là số cung có đỉnh cuối là v – bậc ra của v, kí hiệu là dego(v) là số cung có đỉnh đầu là v – bậc của v deg(v) = degt(v) + dego(v) – Đỉnh có bậc vào và bậc ra cùng bằng 0 gọi là đỉnh cô lập. Đỉnh có bậc vào bằng 1 và bậc ra bằng 0 gọi là đỉnh treo, cung có đỉnh cuối là đỉnh treo gọi là cung treo 27 September 2012 23 3. BẬC CỦA ĐỈNH v1 v2 v3 v4 v5 v6 degt(v1) = 2, dego(v1) = 3, degt(v2) = 5, dego(v2) = 1, degt(v3) = 2, dego(v3) = 4, degt(v4) = 1, deg0(v4) = 3, degt(v5) = 1, dego(v5) = 0, degt(v6) = 0, dego(v6) = 0. 27 September 2012 24 12
3. BẬC CỦA ĐỈNH Mệnh đề: Cho G =(V, E) là một đồ thị có hướng. Khi đó: ∑ deg t (v) = ∑ deg o (v) = |E| v∈V v∈V Chứng minh: Kết quả có ngay là vì mỗi cung được tính một lần cho đỉnh đầu và một lần cho đỉnh cuối. 27 September 2012 25 4. ĐẲNG CẤU ĐN1: Các đơn đồ thị G1=(V1,E1) và G2=(V2,E2) được gọi là đẳng cấu, ký hiệu G1 ≅ G2 – nếu tồn tại một song ánh f: V1 → V2 – sao cho uv là cạnh trong G1 ⇔ f(u)f(v) là cạnh trong G2 với mọi u và v trong V1 – ánh xạ f như thế gọi là một phép đẳng cấu. 27 September 2012 26 13
4. ĐẲNG CẤU Ví dụ: Hai đơn đồ thị G1 và G2 sau là đẳng cấu qua phép đẳng cấu f: a→x, b→u, c→z, d→v, e→y: a u b z v c e d y x G1 G2 27 September 2012 27 4. ĐẲNG CẤU Nhận xét: Nếu G1, G2 là các đơn đồ thị đẳng cấu qua ánh xạ f thì chúng có: – Cùng số đỉnh – Cùng số cạnh – Cùng số đỉnh với bậc cho sẵn – Deg(v) = deg(f(v)) 27 September 2012 28 14
5. ĐỒ THỊ CON ĐN1: Cho hai đồ thị G1=(V1,E1) và G2=(V2,E2). Ta nói G2 là đồ thị con của G1 nếu: – V2 ⊆ V1 và E2 ⊆ E1 – Trường hợp V1=V2 thì G2 gọi là đồ thị con khung (bao trùm) của G1. 27 September 2012 29 5. ĐỒ THỊ CON G1, G2, G3 và G4 là các đồ thị con của G, G5 thì không a d a a d e e b c b c b c G G1 G2 a d a d a d e b c b c b c G3 G4 G5 G2 và G4 là đồ thị con bao trùm của G 27 September 2012 30 15
6. ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG ĐN1: Cho đồ thị (giả đồ thị vô hướng hoặc đa đồ thị có hướng) G=(V,E), u,v ∈ V: – a) Đường đi độ dài n từ u đến v, (n nguyên dương) là một dãy các cạnh (hoặc cung) e1, e2, ..., en của G sao cho e1=(x0,x1),e2=(x1,x2), ...,en=(xn-1,xn), với x0=u và xn=v. – Khi đồ thị không có cạnh (hoặc cung) bội, ta ký hiệu đường đi này bằng dãy các đỉnh x0, x1, ..., xn. 27 September 2012 31 6. ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG – b) Đường đi gọi là chu trình nếu u trùng v – c) Đường đi hoặc chu trình gọi là đường đi (chu trình) đơn nếu nó không có cạnh nào xuất hiện quá một lần – d) Một đường đi hoặc chu trình không có đỉnh nào xuất hiện quá một lần (trừ đỉnh đầu và đỉnh cuối của chu trình là trùng nhau) được gọi là đường đi hoặc chu trình sơ cấp. Rõ ràng rằng một đường đi (t.ư. chu trình) sơ cấp là đường đi (t.ư. chu trình) đơn. 27 September 2012 32 16
6. ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG Ví dụ: x y z w v u •x, y, z, w, v, y là đường đi đơn (ko sơ cấp) độ dài 5 • x, w, v, z, y ko là đường đi vì (v, z) không là cạnh • y, z, w, x, v, u, y là chu trình sơ cấp độ dài 6. 27 September 2012 33 6. ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG ĐN3: Một đồ thị (vô hướng) G= (V,E) được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. Đỉnh u ~ v (u tương đương v) hay có đường đi từ u đến v. Nếu u ~ v ta nói rằng u liên thông với v Một lớp tương đương như vậy gọi là một thành phần liên thông của đồ thị G Như vậy, một đồ thị là liên thông khi và chỉ khi nó chỉ có một thành phần liên thông. 27 September 2012 34 17
6. ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG Ví dụ x y z a b g k u t v w d c h i l G G’ Đồ thị G là liên thông, nhưng đồ thị G’ không liên thông và có 3 thành phần liên thông. 27 September 2012 35 6. ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG ĐN4: Một đỉnh v trong đồ thị G mà khi xoá đi nó và tất cả các cạnh liên thuộc với nó ta nhận được đồ thị con mới có nhiều thành phần liên thông hơn đồ thị G được gọi là đỉnh cắt hay điểm khớp. Một cạnh mà khi ta bỏ nó đi sẽ tạo ra một đồ thị có nhiều thành phần liên thông hơn so với đồ thị xuất phát được gọi là cạnh cắt hay là cầu. Như vậy: việc xoá đỉnh cắt (hoặc cạnh cầu) khỏi một đồ thị liên thông sẽ tạo ra một đồ thị con không liên thông. 27 September 2012 36 18
6. ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG x y z u v w s t Các đỉnh cắt là v, w, s Cầu: (x,v), (w,s). 27 September 2012 37 6. ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG Mệnh đề: Giữa mọi cặp đỉnh phân biệt của một đồ thị liên thông luôn có đường đi sơ cấp. CM: Giả sử u, v là 2 đỉnh phân biệt đồ thị liên thông G có ít nhất một đường đi giữa u và v. Gọi x0, x1, ..., xn, với x0=u và xn=v, là dãy các đỉnh của đường đi có độ dài ngắn nhất. Đây là đường đi sơ cấp cần tìm. Thật vậy, giả sử ko là đường đi đơn, khi đó xi=xj với 0 ≤ i < j. Có nghĩa là giữa đỉnh u và v có đường đi ngắn hơn qua các đỉnh x0, x1, ..., xi-1, xj, ..., xn nhận được bằng cách xoá đi các cạnh tương ứng với dãy các đỉnh xi, ..., xj-1 27 September 2012 38 19
6. ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG Mệnh đề: Cho đơn đồ thị G= (V,E), |V|=n (n ≥ 2), ∀u,v ∈ V, deg(u)+deg(v)≥n thì G liên thông. CM: Giả sử G ko liên thông, tức ∃ 2 đỉnh u, v sao cho u và v ko liên thông. Khi đó trong G tồn tại hai thành phần liên thông G1 có n1 đỉnh và chứa u, G2 chứa v và có n2 đỉnh. Vì G1, G2 là hai trong số các thành phần liên thông của G nên n1+n2 ≤ n. ta có: deg(u)+deg(v) ≤ (n1 −1)+(n2 − 1) = n1+n2−2 ≤ n−2

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.