zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán học rời rạc: Phần 2

Chia sẻ: Minh Vũ | Ngày: | Loại File: PPT | Số trang:28

Báo xấu

112
lượt xem 7
download

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

Bài giảng "Toán học rời rạc: Phần 2" giới thiệu tới người đọc các nội dung: Phép đếm (nguyên lý cộng, nhân và bù trừ; giải tích tổ hợp, nguyên lý Dirichlet, công thức đệ quy), lý thuyết đồ thị (đại cương, đồ thị liên thông, đường đi ngắn nhất, cây khung trọng lượng tối tiểu, luồng cực đại), số học. Mời các bạn cùng tham khảo.

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 Toán học rời rạc: Phần 2

TOÁN HỌC RỜI RẠC PHẦN 2 DISCRETE MATHEMATICS PART TWO
NỘI DUNG 1. PHÉP ĐẾM a. Nguyên lý cộng, nhân & bù trừ b. Giải tích tổ hợp c. Nguyên lý Dirichlet d. Công thức đệ quy 2. LÝ THUYẾT ĐỒ THỊ a. Đại cương b. Đồ thị liên thông c. Đường đi ngắn nhất d. Cây khung trọng lượng tối tiểu e. Luồng cực đại 2. SỐ HỌC a. Lý thuyết chia hết b. Lý thuyết đồng dư 2
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ỢP – S là một tập hợp hữu hạn, |S| = m – Số các tập hợp con của S = 2m m m! – Số các tập con n phần tử của S (n m) = n ( m n)! n! – 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! 3
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ẻ? 4
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? 5
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ạnh • Cạ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 6
LÝ THUYẾT ĐỒ THỊ (2) – BIỂU DIỄN ĐỒ THỊ • Ma trận đỉnhcạnh • Ma 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, …, n1: vi vi+1 • Chu trình: v0 = vn • Chu trình sơ cấp: i=1, …, n1: vi vi+1 – ĐỒ THỊ LIÊN THÔNG • Đồ thị vô hướng liên thông: u, v V, đường đi giữa u, v • Thà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ớp • Giải thuật A2 7
LÝ THUYẾT ĐỒ THỊ (3) Đồ thị có hướng • G=(V, C), V=tập các đỉnh, C=tập các cung (v1, v2), v1, v2 E • Khuyên • Đỉnh cô lập • Đỉnh treo, cung treo: mút cuối của chỉ một cung • Nử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 8
LÝ THUYẾT ĐỒ THỊ (4) – BIỂU DIỄN ĐỒ THỊ • Ma trận đỉnhcung: 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) = w • Danh 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, …, n1: vi vi+1 • Chu trình: v0 = vn • Chu trình sơ cấp: chu trình & i=1, …, n1: 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 u • Thà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} 9
LÝ THUYẾT ĐỒ THỊ (7) • ĐỒ THỊ EULER – G=(V, E) hữu hạn, liên thông – Đường đi Euler, chu trình Euler – Đồ thị Euler, nửa Euler – Định lý Euler • Bậc mỗi đỉnh 2, đồ thị có chu trình • G là đồ thị Euler khi và chỉ khi bậc mỗi đỉnh là chẵn • G 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) 10
LÝ THUYẾT ĐỒ THỊ (8) • ĐỒ THỊ HAMILTON – Đường đi Hamilton – Chu trình Hamilton – Đồ thị Hamilton – Đồ thị nửa Hamilton – Cá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 11
ĐƯỜNG ĐI NGẮN NHẤT • BÀI TOÁN • GiẢI THUẬT MOOREDIJKSTRA – (w(i), p(i)) – Điều chỉ w(i) và p(i) mỗi khi triển khai một đỉnh k • t= w(i) • w(i) = min{ w(i), w(k)+l(k, i) } • Nếu t > w(i): p(i)=k • DAG – Đỉnh gốc – Hạng của một đỉnh = đường đi dài nhất từ gốc 12
CÂY & CÂY CÓ HƯỚNG • Định nghĩa – Cây – Rừng • CÂY KHUNG TRỌNG LƯỢNG NHỎ NHẤT – Bài toán – Giải thuật Kruskal – Giải thuật Prim 13
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 ra • Tồn tại duy nhất một đỉnh thu t, không có cung ra, chỉ có cung vào • Mỗ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 cung • Nế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à 0 – Luồng trong mạng • G = (V, A) là một mạng • Ánh xạ f: A R+ được gọi là một luồng trong mạng G khi • Giớ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 f ( u, v ) f (v, x ) ( u,v ) A (v, x ) A 14
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 f ( s, v ) f ( x, t ) val ( f ) ( s ,v ) A ( x ,t ) A Được gọi là giá trị của luồng trên mạng – Bà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) max val(f) f ( s, v ) f ( x, t ) ( s ,v ) A ( x ,t ) A • LÁT CẮT VÀ SỰ TĂNG LUỒNG – Lát cắt: • G = (V, A) là một mạng, X0 V, Y0 = V – X0 • Lá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 15
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 c ( X 0 , Y0 ) c ( u, v ) u X 0 , 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ất – Sự 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
LUỒNG CỰC ĐẠI (4) • Cung thuận: (u, v) Af, (u, v) A • Cung nghịch: (u, v) Af, (u, v) A • Đường tăng luồng: đường đi trong Gf từ s đến t • Sự tăng luồng: P = { s=v0, v1, …, vk=t } là đường tăng luồng >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ận – g(u, v) = f(u, v) nếu (u, v) là cung thuộc P và là cung nghịch – G(u, v) = f(u, v) nếu (u, v) không thuộc P • f là luồng trong G = (V, A) Các mệnh đề sau là tương đương: – f là luồng cực đại – Khô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ý FordFulkerson: 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 17
LUỒNG CỰC ĐẠI (4) – Thuật toán FordFulkerson: • 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ãn • B1: 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 18
LUỒNG CỰC ĐẠI (4) • B3: Lặp lại B2 cho đến khi – Hoặc đỉnh thu được gán nhãn t : [ y, (t) ]: chuyển sang B4 – Hoặ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ất • B4: đặt x = t : [ y, (t) ], chuyển sang B5 • B5 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 19
SỐ HỌC (1) • CHIA HẾT & CHIA CÓ DƯ • ƯỚC CHUNG LỚN NHẤT, BỘI CHUNG NHỎ NHẤT – Ưcln – Nguyên tố cùng nhau – Nguyên tố sánh đôi – Cá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 a ( a1 , a2 ,..., an ) ( , ,..., n ) d d d d a1 a2 an • (a1, a2, …, an) = d thì ( , ,..., ) 1 d d d • Nếu c | ab , (a, c)=1 thì c | b • Nếu b | a , c | a , (b, c) = 1 thì bc | a • Nếu (a, b)=1 thì (ac, b) = (c, b) 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.