Bài giảng Lý thuyết đồ thị - Phần 1

Đồ thị 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 đó
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị - Phần 1 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ính 2.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ị vô hướng có hướng Đa đồ thị Đa đồ thị vô hướng có hướng 3.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 ⊂V 4.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 K2 K3  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 W3 W5  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 100 101 Q2 Q3 010 011 000 001 00 01  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. ...