Bài giảng Toán rời rạc - Chương 4: Lý thuyết đồ thị

Với "Bài giảng Toán rời rạc - Chương 4: Lý thuyết đồ thị" sẽ giúp bạn nắm vững kiến thức toán học gồm các khái niệm cơ bản về đồ thị EULER và đồ thị HAMILTON.

Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc - Chương 4: Lý thuyết đồ thịChương 4: LÝ THUYẾT ĐỒ THỊ Chương 44.1 MỞ ĐẦU4.2 CÁC KHÁI NIỆM CƠ BẢN4.3 ĐỒ THỊ EULER4.4 ĐỒ THỊ HAMILTON BÀI TOÁN TÌM ĐƯỜNG ĐI4.5 NGẮN NHẤT4.6 CÂY 4.I MỞ ĐẦU Bài toán về những cây cầu ở KonigsberNăm 1736 Euler, cha đẻ của lý thuyết đồ thị, đã giảiđược bài toán hóc búa nổi tiếng thời đó về những câycầu ở Konigberg.Thành phố Konigberg có hai hòn đảo nối với nhau vàvới 2 bờ sông bằng 7 chiếc cầu như hình vẽ.Tìm đường đi qua tất cả 7 cây cầu, mỗi cây cầu chỉđược đi qua một lần, sau đó quay về nơi xuất phát 4.2 CÁC KHÁI NIỆM CƠ BẢN4.2.1 Đồ thị, đỉnh, cạnh, cung:  Đồ thị vô hướng G = (V, E) gồm tập V các đỉnh và tập E các cạnh. nh v w e Ví dụ: 4.2 CÁC KHÁI NIỆM CƠ BẢN  Đồ thị có hướng G = (V, E) gồm tập V các đỉnh và tập E các cạnh có hướng gọi là cung. cung v w e Mỗi cạnh e được liên kết với một cặp đỉnh (v, w) có thứ tựVí dụ: 4.2 CÁC KHÁI NIỆM CƠ BẢN Cho đồ thị G = (V, E). Cạnh e  E liên kết đỉnh vvà w, ta nói e liên thuộc đỉnh v, w; đỉnh v và w gọilà kề nhau. Cạnh song song: Khuyên: Đỉnh cô lập: 4.2 CÁC KHÁI NIỆM CƠ BẢN Đồ thị hữu hạn: là đồ thị có số cạnh (cung) hữu hạn. Đồ thị đơn: là đồ thị không có khuyên và không cócạnh song song. Đồ thị đầy đủ: là đồ thị mà mọi cặp đỉnh đều kề nhau. Bậc của đỉnh vV là tổng số cạnh liên thuộc với nó,kí hiệu d(v). Mỗi khuyên được tính cho 2 bậc. d(v) := Số cạnh + 2* Số khuyên 4.2 CÁC KHÁI NIỆM CƠ BẢN Đỉnh cô lập có bậc bằng 0 Đỉnh treo: là đỉnh có bậc bằng 1.Nửa bậc: Cho đồ thị có hướng G = (V, E). + Nửa bậc ra của đỉnh vV, kí hiệu dr(v) làsố cung đi ra từ đỉnh v. + Nửa bậc vào của đỉnh vV, kí hiệu dv(v)là số cung đi vào đỉnh v MỘT SỐ TÍNH CHẤT* Tính chất 1: Cho đồ thị G = (V, E). Khi đó: i. Tổng bậc các đỉnh của đồ thị là số chẵn và d(v) = 2|E| ii. Nếu G là đồ thị có hướng thì: dv(v) = dr(v) = |E|* Tính chất 2: Cho đồ thị G(V, E). Khi đó số đỉnh bậc lẻ là số chẵn* Tính chất 3: Cho đồ thị đơn G = (V, E) có n đỉnh (n  2) có ít nhất hai đỉnh cùng bậc.* Tính chất 4: Cho đồ thị đơn G = (V, E) có n đỉnh (n > 2) có đúng 2 đỉnh cùng bậc thì 2 đỉnh này không thể đồng thời có bậc bằng 0 hoặc bằng n – 1.4.2.2 Đường đi, chu trình, tính liên thông  Đường đi  từ đỉnh v đến đỉnh w là dãy các cạnh nối tiếp nhau bắt đầu từ đỉnh v và kết thúc tại đỉnh w. Số cạnh trên đường đi  là độ dài của đường đi . Đường đi  có độ dài n từ đỉnh v đến đỉnh w được biểu diễn như sau:  = (v, e1, v1, e2, v2, …, vn-1, en, w) Trong đó: vi (i = 1, …, n-1) là các đỉnh trên đường đi và ei (i = 1, …, n) là các cạnh trên đường đi liên thuộc các cạnh kề trước và sau nó. Chu trình là đường đi có đỉnh đầu và đỉnh cuốitrùng nhau. Đường đi đơn là đường đi không đi qua một cạnhquá một lần.  Chu trình đơn là chu trình không đi qua một cạnh quá một lần.  Đường đi sơ cấp là đường đi không đi qua một đỉnh quá một lần. Chu trình sơ cấp là chu trình không đi qua một đỉnhquá một lần. Đường đi có hướng trong đồ thị có hướng là dãy cáccung nối tiếp nhau (e1, e2, …, en) thỏa mãn đỉnh cuối củacung ei là đỉnh đầu của cung ei+1, i = 1, …, n-1. Chu trình có hướng là đường đi có hướng có đỉnh đầuvà đỉnh cuối trùng nhau. Đường đi đơn (chu trình đơn) có hướng là đường đi(chu trình) có hướng không đi qua một cung quá mộtlần. Đường đi (chu trình) có hướng sơ cấp là đường đi(chu trình) có hướng không đi qua một đỉnh quá mộtlần. Ví dụv1 e1 v2 e4 v3 e2 e9e3 e8 e7v4 e5 v5 e6 v6 a b c d e Đồ thị liên thông là đồ thị mà mọi cặp đỉnh củanó đều có đường đi nối chúng với nhau. Đồ thị con: Cho đồ thị G = (V, E). Đồ thị G’ = (G’, E’) là đồ thị con của G nếu: (i) V’ V và E’ E và (ii) e = (v,w)  E: e  E’  v, w  V’ Thành phần liên thông: Là đồ thị con liên thông tối đại của G. 4.2.3 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY a. Ma trận kề Đồ thị vô hướng Cho đồ thị vô hướng G = (V, E) có n đỉnh theo thứ tự v1, v2, …, vn. Ma trận kề của đồ thị G là ma trận vuông A = (aij)n, trong đó aij là số cạnh nối vi với vj. Lưu ý mỗi khuyên được tính là 2 cạnh. Ma trận kề của đồ thị vô hướng luôn đối xứng qua đường chéo chính. v1 v2 Ví dụ: v3Có ma trận kề là: v5 ...