zunia.vn

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

zunia.vn

» Khoa Học Tự Nhiên

BÀI TẬP - Toán rời rạc và Nhập môn lý thuyết đồ thị

Chia sẻ: Vu Nguyen | Ngày: | Loại File: PDF | Số trang:29

Báo xấu

503
lượt xem 151
download

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

Với mỗi trường hợp sau, vẽ các mô hình đồ thị biểu diễn các đường bay và nói rõ về loại đồ thị được dùng. Trong đó lịch bay mỗi ngày như sau: - Từ TP.HCM: có một chuyến đến Hà Nội, một chuyến đến Đà Nẵng, một chuyến đến Phú Quốc, một chuyến đến Nghệ An, một chuyến đến Hải Phòng; - Từ Hà Nội: có hai chuyến đến TP.HCM, một chuyến đến Đà Nẵng, một chuyến đến Nghệ An, một chuyến đến Hải Phòng; - Từ Đà Nẵng: có một chuyến đến Hải Phòng, hai chuyến bay đến TP.HCM; một chuyến đến Hà Nội....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: BÀI TẬP - Toán rời rạc và Nhập môn lý thuyết đồ thị

BÀI TẬP Toán rời rạc và Nhập môn lý thuyết đồ thị Tài liệu học tập dành cho sinh viên Khoa CNTT - UEF Phiên bản 1.0 2008
MỤC LỤC PHẦN 1 BÀI TẬP...........................................................................................3 CHƯƠNG 1 QUAN HỆ .......................................................................................4 A. Bài tập củng cố lý thuyết..........................................................................4 1Quan hệ và các tính chất của nó................................................................4 2Quan hệ n-ngôi và ứng dụng......................................................................4 B. Bài tập thực hành trên máy tính.............................................................4 C. Viết tiểu luận.............................................................................................4 CHƯƠNG 2 ĐỒ THỊ ...........................................................................................5 A. Bài tập củng cố lý thuyết..........................................................................5 1Giới thiệu......................................................................................................5 2Các thuật ngữ đồ thị....................................................................................6 3Biểu diễn các đồ thị và sự đẳng cấu đồ thị ...............................................9 4Tính liên thông...........................................................................................10 5Các đường đi Euler và Hamilton.............................................................12 6Các bài toán đường đi ngắn nhất.............................................................14 B. Bài tập thực hành trên máy tính...........................................................15 C. Viết tiểu luận...........................................................................................16 CHƯƠNG 4 ĐỘ PHỨC TẠP TÍNH TOÁN .....................................................16 A. Bài tập củng cố lý thuyết........................................................................16 1Dãy và phép tính tổng...............................................................................16 2Độ tăng của hàm........................................................................................17 3Thuật toán..................................................................................................18 4Độ phức tạp của thuật toán......................................................................19 1
5Các kỹ thuật thiết kế thuật toán..............................................................20 6Độ phức tạp thuật toán qua các ví dụ......................................................20 B. Bài tập thực hành trên máy tính...........................................................21 C. Viết tiểu luận...........................................................................................22 PHẦN 2 LỜI GIẢI VÀ HƯỚNG DẪN.........................................................................23 CHƯƠNG 1 QUAN HỆ .....................................................................................24 A. Bài tập củng cố lý thuyết........................................................................24 1Quan hệ và các tính chất của nó..............................................................24 2Quan hệ n-ngôi và ứng dụng....................................................................24 B. Bài tập thực hành trên máy tính...........................................................24 C. Viết tiểu luận...........................................................................................24 CHƯƠNG 2 ĐỒ THỊ .........................................................................................25 A. Bài tập củng cố lý thuyết........................................................................25 1Giới thiệu....................................................................................................25 2Tiêu đề mục 2.............................................................................................26 B. Bài tập thực hành trên máy tính...........................................................26 C. Viết tiểu luận...........................................................................................26 2
Chương 2. Quan hệ PHẦN 1 BÀI TẬP 3
Chương 2. Quan hệ CHƯƠNG 1 QUAN HỆ A. Bài tập củng cố lý thuyết 1 Quan hệ và các tính chất của nó Bài 1.1. Nội dung Bài 1.2. Nội dung …. 2 Quan hệ n-ngôi và ứng dụng Bài 2.1. Nội dung Bài 2.2. Nội dung …. B. Bài tập thực hành trên máy tính Bài 1. Nội dung Bài 2. Nội dung …. C. Viết tiểu luận Bài 1. Nội dung Bài 2. Nội dung …. 4
Chương 2. Quan hệ CHƯƠNG 2 ĐỒ THỊ A. Bài tập củng cố lý thuyết 1 Giới thiệu Bài 1.1. Với mỗi trường hợp sau, vẽ các mô hình đồ thị biểu diễn các đường bay và nói rõ về loại đồ thị được dùng. Trong đó lịch bay mỗi ngày như sau: - Từ TP.HCM: có một chuyến đến Hà Nội, một chuyến đến Đà Nẵng, một chuyến đến Phú Quốc, một chuyến đến Nghệ An, một chuyến đến Hải Phòng; - Từ Hà Nội: có hai chuyến đến TP.HCM, một chuyến đến Đà Nẵng, một chuyến đến Nghệ An, một chuyến đến Hải Phòng; - Từ Đà Nẵng: có một chuyến đến Hải Phòng, hai chuyến bay đến TP.HCM; một chuyến đến Hà Nội; - Từ Nghệ An: có một chuyến đến Hà Nội, một chuyến đến TP.HCM; - Từ Hải Phòng: có một chuyến đến Hà Nội, một chuyến đến TP.HCM, và một chuyến đến Đà Nẵng; - Từ Phú Quốc: có một chuyến đến TP.HCM. a) Đồ thị biểu diễn các thành phố có chuyến bay giữa chúng. b) Đồ thị biểu diễn số chuyến bay hoạt động giữa các thành phố, cộng với một khuyên biểu thị chuyến du lịch đặc biệt ngắm cảnh thành phố, cất và hạ cánh tại Phú Quốc. c) Đồ thị biểu diễn đầy đủ thông tin về hướng bay và số chuyến bay giữa các thành phố. Bài 1.2. Xác định xem đồ thị nào sau đây là đồ thị đơn, đa đồ thị, đồ thị có hướng. 5
Chương 2. Quan hệ a) b) c) d) Bài 1.3. Trong trận đấu vòng tròn, đội H thắng đội G, đội C, và đội A; đội G thắng đội A và đội C; đội C thắng đội A. Hãy mô hình hóa kết quả này bằng một đồ thị có hướng. …. 2 Các thuật ngữ đồ thị Bài 2.1. Xác định số lượng các đỉnh, số lượng các cạnh, và bậc của các đỉnh trong các đồ thị sau. Cho biết đỉnh nào là đỉnh cô lập, đỉnh nào là đỉnh treo. a b c e d f a) 6
Chương 2. Quan hệ a b e d c b) a b c d i g e f h c) Bài 2.2. Tìm tổng các bậc của các đỉnh trong các đồ thị ở các Bài 2.1, và kiểm chứng rằng nó bằng hai lần số các cạnh trong đồ thị. Bài 2.3. Có thể tồn tại một đồ thị đơn có 15 đỉnh, mỗi đỉnh có bậc bằng 5 không? Tại sao? Bài 2.4. Trong một buổi chiêu đãi, mọi người đều bắt tay nhau. Chứng tỏ rằng tổng số người được bắt tay là một số chẵn. Giả sử không ai tự bắt tay mình. Bài 2.5. Xác định số đỉnh, số cạnh, số bậc vào và số bậc ra của mỗi đỉnh đối với đồ thị có hướng sau. a b d c 7
Chương 2. Quan hệ Bài 2.6. Hãy xác định tổng các bậc vào và tổng các bậc ra các đỉnh của đồ thị trong bài 2.5 một cách trực tiếp. Chứng tỏ rằng chúng đều bằng tổng các cạnh của đồ thị. Bài 2.7. Đồ thị sẽ có bao nhiêu cạnh nếu nó có các đỉnh bậc 4, 3, 3, 2, 2. Vẽ một đồ thị như vậy. Bài 2.8. Có tồn tại đồ thị đơn chứa năm đỉnh với các bậc sau đây? Nếu có hãy vẽ đồ thị đó. a) 3, 3, 3, 3, 2. b) 1, 2, 3, 4, 5. c) 1, 2, 3, 4, 4. Bài 2.9. Vẽ tất cả các đồ thị con của đồ thị sau. a b c d Bài 2.10. Tìm hợp của các cặp đồ thị đơn sau a f b f b e c d a) d 8
Chương 2. Quan hệ a f b a b e e c d c g d b) 3 Biểu diễn các đồ thị và sự đẳng cấu đồ thị Bài 3.1. Dùng danh sách kề biểu diễn các đồ thị sau. a b a b c d d c a) b) Bài 3.2. Biểu diễn các đồ thị trong bài 3.1 bằng ma trận kề. Bài 3.3. Vẽ các đồ thị ứng với ma trận kề được cho như sau.  0 0 1 1  1 1 1 0  0 1 0  0   0 1 0  0 0 1 0 a)  1 0 1  b)   c)    1 1 0 1  1 0 1 0  0 1 0      1 1 1 0  1 1 1 0 Bài 3.4. Dùng ma trận liên kết để biểu diễn các đồ thị trong Bài 3.1. Bài 3.5. Xác định xem các cặp đồ thị đã cho có là đẳng cấu không. 9
Chương 2. Quan hệ v1 v2 u1 u2 u3 u4 u5 v3 a) v4 v5 4 Tính liên thông Bài 4.1. Các danh sách đỉnh sau đây có tạo nên đường đi trong đồ thị bên dưới hay không? Đường đi nào là đơn? Đường đi nào là chu trình? Độ dài của các đường đi này là bao nhiêu? a) (a, e, b, c, b) b) (a, e, a, d, b, c, a) c) (e, b, a, d, b, e) 10
Chương 2. Quan hệ d) (c, b, d, a, e, c) Bài 4.2. Các danh sách đỉnh sau đây có tạo nên đường đi trong đồ thị bên dưới hay không? Đường đi nào là đơn? Đường đi nào là chu trình? Độ dài của các đường đi này là bao nhiêu? a) (a, b, e, c, b) b) (a, d, a, d, a) c) (a, d, b, e, a) d) (a, b, e, c, b, d, a) Bài 4.3. Xác định xem các đồ thị đã cho có liên thông không. Bài 4.4. Có bao nhiêu thành phần liên thông trong các đồ thị ở các Bài tập 4.3? Tìm các thành phần liên thông đó. Bài 4.5. Tìm tất cả các đỉnh cắt và cạnh cắt của đồ thị. 11
Chương 2. Quan hệ 5 Các đường đi Euler và Hamilton Bài 5.1. Xác định xem có tồn tại chu trình Euler trong các đồ thị sau hay không. Vẽ chu trình đó khi nó tồn tại. Bài 5.2. Xác định xem các đồ thị trong Bài 5.1 có đường đi Euler không. Vẽ các đường đi đó nếu có. Bài 5.3. Xác định xem có thể vẽ các bức tranh sau bằng một nét liền, không nhấc bút lên khỏi mặt giấy không? Bài 5.4. Xác định sự tồn tại chu trình Euler trong các đồ thị có hướng sau. Vẽ các chu trình này nếu chúng tồn tại. 12
Chương 2. Quan hệ Bài 5.5. Xác định xem đồ thị có hướng trong Bài 5.4 có đường đi Euler hay không. Vẽ các đường đi Euler này nếu có. Bài 5.6. Xác định đồ thị đã cho có chứa chu trình Hamilton hay không. Nếu có hãy tìm một chu trình như thế. Nếu không có hãy giải thích lý do vì sao không tồn tại. 13
Chương 2. Quan hệ Bài 5.7. Đồ thị trong Bài 5.6 có đường đi Hamilton không? Nếu có, hãy tìm đường đó. Nếu không có, cho biết lý do tại sao không tồn tại một đường đi như vậy. 6 Các bài toán đường đi ngắn nhất Bài 6.1. Tìm chiều dài của đường đi ngắn nhất giữa a và z trong đồ thị có trọng số sau đây 14
Chương 2. Quan hệ Bài 6.2. Tìm độ dài của đường đi ngắn nhất giữa các cặp đỉnh sau đây trong các đồ thị có trọng số ở Bài 6.1. a) a và d b) a và f c) c và f d) b và z B. Bài tập thực hành trên máy tính Viết các chương trình với các đầu vào và đầu ra như sau: Bài 1. Một đồ thị cho trước bởi danh sách kề. Xác định bậc các đỉnh của đồ thị này. Bài 2. Một đồ thị cho trước bởi danh sách kề. Xác định xem đồ thị này có là đồ thị lưỡng phân hay không? Bài 3. Một đồ thị cho trước bởi danh sách kề. Xây dựng ma trận kề mô tả đồ thị đó. Bài 4. Một đồ thị cho trước bởi ma trận kề. Liệt kê các cạnh của đồ thị này. Bài 5. Một đồ thị cho trước bởi ma trận liên kết. Liệt kê các cạnh của đồ thị này. 15
Chương 2. Quan hệ C. Viết tiểu luận Bài 1. Tìm hiểu nguồn gốc và sự phát triển của lý thuyết đồ thị trước thế kỷ 20. Bài 2. Tìm hiểu một số thuật toán hiện có để xác định tính đẳng cấu của hai đồ thị, cùng với độ phức tạp tính toán của những thuật toán này. Hiện nay, thuật toán nào trong số đó có hiệu quả cao nhất. Bài 3. Tìm hiểu bài toán người đưa thư (travelling salesman problem). Bài 4. Tìm hiểu bài toán tô màu đồ thị (graph coloring). CHƯƠNG 4 ĐỘ PHỨC TẠP TÍNH TOÁN A. Bài tập củng cố lý thuyết 1 Dãy và phép tính tổng Bài 1.1. Tìm số hạng a8 của dãy {an} nếu an bằng a) 2n-1 b) 7 c) 1 + (– 1)n d) –(–2)n Bài 1.2. Tìm các số hạng a0, a1, a2, và a3 của dãy {an} với an bằng a) (–2)n b) 3 c) 7 + 4n d) 2n + (–2)n Bài 1.3. Liệt kê 10 số hạng đầu của các dãy sau: a) Dãy có được bằng cách bắt đầu từ 10 và các số hạng sau là các số hạng đứng trước trừ đi 3. b) Dãy có số hạng thứ n là tổng của n số nguyên dương đầu tiên. c) Dãy có số hạng thứ n là 3n – 2n. 16
Chương 2. Quan hệ Bài 1.4. Tìm ít nhất ba dãy khác nhau bắt đầu với các số hạng 1, 2, 4 và các số hạng sau được tạo ra bởi một công thức hay quy luật đơn giản nào đó. Bài 1.5. Đối với mỗi liệt kê các số nguyên sau đây, hãy tìm một công thức hay luật đơn giản để tạo ra các số hạng của dãy số nguyên bắt đầu với liệt kê đã cho. a) 3, 6, 11, 18, 27, 38, 51, 66, 83, 102, … b) 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, … c) 1, 10, 11, 100, 101, 111, 1000, 1001, 1010, 1011, … Bài 1.6. Tính giá trị của các tổng sau đây, với S = {1, 3, 5, 7}. a) j jS b) j jS 2 c) j 1 d) 1 . jS jS Bài 1.7. Tính giá trị của các tổng sau: 8 8 8 a)   1  ( 1)  b)   3  2   2  2j  . j j j j1 d) j0 j0 j0 Bài 1.8. Tính các tổng kép sau đây: 3 2 3 2 3 2 a)  (i  j) b)  (3i  2 j) c)  j . i 1 j1 i 0 j0 i 1 j0 Bài 1.9. Tính tổng 200 k k 99 3 2 Độ tăng của hàm Bài 2.1. Xác định các hàm sau đây có phải là O(x2) hay không? a) f(x) = 17x + 11 b) f(x) = x2 + 1000. c) f(x) = x log x d) f(x) = x4/2 Bài 2.2. Dùng định nghĩa f(x) là O(g(x)) để chứng minh 2x + 17 là O(3x). 17
Chương 2. Quan hệ x 3  2x Bài 2.3. Chứng minh rằng là O(x2). 2x  1 Bài 2.4. Tìm số nguyên n nhỏ nhất để có f(x) là O(xn) đối với các hàm sau: x4  x2  1 a) f(x) = 2x2 + x3 log x b) f(x) = . x4  1 Bài 2.5. Chứng minh rằng x3 là O(x4) nhưng x4 không phải là O(x3). Bài 2.6. Xác định xem x3 có là O(g(x)) hay không đối với các hàm g sau: a) g(x) = x2 b) g(x) = x3/2 c) g(x) = x2 + x3 d) g(x) = x2 + x4 Bài 2.7. Chứng minh rằng nếu f(x) là O(x) thì f(x) cũng là O(x2). Bài 2.8. Cho k là một số nguyên dương. Chứng minh rằng 1k + 2k + … + nk là O(nk+1). Bài 2.9. Đối với từng hàm trong bài 2.1, hãy xác định hàm đó có là Ω(x 2) không? Và có là Θ(x2) không? Bài 2.10. Chứng minh rằng a) 3x + 7 là Θ(x) b) 2x2 + x – 7 là Θ(x2) 3 Thuật toán Bài 3.1. Xây dựng thuật toán tính xn, với x là số thực và n là số nguyên. (Gợi ý: trước hết đưa ra thủ tục tính xn khi n không phải số âm bằng cách nhân liên tục với x, bắt đầu từ 1. Sau đó mở rộng thủ tục này và dùng quan hệ x-n = 1/xn để tính xn khi n âm.) Bài 3.2. Trình bày thuật toán chỉ dùng các lệnh gán để đổi chỗ bộ ba (x, y, z) thành (y, z, x). Cần dùng tối thiểu bao nhiêu lệnh gán? Bài 3.3. Liệt kê tất cả các bước cần tiến hành để tìm (nhị phân) số 7 trong dãy số đã sắp tăng 1, 3, 4, 5, 6, 8, 9, 11. Bài 3.4. Trình bày thuật toán tìm số nguyên nhỏ nhất trong một dãy hữu hạn các số tự nhiên. 18

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.