Chương II. Lý thuyết đồ thị

ĐỊNH NGHĨA ĐỒ THỊ (GRAPH)Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được mô tả hình thức: G = (V, E)V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể coi E là tập các cặp (u, v) với u và v là hai đỉnh thuộc V.
Nội dung trích xuất từ tài liệu:
Chương II. Lý thuyết đồ thị ChươngII.Lýthuyếtđồthị I. Các khái niệm cơ bản II. Biểu diễn đồ thị III. Tính liên thông IV. Chu trình Euler V. Bài toán tìm đường đi ngắn nhất VI. Đồ thị phẳng VII.Tô màu đồ thị I.Cáckháiniệmcơbản 1.ĐỊNHNGHĨAĐỒTHỊ(GRAPH) Làmộtcấutrúcrờirạcgồmcácđỉnhvàcáccạnhnốicácđỉnh đó.Đượcmôtảhìnhthức:G=(V,E) Vgọilàtậpcácđỉnh(Vertices)vàEgọilàtậpcáccạnh (Edges).CóthểcoiElàtậpcáccặp(u,v)vớiuvàvlàhai đỉnhthuộcV. Vídụ: Đường Mạng phố máy tính2.Phânloạiđồthị G được gọi là đơn đồ thị nếu giữa hai đỉnh phân biệt u, v của V có nhiều nhất là 1 cạnh trong E n ối t ừ u t ới v. G được gọi là đa đồ thị nếu giữa hai đỉnh phân biệt u, v của V có thể có nhiều hơn 1 cạnh trong E nối t ừ u t ới v G được gọi là giả đồ thị nếu G là đa đồ thị và có thể có cạnh nối từ một đỉnh đến chính nó. Cạnh đó được gọi là khuyên G được gọi là đồ thị vô hướng nếu các cạnh trong E không có sự phân biệt đỉnh nào là đỉnh đầu, đỉnh nào là đỉnh cuối. G được gọi là đồ thị có hướng nếu các cạnh trong E có sự phân biệt đỉnh nào là đỉnh đầu, đỉnh nào là đỉnh cu ối.Vídụ Đơn đồ Đơn đồ thị thị có hướng vô hướng Đa đồ thị Đa đồ thị vô hướng có hướng3.Cạnhliênthuộc,đỉnhkề,bậc Đối với đồ thị vô hướng G = (V, E). Xét một cạnh e ∈ E, nếu e = (u, v) thì ta nói hai đỉnh u và v là kề nhau (adjacent) và cạnh e này liên thuộc (incident) với đỉnh u và đỉnh v. Với một đỉnh v trong đồ thị, ta định nghĩa bậc (degree) của v, ký hiệu deg(v) là số cạnh liên thuộc với v. Định lý: Giả sử G = (V, E) là đồ thị vô hướng với m cạnh, khi đó tổng tất cả các bậc đỉnh trong V sẽ bằng 2m: ∑ deg(v) = 2m v ⊂V Chứng minh: Khi lấy tổng tất cả các bậc đỉnh tức là mỗi cạnh e = (u, v) bất kỳ sẽ được tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra kết quả. Hệ quả: Trong đồ thị vô hướng, số đỉnh bậc lẻ là số chẵn Đối với đồ thị có hướng G = (V, E). Xét một cung e ∈ E, nếu e = (u, v) thì đỉnh u khi đó được gọi là đỉnh đầu,đỉnh v được gọi là đỉnh cuối của cung e. Với mỗi đỉnh v trong đồ thị có hướng, ta định nghĩa: bậc ra của v ký hiệu deg+(v) là số cung đi ra khỏi nó; bậc vào ký hiệu deg-(v) là số cung đi vào đỉnh đó. Định lý: Giả sử G = (V, E) là đồ thị có hướng với m cung, khi đó tổng tất cả các bậc ra bằng tổng tất cả các bậc vào và bằng m: ∑ deg + (v) = ∑ deg − (v) = m v ⊂V v ⊂V4.Mộtsốdạngđồthịđặcbiệt a. Đồ thị đầy đủ Kn (n≥1) có n đỉnh và mỗi cặp đỉnh đều có đúng một cạnh nối. K4 K3 K2 b. Chu trình Cn (n≥3) có n đỉnh v1,v2,..vn và các cạnh (v1,v2); (v2,v3)....(vn-1,vn) và (vn,v1) C4 C3 c5 c. Đồ thị hình bánh xe Khi thêm một đỉnh vào giữa chu trình Cn và nối đỉnh này với các đỉnh của đồ thị Cn ta thu được đồ thị hình bánh xe. W4 W5 W3 d. Đồ thị hình khối Qn có 2n đỉnh, mỗi đỉnh được biểu diễn bằng xâu nhị phân độ dài n. Hai đỉnh là liền kề nếu các xâu nhị phân biểu diễn chúng khác nhau đúng một bit. 10 11 110 111 Q1 101 100 Q2 Q3 010 011 001 000 01 00 e. Đồ thị phân đôi là đồ thị có tập các đỉnh V có thể phân làm hai tập con không rỗng, rời nhau V1 và V2 sao cho mỗi cạnh của đồ thị nối 1 đỉnh của V1 với 1 đỉnh của V2 Đồ thị phân đôi đầy đủ Km,n là đồ thị có tập các đỉnh được phân thành hai tập con tương ứng có m đỉnh và n đỉnh và có cạnh giữa hai đỉnh nếu đỉnh thứ nhất thuộc tập con này, đỉnh thứ hai thuộc tập con kia.II.Biểudiễnđồthị1. Ma trận liền kề (ma trận kề) Giả sử G = (V, E) là một đơn đồ thị có số đỉnh là n, không mất tính tổng quá ...