zunia.vn

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

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Lý thuyết đồ thị: Chương 1 - Nguyễn Trần Phi Phượng

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

Báo xấu

189
lượt xem 7
download

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

Bài giảng Lý thuyết đồ thị: Chương 1 - Các khái niệm cơ bản của lý thuyết đồ thị của Nguyễn Trần Phi Phương nêu lên định nghĩa đồ thị; các thuật ngữ cơ bản; đường đi, chu trình, đồ thị liên thông; một số dạng đồ thị đặc biệt. Mời các bạn tham khảo bài giảng để hiểu rõ hơn về những nội dung này.

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 Lý thuyết đồ thị: Chương 1 - Nguyễn Trần Phi Phượng

Chương 1 CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ
1.1 Định nghĩa đồ thị Định nghĩa 1. Đơn đồ 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. Ví dụ a. Đơn đồ thị vô hướng b. Không phải đơn đồ thị c. Không phải đơn đồ thị vô hướng do có các cặp vô hướng do có cạnh nối cạnh nối cùng một cặp một đỉnh với chính nó. đỉnh 18/02/2011 Lý thuyết đồ thị 2
1.1 Định nghĩa đồ thị Định nghĩa 2. Đa đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh, và E là họ 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 một cặp đỉnh. Ví dụ e2 e1 Đa đồ thị vô hướng. e1 và e2 là các cạnh song song. 18/02/2011 Lý thuyết đồ thị 3
1.1 Định nghĩa đồ thị Định nghĩa 3. Giả đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử (không nhất thiết phải khác nhau) của V gọi là các cạnh. Cạnh e được gọi là khuyên nếu nó có dạng e=(u,u). Ví dụ e Giả đồ thị vô hướng. e là khuyên 18/02/2011 Lý thuyết đồ thị 4
1.1 Định nghĩa đồ thị Định nghĩa 4. Đơ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 phần tử khác nhau của V gọi là các cung. Ví dụ a. Đơn đồ thị có hướng b. Không phải đơn đồ thị có hướng do có cặp cạnh nối cùng một cặp đỉnh 18/02/2011 Lý thuyết đồ thị 5
1.1 Định nghĩa đồ thị Định nghĩa 5. Đa đồ thị có hướng G = (V,E) bao gồm V là tập các đỉnh, và E là họ các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Hai cung e1, e2 tương ứng với cùng một cặp đỉnh được gọi là cung song song. Ví dụ e2 e1 Đa đồ thị có hướng. e1 và e2 là các cung song song 18/02/2011 Lý thuyết đồ thị 6
1.2 Các thuật ngữ cơ bản Xét đồ thị vô hướng G = (V,E) – Nếu e = (u,v) là một cạnh của G thì: • Hai đỉnh u, v được gọi là hai đỉnh kề nhau • Cạnh e được gọi là cạnh liên thuộc với đỉnh u và đỉnh v • Đỉnh u, đỉnh v được gọi là đỉnh đầu của cạnh e u – Bậc của một đỉnh v (deg(v)) e là số cạnh liên thuộc với nó. – VD: deg(0) = 3, deg(5) = 4, v deg(2) = 6, deg(8) = 2,… 18/02/2011 Lý thuyết đồ thị 7
1.2 Các thuật ngữ cơ bản Đỉnh có bậc 0 được gọi là đỉnh cô lập. Đỉnh có bậc 1 được gọi là đỉnh treo. Định lý. Xét đồ thị vô hướng G = (V,E). Khi đó, tổng bậc của tất cả các đỉnh của đồ thị sẽ bằng hai lần số cạnh của nó. deg(v) 2 | E | v V Hệ quả. Trong đồ thị vô hướng, số đỉnh bậc lẻ là một số chẵn. 18/02/2011 Lý thuyết đồ thị 8
1.2 Các thuật ngữ cơ bản  Xét đồ thị có hướng G = (V,E) – Nếu e = (u,v) là một cung của G thì: • Đỉnh v được gọi là đỉnh kề của đỉnh u • Cung e được gọi là cung đi ra khỏi đỉnh u và là cung đi vào đỉnh v • Đỉnh u được gọi là đỉnh đầu của cung e, đỉnh v được gọi là đỉnh cuối của cạnh e – Bán bậc ra của một đỉnh v (deg+(v)) u là số cung đi ra khỏi nó. e – Bán bậc vào của một đỉnh v (deg-(v)) t v là số cung đi vào nó. – VD: deg+(t) = 1, deg-(t) = 1, deg+(v) = 0, deg-(v) = 3,… s x 18/02/2011 Lý thuyết đồ thị 9
1.2 Các thuật ngữ cơ bản Định lý. Xét đồ thị có hướng G = (V,E). Khi đó, tổng bán bậc ra của tất cả các đỉnh sẽ bằng tổng bán bậc vào của tất cả các đỉnh và bằng số cung của đồ thị. deg (v) deg (v) | E | v V v V 18/02/2011 Lý thuyết đồ thị 10
1.2 Các thuật ngữ cơ bản Định nghĩa. Xét đồ thị G = (V,E). Đồ thị H = (W,F) là một đồ thị con của G nếu và chỉ nếu mọi đỉnh của H cũng là đỉnh của G và mọi cạnh/cung của H cũng là cạnh/cung của G. (W V, F E). Ví dụ: 1 2 3 4 5 1 2 1 2 3 1 2 3 4 5 4 5 4 5 Đồ thị con của G Đồ thị con của G Không là đồ thị con của G 18/02/2011 Lý thuyết đồ thị 11
1.2 Các thuật ngữ cơ bản Định nghĩa. Cho hai đồ thị G=(V,E) và G’=(V’,E’). Ta nói rằng G đẳng cấu G’, ký hiệu G G’, nếu tồn tại song ánh f:V→ V’ sao cho: uv là cạnh của G f(u)f(v) là cạnh của G 18/02/2011 Lý thuyết đồ thị 12
1.3 Đường đi, chu trình, đồ thị liên thông Định nghĩa 1. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương trên đồ thị G=(V,E) là dãy x0, x1, …, xn-1, xn trong đó u = x0, v = xn, (xi, xi+1) E, i = 0, 1, 2, …, n-1. Đỉnh u gọi là đỉnh đầu, đỉ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 không có cạnh/cung nào xuất hiện quá một lần được gọi là đường đi đơn. Đường đi không có đỉnh nào xuất hiện quá một lần được gọi là đường đi sơ cấp. 18/02/2011 Lý thuyết đồ thị 13
1.3 Đường đi, chu trình, đồ thị liên thông Ví dụ: Các đường đi từ 1 đến 5: Độ dài 2 Đường đi sơ cấp d1: 1 2 5 (hiển nhiên đơn) Độ dài 6 Đường đi đơn d2: 1 2 4 3 9 2 5 (không sơ cấp) Độ dài 6 Đường đi không d3: 1 9 2 3 9 2 5 đơn (không sơ cấp) Các chu trình trong đồ thị: Độ dài 3 Chu trình sơ cấp (hiển nhiên đơn) C1: 1 2 9 1 Độ dài 6 C2: 1 9 0 3 9 2 1 Chu trình đơn (không sơ cấp) Độ dài 5 C3: 1 9 2 3 9 1 Chu trình không đơn (không sơ cấp) 18/02/2011 Lý thuyết đồ thị 14
1.3 Đường đi, chu trình, đồ thị liên thông Ví dụ: c b a Các đường đi từ a đến e: Độ dài 2 Đường đi sơ cấp d1: a b e (hiển nhiên đơn) Độ dài 5 d2: a b c f b e Đường đi đơn (không sơ cấp) Các chu trình trong đồ thị: f e d Độ dài 4 C1: a b e d a Chu trình sơ cấp (hiển nhiên đơn) Độ dài 6 C2: a d c f e d a Chu trình đơn (không sơ cấp) Độ dài 8 C3: a b e d c f e d a Chu trình không đơn (không sơ cấp) 18/02/2011 Lý thuyết đồ thị 15
1.3 Đường đi, chu trình, đồ thị liên thông Định nghĩa 2. Đồ thị vô hướng 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ó. Đồ thị vô hướng liên thông Đồ thị vô hướng không liên thông 18/02/2011 Lý thuyết đồ thị 16
1.3 Đường đi, chu trình, đồ thị liên thông Một đồ thị không liên thông là hợp của nhiều đồ thị con liên thông rời nhau. Mỗi đồ thị con này được gọi là một thành phần liên thông của đồ thị ban đầu. Đồ thị trên có 3 thành phần liên thông 18/02/2011 Lý thuyết đồ thị 17
1.3 Đường đi, chu trình, đồ thị liên thông Định nghĩa 3. Đỉnh v được gọi là đỉnh rẽ nhánh (đỉnh khớp) nếu việc loại bỏ v cùng với các cạnh liên thuộc với nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị. Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị. Ví dụ: Đỉnh khớp: e, x, y Cầu: (e,x), (y,w) 18/02/2011 Lý thuyết đồ thị 18
1.3 Đường đi, chu trình, đồ thị liên thông Định nghĩa 4. Đồ thị có hướng G=(V,E) được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. Đồ thị có hướng G=(V,E) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là đồ thị vô hướng liên thông. Ví dụ: Đồ thị có hướng liên thông mạnh Đồ thị có hướng không liên thông yếu (hiển nhiên cũng là liên thông yếu) (hiển nhiên không liên thông mạnh) 18/02/2011 Lý thuyết đồ thị 19
1.4 Một số dạng đồ thị đặc biệt Đồ thị đầy đủ. Đồ thị đầy đủ n đỉnh, ký hiệu là Kn là đơn đồ thị vô hướng mà giữa hai đỉnh bất kỳ của nó luôn có cạnh nối. Số đỉnh: n n(n 1) Số cạnh: 2 Bậc của mỗi đỉnh: n-1 18/02/2011 Lý thuyết đồ thị 20

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.