Bài giảng Lý thuyết đồ thị: Chương 1 - Nguyễn Thanh Sơn
lượt xem 6
download
Bài giảng Lý thuyết đồ thị: Chương 1 trình bày những kiến thức đại cương về đồ thị. Nội dung cụ thể trong chương này gồm có: Định nghĩa đồ thị, đồ thị hữu hạn, đỉnh kề, một số khái niệm, các dạng đồ thị, bậc của đỉnh, mối liên hệ bậc - số cạnh,...và các nội dung khác. Mời các bạn cùng tham khảo.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 1 - Nguyễn Thanh Sơn
- LÝ THUYẾT ĐỒ THỊ ntsonptnk@gmail.com
- NỘI DUNG 1. Đại cương về đồ thị 2. Cây 3. Các bài toán đường đi 4. Đồ thị phẳng và bài toán tô màu đồ thị 5. Mạng và bài toán luồng trên mạng, bài toán cặp ghép GV: Döông Anh Ñöùc 2
- TÀI LIỆU THAM KHẢO 1. Giáo trình Lý Thuyết Đồ Thị - Dương Anh Đức, Trần Đan Thư 2. Toán rời rạc – Nguyễn Tô Thành, Nguyễn Đức Nghĩa 3. ... GV: Döông Anh Ñöùc 3
- ĐẠI CƯƠNG VỀ ĐỒ THỊ
- ĐỊNH NGHĨA Một đồ thị có hướng G=(X, U) được định nghĩa bởi: Tập hợp X được gọi là tập các đỉnh của đồ thị; Tập hợp U là tập các cạnh của đồ thị; Mỗi cạnh u U được liên kết với một cặp đỉnh (i, j) X2. GV: Döông Anh Ñöùc 5
- ĐỊNH NGHĨA Một đồ thị vô hướng G=(X, E) được định nghĩa bởi: Tập hợp X được gọi là tập các đỉnh của đồ thị; Tập hợp E là tập các cạnh của đồ thị; Mỗi cạnh e E được liên kết với một cặp đỉnh {i, j} X2, không phân biệt thứ tự GV: Döông Anh Ñöùc 6
- ĐỒ THỊ HỮU HẠN Đồ thị có tập đỉnh và tập cạnh hữu hạn được gọi là ĐỒ THỊ HỮU HẠN Học phần này chỉ làm việc các ĐỒ THỊ HỮU HẠN, tuy nhiên để ngắn gọn chúng ta chỉ dùng thuật ngữ ĐỒ THỊ và hiểu ngầm đó là đồ thị hữu hạn. GV: Döông Anh Ñöùc 7
- ĐỈNH KỀ Trên đồ thị có hướng, xét cạnh u được liên kết với cặp đỉnh (i, j): Cạnh u kề với đỉnh i và đỉnh j (hay đỉnh i và đỉnh j kề với cạnh u); có thể viết tắt u=(i, j). Cạnh u đi ra khỏi đỉnh i và đi vào đỉnh j Đỉnh j được gọi là đỉnh kề của đỉnh i GV: Döông Anh Ñöùc 8
- ĐỈNH KỀ Trên đồ thị vô hướng, xét cạnh e được liên kết với cặp đỉnh (i, j): Cạnh e kề với đỉnh i và đỉnh j (hay đỉnh i và đỉnh j kề với cạnh e); có thể viết tắt e=(i, j). Đỉnh i và đỉnh j được gọi là 2 đỉnh kề nhau (hay đỉnh i kề với đỉnh j và ngược lại, đỉnh j kề với đỉnh i) GV: Döông Anh Ñöùc 9
- MỘT SỐ KHÁI NIỆM Cạnh song song Khuyên Đỉnh treo Đỉnh cô lập GV: Döông Anh Ñöùc 10
- CÁC DẠNG ĐỒ THỊ Đồ thị RỖNG: tập cạnh là tập rỗng Đồ thị ĐƠN: không có khuyên A B và cạnh song song Đồ thị ĐỦ: đồ thị vô hướng, đơn, giữa hai đỉnh bất kỳ đều có C đúng một cạnh. Đồ thị đủ N đỉnh ký hiệu là KN. KN có N(N-1)/2 cạnh. GV: Döông Anh Ñöùc 11
- CÁC DẠNG ĐỒ THỊ Đồ thị LƯỠNG PHÂN: đồ thị G=(X, E) được gọi là đồ thị lưỡng phân nếu tập X được A chia thành hai tập X1 và X2 thỏa: D X1 và X2 phân hoạch X; B Cạnh chỉ nối giữa X1 và X2. E Đồ thị LƯỠNG PHÂN ĐỦ: là đồ C thị lưỡng phân đơn, vô hướng thỏa với (i, j)/i X1 và j X2 có đúng một cạnh i và j. X1 =N và X2 =M, kýGV: Döông Anh Ñöùc hiệu KM, N. 12
- VÍ DỤ: ĐỒ THỊ ĐỦ K4 K3 K4 K2 K1, 1 K3, 3 K2, 3 GV: Döông Anh Ñöùc 13
- BẬC CỦA ĐỈNH Xét đồ thị vô hướng G Bậc của đỉnh x trong đồ thị G là số các cạnh kề với đỉnh x, mỗi khuyên được tính hai lần, ký hiệu là dG(x) (hay d(x) nếu đang xét một đồ thị nào đó). GV: Döông Anh Ñöùc 14
- BẬC CỦA ĐỒ THỊ Xét đồ thị có hướng G Nửa bậc ngoài của đỉnh x là số các cạnh đi ra khỏi đỉnh x, ký hiệu d+(x). Nửa bậc trong của đỉnh x là số các cạnh đi vào đỉnh x, ký hiệu d-(x). Bậc của đỉnh x: d(x)=d+(x)+d-(x) GV: Döông Anh Ñöùc 15
- BẬC CỦA ĐỈNH Đỉnh TREO là đỉnh có bậc A B bằng 1. Đỉnh CÔ LẬP là đỉnh có bậc bằng 0. D C GV: Döông Anh Ñöùc 16
- MỐI LIÊN HỆ BẬC - SỐ CẠNH Định lý: Xét đồ thị có hướng G=(X, U). Ta có: d x d x và dx 2U x X x X x X Xét đồ thị vô hướng G=(X, E). Ta có: d x 2E x X Hệ quả: số lượng các đỉnh có bậc lẻ trong một đồ thị là một số chẳn. GV: Döông Anh Ñöùc 17
- ĐẲNG CẤU ĐỒ THỊ 1 u1 2 Hai đồ thị vô hướng G1 =(X1, u5 u2 u4 E1) và G2=(X2, E2) được gọi là đẳng cấu với nhau nếu tồn tại G1 u3 hai song ánh và thỏa mãn 4 3 điều kiện: u6 : X1 X2 và : E1 E2 a Nếu cạnh e E1 kề với cặp đỉnh {x, y} X1 trong G1 thì e1 e4 e2 cạnh (e) sẽ kề với cặp đỉnh G2 e6 { (x), (y)} trong G2 (sự e5 d tương ứng cạnh). e3 b c GV: Döông Anh Ñöùc 18
- ĐẲNG CẤU ĐỒ THỊ Hai đồ thị có hướng G1=(X1, U1) 1 và G2=(X2, U2) được gọi là G3 đẳng cấu với nhau nếu tồn tại hai song ánh và thỏa mãn 2 3 điều kiện: 1 : X1 X2 và : U1 U2 G4 Nếu cạnh u U1 liên kết với cặp đỉnh (x, y) X1 trong G1 thì 3 cạnh (u) sẽ liên kết với cặp đỉnh ( (x), (y)) trong G2 (sự tương ứng cạnh). 2 GV: Döông Anh Ñöùc 19
- ĐỒ THỊ CON Xét hai đồ thị G=(X, U) và G1=(X1, U1). G1 được gọi là đồ thị con của G và ký hiệu G1 G nếu: X1 X; U1 U u=(i, j) U của G, nếu u U1 thì i, j X1 1 u1 2 1 u1 2 u5 u2 u3 u2 u4 G G1 u3 4 4 3 u6 GV: Döông Anh Ñöùc 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Lý thuyết đồ thị (296 tr)
296 p | 124 | 20
-
Bài giảng Lý thuyết đồ thị (Graph Theory)
132 p | 134 | 8
-
Bài giảng Lý thuyết đồ thị: Chương 5 - PGS.TS. Hoàng Chí Thành
37 p | 12 | 6
-
Bài giảng Lý thuyết đồ thị: Chương 1 - PGS.TS. Hoàng Chí Thành
62 p | 15 | 6
-
Bài giảng Lý thuyết đồ thị: Chương 10 - PGS.TS. Hoàng Chí Thành
25 p | 13 | 6
-
Bài giảng Lý thuyết đồ thị: Chương 3 - TS. Lê Nhật Duy
26 p | 13 | 5
-
Bài giảng Lý thuyết đồ thị: Chương 8 - PGS.TS. Hoàng Chí Thành
44 p | 7 | 5
-
Bài giảng Lý thuyết đồ thị: Chương 3 - PGS.TS. Hoàng Chí Thành
61 p | 17 | 5
-
Bài giảng Lý thuyết đồ thị: Chương 5 - Đặng Nguyễn Đức Tiến
45 p | 79 | 4
-
Bài giảng Lý thuyết đồ thị: Chương 2 - PGS.TS. Hoàng Chí Thành
29 p | 12 | 4
-
Bài giảng Lý thuyết đồ thị: Chương 1 - TS. Lê Nhật Duy
64 p | 17 | 4
-
Bài giảng Lý thuyết đồ thị: Chương 8 - TS. Lê Nhật Duy
25 p | 12 | 4
-
Bài giảng Lý thuyết đồ thị: Chương 7 - TS. Lê Nhật Duy
19 p | 16 | 4
-
Bài giảng Lý thuyết đồ thị: Chương 5 - TS. Lê Nhật Duy
58 p | 15 | 4
-
Bài giảng Lý thuyết đồ thị: Chương 2 - TS. Lê Nhật Duy
26 p | 13 | 3
-
Bài giảng Lý thuyết đồ thị: Chương 4 - TS. Lê Nhật Duy
26 p | 13 | 3
-
Bài giảng Lý thuyết đồ thị: Chương 6 - TS. Lê Nhật Duy
17 p | 12 | 3
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