Bài giảng: Đại cương về đồ thị

Đồ thị vô hướng (undirected graph)Đỉnh (vertex) Cạnh (edge) {1,4}Số đỉnh n = 4. Số cạnh m = 5.“Đỉnh 2 và đỉnh 3 kề nhau (adjacent)” (adjacent)”Đa đồ thị, Đồ thị đơn (simple graph)Khuyên (loop) Đồ thị G(V, E) Tập đỉnh V = {1, 2, 3, 4} Tập cạnh: E = {12, 13, 14, 23, 34} ‘Đơn’ = Không có cạnh song song và không có khuyênHai cạnh song song (parallel)Đồ thị có hướng (directed graph)Khuyên (loop)Cung (arc) [1,2]Đỉnh đầu (initial) Đỉnh cuối (terminal)Bậc của đỉnh trong đồ thị vô hướngĐịnh nghĩa: Bậc (degree) của một đỉnh x là số...
Nội dung trích xuất từ tài liệu:
Bài giảng: Đại cương về đồ thịĐại cương về đồ thị Đồ thị vô hướng (undirected graph) Đỉnh (vertex) Cạnh (edge) {1,4} “Đỉnh 2 và đỉnh 3Số đỉnh n = 4. kề nhau (adjacent)” kềSố cạnh m = 5. Đa đồ thị, Đồ thị đơn (simple graph) Khuyên (loop) ‘Đơn’ = Không có cạnh song song và Đồ thị G(V, E) không có khuyênTập đỉnh V = {1, 2, 3, 4}Tập cạnh: E = {12, 13, 14, 23, 34} Hai cạnh song song (parallel)Đồ thị có hướng (directed graph) Khuyên (loop) Cung (arc) [1,2] Đỉnh đầu (initial) Đỉnh cuối (terminal) Bậc của đỉnh trong đồ thị vô hướngĐịnh nghĩa: Bậc (degree) của một đỉnh x là số cạnh kề với x. Degree(1) = d(1) = 3 Degree(2) = d(2) = 2 Đỉnh treo, đỉnh cô lập d(3) = 1đỉnh treo (pendant) d(5) = 0 đỉnh cô lập (isolated) Bậc của đỉnh trong đồ thị có hướngĐịnh nghĩa: Bậc ra (out-degree) của một đỉnh x là số cung coi x là đỉnh đầu; bậc vào (in- degree) là số cung coi x là đỉnh cuối. InDegree(1) = d-(1) = 2 OutDegree(1) = d+(1) = 1 Mối quan hệ giữa số đỉnh và số cạnhĐịnh lý: Cho G = (X, E) a) 2m = ∑d (i ) i∈X b) Số đỉnh bậc lẻ là số chẵn. chẵn. c) ếu G có hướng m = ∑d − (i ) = ∑d + (i ) i∈X i∈XChứng minh: (Bài tập) Bài tập1. Trong một bữa tiệc, mọi người bắt tay nhau. CMR số người bắt tay với một số lẻ người khác là một số chẵn.2.2. Bảng A của môn bóng đá Seagames 24 thi đấu vòng tròn một lượt. CMR tại mọi thời điểm của giải, luôn có hai đội có số trận đấu bằng nhau. Đồ thị đủ KnĐ : Đồ thị đủ (complete graph) Kn là đồ thị đơn vô hướng, mỗi đỉnh đều kề với các đỉnh còn lại. K2 K3 K4 Tính chất của Kn• Bậc mỗi đỉnh: d(x) = n – 1.• Số cạnh của Kn: m = n(n – 1)/2. K3 K4 Đồ thị bùG = Kn −G Bài tập1. Một lớp học có 6 học sinh. CMR luôn có 3 người quen nhau hoặc 3 người không quen nhau.2. Bốn người bất kỳ (trong số n>3 người) đều có một người quen với ba người còn lại. CMR luôn có một người quen với tất cả n – 1 người còn lại.3. Trong giải cờ tướng quốc gia (có 20 kỳ thủ) hiện đã có 21 trận đấu được tiến hành. CMR có một kỳ thủ đã thi đấu ít nhất 3 trận. Đẳng cấuĐịnh nghĩa: G1(X1,E1) ≅ G2(X2,E2) nếu có song ánh ϕ : X1 X2 sao cho {i , j } ∈ E1 ⇔ {ϕ(i ), ϕ( j )} ∈ E 2Ví dụ: hai đồ thị sau đẳng cấu với song ánh1 DN, 2 CT, 3 BD, 4 AG Tính chất của sự đẳng cấu Tính chất: ếu G1(X1,E1) ≅ G2(X2,E2) thì: 1. |X1| = |X2|: cùng số đỉnh 2. |E1| = |E2|: cùng số cạnh 3. Cùng số đỉnh với bậc tương ứng. 4. Số đỉnh kề với i ∈ X1 và ϕ(i) ∈ X2 như nhau.•Tính chất trên chỉ cóđiều kiện cần ?•Ví dụ: hai đồ thị saukhông đẳng cấu Bài tập1. Xét sự đẳng cấu của các cặp đồ thị sau. Chỉ ra song ánh nếu chúng đẳng cấu Bài tập2. Một đồ thị đơn G gọi là tự bù nếu nó đẳng cấu với đồ thị bù của nó. a) CMR nếu G tự bù thì số đỉnh của G là 4k hay 4k+1 4k+1 (k nguyên dương) b) Tìm tất cả các đồ thị tự bù có 4 đỉnh; 5 đỉnh. Đường điĐịnh nghĩa: Cho G = (X, E).• Đường đi (path) là một dãy các cạnh liên tiếp nhau (x0, x1, x2, …, xk) trong đó xixi+1 là một cạnh ∈ E. Độ dài (length) của đường đi = k.• Đường đi đơn (simple) nếu không có cạnh nào xuất hiện quá một lần.• Đường đi sơ cấp (elementary) nếu không có đỉnh nào xuất hiện quá một lần.• Đường đi là chu trình (cycle) nếu đỉnh đầu trùng đỉnh cuối x0 = xk. Ví dụ đường đi• (u, y, w, v) là một đường đi độ dài 3.• (z, u, y, v, u) là một đường đi đơn nhưng không sơ cấp.• (u, y, w, v, u) là một chu trình. Có thể xem chu trình này như chu trình (w, v, u, y, w). Định lýĐL: ếu mọi đỉnh của một đồ thị G đều có bậc ≥ 2 thì G có ít nhất một chu trình đơn.Chứng minh (Xem giáo trình) ...