Bài Giảng Toán Rời Rạc Và Lý Thuyết đồ Thị - Chương 4 - Tài Liệu - Ebook
Có thể bạn quan tâm
- Đăng ký
- Đăng nhập
- Liên hệ
Thư viện tài liệu, ebook tổng hợp lớn nhất Việt Nam
Website chia sẻ tài liệu, ebook tham khảo cho các bạn học sinh, sinh viên
- Trang Chủ
- Tài Liệu
- Upload
Các tính chất của ma trận kề: 1) Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là a[i,j]=a[j,i], i,j=1,2,. . .,n. 2) Tổng các phần từ trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j). Ma trận kề của đồ thị có hướng được định nghĩa một cách hoàn toàn tương tự. MA TRẬN TRỌNG SỐ Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, mỗi cạnh e=(u,v) của đồ thị được gán với một con số a(e) [còn viết là a(u,v)] gọi là trọng số của cạnh e. Đồ thị trong trường hợp như vậy được gọi là đồ thị có trọng số. Trong trường hợp đồ thị có trọng số, thay vì mà trận kề, để biểu diễn đồ thị ta sử dụng ma trận trọng số.
50 trang | Chia sẻ: hoant3298 | Lượt xem: 5148 | Lượt tải: 2 Bạn đang xem trước 20 trang tài liệu Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 4: Các khái niệm về Đồ Thị - Võ Tấn Dũng, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trênGV: Võ Tấn Dũng TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP.HCM MÔN TOÁN RỜI RẠC ĐƠN ĐỒ THỊ VÔ HƯỚNG Đơn đồ thị vô hướng G = (V,E) là một bộ gồm hai tập hợp V và E. V là tập các đỉnh (vertices). E là tập các cạnh (edges), mỗi cạnh là một cặp không có thứ tự gồm 2 đỉnh khác nhau của tập V. 3 Ví dụ: Đơn đồ thị G1 = (V1, E1), trong đó V1={a, b, c, d, e, f, g, h}, E1={(a,b), (b,c), (c,d), (a,d), (d,e), (a,e), (d,b), (f,g)}. Đồ thị G1 a b e d c g f h ĐA ĐỒ THỊ VÔ HƯỚNG Đa đồ thị vô hướng G= (V, E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh song song nếu chúng cùng tương ứng với một cặp đỉnh. Ví dụ: Đa đồ thị G2 = (V2, E2), trong đó V2={a, b, c, d, e, f, g, h}, E2={(a,b), (b,c), (b,c), (c,d), (a,d), (d,e), (a,e), (a,e), (a, e), (d,b), (f,g)}. Đồ thị G2 d Cạnh song song e a b c f g h Cạnh song song, cạnh vòng Cạnh song song (cạnh bội) Hai hay nhiều cạnh phân biệt cùng tương ứng với một cặp đỉnh Cạnh vòng (cạnh loop): Một cạnh tương ứng với hai đỉnh trùng nhau. Đơn đồ thị Đồ thị không có vòng và cạnh song song Đa đồ thị Các đồ thị không phải là đơn đồ thị x y z A B C D ĐỒ THỊ CÓ HƯỚNG Đơn đồ thị có hướng G = (V, E) bao gồm V là tập các đỉnh và E là tập các cặp có thứ tự gồm hai đỉnh khác nhau của V gọi là các cạnh (cung). G = (V, E) Tập đỉnh V Tập cạnh (cung) E = { (a, b) | a,b V } e = (a, b) E Ký hiệu: e = e có hướng từ a đến b a: đỉnh đầu; b: đỉnh cuối e là cạnh vòng ab ab CÁC THUẬT NGỮ CƠ BẢN Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G. Nếu e = (u, v) là cạnh của đồ thị ta nói cạnh này là cạnh liên thuộc với hai đỉnh u và v (hoặc cũng nói là nối đỉnh u và đỉnh v) Đồng thời các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u, v). BẬC CỦA ĐỈNH Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ ký hiệu là deg(v). deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(f) = 3, deg(d) = 1, deg(e) = 3, deg(g) = 0 Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 được gọi là đỉnh treo. Trong ví dụ trên đỉnh g là đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh Đỉnh của đồ thị G có bậc là n nếu nó kề với n đỉnh khác. Ký hiệu: deg(v) hay d(v) Mỗi vòng được kể là 2 cạnh tới một đỉnh Đỉnh cô lập deg(v)=0 Đỉnh treo deg(v)=1 Cạnh treo có đầu mút là một đỉnh treo Đồ thị rỗng: deg(v)=0 v a b c d efg Tính chất bậc của đỉnh Định lý 1. Giả sử G = (V, E) là đồ thị vô hướng với |E| cạnh. Khi đó tổng bậc của tất cả các đỉnh bằng hai lần số cạnh. Hệ quả. Trong đồ thị vô hướng thì: Tổng bậc là một số chẵn. Số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn. 32 Ví dụ. Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 14 đỉnh và 25 cạnh đều có bậc là 3 hoặc 5. Hỏi G có bao nhiêu đỉnh bậc 3? Giải. Giả sử G có x đỉnh bậc 3. Khi đó có 14-x đỉnh bậc 5. Do | E | = 25, nên tổng tất cả các bậc là 50. Từ đó, 3x + 5(14-x) = 50 Suy ra x = 10. Cạnh vào, cạnh ra Nếu e = (u, v) là cung của đồ thị có hướng G thì ta nói hai đỉnh u và v là kề nhau. Và nói cung (u, v) nối đỉnh u với đỉnh v Hoặc cũng có thể nói là cung này là đi ra khỏi đỉnh u và vào đỉnh v. Đỉnh u(hoặc v) sẽ được gọi là đỉnh đầu (cuối) của cung (u,v). Bậc vào, bậc ra Ta gọi bậc ra của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó và ký hiệu là deg+(v) Ta gọi bậc vào của đỉnh v trong đồ thị có hướng là số cung của đồ thị vào nó và ký hiệu là deg-(v) deg-(a)=1, deg-(b)=2, deg-(c)=2, deg-(d)=2, deg-(e) = 2. deg+(a)=3, deg+(b)=1, deg+(c)=1, deg+(d)=2, deg+(e)=2. Định lý: Giả sử G = (V, E) là đồ thị có hướng. Khi đó: Ví dụ f a b c ed deg-(d) = 2 deg+(d)= 1 deg-(f) = 0 deg+(f)= 0 b kề tới c và c kề từ b deg-(a) = 0 deg+(a)= 2 a- đỉnh nguồn deg-(e) = 2 deg+(e)= 0 e – đỉnh đích (target) Ví dụ: hai đồ thị sau đẳng cấu 1 DN, 2 CT, 3 BD, 4 AG 17 ĐỒ THỊ ĐẲNG CẤU 18 Điều kiện cần nhưng không phải là đủ để G1=(V1, E1) là đẳng cấu với G2=(V2, E2): Ta phải có |V1|=|V2|, và |E1|=|E2|. Số lượng đỉnh bậc k ở hai đồ thị là như nhau. ĐỒ THỊ ĐẲNG CẤU •Tính chất trên chỉ có điều kiện cần •Ví dụ: hai đồ thị sau không đẳng cấu ? 19 ĐỒ THỊ ĐẲNG CẤU Xét sự đẳng cấu của các cặp đồ thị sau. Chỉ ra song ánh nếu chúng đẳng cấu 20 BÀI TẬP 21 Sự đẳng cấu giữa các đồ thị Chứng minh 2 đồ thị đẳng cấu Nếu là đẳng cấu thì hãy gán tên cho đồ thị thứ hai để thấy rõ sự đẳng cấu, trái lại hãy nêu rõ sự khác biệt. a b cd e f b d a e fc BÀI TẬP Có đẳng cấu không? Nếu là đẳng cấu thì hãy gán tên cho đồ thị thứ hai để thấy rõ sự đẳng cấu, trái lại hãy nêu rõ sự khác biệt. a b c d e • Cùng số lượng đỉnh • Cùng số lượng cạnh • Khác số lượng đỉnh bậc 2 (1 3) CHU TRÌNH (vô hướng) Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G = (V, E) là dãy x0, x1,, xn-1, xn trong đó Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0, x1), (x1, x2), , (xn-1, xn) Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại. CHU TRÌNH (có hướng) Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị có hướng G = (V, E) là dãy x0, x1,, xn-1, xn trong đó Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0, x1), (x1, x2), , (xn-1, xn) Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại. 26 Ví dụ: đường đi Ví dụ: chu trình Ví dụ: 1, 2, 5, 3, 4 hoặc 1, a, 2, c, 5, d, 3, e, 4 • Là đường đi đơn Ví dụ: 5, 2, 3, 4 hoặc 5, c, 2, b, 3, e, 4. Không có đỉnh lặp nên là đường đi đơn 2 3 4 a b c 1 5 d e 2 3 4 a b c 1 5 d e Đường đi (Path) 28 P1 Ví dụ (tiếp) P1=(1,b,2,h,3) là đường đi đơn P2=(4,c,5,e,2,g,6,f,5,d,1) là đường đi nhưng không là đường đi đơn 24 1 5 3 6 a c b e d f g hP2 P1 Ví dụ (tiếp) P1=(1, b, 2, h, 3) là đường đi đơn P2=(4,c,5,e,2,g,6,f,5,d,1) là đường đi nhưng không là đường đi đơn 24 1 5 3 6 a c b e d f g hP2 Chu trình 1, 2, 3, 1. (hay 1, a, 2, b, 3, e) • Chu trình đơn Chu trình: (1, 2, 3, 4, 1) hay 1, a, 2, b, 3, c, 4, d, 1 • Chu trình đơn 2 3 4 a b cd 1 e 2 3 4 a b cd 1 e Chu trình (Cycle) Ví dụ: Chu trình trên đồ thị vô hướng C1=(V,b,X,g,Y,f,W,c,U,a,V) là chu trình đơn C2=(U,c,W,e,X,g,Y,f,W,d,V,a,U) là chu trình nhưng không là chu trình đơn C1 XU V W Z Y a c b e d f g h C2 C1=(V,b,X,g,Y,f,W,c,U,a,V) là chu trình đơn C2=(U,c,W,e,X,g,Y,f,W,d,V,a,U) là chu trình nhưng không là chu trình đơn C1 XU V W Z Y a c b e d f g hC2 Ví dụ: Chu trình trên đồ thị vô hướng LIÊN THÔNG Đồ thị G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. Ví dụ. Đồ thị gồm các đỉnh a,b,c,d,e,f,g là liên thông. Còn đồ thị H tạo ra từ H1,H2,H3 là không liên thông. 34 Tính liên thông Tính liên thông trong đồ thị vô hướng Đỉnh cắt và cầu u là một đỉnh cắt số thành phần liên thông tăng lên nếu bỏ u và các cạnh liên thuộc với nó e là một cầu số thành phần liên thông tăng lên nếu bỏ cạnh e ĐỒ THỊ CON CÁC THÀNH PHẦN LIÊN THÔNG Ta gọi đồ thị con của đồ thị G = (V, E) là đồ thị H = (W, F), trong đó Trong trường hợp đồ thị là không liên thông, nó sẽ rã ra thành một số đồ thị con liên thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy ta sẽ gọi là các thành phần liên thông của đồ thị. Ví dụ. Đồ thị H trong hình dưới gồm 3 thành phần liên thông H1, H2, H3. MỘT SỐ DẠNG ĐẶC BIỆT CỦA ĐỒ THỊ Đồ thị đầy đủ. Đồ thị hai phía Đồ thị hai phía đầy đủ 37 Đồ thị đầy đủ Kn Đơn đồ thị Số đỉnh: |V| = n Bậc: deg(v) = n – 1 v V Số cạnh: |E| = n(n - 1) / 2 K5K4 K1 K2 K3 K6 ĐỒ THỊ ĐẦY ĐỦ Đồ thị đầy đủ Kn có tất cả n(n-1)/2 cạnh, nó là đơn đồ thị có nhiều cạnh nhất. 38 Một đồ thị G được gọi là đồ thị lưỡng phân nếu tập các đỉnh của G có thể phân thành 2 tập hợp không rỗng, rời nhau sao cho mỗi cạnh của G nối một đỉnh thuộc tập này đến một đỉnh thuộc tập kia. Ký hiệu: Km,n ĐỒ THỊ LƯỠNG PHÂN (HAI PHÍA) ĐỒ THỊ LƯỠNG PHÂN ĐẦY ĐỦ Đồ thị hai phía được gọi là đồ thị hai phía đầy đủ nếu mỗi đỉnh của phía này đều có một cạnh nối đến từng đỉnh của phía kia. Và ký hiệu là Km,n. Ví dụ: K2,3, K3,3, K3,4 được cho trong hình dưới. ĐỒ THỊ PHẲNG Đồ thị được gọi là đồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngọai trừ ở đỉnh. Ví dụ đồ thị K4 là phẳng. CÔNG THỨC EUCLER Euler đã chứng minh được rằng: các cách biểu diễn phẳng khác nhau của một đồ thị phẳng, đều chia mặt phẳng ra thành cùng một số miền. Euler đã tìm được mối liên hệ giữa số miền, số đỉnh và số cạnh của đồ thị phẳng như sau. Giả sử G=(V,E) là đồ thị phẳng liên thông với |V| đỉnh, |E| cạnh. Gọi |R| là số miền của mặt phẳng bị chia bởi biểu diễn phẳng của G. Khi đó Ví dụ: Cho G là đồ thị phẳng liên thông với 20 đỉnh, mỗi đỉnh đều có bậc là 3. Hỏi mặt phẳng bị chia làm bao nhiêu phần bởi biểu diễn phẳng của đồ thị G? Giải. Do mỗi đỉnh của đồ thị đều có bậc là 3, nên tổng bậc của các đỉnh là 3x20=60. Từ đó suy ra số cạnh của đồ thị |E|=60/2=30. Vì vậy, theo công thức Euler, số miền cần tìm là |R|=30-20+2=12. MA TRẬN KỀ Xét đơn đồ thị vô hướng G=(V,E), với tập đỉnh V={ 1, 2,. . . ,n} , tập cạnh E={ e1, e2,. . .,em} . Ta gọi ma trận kề của đồ thị G là ma trận vuông. A={ ai,j : i,j=1, 2,. . . ,n} Với các phần tử được xác định theo qui tắc sau đây: Ví dụ ma trận kề Lưu ý rằng ma trận kề của đồ thị có hướng không phải là ma trận đối xứng. Ví dụ ma trận kề TÍNH CHẤT MA TRẬN KỀ Các tính chất của ma trận kề: 1) Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là a[i,j]=a[j,i], i,j=1,2,. . .,n. 2) Tổng các phần từ trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j). Ma trận kề của đồ thị có hướng được định nghĩa một cách hoàn toàn tương tự. MA TRẬN TRỌNG SỐ Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, mỗi cạnh e=(u,v) của đồ thị được gán với một con số a(e) [còn viết là a(u,v)] gọi là trọng số của cạnh e. Đồ thị trong trường hợp như vậy được gọi là đồ thị có trọng số. Trong trường hợp đồ thị có trọng số, thay vì mà trận kề, để biểu diễn đồ thị ta sử dụng ma trận trọng số. MA TRẬN TRỌNG SỐ Hết chươngCác file đính kèm theo tài liệu này:
- toanchuong4_dothi_6266_2016069.pdf
- Bài toán đếm
15 trang | Lượt xem: 3635 | Lượt tải: 2
- Chuyên đề Elip luyện thi đại học. Đầy đủ lí thuyết và các dạng bài tập từ dễ đến khó
10 trang | Lượt xem: 7389 | Lượt tải: 2
- Bài giảng Lý thuyết xác suất thống kê toán - Chương 3 Một số phân phối xác suất thông dụng
Lượt xem: 1484 | Lượt tải: 0
- Bài giảng Tổng hợp và trình bày số liệu
31 trang | Lượt xem: 2332 | Lượt tải: 0
- Giải tích 1 - Chương 3: Tích phân (tiếp)
35 trang | Lượt xem: 971 | Lượt tải: 0
- Toán học: STGT Hình học giải tích.
8 trang | Lượt xem: 2439 | Lượt tải: 0
- Toán học - Chương 5: Các khái niệm cơ bản của lý thuyết đồ thị (chương 2)
47 trang | Lượt xem: 918 | Lượt tải: 0
- Bài giảng Quy hoạch tuyến tính - Chương 3: Bài toán vận tải
15 trang | Lượt xem: 543 | Lượt tải: 0
- Phương trình vi phân - Hệ phi tuyến và các hiện tượng
24 trang | Lượt xem: 2230 | Lượt tải: 1
- Đề cương môn học Toán kinh tế
6 trang | Lượt xem: 955 | Lượt tải: 0
Từ khóa » Toán Rời Rạc đồ Thị Pdf
-
[PDF] Giới Thiệu Về đồ Thị - TOÁN RỜI RẠC
-
[PDF] TOÁN RỜI RẠC (DISCRETE MATHEMATICS) - HNUE
-
Chuyên Đề Toán Logic - Rời Rạc - Lý Thuyết Đồ Thị.pdf
-
Bài Tập Toán Rời Rạc Đồ Thị - Luan Van Mien Phi - Hỗ Trợ Ôn Tập
-
[PDF] LÝ THUYẾT ĐỒ THỊ
-
[PDF] TOÁN RỜI RẠC
-
Bài Giảng Toán Rời Rạc Và Lý Thuyết đồ Thị - Chương 1: Cơ Sở Logic
-
[PDF]Bài Tập Toán Rời Rạc : Đồ Thị.pdf - TailieuMienPhi
-
LÝ THUYẾT ĐỒ THỊ (TOÁN RỜI RẠC, CẤU TRÚC RỜI RẠC) - 123doc
-
đại Học Quảng Ngãi Toán Rời Rạc
-
[PDF] Tài-liệu-tham-khảo-Toán-rời-rạc.pdf
-
Đồ Thị Euler, đồ Thị Hamilton.pdf (Bài Giảng Toán Rời Rạc 2) | Tải Miễn ...
-
Bài Giảng Toán Rời Rạc - Chương 5: Các Khái Niệm Cơ Bản Của Lý ...
-
[PDF] Toán Rời Rạc – N.T.T.H - FITA-VNUA
-
Toán Rời Rạc 7-Đồ Thị PDF - Download Thư Viện Tài Liệu Miên Phí
-
Biểu Diễn Đồ Thị Trên Máy Tính: Toán Rời Rạc 2 | PDF - Scribd
-
(PDF) TOÁN RỜI RẠC NGUYỄN ĐÌNH CƯỜNG BỘ MÔN KỸ ...
-
Hướng Dẫn Học Toán Rời Rạc - Thư Viện PDF