Đề thi toán rời rạc

Tài liệu tham khảo ngân hàng Đề thi môn toán rời rạc II
Nội dung trích xuất từ tài liệu:
Đề thi toán rời rạc HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Km10 Đường Nguyễn Trãi, Hà Đông-Hà Tây Tel: (04).5541221; Fax: (04).5540587 Website: http://www.e-ptit.edu.vn; E-mail: dhtx@e-ptit.edu.vn NGÂN HÀNG ĐỀ THI Môn: TOÁN RỜI RẠC II Số tín chỉ : 3 SỬ DỤNG CHO NGÀNH CÔNG NGHỆ THÔNG TIN HỆ ĐẠI HỌC TỪ XA CHƯƠNG I: Những khái niệm cơ bản1/ Cho đồ thị G =, hãy cho biết đâu là tính chất đúng của đơn đồ thị vô hướng: a Giữa hai đỉnh bất kì i, j V có thể có nhiều hơn một cung nối; có kể đến thứ tự các đỉnh. b Giữa hai đỉnh bất kì i, j V có nhiều nhất một cung nối; có kể đến thứ tự các đỉnh. c Giữa hai đỉnh bất kì i, j V có nhiều nhất một cạnh nối; không kể đến thứ tự các đỉnh. d Giữa hai đỉnh bất kì i, j V có thể có nhiều hơn một cạnh nối; không kể đến thứ tự các đỉnh. 2/ Cho đồ thị G =, hãy cho biết đâu là tính chất đúng của đa thị vô hướng: a Giữa hai đỉnh bất kì i, j V có thể có nhiều hơn một cạnh nối; không kể đến thứ tự các đỉnh. b Giữa hai đỉnh bất kì i, j V có thể có nhiều hơn một cung nối; có kể đến thứ tự các đỉnh. c Giữa hai đỉnh bất kì i, j V có nhiều nhất một cạnh nối; không kể đến thứ tự các đỉnh. d Giữa hai đỉnh bất kì i, j V có nhiều nhất một cung nối; có kể đến thứ tự các đỉnh. 3/ Cho đồ thị G =, hãy cho biết đâu là tính chất đúng của đơn đồ thị có hướng: a Giữa hai đỉnh bất kì i, j V có nhiều nhất một cung nối; có kể đến thứ tự các đỉnh. b Giữa hai đỉnh bất kì i, j V có nhiều nhất một cạnh nối; không kể đến thứ tự các đỉnh. c Giữa hai đỉnh bất kì i, j V có thể có nhiều hơn một cạnh nối; không kể đến thứ tự các đỉnh. d Giữa hai đỉnh bất kì i, j V có thể có nhiều hơn một cung nối; có kể đến thứ tự các đỉnh. 4/ Cho đồ thị G =, hãy cho biết đâu là tính chất đúng của đa đồ thị có hướng: a Giữa hai đỉnh bất kì i, j V có thể có nhiều hơn một cạnh nối; không kể đến thứ tự các đỉnh. b Giữa hai đỉnh bất kì i, j V có thể có nhiều hơn một cung nối; có kể đến thứ tự các đỉnh. c Giữa hai đỉnh bất kì i, j V có nhiều nhất một cung nối; có kể đến thứ tự các đỉnh. d Giữa hai đỉnh bất kì i, j V có nhiều nhất một cạnh nối; không kể đến thứ tự các đỉnh. 5/ Nếu G = là một đơn đồ thị vô hướng thì a G không có khuyên. b G có khuyên. c G có thể có cạnh bội. d G không có cạnh bội. 6/ Nếu G = là một đa đồ thị vô hướng thì a G không có cạnh bội. b G không có khuyên. c G có khuyên. d G có thể có cạnh bội. 7/ Nếu G = là một đơn đồ thị có hướng thì a G không có khuyên. b G có thể có cung bội. 1 c G có khuyên. d G không có cung bội.8/ Nếu G = là một đa đồ thị có hướng thì a G có thể có cung bội. b G không có cung bội. c G có khuyên. d G không có khuyên.9/ Ta nói hai đỉnh u, v V của đồ thị G = được gọi là kề nhau nếu: a Có đường nối từ u đến v và từ v đến u. b Có đường nối từ v đến u. c Có đường nối từ u đến v. d (u, v) là một cạnh (cung) của đồ thị.10/ Ta gọi đỉnh v là đỉnh treo trong đồ thị vô hướng G = a Nếu bậc của đỉnh v là một số lẻ. b Nếu bậc của đỉnh v là 0. c Nếu bậc của đỉnh v là một số chẵn. d Nếu bậc của đỉnh v là 1.11/ Ta gọi đỉnh v là đỉnh cô lập trong đồ thị vô hướng G = a Nếu bậc của đỉnh v là một số chẵn. b Nếu bậc của đỉnh v là 1. c Nếu bậc của đỉnh v là 0. d Nếu bậc của đỉnh v là một số lẻ.12/ Đồ thị vô hướng G = được gọi là liên thông nếu a Giữa hai đỉnh bất kì u, v V của G luôn tìm được đường đi. b Nếu u V, thì tồn tại đỉnh v≠ u sao cho v liên thông với u. c Nếu u V, thì với mọi v≠ u đều kề với u. d Nếu u V, thì tồn tại đỉnh v≠ u kề với u.13/ Đồ thị có hướng G = được gọi là liên thông mạnh nếu a Giữa hai đỉnh bất kì u, v V của G luôn tìm được đường đi. b Nếu u V, thì với mọi v≠ u đều kề với u. c Nếu u V, thì tồn tại đỉnh v≠ u sao cho v liên thông với u. d Nếu u V, thì tồn tại đỉnh v≠ u kề với u.14/ Đỉnh u V của đồ thị G = được gọi là cầu nếu: a Đỉnh u luôn là đỉnh cô lập. b Loại bỏ đỉnh u và các cạnh liên thuộc với nó làm tăng số thành phần liên thông của đồ thị. c Đỉnh u luôn là đỉnh treo. d Loại bỏ đỉnh u và các cạnh liên thuộc với nó không làm tăng số thành phần liên thông của đồ thị.15/ Cạnh (u, v) E của đồ thị G = được gọi là cầu nếu: a Loại bỏ đỉnh u, v làm tăng số thành phần liên thông của đồ thị. b Loại bỏ cạnh (u,v) và các đỉnh u, v làm tăng số thành phần liên thông của đồ thị. c Đỉnh u và v luôn là các đỉnh treo. d Loại bỏ cạnh (u, v) làm tăng số thành phần liên thông của đồ thị.16/ Ma trận kề của đồ thị vô hướng G = có tính chất: a Là ma ...