Top 17 # Các Bài Tập Toán Rời Rạc Có Lời Giải / 2023 Xem Nhiều Nhất, Mới Nhất 11/2022 # Top Trend | Caffebenevietnam.com

Tổng Hợp Bài Tập Toán Rời Rạc Có Đáp Án Rời Rạc Có Lời Giải, Bài Tập Toán Rời Rạc Có Lời Giải / 2023

Giải Toán 6 Đề CươngGiải Toán Lớp 6 Đề CươngGiải Toán 7 Đề CươngĐề Cương Toán Rời Rạc Có GiảiGiải Toán 9 Đề CươngGiải Toán Lớp 5 Đề CươngĐề Cương ôn Tập Toán 8 Thcs Long Toàn Có Đáp ánPhương Hướng,nội Dung,giải Pháp Phát Huy Sức Mạnh Toàn Dân Tộc Trong Giai Đoạn Hiện NayBài Giải Vật Lý Đại Cương A2Bài Giải Vật Lý Đại CươngGiải Bài Hoá Đại Cương 2Bài Giải Vật Lý Đại Cương 2Bài Giải Hóa Đại CươngGiải Đề CươngGiải Hóa 8 Đề CươngGiải Bài Tập Vật Lý Đại Cương 1Bài Giải Logic Học Đại CươngĐề Cương Giải Tích 2

Giải Toán 6 Đề Cương,Giải Toán Lớp 6 Đề Cương,Giải Toán 7 Đề Cương,Đề Cương Toán Rời Rạc Có Giải,Giải Toán 9 Đề Cương,Giải Toán Lớp 5 Đề Cương,Đề Cương ôn Tập Toán 8 Thcs Long Toàn Có Đáp án,Phương Hướng,nội Dung,giải Pháp Phát Huy Sức Mạnh Toàn Dân Tộc Trong Giai Đoạn Hiện Nay,Bài Giải Vật Lý Đại Cương A2,Bài Giải Vật Lý Đại Cương,Giải Bài Hoá Đại Cương 2,Bài Giải Vật Lý Đại Cương 2,Bài Giải Hóa Đại Cương,Giải Đề Cương,Giải Hóa 8 Đề Cương,Giải Bài Tập Vật Lý Đại Cương 1,Bài Giải Logic Học Đại Cương,Đề Cương Giải Tích 2,Đề Cương Giải Tích 3,Giải Bài Tập Quản Trị Học Đại Cương,Giải Bài Tập Excel Tin Học Đại Cương,Giai Bai Tap Thien Van Dai Cuong,Bài Giải Đề Cương ôn Thi Ppnckh,Đề Cương Bài Tập Giải Tích 2,Đề Cương Giải Tích 3 Hust,Đề Cương 45 Năm Giải Phóng Miền Nam,Đề Cương 40 Năm Giải Phóng Miền Nam,Đề Cương Giải Tích 2 Sami,Giải Bài Tập 24 Cường Độ Dòng Điện,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Tiếp,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Violet,Lười Giải Phiếu Bài Tập Toán Cuối Tuần Toán 4tuân 16,Toán 9 Giải Bài Toán Bằng Cách Lập Phương Trình Violet,Toán Đại 8 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán 9 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán Lớp 8 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán 9 Giải Bài Toán Bằng Cách Lập Hệ Phương Trình,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Tt,Giải Toán Lớp 5 Toán Phát Chiển Năng Lực Tư Tuần 14 Đến 15,16,Các Dạng Toán Và Phương Pháp Giải Toán 8,Các Dạng Toán Và Phương Pháp Giải Toán 6,Phương Pháp Giải Toán Qua Các Bài Toán Olympic,Các Dạng Toán Và Phương Pháp Giải Toán 8 Tập 1,Đề Cương Sơ Bộ Giải Quyết Tranh Chấp Về Thừa Kế,Đề Cương Tuyên Truyền 39 Năm Giải Phóng Miền Nam,Giải Pháp Tăng Cường Công Tác Tư Tưởng Của Đảng,Giải Toán Cuối Tuần 12 Lớp 3 Môn Toán,Toán Lớp 5 Bài Giải Toán Về Tỉ Số Phần Trăm,Đề Cương Toán Lớp 7 Học Kì 2,Đề Cương Kì 2 Toán 7,Đề Cương Toán Lớp 5,Đề Cương Toán Lớp 4 Học Kỳ 1,Đề Cương Toán Lớp 4,Đề Cương Toán Lớp 3,Đề Cương ôn Tập Học Kì 1 Toán 9,Đề Cương Toán Lớp 2 Học Kỳ 1,Đề Cương Học Kì 2 Toán 8,Đề Cương Toán Lớp 5 Học Kì 1,Đề Cương Toán Lớp 5 Học Kỳ 1,Đề Cương ôn Tập Học Kì 2 Toán 6,Đề Cương Toán Rời Rạc,Đề Cương Toán Lớp 5 Học Kỳ 2,Đề Cương ôn Tập Kì 2 Toán 6,Đề Cương ôn Tập Toán 6 Học Kì 1,Đề Cương ôn Tập Kì 1 Toán 9,Đề Cương ôn Tập Toán 8 Kì 1 Có Đáp án,Đề Cương ôn Tập Học Kì 2 Toán 8,Đề Cương ôn Tập Học Kì 2 Toán 7,Đề Cương Học Kì 2 Toán 7,Đề Cương Học Kì 2 Toán 6,Đề Cương Toán 5 Học Kì 1,Đề Cương Toán 5 Học Kì 2,Đề Cương Toán 5 Học Kỳ 1,Đề Cương Toán 6,Đề Cương Toán 6 Học Kì 1,Đề Cương ôn Tập Môn Toán Rời Rạc,Đề Cương Toán 6 Học Kì 2,Đề Cương ôn Tập Môn Toán Lớp 7,Đề Cương ôn Tập Môn Toán Lớp 6,Đề Cương ôn Tập Môn Toán Lớp 5,Đề Cương ôn Tập Môn Toán Lớp 4,Đề Cương Toán 6 Học Kỳ 1,Đề Cương ôn Tập Môn Toán Lớp 3 Học Kì 1,Đề Cương Toán 7 Học Kì 1,Đề Cương Toán 7,Đề Cương Toán 6 Kì 2,Đề Cương ôn Tập Môn Toán Lớp 3,Đề Cương Toán 5,Đề Cương Toán 7 Học Kì 2,Đề Cương Học Kì 2 Toán 11,Đề Cương Học Kì 2 Toán 10,Đề Cương Toán 9 Học Kì 2 Có Đáp án,Đề Cương Toán 9 Học Kì 2,Đề Cương Học Kì 1 Toán 8,Đề Cương Toán 9 Học Kì 1,Đề Cương Học Kì 1 Toán 7,Đề Cương ôn Tập Học Kì 1 Toán 8,Đề Cương Học Kì 1 Toán 6,Đề Cương Toán 8 Học Kì 2,

Giải Toán 6 Đề Cương,Giải Toán Lớp 6 Đề Cương,Giải Toán 7 Đề Cương,Đề Cương Toán Rời Rạc Có Giải,Giải Toán 9 Đề Cương,Giải Toán Lớp 5 Đề Cương,Đề Cương ôn Tập Toán 8 Thcs Long Toàn Có Đáp án,Phương Hướng,nội Dung,giải Pháp Phát Huy Sức Mạnh Toàn Dân Tộc Trong Giai Đoạn Hiện Nay,Bài Giải Vật Lý Đại Cương A2,Bài Giải Vật Lý Đại Cương,Giải Bài Hoá Đại Cương 2,Bài Giải Vật Lý Đại Cương 2,Bài Giải Hóa Đại Cương,Giải Đề Cương,Giải Hóa 8 Đề Cương,Giải Bài Tập Vật Lý Đại Cương 1,Bài Giải Logic Học Đại Cương,Đề Cương Giải Tích 2,Đề Cương Giải Tích 3,Giải Bài Tập Quản Trị Học Đại Cương,Giải Bài Tập Excel Tin Học Đại Cương,Giai Bai Tap Thien Van Dai Cuong,Bài Giải Đề Cương ôn Thi Ppnckh,Đề Cương Bài Tập Giải Tích 2,Đề Cương Giải Tích 3 Hust,Đề Cương 45 Năm Giải Phóng Miền Nam,Đề Cương 40 Năm Giải Phóng Miền Nam,Đề Cương Giải Tích 2 Sami,Giải Bài Tập 24 Cường Độ Dòng Điện,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Tiếp,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Violet,Lười Giải Phiếu Bài Tập Toán Cuối Tuần Toán 4tuân 16,Toán 9 Giải Bài Toán Bằng Cách Lập Phương Trình Violet,Toán Đại 8 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán 9 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán Lớp 8 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán 9 Giải Bài Toán Bằng Cách Lập Hệ Phương Trình,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Tt,Giải Toán Lớp 5 Toán Phát Chiển Năng Lực Tư Tuần 14 Đến 15,16,Các Dạng Toán Và Phương Pháp Giải Toán 8,Các Dạng Toán Và Phương Pháp Giải Toán 6,Phương Pháp Giải Toán Qua Các Bài Toán Olympic,Các Dạng Toán Và Phương Pháp Giải Toán 8 Tập 1,Đề Cương Sơ Bộ Giải Quyết Tranh Chấp Về Thừa Kế,Đề Cương Tuyên Truyền 39 Năm Giải Phóng Miền Nam,Giải Pháp Tăng Cường Công Tác Tư Tưởng Của Đảng,Giải Toán Cuối Tuần 12 Lớp 3 Môn Toán,Toán Lớp 5 Bài Giải Toán Về Tỉ Số Phần Trăm,Đề Cương Toán Lớp 7 Học Kì 2,

Bài Tập Toán Rời Rạc Có Lời Giải / 2023

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai BT Toan roi rac 1

BÀI TẬP CHƯƠNG I Bài 1: Số mã vùng cần thiết nhỏ nhất là bao nhiêu để đảm bảo 25 triệu máy điện thoại khác nhau. Mỗi điện thoại có 9 chữ số có dạng 0XX-8XXXXX với X nhận giá trị từ 0 đến 9.

Giải:

Vì số mã vùng có dạng: 0XX-8XXXXX, với X nhận các giá trị từ 0 đến 9 (10 số), có 07 ký tự X do vậy sẽ có 107 trường hợp. Do đó, theo nguyên lý Dirichlet với 10 triệu máy điện thoại thì số mã vùng cần thiết là: ][35,2000.000.10000.000.25

Bài 2: Biển số xe gồm 8 ký tự, dạng NN-NNNN-XN, ví dụ 75_1576_F1. Hai số đầu là mã tỉnh, X là chữ cái (26 chũ cái). N gồm các số 0, 1, …, 9. Hỏi một tỉnh nào đó cần đăng ký cho 10 triệu xe thì cần bao nhiêu serial (X).

Giải

Bài toán này có 02 cách hiểu: serial ở đây có thể là 02 ký tự NN đầu tiên hoặc là 02 ký tự XN cuối cùng. Cách hiểu 1: (serial là 02 ký tự XN cuối cùng). Hai số NN đầu là mã tỉnh, do nhà nước quy định nên không ảnh hưởng đến kết quả bài toán. Sáu ký tự còn lại có 5 ký tự là N, như vậy có 510 trường hợp. Theo nguyên lý Dirichlet, số serial X tối thiểu phải thỏa mãn: 100000.100000.000.10=⎢⎣⎡⎥⎦⎤. Điều này không hợp lý vì số ký tự chữ cái chỉ là 26. Do vậy, nếu bài toán sửa lại là 1 triệu bảng số xe thì kết quả hợp lý hơn, khi đó số serial là: 10000.100000.000.1=

⎢⎣⎡⎥⎦⎤. Cách hiểu 2: (serial là 02 ký tự NN đầu tiên) Bốn ký tự NNNN sẽ có 104 trường hợp, 02 ký tự XN sẽ có 26*10 = 260 trường hợp. Theo quy tắc nhân, tổng số trường hợp sẽ là: 104*260 = 2.600.000. Do đó, theo nguyên lý Dirichlet, số serial tối thiểu phải là:

Bài 3: Có bao nhiêu xâu nhị phân có độ dài 10: a. Bắt đầu bằng 00 hoặc kết thúc bằng 11. b. Bắt đầu bẳng 00 và kết thúc bằng 11.

Giải

a. Bắt đầu bằng 00 hoặc kết thúc bằng 11. Xâu nhị phân bắt đầu bằng 00 có dạng: 00.xxxxxxxx. Ký tự x có thể là 0 hoặc 1, có 8 ký tự x do vậy có 82 xâu. Xâu nhị phân kết thúc bằng 11 có dạng: xxxxxxxx11. Tương tư ta cũng tính được có 82 xâu. Xâu nhị phân bắt đầu bằng 00 và kết thúc bằng 11 có dạng 00.xxxxxx11. Tương tự như trên, ta cũng tính được có 62 xâu. Vậy số xâu nhị phân bắt đầu bằng 00 hay kết thúc bằng 11 là: Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 2 4486451222*268=−=−=n xâu. b. Bắt đầu bằng 00 và kết thúc bằng 11. Xâu nhị phân thỏa mãn đề bài phải có dạng: 00.xxxxxx11. Hai ký tự đầu và 02 ký tự cuối là không đổi, do vậy chỉ còn 06 ký tự ở giữa. Do đó số xâu nhị phân thỏa mãn đề bài là: 26

xâu.

Bài 4: Khóa 29 CNTT có 150 SV học NNLT Java, 160 SV hoc Delphi, 40 SV học cả hai môn trên. a. Tìm tất cả SV của khóa 29 biết rằng SV nào cũng phải học ít nhất 01 môn. b. Biết tổng số SV là 285, hỏi có bao nhiêu SV không học Java hoặc Delphi.

Giải

Gọi J: SV học Java D: SV học Delphi a. Số SV của khóa 29 là: 270401601501=−+=−+== DJDJDJn IU SV b. Câu b có 02 cách hiểu: Cách 01: không học ít nhất 01 môn. Số SV không học Java hoặc Delphi là (áp dụng nguyên lý bù trừ) ta tính được: 245402852=−=−= DJnn I SV Cách 02: không học Java cũng chẳng học Delphi: Theo cách hiểu này, áp dụng nguyên lý bù trừ ta tính được số SV như sau: 1540160150285‘2=+−−=+−−== DJDJnDJn IU SV

Giải

Bài toán này cũng có thể được hiểu theo 02 cách. Cách 01: phân biệt chữ thường với chữ hoa. Chữ cái thường: 26 Chữ cái hoa: 26 Chữ số: 10 Do đó, tổng cộng có 26 + 26 + 10 = 62 ký tự khác nhau. Nếu password có n ký tự. Tổng số trường hợp: n62 Số password không có chữ số: n52 Suy ra số password có ít nhất 01 chữ số: nnnn 5262 −= Áp dụng cho các trường hợp n = 6, 7, 8. Tổng số password thỏa yêu cầu đề bài là: 040.583.949.410.167526252625262887766876=−+−+−=++= nnnn

Cách 02: không phân biệt chữ thường với chữ hoa: Cách làm hoàn toàn tương tự, nhưng thay vì sử dụng các số 62 và 52 thì ở đây sử dụng 02 số: 36 và 26. Kết quả sẽ là:

063.3602.684.483.263626362636887766876=−+−+−=++= nnnnBài 6: Có n lá thư bỏ vào n bì thư. Hỏi xác suất để xảy ra trường hợp không có lá thư nào bỏ đúng được bì thư của nó.

Giải Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

Bài 7: Chỉ ra rằng nếu chọn 5 số từ tập 8 số {1, 2, …, 7, 8} thì bao giờ cũng có ít nhất 01 cặp số có tổng là 9.

Giải

Từ 8 số ở trên, ta chia thành 04 cặp: {1, 8}, {2, 7}, {3, 6}, {4, 5} và tổng của mỗi cặp đều bằng 9. Như vậy, đề bài sẽ trở thành chọn 5 số từ 4 cặp số trên. Theo nguyên lý Dirichlet, phải có ít nhất 01 cặp số được chọn hết. Vậy bài toán đã được chứng minh.

Bài 8: Chứng minh rằng trong bất kỳ một nhóm 27 từ tiếng Anh nào cũng có ít nhất 2 từ bắt đầu từ cùng 01 chữ cái.

Giải

Bảng chữ cái của tiếng anh gồm 26 ký tự: a, b, c, …, x, y, z. Vì có 27 từ tiếng Anh và mỗi từ bắt đầu bằng 01 chữ cái nên theo nguyên lý Dirichlet phải có ít nhất 02 từ bắt đầu bằng cùng 01 chữ cái.

Bài 9: Cần phải có bao nhiêu SV ghi tên vào lớp TRR để chắc chắn có ít nhất 65 SV đạt cùng điểm thi, giả sử thang điểm thi gồm 10 bậc.

Giải Gọi n là số sinh viên tối thiểu thỏa mãn đề bài, theo nguyên lý Dirichlet thì ] [6510=n. Do vậy 641164*10 =+=n SV.

Bài 10: Tìm hệ thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân có độ dài n và không có 2 số 0 liên tiếp. Có bao nhiêu xâu nhị phân như thế có độ dài bằng 5.

Giải

Với xâu nhị phân có độ dài n, ta chia thành 02 trường hợp: Nếu ký tự cuối cùng là 1 thì ký tự trước đó (ký tự thứ n – 1) có thể là 1 hay là 0 đều được. Nếu ký tự cuối cùng là 0 thì ký tự trước đó (ký tự thứ n – 1) chỉ có thể là 1 (vì nếu là 0 thì vi phạm yêu cầu bài toán) nhưng ký tự trước đó nữa (thứ n – 2) có thể là 0 hay 1 đều được. Từ 02 trường hợp trên ta suy ra được: 21 −−+=nnnfff Các điều kiện đầu: 21=f , 32=f Có 13 xâu nhị phân có độ dài 5 và không có 2 số 0 liên tiếp. Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 4

Giải

Giải

Vậy nghiệm của hệ thức truy hồi là: nnna 3)2(35 −−+=

Bài 13: Tìm hệ thức truy hồi và nr . Với nr là số miền của mặt phẳng bị phân chia bởi n đường thẳng. Biết rằng không có 2 đường thẳng nào song song và cũng không có 03 đường thẳng nào đi qua cùng 1 điểm.

Giải

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 5 Với n đường thẳng, theo đề bài thì đường thẳng thứ n sẽ cắt n – 1 đường thẳng còn lại tại n – 1 điểm, tức là sẽ cắt n – 1 + 1 = n phần mặt phẳng. Do đó, số phần mặt phẳng tăng lên là n. Từ đó, ta có được hệ thức truy hồi: nrrnn+=−1. Các điều kiện đầu là: n = 0: r0 = 1. n = 1: r1 = 2.

BÀI TẬP CHƯƠNG II

Bài 14 Chứng minh rằng trong một đơn đồ thị luôn có ít nhất 02 đỉnh có cùng bậc.

Giải

Trong đồ thị đơn, số bậc tối đa cung TH1: Giả sử đồ thì không có đỉnh treo, do đó số bậc tối thiểu của các đỉnh là 1, số bậc tối đa của các đỉnh là n-1 (vì là đơn đồ thị). Có n đỉnh, số bậc của các đỉnh đi từ 1 đến n-1 (n-1) giá trị. Do đó theo nguyên lý Dirichlet phải có ít nhất 02 đỉnh có cùng bậc. TH2: Giả sử đồ thị có ít nhất 01 đỉnh treo, khi đó số bậc tối thiểu của các đỉnh là 0, và số bậc tối đa chỉ là n-2 (vì là đơn đồ thị, đồng thời có đỉnh treo). Có n đỉnh, số bậc của các đỉnh chỉ có thể đi từ 0 đến n-2 (n-1) giá trị. Do đó theo nguyên lý Dirichlet phải có ít nhất 02 đỉnh có cùng bậc.

Bài 15: Tính tổng số bậc của nK (đơn đồ thị đủ).

Giải

Với đồ thị đủ thì mỗi đỉnh đều nối với các đỉnh còn lại. Do vậy, khi có n đỉnh thì mỗi đỉnh đều nối với n -1 đỉnh còn lại, tức là bậc của mỗi đỉnh đều bằng n – 1. Vậy, tổng số bậc của cả đồ thị là: n*(n – 1) bậc.

II. Các bài tập trong giấy kiểm tra lần 1. Bài 16: (giống bài 12 phần trước).

Bài 17: Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 6

Trong tổng số 2504 sinh viên của một khoa công nghệ thông tin, có 1876 theo học môn NNLT Pascal, 999 học môn ngôn ngữ Fortran và 345 học môn ngôn ngữ C. Ngoài ra còn biết 876 sinh viên học cả Pascal và Fortran, 232 học cả Fortran và C, 290 học cả Pascal và C. Nếu 189 sinh viên học cả 03 môn Psacal, Fortran và C thì trong trường hợp đó có bao nhiêu sinh viên không học môn nào trong cả 03 môn nói trên.

Giải

Gọi P: là tập gồm các SV học Pascal F: là tập gồm các SV học Fortran C: là tập gồm các SV học C N: là tổng số SV (2504 SV) Gọi K là số SV học ít nhất 01 môn Theo nguyên lý bù trừ, ta có: KPFCPFCPFFCCPPFC==++−−−+UU I I I II 4932011250420111892902328763459991876 =−=−=⇒=+−−−++= KNKK SV Vậy có 493 SV không học môn nào trong 03 môn: Pascal, Fortran và C.

Bài 18: Hãy tìm số đỉnh, số cạnh, số bậc của mỗi đỉnh và xác định các đỉnh cô lập, đỉnh treo, ma trận liền kề, ma trận liên thuộc trong mỗi đồ thị vô hướng sau:

Giải

Câu 18.1. Số đỉnh: 8 Số cạnh: 11 Đỉnh cô lập: D Đỉnh treo: không có

Tên đỉnh a b C d e g h i Bậc của định 3 2 4 0 5 3 2 3

Câu 18.2. Số đỉnh: 5 Số cạnh: 12 Đỉnh cô lập: không có Đỉnh treo: không có

Tên đỉnh a b c d e Bậc của định 6 5 5 5 3

Giải

Dựa vào ma trận liền kề của hai đơn đồ thị ta có thể vẽ lại các đồ thị bằng hình vẽ: Theo hình vẽ của hai đơn đồ thị ta thấy chúng không có cùng số cạnh, một bên có 4 cạnh và một bên có 5 cạnh. Vậy hai đồ thị có ma trận liền kề đã cho ở trên không đẳng cấu. Bài toán này có thể không cần vẽ hình lại cũng được, từ ma trận kề ta cũng có thể dễ dàng xác định được số cạnh của mỗi đồ thị lần lượt là 4 và 5. Do vậy chúng không thể đẳng cấu.

Bài 20: Xét xem các đồ thị cho sau đây có đẳng cấu với nhau không?

Giải

a. Hình 01. Hai đồ thị cho ở trên có: số đỉnh, số cạnh, tổng số bậc và số bậc của mỗi đỉnh bằng nhau. Đặc biệt, các đỉnh của đồ thị thứ nhất và thứ hai khi sắp theo thứ tự sau đây thì chúng hoàn toàn tương đương về mọi mặt:

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 9Số bậc của mỗi đỉnh 3 4 4 3 5 5

Chính vì vậy, hai đồ thị trên là đẳng cấu. b. Hình 02. Hai đồ thị có hướng cho ở trên khi sắp theo thứ tự sau đây về các đỉnh thì chúng tương đương về tất cả các mặt: từ số đỉnh, tổng số bậc, bậc vào, bậc ra của mỗi đỉnh, tổng số cạnh, thứ tự và chiều của các cạnh đều tương ứng:

Vì vậy, hai đồ thị có hướng ở trên là đẳng cấu với nhau.

Bài 21: (3.1) Cho G là đồ thị có v đỉnh và e cạnh, còn m và M tương ứng là bậc nhỏ nhất và lớn nhất các đỉnh của G. Chứng tỏ rằng: 2emMv≤≤

Giải

Vì m và M tương ứng là bậc nhỏ nhất và lớn nhất các đỉnh của G, do đó ta dễ dàng có được:

Bài 22: (3.2) Chứng minh rằng nếu G là đơn đồ thị phân đôi có v đỉnh và e cạnh, khi đó chứng minh bất đẳng thức sau đây: 2(1)4ve ≤Giải

Bài 24: (3.6) Tìm ma trận liền kề cho các đồ thị sau:

Hai đồ thị với ma trận liền kề ở trên không thể đẳng cấu với nhau vì: chúng có số cạnh khác nhau: đồ thị thứ nhất có 4 cạnh, đồ thị thứ hai có 5 cạnh.

Bài 26: (3.9)

Thưa thầy, theo em nghĩ thì đây là hai ma trận liên thuộc chứ không phải là hai ma trận liền kề. Và nếu là hai ma trận liên thuộc thì chúng đẳng cấu với nhau vì: Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

Giải

Bài này hoàn toàn giống bài số 20 đã giải ở trên.

Bài 28: (3.11) Cho V = {2, 3, 4, 5, 6, 7, 8} và E là tập hợp các cặp phần tử (u, v) của V sao cho u < v và u với v là các số nguyên tố cùng nhau. Hãy vẽ đồ thị có hướng (),GVE= . Tìm số đường đi phân biệt độ dài 3 từ đỉnh 2 tới đỉnh 8. Giải 72438Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 13 Bài 29: (3.12)

Hãy tìm số đường đi độ dài n giữa hai đỉnh liền kề (t.ư không liền kề) tùy ý trong K3,3 với mỗi giá trị của n sau: a. n = 2, b. n = 3, c. n = 4, d. n = 5.

Giải

Hai đỉnh liền kề phải ở 2 phần khác nhau. Một cạnh chỉ có thể nối từ 1 đỉnh ở phần (I) đến 1 đỉnh ở phần (II) và ngược lại. Gọi m là số đường đi giữa 2 đỉnh bất kỳ trong K3,3 có độ dài n. TH1: n chẵn. Nếu n chẵn thì đỉnh đầu và đỉnh cuối của đường đi phải ở cùng 1 phần, do vậy chúng không thể liền kề. TH2: n lẻ.

Nếu n lẻ thì đỉnh đầu và đỉnh cuối của đường đi phải ở trên 2 phần khác nhau, do vậy chúng phải liền kề (vì đây là K3,3). Mặc khác mỗi một đỉnh ở phần này luôn có 3 phương án để đi qua 1 đỉnh ở phần kia. Do vậy ta có được các kết luận sau đây: o Hai đỉnh liền kề, n chẵn: m = 0, o Hai đỉnh liền kề, n lẻ: m = 3n-1, o Hai đỉnh không liền kề, n chẵn: m = 3n-1, o Hai đỉnh không liền kề, n lẽ: m = 0.

Áp dụng cho các trường hợp:

BT Toan roi rac 14Bài tập chương III

Câu 1: Cho G là đồ thị có v đỉnh và e cạnh, còn M, m tương ứng là bậc lớn nhất và nhỏ nhất của các đỉnh của G. Chứng tỏ rằng: m ≤ ve2 ≤ M. Câu 2: Chứng minh rằng nếu G là đơn đồ thị phân đôi có v đỉnh và e cạnh, khi đó e ≤ v2/4.

BT Toan roi rac 15Câu 10: Các đồ thị G và G’ sau có đẳng cấu với nhau không? a) b) Câu 11: Cho V={2,3,4,5,6,7,8} và E là tập hợp các cặp phần tử (u,v) của V sao cho u<v và u,v nguyên tố cùng nhau. Hãy vẽ đồ thị có hướng G=(V,E). Tìm số các đường đi phân biệt độ dài 3 từ đỉnh 2 tới đỉnh 8.

Câu 12: Hãy tìm số đường đi độ dài n giữa hai đỉnh liền kề (t.ư. không liền kề) tùy ý trong K3,3 với mỗi giá trị của n sau: a) n=2, b) n=3, c) n=4, d) n=5. u1

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 16Câu 1:

Vì m và M tương ứng là bậc nhỏ nhất và lớn nhất các đỉnh của G, do đó ta dễ dàng có được: deg() , i=1,vimvM≤≤ ⇔

Khi đó, số cạnh nhiều nhất sẽ là:12 12 (2)ddd edd=× ⇔≤ Ta dễ dàng có được: 22 22 212 1 122 1 122 12()0 2 0 2 4dd d ddd d ddd dd− ≥⇔− +≥⇔+ +≥

Câu 4:

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 20Câu 8: Dựa vào ma trận liền kề của hai đơn đồ thị ta có thể vẽ lại các đồ thị bằng hình vẽ: Dựa vào hình vẽ của hai đơn đồ thị ta thấy hai đơn đồ thị không có cùng số cạnh, một bên có 4 cạnh và một bên có 5 cạnh. Vậy hai đơn đồ thị có ma trận liền kề đã cho không đẳng cấu.

Câu 9: Theo em dề ra là hai ma trận liên thuộc Dựa vào hai ma trận liên thuộc ta có thể vẽ lại đồ thị của hai ma trận như sau:

Hai đồ thị có các cạnh tương ứng là:

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

b/ Hai đồ thị có hướng G1, G2 cho ở trên khi sắp lại thứ tự về các đỉnh thì chúng tương đương về tất cả các mặt: từ số đỉnh, tổng số bậc, bậc vào, bậc ra của mỗi đỉnh, tổng số cạnh, thứ tự và chiều đi và đến của các cạnh đều tương ứng với nhau:

Bậc vào: 1 2 1 2 2 1 Bậc ra: 2 1 2 1 1 2

Vì vậy, hai đồ thị G1,G2 có hướng cho ở trên là đẳng cấu với nhau. Câu 12: Hai đỉnh liền kề phải ở 2 phần khác nhau cảu đồ thị. Một cạnh chỉ có thể nối từ 1 đỉnh ở phần (I) đến 1 đỉnh ở phần (II) và ngược lại. Gọi b là số đường đi giữa 2 đỉnh bất kỳ trong K3,3 có độ dài n. TH1: n chẵn. Nếu n chẵn thì đỉnh đầu và đỉnh cuối của đường đi phải ở cùng 1 phần, do vậy chúng không thể liền kề. TH2: n lẻ. Nếu n lẻ thì đỉnh đầu và đỉnh cuối của đường đi phải ở trên 2 phần khác nhau, do vậy chúng phải liền kề (vì đây là K3,3). Mặc khác mỗi một đỉnh ở phần này luôn có 3 đường đi để đi qua 1 đỉnh ở phần kia. Do vậy ta có được các kết quả sau đây rút ra từ suy luận trên: o Hai đỉnh liền kề, n chẵn: b = 0, o Hai đỉnh liền kề, n lẻ: b = 3n-1, (II) (I) 1 43 2 56Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 22o Hai đỉnh không liền kề, n chẵn: b = 3n-1, o Hai đỉnh không liền kề, n lẽ: b = 0. Áp dụng cho các trường hợp:

Số cạnh n = 2 n = 3 n = 4 n = 5 Liền kề 0 9 0 81 Không liền kề 3 0 27 0

BÀI TẬP CHƯƠNG 4 ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON Bài 1: Với giá trị nào của n thì các đồ thị sau đây là đồ thị Euler? a. Kn b. Cn c. Wn d. QnGiải:

Bài 2:

Với các giá trị nào của m và n thì đồ thị phân đôi đầy đủ Km,n có: a. Chu trình Euler. b. Đường đi Euler.

Giải

a. Vì các đỉnh của đồ thị phân đôi đủ Km,n có bậc là m hoặc n. Do vậy, để nó là đồ thị Euler thì m và n đều phải là một số chẵn. b. Để một đồ thị có đường đi Euler thì phải có đúng 2 đỉnh bậc lẻ, các đỉnh còn lại phải là bậc chẵn. Vậy một trong 2 giá trị m, n phải là 2, giá trị còn lại phải là số lẻ. Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 23Bài 3: Với giá trị nào của m và n thì đồ thị phân đôi đầy đủ Km,n có chu trình Hamilton.

Giải

Theo định lý Dirac, nếu G là đơn đồ thị có n đỉnh và mọi đỉnh của G đều có bậc không nhỏ hơn 2n thì G là một đồ thị Hamilton. Với Km,n các đỉnh có bậc m hoặc n, nên để đồ thị đầy đủ Km,n là đồ thị Hamilton thì phải có điều kiện sau:

Câu 4: Chứng minh rằng đồ thị lập phương Qn là một đồ thị Hamilton. Vẽ cây liệt kê tất cả các chu trình Hamilton của đồ thị lập phương Q3.

Câu 5: Trong một cuộc họp có 15 người mỗi ngày ngồi với nhau quanh một bàn tròn một lần. Hỏi có bao nhiêu cách sắp xếp sao cho mỗi lần ngồi họp, mỗi người có hai người bên cạnh là bạn mới, và sắp xếp như thế nào ?

Câu 6: Hiệu trưởng mời 2n (n ≥ 2) sinh viên giỏi đến dự tiệc. Mỗi sinh viên giỏi quen ít nhất n sinh viên giỏi khác đến dự tiệc. Chứng minh rằng luôn luôn có thể xếp tất cả các sinh viên giỏi ngồi xung quanh một bàn tròn, để mỗi người ngồi giữa hai người mà sinh viên đó quen. Giải Giả sử có đồ thị G = (V, E) mà trong đó ta có: V là tập hợp các sinh viên được mời dự tiệc, E = (u,v) với u, v thuộc V và u, v có quan hệ là quen biết nhau (theo giả thiết của đề bài). Như vậy theo giả thiết của bài toán ta sẽ xác lập được một đồ thị là một đơn đồ thị có 2n đỉnh, mỗi đỉnh có bậc tối thiểu là n (vì theo đề bài cho: mỗi sinh viên quen biết với ít nhất là n sinh viên khác).Cho nên ta có: số bậc của mỗi đỉnh 2

Do đó, theo định lý Dirac thì G là đồ thị Hamilton. Mặc khác, đây là đồ thị vô hướng Vậy theo các lập luận trên thì luôn luôn có thể xếp tất cả các sinh viên giỏi ngồi xung quanh một bàn tròn, để mỗi người ngồi giữa hai người mà sinh viên đó quen. (đpcm) Câu 7: Một ông vua đã xây dựng một lâu đài để cất báu vật. Người ta tìm thấy sơ đồ của lâu đài (hình sau) với lời dặn: muốn tìm báu vật, chỉ cần từ một trong các phòng bên ngoài cùng (số 1, 2, 6, 10, ), đi qua tất cả các cửa phòng, mỗi cửa chỉ một lần; báu vật được giấu sau cửa cuối cùng. Hãy tìm nơi giấu báu vật? 21 3 4 567Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

Câu 9: Giải bài toán người phát thư Trung Hoa với đồ thị cho trong hình sau:

Đồ thị G có đường đi Hamilton từ s tới r nhưng không có chu trình Hamilton thì ta cần tìm một đường đi từ s tới r qua tất cả các đỉnh còn lại nhưng không trở về đỉnh xuất phát . Đường đi Hamilton là : s Æ a Æ b Æ c Æ e Æ f Æ g Æ d Æ h Æ r Từ đồ thị ta nhận thấy sẽ không có bất kỳ chu trình Hamilton nào xuất phát từ s và lại trở về s. Câu 11: Cho thí dụ về: a) Đồ thị có một chu trình vừa là chu trình Euler vừa là chu trình Hamilton; b) Đồ thị có một chu trình Euler và một chu trình Hamilton, nhưng hai chu trình đó không trùng nhau; c) Đồ thị có 6 đỉnh, là đồ thị Hamilton, nhưng không phải là đồ thị Euler; d) Đồ thị có 6 đỉnh, là đồ thị Euler, nhưng không phải là đồ thị Hamilton. Giải a) b) acbsrfedgh13 2 1 2 34 65

Bài Giải Toán Rời Rạc Nguyễn Hữu Anh / 2023

Giải Sách Bồi Dưỡng Năng Lực Tự Học Toán 6 Phần 2 Dố Nguyên Tiết 1 Phép Cộng Và Phép Trừ 2 Số Nguyên, Bài Giải Nguyên Lý Kế Toán, Bài Giải Toán Rời Rạc Nguyễn Hữu Anh, Giải Bài Tập Nguyên Lý Kế Toán, Bài Giải Bài Tập Nguyên Lý Kế Toán Võ Văn Nhị, Giải Nguyên Lí Kế Toán, Giải Bài Tập Nguyên Lý Kế Toán Neu, Bài Giải Nguyên Lý Kế Toán Đại Học Kinh Tế, Giai Bài 33 Trang 39 Toán Rời Rạc Nguyễn Huu Anh, Giải Bài Tập Nguyên Lý Kế Toán Chương 1, Giải Bài Tập Nguyên Lý Kế Toán Chương 3, Giải Bài Tập Nguyên Lý Kế Toán Chương 4, Giải Bài Tập Nguyên Lý Kế Toán Chương 5, Cẩm Nang Giải Toán Vật Lý 12 Nguyễn Anh Vinh, Giải Sách Bồi Dưỡng Năng Lực Toán 6 Phần 2 Số Nguyên Tiết 1, Giải Bài Tập 1 Nguyên Hàm, Giải Bài Tập Nguyên Hàm, Bài Giải Nguyên Hàm, Giải Bài Tập 2 Nguyên Hàm, Giải Bài Tập Phần Nguyên Hàm, Nguyên Tắc Giải ô Số Sudoku, Bài Giải Nguyên Lý Thống Kê, Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Tiếp, Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Violet, Toán 9 Giải Bài Toán Bằng Cách Lập Phương Trình Violet, Lười Giải Phiếu Bài Tập Toán Cuối Tuần Toán 4tuân 16, Giải Toán Lớp 5 Toán Phát Chiển Năng Lực Tư Tuần 14 Đến 15,16, Toán Đại 8 Giải Bài Toán Bằng Cách Lập Phương Trình, Toán 9 Giải Bài Toán Bằng Cách Lập Phương Trình, Toán 9 Giải Bài Toán Bằng Cách Lập Hệ Phương Trình, Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Tt, Toán Lớp 8 Giải Bài Toán Bằng Cách Lập Phương Trình, Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình, Hãy Giải Thích Nguyên Nhân Của Sự Mỏi Cơ, Giải Bài Tập Nguyên Lý Thống Kê Hvtc, Giải Bài Tập Xác Suất Thống Kê Của Nguyễn Cao Văn, Giải Bài Tập Bài 5 Cấu Hình Electron Nguyên Tử, Nguyên Tắc Hòa Giải Trong Tố Tụng Dân Sự, Các Dạng Toán Và Phương Pháp Giải Toán 6, Các Dạng Toán Và Phương Pháp Giải Toán 8 Tập 1, Phương Pháp Giải Toán Qua Các Bài Toán Olympic, Các Dạng Toán Và Phương Pháp Giải Toán 8, Phương án Nào Lý Giải Nguyên Nhân Dẫn Đến Cạnh Tranh, Hãy Giải Thích Những Nguyên Tắc Xây Dựng Thực Đơn, Thực Trajng Và Giải Pháp Bảo Hiểm Y Tế Tự Nguyện, Thực Trạng, Nguyên Nhân Hậu Quả Giải Pháp, Phương án Lí Giải Nguyên Nhân Dẫn Đến Cạnh Tranh, Giải Bài Tập Nguyên Lý Thống Kê Học Viên Ngân Hàng, Toán Lớp 5 Bài Giải Toán Về Tỉ Số Phần Trăm, Giải Toán Cuối Tuần 12 Lớp 3 Môn Toán, Giải Quyết Tranh Chấp Quốc Tế Nguyễn Thị Thu Thảo, Mẫu Công Văn Giải Trình Nguyên Vật Liệu Chênh Lệch, Con Đường Cứu Nước Giải Phóng Dân Tộc Mà Lãnh Tụ Nguyễn ái Quốc, Nguyên Tắc Hòa Bình Giải Quyết Tranh Chấp Quốc Tế, Phương án Nào Dưới Đây Lí Giải Nguyên Nhân Dẫn Đến Cạnh Tranh, Nguyên Lý Kế Toán Bài Tập, Sơ Đồ Chữ T Nguyên Lý Kế Toán, Nguyên Lý Kế Toán Pdf, 7 Nguyên Tắc Kế Toán, Nguyên Lý Kế Toán Cơ Bản, Tìm X Nguyên Lý Kế Toán, 8 Nguyên Tắc Kế Toán, 4 Nguyên Lý Kế Toán, Đề Thi Nguyên Lý Kế Toán, 7 Nguyên Lý Kế Toán, Đồ án Môn Học Nguyên Lý Kế Toán, 6 Nguyên Tắc Kế Toán, Tìm X Y Nguyên Lý Kế Toán, Đồ án Nguyên Lý Kế Toán, Đề Thi Ueh Nguyên Lý Kế Toán, Đề Thi Môn Nguyên Lý Kế Toán Có Đáp án, Bài Tập Nguyên Lý Kế Toán Pgs. Ts. Võ Văn Nhị, Mẫu Đồ án Môn Học Nguyên Lý Kế Toán, Toán Rời Rạc Nguyễn Hữu Anh, 12 Nguyên Tắc Kế Toán, Nguyên Lý Kế Toán, Bài Tập ôn Thi Nguyên Lý Kế Toán, Đề Thi Vấn Đáp Môn Nguyên Lý Kế Toán, 4 Nguyên Tắc Kế Toán, 2 Nguyên Tắc Kế Toán Cơ Bản, Đáp án Nguyên Lý Kế Toán, Bài Tập Nguyên Lý Kế Toán, Nguyên Tắc Kế Toán, 07 Nguyên Tắc Kế Toán, Bài Tập ôn Thi Môn Nguyên Lý Kế Toán, Nêu Tồn Tại Về Vấn Đề Giao Tiếp ứng Sử Tìm Nguyên Nhân Va Giải Pháp Khắc Phục, Công Văn Giải Trình Nguyên Nhân Không Có Xuất Tờ Khai, Nguyên Lý Kế Toán Chương 3, Đề Cương Nguyên Lý Kế Toán, Nguyên Tắc In Sổ Sách Kế Toán, Chương 5 Nguyên Lý Kế Toán, Nguyên Tắc An Toàn Điện, Nguyên Lý Kế Toán Chương 1, Tìm X Trong Nguyên Lý Kế Toán, Uef Nguyên Lí Kế Toán Chương 3, Kế Toán Nguyên Vật Liệu, Nguyên Tắc Hạch Toán, Nguyên Lý Kế Toán Chương 2, Bài Tập Chuyên Đề Số Nguyên Môn Toán Lớp 6, Bài Tập Chương 6 Nguyên Lý Kế Toán,

Giải Sách Bồi Dưỡng Năng Lực Tự Học Toán 6 Phần 2 Dố Nguyên Tiết 1 Phép Cộng Và Phép Trừ 2 Số Nguyên, Bài Giải Nguyên Lý Kế Toán, Bài Giải Toán Rời Rạc Nguyễn Hữu Anh, Giải Bài Tập Nguyên Lý Kế Toán, Bài Giải Bài Tập Nguyên Lý Kế Toán Võ Văn Nhị, Giải Nguyên Lí Kế Toán, Giải Bài Tập Nguyên Lý Kế Toán Neu, Bài Giải Nguyên Lý Kế Toán Đại Học Kinh Tế, Giai Bài 33 Trang 39 Toán Rời Rạc Nguyễn Huu Anh, Giải Bài Tập Nguyên Lý Kế Toán Chương 1, Giải Bài Tập Nguyên Lý Kế Toán Chương 3, Giải Bài Tập Nguyên Lý Kế Toán Chương 4, Giải Bài Tập Nguyên Lý Kế Toán Chương 5, Cẩm Nang Giải Toán Vật Lý 12 Nguyễn Anh Vinh, Giải Sách Bồi Dưỡng Năng Lực Toán 6 Phần 2 Số Nguyên Tiết 1, Giải Bài Tập 1 Nguyên Hàm, Giải Bài Tập Nguyên Hàm, Bài Giải Nguyên Hàm, Giải Bài Tập 2 Nguyên Hàm, Giải Bài Tập Phần Nguyên Hàm, Nguyên Tắc Giải ô Số Sudoku, Bài Giải Nguyên Lý Thống Kê, Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Tiếp, Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Violet, Toán 9 Giải Bài Toán Bằng Cách Lập Phương Trình Violet, Lười Giải Phiếu Bài Tập Toán Cuối Tuần Toán 4tuân 16, Giải Toán Lớp 5 Toán Phát Chiển Năng Lực Tư Tuần 14 Đến 15,16, Toán Đại 8 Giải Bài Toán Bằng Cách Lập Phương Trình, Toán 9 Giải Bài Toán Bằng Cách Lập Phương Trình, Toán 9 Giải Bài Toán Bằng Cách Lập Hệ Phương Trình, Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Tt, Toán Lớp 8 Giải Bài Toán Bằng Cách Lập Phương Trình, Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình, Hãy Giải Thích Nguyên Nhân Của Sự Mỏi Cơ, Giải Bài Tập Nguyên Lý Thống Kê Hvtc, Giải Bài Tập Xác Suất Thống Kê Của Nguyễn Cao Văn, Giải Bài Tập Bài 5 Cấu Hình Electron Nguyên Tử, Nguyên Tắc Hòa Giải Trong Tố Tụng Dân Sự, Các Dạng Toán Và Phương Pháp Giải Toán 6, Các Dạng Toán Và Phương Pháp Giải Toán 8 Tập 1, Phương Pháp Giải Toán Qua Các Bài Toán Olympic, Các Dạng Toán Và Phương Pháp Giải Toán 8, Phương án Nào Lý Giải Nguyên Nhân Dẫn Đến Cạnh Tranh, Hãy Giải Thích Những Nguyên Tắc Xây Dựng Thực Đơn, Thực Trajng Và Giải Pháp Bảo Hiểm Y Tế Tự Nguyện, Thực Trạng, Nguyên Nhân Hậu Quả Giải Pháp, Phương án Lí Giải Nguyên Nhân Dẫn Đến Cạnh Tranh, Giải Bài Tập Nguyên Lý Thống Kê Học Viên Ngân Hàng, Toán Lớp 5 Bài Giải Toán Về Tỉ Số Phần Trăm, Giải Toán Cuối Tuần 12 Lớp 3 Môn Toán,

Bài Tập Toán Rời Rạc Chương 2: Đồ Thị / 2023

BÀI TẬP TOÁN RỜI RẠC *** CHƯƠNG 2: ĐỒ THỊ Giảng viên : Nguyễn Mậu Hân Sinh viên thực hiện : Nguyễn Thị Diệu Hằng Lớp : Tin K30D * Bài 1: Cho G là một đồ thị có v đỉnh và e cạnh.M và m tương ứng là bậc lớn nhất và nhỏ nhất của các đỉnh của G.Chứng minh rằng: m £ 2.e/v £ M Lời giải: Theo đề ra ta có: M: bậc lớn nhất của đỉnh của G. m: bậc nhỏ nhất của đỉnh của G. Như vậy: m £ deg(vi) £ M (với deg(vi) : bậc của đỉnh vi) v.m £ ∑deg(vi) £ v.M v.m £ 2.e £ v.M m £ 2.e £ M Vậy ta có điều phải chứng minh. * Bài 2: Chứng minh rằng nếu G là đơn đồ thị phân đôi có v đỉnh và e cạnh, khi đó e £ v2/4. Lời giải : Ta có: G=(V,E) là đơn đồ thị phân đôi. V=V1 U V2, V1 ∩ V2 =ø, V1 ≠ ø, V2 ≠ ø. Gọi n1 và n2 lần lượt là số phần tử của V1 và V2. n1 + n2 = v G là đồ thị phân đôi nên e đạt giá trị max khi G là đồ thị phân đôi đầy đủ.Khi đó: e = n1.n2 Có nghĩa là trong trường hợp tổng quát thì: e £ n1.n2 Như vậy, để chứng minh e £ v2/4 chỉ cần chứng minh: n1.n2£ v2/4 Thật vậy: n1.n2 £ v2/4 n1.n2 £ (n1+ n2)2/4 4.n1.n2 £ n12 + n22 + 2.n1.n2 n12 + n22 – 2.n1.n2 ≥ 0£ v2/4 (n1- n2)2 ≥ 0 (hiển nhiên đúng) Suy ra: e £ n1.n2 £ v2/4 Vậy ta có điều phải chứng minh. * Bài 3: Trong một phương án mạng kiểu lưới kết nối n=m2 bộ xử lý song song, bộ xử lý P(i,j) được kết nối với 4 bộ xử lý (P(i±1) mod m, j), P(i, (j±1) mod m), sao cho các kết nối bao xung quanh các cạnh của lưới. Hãy vẽ mạng kiểu lưới có 16 bộ xử lý theo phương án này. Lời giải: P(0,1) P(0,0) P(2,0) P(2,1) P(0,2) P(0,3) P(2,2) P(2,3) P(3,1) P(3,0) P(1,0) P(1,1) P(3,2) P(3,3) P(1,3) P(1,2) * Bài 4: Hãy vẽ các đồ thị vô hướng được biểu diễn bởi ma trận liền kề sau: a) b) 1 2 3 1 2 0 1 2 0 4 2 0 3 0 3 4 0 0 3 1 1 1 0 1 0 c) 0 1 3 0 4 1 2 1 3 0 3 1 1 0 1 0 3 0 0 2 4 0 1 2 3 Lời giải: a) b) V1 V3 V2 c) V4 V3 V1 V2 V1 V2 V5 V3 V4 *Bài 5: Nêu ý nghĩa của tổng các phần tử trên một hàng (tương ứng cột) của một ma trận liền kề đối với một đồ thị vô hướng ? Đối với đồ thị có hướng ? Lời giải: Cho đồ thị G=(V,E).V= {v1,v2,…,vn } Ma trận liền kề của đồ thị G=(V,E) là ma trận: A=( aij ) với 1≤i,j≤n a11 a12 … a1n a21 a22 … a2n A= ……… an1 an2 … ann *Nếu G là đồ thị vô hướng: aij là số cạnh nối đỉnh vi và vj -Tổng hàng i của ma trận A: n ∑ aij chính là bậc của đỉnh vi j=1 -Tổng cột j của ma trận A: n ∑aij chính là bậc của đỉnh vj i=1 *Nếu G là đồ thị có hướng: aij là số cung nối vi và vj mà vj là đỉnh cuối -Tổng hàng i của ma trận A: n ∑ aij chính là bậc ra của đỉnh vi j=1 -Tổng cột j của ma trận A: n ∑aij chính là bậc ra của đỉnh vj i=1 *Bài 6: Tìm ma trận liền kề cho các ma trận sau: a) Kn b) Cn c) Wn d) Km,n e) Qn Lời giải: Ma trận liền kề của đồ thị đầy đủ Kn: ai1 ai2 … aij … ain a1j 0 1 … 1 … 1 a2j 1 0 … 1 … 1 … … … … … … … aij 1 1 … 0 … 1 … … … … … … … anj 1 1 … 1 … 0 Hay viết cách khác: Ma trận liền kề của đồ thị đầy đủ Kn là: 0 nếu i = j A = (aij), trong đó aij = 1 nếu i ≠ j Ma trận liền kề của đồ thị vòng Cn: ai1 ai2 ai3 … aij-1 aij aij+1 … ain-1 ain a1j 0 1 0 … 0 0 0 … 0 1 a2j 1 0 1 … 0 0 0 … 0 0 a3j 0 1 0 … 0 0 0 … 0 0 … … … … … … … … … … … aij 0 0 0 … 1 0 1 … 0 0 … … … … … … … … … … … anj 1 0 0 … 0 0 0 … 1 0 Viết cách khác: Ma trận liền kề của đồ thị vòng Cn là: A = (aij), trong đó: 1 nếu j=2 hoặc j=n – Với i=1: aij= 0 nếu j≠2và j≠n 1 nếu j=1 hoặc j=n-1 – Với i=n: aij= 0 nếu j≠1 và j≠n-1 -Với i≠1 và i≠n: 1 nếu j=i+1, j=i-1 aij = 0 nếu j≠i+1 và j≠i-1 c) Ma trận liền kề A của đồ thị bánh xe Wn: ai1 ai2 ai3 … aij-1 aij aij+1 … ain-1 ain ain +1 a1j 0 1 0 … 0 0 0 … 0 1 1 a2j 1 0 1 … 0 0 0 … 0 0 1 … … … … … … … … … … … … aij 0 0 0 … 1 0 1 … 0 0 1 … … … … … … … … … … … … anj 1 0 0 … 0 0 0 … 1 0 1 an+1j 1 1 1 … 1 1 1 … 1 1 0 Ma trận liền kề của đồ thị phân đôi đầy đủ Km,n: Cho G=(V,E)=Km,n, trong đó V=V1 U V2 V1={v1,v2,…,vm} V2={v’1,v’2,…,v’n} Ta có ma trận liền kề của Km,n như sau: v1 v2 … vm v’1 v’2 … v’n v1 0 0 … 0 1 1 … 1 v2 0 0 … 0 1 1 … 1 … … … … … … … … … vm 0 0 … 0 1 1 … 1 v’1 1 1 … 1 0 0 … 0 v’2 1 1 … 1 0 0 … 0 … … … … … … … … … v’n 1 1 … 1 0 0 … 0 Ma trận liền kề của đồ thị lập phương Qn( 2n đỉnh ứng với n xâu nhị phân khác nhau chứa bit 0, 1) 00..00 00..01 00..10 00..11 … 10..00 10..01 … 11..11 00..00 0 1 1 0 … 1 0 … 0 00..01 1 0 0 1 … 0 1 … 0 00..10 1 0 0 1 … 0 0 … 0 00..11 0 1 1 0 … 0 0 … 0 … … 10..00 1 0 0 0 … 0 1 … 0 10..01 0 0 0 0 … 1 0 … 0 … 11..11 0 0 0 0 … 0 0 … 0 *Bài 7: Hai đơn đồ thị với ma trận liền kề sau đây có là đẳng cấu không? 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 0 Ma trận 1 Ma trận 2 Lời giải: * Cách 1: Dựa vào ma trận liền kề, ta có thể vẽ được 2 đồ thị tương ứng như sau: V1 V4 V3 V2 V’4 V’1 V’3 V’2 G1 G2 G1=(V,E): đồ thị ứng với ma trận 1 G2=(V’,E’): đồ thị ứng với ma trận 2 Dễ dàng nhận thấy: Số cạnh của 2 đồ thị khác nhau: G1 có 4 cạnh, G2 có 5 cạnh Ngoài ra: G1 có 1 đỉnh bậc 1 (V3) 2 đỉnh bậc 2 (V1,V2) 1 đỉnh bậc 3 (V4) G2 không có đỉnh bậc 1 2 đỉnh bậc 2(V’2,V’3) 2 đỉnh bậc 3(V’1,V’4) Vậy 2 đồ thị trên không đẳng cấu. * Cách 2: Tổng các phần tử trong ma trận liền kề của đơn đồ thị bằng tổng số bậc của các đỉnh và bằng 2 lần số cạnh của đồ thị. Từ 2 ma trận trên ta có: Đồ thị ứng với ma trận 1 có 8:2=4 cạnh Đồ thị ứng với ma trận 2 có 10:2=5 cạnh Như vậy, 2 đơn đồ thị ứng với 2 ma trận liền kề trên không đẳng cấu. *Bài 8: Hai đơn đồ thị với ma trận liên thuộc sau có là đẳng cấu không? 1 0 0 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 Lời giải: – Ma trận 1: e1 e2 e3 e4 e5 u1 1 1 0 0 0 u2 1 0 1 0 1 u3 0 0 0 1 1 ứng với đồ thị G=(U,E) u4 0 1 1 1 0 Ma trận 2: e’1 e’2 e’3 e’4 e’5 v1 0 1 0 0 1 v2 0 1 1 1 0 ứng với đồ thị G’=(V,E’) v3 1 0 0 1 0 v4 1 0 1 0 1 U2 V1 V2 U1 e1 e’2 e2 e3 e5 e’5 e’3 e’4 U3 V4 V3 U4 e4 e’1 G=(U,E) G’=(V,E’) Xét phép đẳng cấu f: e1→e’2 e2→e’5 e3→e’3 e4→e’1 e5→e’4 Lúc này, ta biểu diễn lại ma trận liên thuộc của đồ thị G’ theo thứ tự các đỉnh v1, v2, v3,v4 và thứ tự các cạnh e’2, e’5, e’3, e’1, e’4 như sau: e’2 e’5 e’3 e’1 e’4 v1 1 1 0 0 0 v2 1 0 1 0 1 v3 0 0 0 1 1 v4 0 1 1 1 0 Ma trận n ày và ma trận liên thuộc của G bằng nhau. Vậy G và G’ đẳng cấu với nhau. * Bài 9: Các đồ thị G và G’ sau có đẳng cấu với nhau không? v2 v1 v6 u1 a) v4 u2 u3 v5 u4 v3 u6 u5 v2 v1 u3 u2 u1 b) v3 v6 u6 u5 u4 v5 v4 Lời giải: Xét phép đẳng cấu f: u1→v2 u2→v3 u3→v6 u4→v5 u5→v4 u6→v1 Lúc này, ma trận liền kề của G (theo thứ tự các đỉnh u6, u1, u2, u5, u4, u3) và ma trận liền kề của G’ là bằng nhau và bằng: 0 1 1 1 1 1 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 0 Vậy G và G’ đẳng cấu với nhau. b)Xét phép đẳng cấu f: u1→v3 u2→v5 u3→v1 u4→v2 u5→v4 u6→v6 Lúc này, ma trận liền kề của G(theo thứ tứ các đỉnh v3, v4, v1, v5, v2, v6) và na trận liền kề của G’ bằng nhau và bằng: 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 Vậy, hai đồ thị G và G’ đẳng cấu với nhau. * Bài 10: Cho V={2,3,4,5,6,7,8} và E là tập hợp các cặp phần tử (u,v) của V sao cho u<v và u,v nguyên tố cùng nhau. Hãy vẽ đồ thị có hướng G=(V,E). Tìm số các đường đi phân biệt độ dài 3 từ đỉnh 2 tới đỉnh 8. Lời giải: Các cặp phần tử (u,v) thỏa mãn yêu cầu đề bài là: E={(2,3), (2,5), (2,7), (3,4), (3,5), (3,7), (3,8), (4,5), (4,7), (5,6), (5,7), (5,8), (6,7), (7,8)} Đồ thị G cần vẽ : 4 3 2 8 7 6 5 Các đường đi phân biệt độ dài 3 đi từ 2 đến 8 là: 2, 3, 7, 8 2, 3, 5, 8 2, 5, 7, 8 * Bài 11: Hãy tìm số đường đi độ dài n giữa hai đỉnh liền kề (t.ư. không liền kề) tùy ý trong K3,3 với mỗi giá trị của n sau: a) n=2 b) n=3 c) n=4 d) n=5 Lời giải: V4 V5 V6 V2 V3 V1 K3,3 * Cách 1: Tập các đỉnh của K3,3 được chia làm 2 phần: Phần 1 gồm V1, V2, V3 Phần 2 gồm V4, V5, V6 Trong đó, 2 đỉnh thuộc cùng 1 phần thì không liền kề 2 đỉnh thuộc 2 phần khác nhau thì liền kề. Gọi d là số đường đi độ dài n giữa 2 đỉnh thuộc K3,3. * Nếu n chẵn thì điểm đầu và điểm cuối của đường đi phải nằm trong cùng 1 phần (chúng không liền kề). * Nếu n lẻ thì điểm đầu và điểm cuối của đường đi phải nằm ở 2 phần khác nhau (chúng liền kề với nhau). Mà khi xuất phát từ 1 đỉnh ta luôn có 3 cách đi(do mỗi phần gồm 3 đỉnh). Áp dụng quy tắc nhân ta có số đường đi có độ dài n giữa 2 đỉnh là: Nếu 2 đỉnh liền kề: + n chẵn: d=0 + n lẻ : d=3n-1(do cạnh cuối cùng nối với đỉnh cuối chỉ có 1 cách) Nếu 2 đỉnh không liền kề: + n chẵn : d=3n-1(do cạnh cuối cùng nối với đỉnh cuối chỉ có 1 cách) + n lẻ : d=0 Áp dụng cụ thể: Độ dài Đỉnh n=2 n=3 n=4 n=5 Liền kề d=0 d=9 d=0 d=81 Không liền kề d=3 d=0 d=27 d=0 * Cách 2: Đồ thị K3,3 có ma trận liền kề theo thứ tự các đỉnh V1, V2, V3, V4, V5, V6 như sau: 0 0 0 1 1 1 0 0 0 1 1 1 A= 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 Ta có mệnh đề: Cho G là một đồ thị (vô hướng hoặc có hướng) với ma trận liền kề A theo thứ tự các đỉnh v1, v2, …, vn. Khi đó số các đường đi khác nhau độ dài r từ vi tới vj trong đó r là một số nguyên dương, bằng giá trị của phần tử dòng i cột j của ma trận Ar. n Ta có: An = A.A…A.A 3n-1 3n-1 3n-1 0 0 0 3n-1 3n-1 3n-1 0 0 0 A= 3n-1 3n-1 3n-1 0 0 0 , nếu n chẵn 0 0 0 3n-1 3n-1 3n-1 0 0 0 3n-1 3n-1 3n-1 0 0 0 3n-1 3n-1 3n-1 0 0 0 3n-1 3n-1 3n-1 0 0 0 3n-1 3n-1 3n-1 0 0 0 3n-1 3n-1 3n-1 A= 3n-1 3n-1 3n-1 0 0 0 , nếu n lẻ 3n-1 3n-1 3n-1 0 0 0 3n-1 3n-1 3n-1 0 0 0 Như vậy, theo mệnh đề trên, áp dụng vào các trường hợp cụ thể đề bài đã cho ta có kết quả như ở cách 1. * Bài 12: Một cuộc họp có ít nhất 3 đại biểu đến dự.Mỗi người quen ít nhất 2 đại biểu khác.Chứng minh rằng có thể sắp xếp một số đại biểu ngồi xung quanh một bàn tròn để mỗi người ngồi giữa 2 người mà đại biểu đó quen. Lời giải: * Ta có thể biểu diễn mối quan hệ của các đại biểu đến tham dự cuộc họp bằng đơn đồ thị G=(V,E). G có n đỉnh (n≥3, n là số đại biểu) và e cạnh. Mỗi đỉnh của đồ thị ứng với 1 đại biểu, giữa 2 đỉnh ứng với 2 đại biểu quen nhau tồn tại 1 cạnh. Gọi Vi (i=1,2,…,n): đỉnh của đồ thị (ứng với 1 đại biểu) Do mỗi người quen ít nhất 2 đại biểu khác nên deg(Vi) ≥ 2 n ∑deg(Vi) ≥ 2n i=1 Số cạnh của đồ thị: e ≥ n (1) * Mặt khác, theo đề ra ta có: các đại biểu ngồi xung quanh 1 bàn tròn. Vì vậy, đồ thị biểu diễn cách sắp xếp chỗ ngồi của các đại biểu thỏa yêu cầu là đồ thị vòng Cn. Trong đồ thị vòng Cn có n (cạnh), n cạnh này được lấy từ e cạnh của G(do nó biểu thị mối quan hệ giữa các đại biểu) (2) * Tập đỉnh của G và Cn bằng nhau và bằng n. (3) Từ (1), (2) và (3) cho thấy, Cn là đồ thị con bao hàm của G.(Cn được tạo ra bằng cách bỏ đi một số cạnh thích hợp của G) Vậy, dựa trên mối quan hệ giữa các đại biểu như trên ta có thể sắp xếp các đại biểu ngồi quanh bàn tròn sao cho mỗi người ngồi giữa 2 người mà họ quen.( Đpcm) *Bài 13: Một lớp học có ít nhất 4 sinh viên. Mỗi sinh viên thân với ít nhất 3 sinh viên khác. Chứng minh rằng có thể xếp một số chẵn sinh viên ngồi quanh một cái bàn tròn để mỗi sinh viên ngồi giữa 2 sinh viên mà họ thân. Lời giải: * Mối quan hệ giữa các sinh viên trong lớp có thể biểu diễn bằng 1 đơn đồ thị G=(V,E) n đỉnh(n≥4, n: số sinh viên), e cạnh. Hai đỉnh ứng với 2 sinh viên thân nhau liền kề với nhau. Gọi Vi (i=1,2,…,n): đỉnh của đồ thị ứng với 1 sinh viên. Mỗi sinh viên thân với ít nhất 3 người deg(Vi) ≥ 3 n ∑ deg(Vi) ≥ 3n i=1 Tổng số cạnh của G là: e ≥ 3n/2 (1) * Mặt khác, theo đề ra ta có: cách sắp xếp chỗ ngồi của các sinh viên có thể biểu diễn bằng đồ thị vòng Cn (do các sinh viên ngồi quanh bàn tròn). Cn có n cạnh (n cạnh này lấy từ e cạnh của G) Mà e phải là số nguyên suy ra n phải chia hết cho 2 (n chẵn) Tập đỉnh của Cn và G bằng nhau và bằng n. Từ đó, ta thấy Cn chính là đồ thị con bao hàm của G.(Cn có thể tạo ra từ G bằng cách bỏ đi một số cạnh thích hợp) Hay: có thể sắp xếp một số chẵn sinh viên ngồi quanh một cái bàn tròn sao cho mỗi người ngồi giữa 2 người mà họ thân.( Đpcm) * Bài 14: Trong một cuộc họp có đúng 2 đại biểu không quen nhau và mỗi đại biểu này có một số lẻ người quen đến dự.Chứng minh rằng luôn luôn có thể xếp một số đại biểu ngồi chen giữa 2 đại biểu nói trên, để mỗi người ngồi giữa 2 người mà đại biểu đó quen. Lời giải: Mối quan hệ giữacác đại biểu đến tham dự cuộc họp có thể biểu diễn bằng 1 đơn đồ thị G=(V,E).Trong đó mỗi đỉnh là một đại biểu, giữa 2 đỉnh ứng với 2 đại biểu quen nhau tồn tại 1 cạnh. Trong cuộc họp có đúng 2 đại biểu không quen nhau và có số lẻ người quen đến tham dự.Vậy G có đúng 2 đỉnh không liền kề và 2 đỉnh này có bậc lẻ. Từ mệnh đề: Nếu một đồ thị có đúng hai đỉnh bậc lẻ thì hai đỉnh này phải liên thông, tức là có một đường đi nối chúng ta suy ra có thể tìm ra một số đại biểu ngồi chen vào giữa 2 đại biểu này sao cho mỗi đại biểu ngồi giữa 2 người mà đại biểu đó quen.(do 2 đỉnh ứng với 2 người này không liên thông, 2 người không ngồi sát nhau và họ quen với n-2 người còn lại) *Bài 15: Một thành phố có n (n ³ 2) nút giao thông và hai nút giao thông bất kỳ đều có số đầu mối đường ngầm tới một trong các nút giao thông này đều không nhỏ hơn n. Chứng minh rằng từ một nút giao thông tuỳ ý ta có thể đi đến một nút giao thông bất kỳ khác bằng đường ngầm. Lời giải: – Ta có thể xem hệ thống đường ngầm của thành phố là một đơn đồ thị có các đỉnh là các nút giao thông. Số đỉnh của đồ thị chính là số nút giao thông: n (n≥2) Cạnh của đồ thị là đường ngầm nối 2 nút giao thông. Theo đề ra ta có: Hai nút giao thông bất kì đều có số đầu mối đường ngầm tới một trong các nút giao thông đều không nhỏ hơn n. – Ta có mệnh đề: Mọi đơn đồ thị n đỉnh (n≥2) có tổng bậc của 2 đỉnh tùy ý không nhỏ hơn n đều là đồ thị liên thông. Vậy, theo định lí trên, hệ thống đường ngầm của thành phố là đồ thị liên thông. Suy ra, từ một nút giao thông tuỳ ý ta có thể đi đến một nút giao thông bất kỳ khác bằng đường ngầm.(Đpcm). *Bài 16: Có bao nhiêu đơn đồ thị đẳng cấu với n đỉnh khi: a) n=2 b) n=3 c) n=4 Lời giải: Với n=2, có 2 đơn đồ thị không đẳng cấu như sau: và Với n=3, có 4 đơn đồ thị không đẳng cấu: c) Với n=4 có 11 đơn đồ thị không đẳng cấu: