Giáo Trình Toán Rời Rạc (Giáo Trình Dành Cho Sinh Viên Ngành Công Nghệ Thông Tin) - Vũ Kim Thành (Download Tai Tailieutuoi.com)

- Biểu diễn ñồ thị bằng ñại số 79 3.
- Sự ñẳng cấu của các ñồ thị 82 4.
- Tính liên thông trong ñồ thị 84 5.
- Cây khung (cây bao trùm) của ñồ thị 131 5.
- Bài toán ñường ñi ngắn nhất trong ñồ thị 147 2.
- Tâm, Bán kính, ðường kính của ñồ thị 152 3.
- Lý thuyết ñồ thị.
- Các ñịnh nghĩa và các loại ñồ thị 1.2.
- Bậc của ñỉnh của ñồ thị 1.3.
- Một số dạng ñồ thị ñặc biệt 1.4.
- Biểu diễn ñồ thị bằng ñại số 2.1.
- Tính liên thông trong ñồ thị 4.1.
- Sắc số của ñồ thị 6.1.
- Người ta phânloại ñồ thị theo ñặc tính và số các cạnh nối giữa các ñỉnh.Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc .
- Các ñịnh nghĩa và các loại ñồ thị a.
- BộG = (X, U) ñược gọi là một ñồ thị.
- Nếu X làtập vô hạn thì gọi là ñồ thị vô hạn.
- Mỗi phần tử u∈U gọi là một cạnh của ñồ thị.
- Nếu mọi phần tử u = (x, y)∈U của ñồ thị ñược sắp thứ tự (x trước, y sau) thì ñồ thịñược gọi là ñồ thị có hướng.
- Tập U ñược gọi là tập các cung của ñồ thị.
- ðó là một ñồ thị cóhướng gồm 5 ñỉnh b.
- Hình 3 là một thí dụ về ñơn ñồ thị có hướng.
- Hình 4 là một ñơn ñồ thị vô hướng.(Hạ Long) x3 x2 (Hải Phòng) (Nha Trang) x7 x8 (Biên Hòa) x1 x4 x5 x6 x9 x10 (Hà Nội) (Vinh) (Huế) (ðà Nẵng) (Tp Hồ Chí Minh) (Cần Thơ) Hình 4.
- ðó là một mô hình ña ñồ thị.Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc x3 x2 x7 x8 x1 x4 x5 x6 x9 x10 Hình 5.
- ðồ thị này gọi là ñồ thị ưu tiên trước sau.
- Bậc của ñỉnh của ñồ thị a.
- x∈Xcòn trong ñồ thị có hướng G = (X, U) thì.
- Chứng minh: Giả sử ñồ thị G = (X, U) có n ñỉnh (N(X.
- n – 2.Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc Nếu ñồ thị có ñỉnh bậc n – 1 thì ñồ thị không có ñỉnh nào có bậc 0.
- Một số dạng ñồ thị ñặc biệt a.
- thì G không phải là ñồ thị phân ñôi.
- Thí dụ 1: Xét ñồ thị trên hình 17.
- Vậy ñồ thị ñã cho không phải là ñồ thị phân ñôi.Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc Thí dụ 2: Xét ñồ thị trên hình 18a.
- Biểu diễn ñồ thị bằng ñại số.
- Với mỗi x ∈ X của ñồ thị G = (X, U) không có cạnh bội, ñặt: G(x.
- xi ∈ X } gọi là danh sách kề của ñồ thị.
- Thí dụ 1: Xét ñồ thị ở hình 23, ta có: G(x1.
- ðiều ñócó nghĩa là với một ñồ thị n ñỉnh có thể viết ñược n! ma trận kề tương ứng.Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc Thí dụ 1: Với ñồ thị trong hình 25, ta có: x1 x 2 x 3 x 4 x1 x x1.
- ðịnh nghĩa: Hai ñồ thị G1 = (X1, E1) và G2 = (X2, E2) ñược gọi là ñẳng cấu vớinhau nếu tồn tại một song ánh f : X1 → X2 sao cho các ñỉnh x và y là kề nhau trong G1 khivà chỉ khi f(x) và f(y) là kề nhau trong G2.Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc Thí dụ 1: Hai ñồ thị trong hình 30 là ñẳng cấu qua song ánh: f(A.
- 1 2 A B C 3 4 5 6 D E 7 8 F G H H1 H2 Hình 32Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc Dễ thấy là hai ñồ thị ñẳng cấu thì hai ma trận kề (theo một thứ tự nào ñó của các ñỉnh)tương ứng là bằng nhau.4.
- ðồ thị bộ phận của ñồ thị G = (X, U) là ñồ thị K = (X, F), trong ñó F ⊆ U.
- Gọi G1 = (X1, U1) và G2 = (X2, U2) là hai thànhphần liên thông của ñồ thị.
- ðịnh nghĩa 2: ðồ thị có hướng G = (X, U) gọi là liên thông yếu nếu ñồ thị vô hướngtương ứng (tức ñồ thị ñã cho ñược thay cung bằng cạnh) với nó là ñồ thị liên thông.Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc Thí dụ: x1 x2 x1 x2 x3 x3 x5 x4 x5 x4 Hình 39.
- Chứng minh: ðiều kiện cần: Giả sử (x, y) là một cạnh của ñồ thị.
- A ∈ L }gọi là số ổn ñịnh trong của ñồ thị G.5.2.
- B ∈ M }gọi là số ổn ñịnh ngoài của ñồ thị G.
- N(B).Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc Thí dụ: Tìm số ổn ñịnh ngoài của ñồ thị trong hình 41.
- Sắc số của ñồ thị G ñược ký hiệu là λ(G).
- Trong ñóα(G) là số ổn ñịnh trong và λ(G) là sắc số của ñồ thị.Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc Chứng minh: Giả sử λ(G.
- k (k ≤ n), như vậy các ñỉnh của ñồ thị ñược tô bằng kmàu.
- b) Tìm ma trận kề của các ñồ thị.
- c) Tìm ma trận liên thuộc của các ñồ thị.3.2.
- Hợp của 2 ñồ thị ñơn G1 = (X1, U1) và G2 = (X2, U2) là một ñồ thị, ký hiệu G1∪G2 =(X, U) với X = X1∪X2.
- Hãy xét xem các cặp ñồ thị sau có ñẳng cấu không? a) b) c) d) e)Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc .
- của các ñồ thị: Kn,Km,n, Cn, Wn, Qn.4.
- ðịnh nghĩa ñồ thị con, ñồthị bộ phận.
- Nêu thuật toán tìmtập ổn ñịnh ngoài cực tiểu của ñồ thị.
- ðịnh nghĩa sắc số của ñồ thị.
- Nhận biết ñồ thị Euler 1.3.
- Nhận biết ñồ thị nửa Euler 1.4.
- Nhận biết ñồ thị Hamilton 2.3.
- Nhận biết ñồ thị không phẳng1.
- ðồ thị có chu trình Euler gọi là ñồ thị Euler.
- Các ñồ thị G2 và H2 là các ñồ thịnửa Euler (Hình 1).Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc G1 G2 H1 H2 Hình 1.
- Các ñồ thị Euler (G1, H1) và nửa Euler (G2, H2)1.2.
- Kiểm tra tính liên thông của ñồ thị.
- Thí dụ 1: Xét ñồ thị ở hình 3.
- ðồ thị có chu trình Hamilton gọi là ñồ thị Hamilton.
- Thí dụ: Xét ñồ thị trong hình 10a.
- 1) thì G không phải là ñồ thị Hamilton.
- Vậy ñồ thị ñã cho không có chu trình Hamilton.
- Cách biểu diễn như vậyñược gọi là biểu diễn phẳng của ñồ thị.Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc Thí dụ: ðồ thị phẳng (ba cách vẽ của ñồ thị K4) ðồ thị không phẳng Hình 16.
- Trước hết chúngta nghiên cứu phép biến ñổi ñó.Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc Cho ñồ thị G, nếu bỏ ñi cạnh (x,y) của G và thêm vào ñỉnh z cùng hai cạnh (x,z) và(z,y) ñược một ñồ thị mới G'.
- Vậy ñồ thị Petersen là không phẳng.
- Tìm số cạnh và số mặt của ñồ thị.
- ðịnh nghĩa ñồ thị phẳng.
- Khái niệm ñồ thị ñồng phôi và phát biểu ñịnh lý Kuratowski ñể nhận biết ñồ thịkhông phẳng.Trường ðại học Nông nghiệp Hà Nội – Giáo trình Giáo trình Toán Rời rạc CHƯƠNG 5.
- Cây khung (cây bao trùm) của ñồ thị 4.1.
- ðiều kiện ñồ thị có cây khung 4.3.
- ðịnh nghĩa: Cho ñồ thị vô hướng G = (X, U) với N(X.
- Hình 12 là 3 cây khung của một ñồ thị (ñồ thị G).4.2.
- ðịnh nghĩa: Tập các chu trình: Ω = {C | C = C(X, V∪{u}, u∈ U \ V}gọi là hệ chu trình ñộc lập hay hệ chu trình cơ bản của ñồ thị liên thông G = (X,U), trongñó T = (X,V) là cây khung của ñồ thị G.
- Nếu G = (X, U) là ñồ thị vô hướng liên thông có N(X.
- Số µ(G) gọi là chu số của ñồ thị.
- Tìm cây khung T của ñồ thị.
- ñồ thị rỗng có n ñỉnh là các ñỉnh của G.
- Giả sử tồn tại cây khung S của ñồ thị mà l(S.
- Ouput: Cây khung nhỏ nhất T của ñồ thị.
- Cây khung nhỏ nhất của ñồ thị l(T.
- Gọi ω là chu trình có trong ñồ thị (X, V1∪{uk.
- Cho ñồ thị G = (X,U) với X = {x2, x3.
- Là ñồ thị liên thông.5.14.
- Bài toán ñường ñi ngắn nhất trong ñồ thị 1.1.
- Giả sử x, y là 2 ñỉnh của ñồ thị G.
- Ký hiệu bán kínhcủa ñồ thị G là r(G), ta có: r(G.
- Thí dụ: Xét ñồ thị trong hình 4.
- ðường kính của ñồ thị: d0 = 25 (ñó là ñộ dài của ñường ñi x1x2x3x4).3.
- Gọi H là tập hợp mọi chu trình Hamilton (hành trình) có trong ñồ thị.
- Kiểm tra tính liên thông của một ñồ thị.
- Lý thuyết ñồ thị và ứng dụng

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt