Bài giảng Toán học rời rạc

TOÁN HỌC RỜI RẠCPHẦN 2 DISCRETE MATHEMATICSPART TWONỘI DUNGPHÉP ĐẾMNguyên lý cộng, nhân & bù trừGiải tích tổ hợpNguyên lý DirichletCông thức đệ quyLÝ THUYẾT ĐỒ THỊĐại cươngĐồ thị liên thôngĐường đi ngắn nhấtCây khung trọng lượng tối tiểuLuồng cực đạiSỐ HỌCLý thuyết chia hếtLý thuyết đồng dư*PHÉP ĐẾM (1)NGUYÊN LÝ CỘNG, NHÂN, BÙA là một tập hợp, ký hiệu |A| bản số của A, trong trường hợp A là tập hữu hạn, |A| chính là số phần tử của A|A  B|=|A| + |B| -|A  B| nếu A  B =  thì |A  B|=|A| + |B| |A x B| = |A| * |B|BA: |A – B| = |A| - |B|GIẢI TÍCH TỔ HỢPS là một tập hợp hữu hạn, |S| = mSố các tập hợp con của S = 2m Số các tập con n phần tử của S (n  m) = Một bộ n phần tử cũa S: (a1, a2, , an)  Sn số các bộ n phần tử của S = mn Số các hoán vị của một dãy m phần tử = m! *PHÉP ĐẾM (2)CÁC VÍ VỤTrong một phòng họp có n người, mỗi người bắt tay với mỗi người khác đúng một lần. Số bắt tay?Dùng n bit để biểu diễn nhị phân cho các số nguyên không âm, số số nguyên có thể được biểu diễn?Có bao nhiêu số thập phân có 6 chữ số? Bao nhiêu số thập phân có số chữ số nhỏ hơn sáu?Có bao nhiêu cách sắp xếp chỗ ngồi cho n người xung quanh một chiếc bàn họp tròn? Bây giờ giả sử ông chủ tịch cuộc họp được sắp ngồi ở một ghế xác định, có bao nhiêu cách sắp xếp chỗ ngồi cho các người còn lại?Có bao nhiêu dãy số nguyên dương, có tổng bằng n?Có bao nhiêu dãy k số nguyên dương có tổng bằng n?Có bao nhiêu cách phân phát n món quà (khác nhau đô một) cho k đứa trẻ?*PHÉP ĐẾM (3)Có bao nhiêu cách sắp xếp 8 các quân xe trong bàn cờ 8x8 sao cho không quân xe nào « bị tấn công »?Cây nhị phân chiều cao h có nhiều nhất bao nhiêu nút lá?Trong mặt phẳng, cho n đường thẳng đôi một cắt nhau và không có ba đường thẳng nào đồng quy. n đường thẳng này chia mặt phẳng thành bao nhiêu miền?Cho n giác lồi, không có ba đường chéo nào đồng quy, các đường chéo của đa giác chia da giác thành bao nhiêu miền? *LÝ THUYẾT ĐỒ THỊ (1)CÁC ĐỊNH NGHĨA, KHÁI NIỆM Đồ thị (vô hướng)G=(V, E), V = tập các đỉnh, E=tập các cạnh v1v2, v1, v2  E Đỉnh cô lập: đỉnh không có cạnh đi quaĐỉnh treo: chỉ thuộc một cạnh duy nhất (cạnh treo)Đa đồ thị: tồn tại nhiều hơn 1 cạnh nối hai đỉnh đồ thị đơn: tồn tại nhiều nhất một cạnh nối hai đỉnhĐỉnh kề: chung cạnhCạnh kề: chung đỉnhĐồ thị đầy đủ: mọi cặp đỉnh (phân biệt) đều có cạnh nốiĐồ thị con: AV, EA={(v1, v2)  E | v1, v2 A}, GA=(A, EA) Đồ thị bộ phận: C  E, GC=(E, C) Đồ thị bộ phận con*LÝ THUYẾT ĐỒ THỊ (2)BIỂU DIỄN ĐỒ THỊMa trận đỉnh-cạnhMa trận kềMa trận trọng sốDanh sách đỉnh kềĐƯỜNG ĐI & CHU TRÌNHĐường đi: u, v  V, u=v0, v1, , vn=v sao cho vivi+1  EĐường đi sơ cấp: tập i=0, , n-1: vi  vi+1 Chu trình: v0 = vnChu trình sơ cấp: i=1, , n-1: vi  vi+1 ĐỒ THỊ LIÊN THÔNGĐồ thị vô hướng liên thông: u, v  V, đường đi giữa u, vThành phần liên thông: Giải thuật A1Đỉnh khớp, cạnh eoĐồ thị liên thông bậc 2: Liên thông, bậc  3, không có đỉnh khớpGiải thuật A2*LÝ THUYẾT ĐỒ THỊ (3) Đồ thị có hướngG=(V, C), V=tập các đỉnh, C=tập các cung (v1, v2), v1, v2  EKhuyênĐỉnh cô lậpĐỉnh treo, cung treo: mút cuối của chỉ một cungNửa bậc trong (vào): d-(x)Nửa bậc ngoài (ra): d+(x)Bậc của đỉnh: d(x) = d- (x) + d+(x)+(A) = { (i, j)| iA, j A }-(A) = { (i, j)| jA, i A }(A) = +(A)  -(A) Đa đồ thị, đồ thị đơnĐỉnh kề, cung kềĐồ thị có hướng đối xứng, phi đối xứng*LÝ THUYẾT ĐỒ THỊ (4)BIỂU DIỄN ĐỒ THỊMa trận đỉnh-cung: c=(v, .): M(v, c)=1, c=(., v): M(v, c)=-1 Ma trận kề: (u, v)  C: M(u, v) = 1 Ma trận trọng số: (u, v)  C, trọng số w: M(u, v) = wDanh sách đỉnh kềĐƯỜNG ĐI & CHU TRÌNHĐường đi: u, v  V, u=v0, v1, , vn=v sao cho (vi, vi+1)  CĐường đi sơ cấp: tập i=0, , n-1: vi  vi+1 Chu trình: v0 = vnChu trình sơ cấp: chu trình & i=1, , n-1: vi  vi+1 ĐỒ THỊ LIÊN THÔNGĐồ thị có hướng liên thông: đồ thị vô hướng tương ứng liên thôngĐồ thị có hướng liên thông một chiều: u, v  V, đường đi từ u đến v hoặc từ v đến uĐồ thị có hướng liên thông mạnh: u, v  V, đường đi từ u đến v và đường đi từ v đến uThành phần liên thông: quan hệ R={(u, u)| u E} {(u, v) | đường đi từ u đến v và đường đi từ v đến u} *LÝ THUYẾT ĐỒ THỊ (7)ĐỒ THỊ EULERG=(V, E) hữu hạn, liên thôngĐường đi Euler, chu trình EulerĐồ thị Euler, nửa EulerĐịnh lý EulerBậc mỗi đỉnh  2, đồ thị có chu trìnhG là đồ thị Euler khi và chỉ khi bậc mỗi đỉnh là chẵnG là đồ thị nửa Euler khi và chỉ khi G có không quá hai đỉnh bậc lẻG có hướng, liên thông mạnh là Euler khi và chỉ khi xE: d-(x)=d+(x)*LÝ THUYẾT ĐỒ THỊ (8)ĐỒ THỊ HAMILTONĐường đi HamiltonChu trình HamiltonĐồ thị HamiltonĐồ thị nửa HamiltonCác định lý:Đồ thị đơn vô hướng bậc n > 2, nếu x  E, d(x)  n/2 thì là đồ thị HamiltonĐồ thị có hướng liên thông bậc n, nếu x  E, d-(x), d+(x)  n/2 thì là đồ thị HamiltonĐồ thị có hướng, đầy đủ là đồ thị nửa HamiltonĐồ thị có hướng, đầy đủ bậc > 2 là đồ thị HamiltonĐồ thị đấu loạiĐồ thị đấu loại là nửa HamiltonĐồ thị đấu loại liên thông là Hamilton*ĐƯỜNG ĐI NGẮN NHẤTBÀI TOÁNGiẢI THUẬT MOORE-DIJKSTRA(w(i), p(i))Điều chỉ w(i) và p(i) mỗi khi triển khai một đỉnh kt= w(i)w(i) = min{ w(i), w(k)+l(k, i) }Nếu t > w(i): p(i)=k DAGĐỉnh gốcHạng của một đỉnh = đường đi dài nhất từ gốc*CÂY & CÂY CÓ HƯỚNGĐịnh nghĩaCâyRừngCÂY KHUNG TRỌNG LƯỢNG NHỎ NHẤTBài toánGiải thuật KruskalGiải thuật Prim*LUỒNG CỰC ĐẠI (1)MẠNG:Đổ thị có hướng G = (V, A) là một mạng khi:Tồn tại duy nhất một đỉnh phát s, không có cung vào, chỉ có cung raTồn tại duy nhất một đỉnh thu t, không có cung ra, chỉ có cung vàoMỗi cung a được gắn với một giá trị không âm c(a), được gọi là băng thông của cungNếu không tồn tại cung từ u đến v, băng thông của (u, v) dược quy ước là 0Luồng trong mạngG = (V, A) là một mạngÁnh xạ f: A  R+ được gọi là một luồng trong mạng G khiGiới hạn của luồng: a  A: f(a)  c(a) (luồng của cung không vượt quá băng thông của cung)Điều kiện cân bằng luồng: v  V, v  s, v  t, tổng các luồng trên các cung vào v bằng các luồng trên các cung ra khỏi v*LUỒNG CỰC ĐẠI (2)Giá trị của luồng: Tổng luồng trên các cung xuất ra từ s bằng với tổng luồng trên các cung thu vào tại t Được gọi là giá trị của luồng trên mạngBài toán luồng cực đại trong mạng:Xác định luồng cực đại f (luồng có giá trị lớn nhất)LÁT CẮT VÀ SỰ TĂNG LUỒNGLát cắt: G = (V, A) là một mạng, X0  V, Y0 = V – X0Lát cắt (X0, Y0) là tập các cung (i, j) sao cho: nếu i  X0 thì j  Y0 nếu i  Y0 thì j  X0 Nếu điểm phát và điểm thu thuộc hai phần khác nhau của lát cắt, lát cắt được gọi là lát cắt tách*LUỒNG CỰC ĐẠI (3)Khả năng thông của lát cắt là tổng các băng thông của các cung (u, v) với u  X0, v  Y0 Lát cắt với khả năng thông nhỏ nhất được gọi là lát cắt hẹp nhấtSự tăng luồng trong mạng:Nếu f là một luồng, (X0, Y0) là một lát cắt thì: Val(f)  c(X0, Y0)Giá trị của luồng cực đại không vượt quá khả năng thông của lát cắt hẹp nhấtĐồ thị tăng luồng: f là một luồng trong G = (V, A) Đồ thị tăng luồng Gf = (V, Af) được xây dựng như sau:(u, v)  A: f(u, v)=0 thì (u, v)  Af với trọng số p(u, v) = c(u, v)(u, v)  A: f(u, v)=c(u, v) thì (u, v)  Af với trọng số p(u, v)=f(u, v)(u, v)  A: 0 0 là giá trị nhỏ nhất trong các trọng số của các cung trên P. Xây dựng ánh xạ g: Af  R+ như sau:g(u, v) = f(u, v) +  nếu (u, v) là cung thuộc P và là cung thuậng(u, v) = f(u, v) -  nếu (u, v) là cung thuộc P và là cung nghịchG(u, v) = f(u, v) nếu (u, v) không thuộc Pf là luồng trong G = (V, A) Các mệnh đề sau là tương đương:f là luồng cực đạiKhông tìm được đường tăng luồng P Tồn tại lát cắt (X0, Y0): Val(f) = c(X0, Y0)TÌM LUỒNG CỰC ĐẠIĐịnh lý Ford-Fulkerson: Giá trị của luồng cực đại bằng khả năng thông của lát cắt hẹp nhất*LUỒNG CỰC ĐẠI (4)Thuật toán Ford-Fulkerson:Gán nhãn: Mỗi đỉnh trong mạng thuộc vào một trong ba trạng thái:Chưa được gán nhãnĐã được gán nhãn nhưng chưa được duyệtĐã được gán nhãn và đã được duyệt Nhãn của một đỉnh y có dạng: y : [ x, (y) ] +x có nghĩa cần tăng luồng theo cung (x, y) -x có nghĩa cần giảm luồng theo cung (x, y)Khởi đầu tất cả các đỉnh đều chưa được gán nhãnB1: gán nhãn cho s : [+s, ]B2:Chọn một đỉnh x có nhãn nhưng chưa được duyệt, giả sử nhãn của x có dạng x : [ y, (x) ]Gãn nhãn cho mỗi ảnh u của x chưa được gán nhãn mà f(x, u) 0 v : [-x, (v) ] / (v) = min{ (x), f(v, x) }x được duyệt*LUỒNG CỰC ĐẠI (4)B3: Lặp lại B2 cho đến khiHoặc đỉnh thu được gán nhãn t : [ y, (t) ]: chuyển sang B4Hoặc không thể gán nhãn cho đỉnh thu t: thuật toán kết thúc. Đặt X0 tập các đỉnh được gán nhãn, Y0 tập các đỉnh không được gán nhãn, khi đó (X0, Y0) là lát cắt hẹp nhấtB4: đặt x = t : [ y, (t) ], chuyển sang B5B5 Nếu x có nhãn x : [+u, (x) ] tăng luồng trên cung (u, x) như sau: f(u, x) = f(u, x) + (t) Nếu x có nhãn x : [-u, (x) ] giảm luồng trên cung (x, u) như sau: f(x, u) = f(x, u) - (t) B6 Nếu x  s, đặt x = u quay lại B5. khác đi xóa tất cả các nhãn, quay lại B1 *SỐ HỌC (1)CHIA HẾT & CHIA CÓ DƯƯỚC CHUNG LỚN NHẤT, BỘI CHUNG NHỎ NHẤTƯclnNguyên tố cùng nhauNguyên tố sánh đôiCác tính chất:(a1, a2, , an) = d  x1, x2, , xn / a1x1 + a2x2 + +anxn=d m nguyên dương: (ma1, ma2, , man) =m (a1, a2, , an)d>0 là ước chung của a1, a2, , an thì (a1, a2, , an) = d thìNếu c | ab , (a, c)=1 thì c | bNếu b | a , c | a , (b, c) = 1 thì bc | aNếu (a, b)=1 thì (ac, b) = (c, b) *SỐ HỌC (2)Nếu (a, b)=1, (a, c)=1 thì (a, bc)=1Nếu a=pb + r (0  r 1, n phân tích thành tích của các số nguyên tố, sự phân tích đó là duy nhất (sai khác thứ tự nhân tử)Dạng phân tích chuẩn: , d | iff i: 0  i  i *SỐ HỌC (4)PHƯƠNG TRÌNH NGUYÊNax + by =cd=(a, b)Nếu d không là ước của c thì phương trình vô nghiệmNếu d | c thì nghiệm của phương trình có dạng:a1x1 + a2x2 + + anxn =bPhương trình có nghiệm (nguyên) iif các ai nguyên tố cùng nhauPhương trình bậc caoĐỒNG DƯa = b (mod m) iif dư của phép chia a cho m = dư của phép chia b cho m*Trong đó, x0, y0 là một nghiệm (nguyên) của phương trìnhSỐ HỌC (5)Quan hệ đồng dư là quan hệ tương đươngCác mệnh đề tương đương:a = b (mod m)a = b + mt(a-b) = 0 (mod m)Các tính chất:ai = bi (mod m) i=1, 2, , n thì (a1 + a2 + + an ) = (b1 + b2 + + bn) (mod m) a1a2an = b1b2 bn (mod m)a = b (mod m) thì (a+c) = (b+c) (mod m)a = b (mod m) thì a = (b +km) (mod m), (a+km) = b (mod m)a = b (mod m) thì an = bn (mod m)a = b (mod m) thì ac = bc (mod m)(c, m)=1, a = b (mod m) iif ac = bc (mod m)d = (a, b, m) thì (a/d) = (b/d) (mod (m/d))d=(a, b), (d, m)=1 thì (a/d) = (b/d) (mod m)a = b (mod mi) i=1, 2, , n thì a = b (mod [m1, m2, , mn]) *SỐ HỌC (6)a = b (mod m), d | m thì a = b (mod d)a = b (mod m), d | a , d | m thì d | ba = b (mod m) thì (a, m) = (b, m)VÀNH Zn PHƯƠNG TRÌNH ĐỒNG DƯ MỘT ẨNax = b (mod m)d=(a, m)Nếu d không là ước của b, phương trình vô nghiệmNếu d | b phương trình có đúng d nghiệm *x0 là một giá trị thỏa mãn phương trìnhSỐ HỌC (7)HỆ PHƯƠNG TRÌNH ĐỒNG DƯ BẬC NHẤT MỘT ẨNNếu m1, m2, , mn nguyên tố sánh đôi thì hệ có nghiệm duy nhất:M=[m1, m2, , mn ] = m1m2 mn Mi = M/mi (i=1, , n)Giải phương trình đồng dư Miy = ai (mod mi) (i=1, , n) tìm được nghiệm: y = Ni (mod mi)x=M1N1 + + MnNn (mod M) là nghiệm của hệ *SỐ HỌC (8)PHƯƠNG TRÌNH BẬC CAO MỘT ẨNf(x) = a0xn + a1xn-1 + + an = 0 (mod m)Phương trình tương đương với hệ:Giải phương trình f(x) = a0xn + a1xn-1 + + an = 0 (mod p) (*)  Giải phương trỉnh f(x) = a0xn + a1xn-1 + + an = 0 (mod p-1) (**)Giả sử phương trình có nghiệm x = x0 (mod p-1)Giải phương trình: f’(x0) t + f(x0)/p-1 = 0 (mod p-1)Gọi t = t0 (mod p-1) là nghiệm của phương trình Khi đó nghiệm của phương trình (*) là: x=x0 + t0 p-1 (mod p)**END OF PART TWO'S THEORY