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

Chia sẻ: AN TON | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

240
lượt xem 35
download

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

Đồ 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ên 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ố...

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: Đạ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 3 Số đỉ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ên Tậ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∈X Chứng minh: (Bài tập)
Bài tập 1. 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ập 1. 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 2 Ví dụ: hai đồ thị sau đẳng cấu với song ánh 1 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ị sau không đẳng cấu
Bài tập 1. 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ập 2. 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)