BÀI TẬP TOÁN RỜI RẠC - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (10 trang)

Trang chủ

Giáo án - Bài giảng

Toán học

BÀI TẬP TOÁN RỜI RẠC

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (942.27 KB, 10 trang )

BT TRRMĐBÀI TẬP TỐN RỜI RẠCI/ Logic tốn họcI.1: Lập bảng chân trị (giá trị chân lý) cho các mệnh đề sau1/ p  (q  r )2/ p  (q  r )3/ ( p  q)  ( p  r )4/ ( p  q)  ( p  r )5/ ( p  q)  (q  r )6/ ( p  q)  (q  r )I.2: Chứng minh rằng các mệnh đề sau là một hằng đúng (đồng nhất đúng)1/ ( p  q)  ( p  q)2/ (( p  q)  p)  q3/ ( p  ( p  q))  qI.3: Hãy chứng tỏ rằng các mệnh đề sau không phải là một hằng đúng1/ ( p  z)  p  ( z  q)  q2/ (( x  y)  ( y  z)  (t  z)  t )  xI.4: Chứng minh rằng các cặp biểu thức logic sau là tương đương1/ ( p  q) và (q  p) 2/ ( p  q) và ( p  q) 3/ p  q và ( p  q)  ( p  q)I.5: Chứng tỏ rằng các cặp mệnh đề sau là không tương đương1/ ( p  q)  z và p  ( q  z )2/ p  q và p  qI.6: 1/ Kiểm tra các suy luận sau là đúng hay sai?a/b/xrpyxy zryc/prrstszyztxxp2/ Cho p1 , p2 , … , pn là các mệnh đề chứng minh rằng:p1  p2  ...  pn  p1  p2  ...  pn3/ Dùng quy tắc suy diễn, chỉ ra các công thức sau là hằng đúng (đồng nhất đúng):a/ (( x  y)  ( y  z )  x)  zb/ (( A  B)  ( B  C )  ( D  C )  ( D  E)  E)  Ac/ (A → B) ∧ (A ∨ C) ∧ (𝐶 ∨ D) → (B ∨ D).d/ ((X1 → X2) ∧ (X3 → X4) ∧ (𝑋1 → X3)) → (X2 ∨ X4).e/ (((A ∨ B) → (C ∧ D)) ∧ (C → E) ∧ 𝐸) → (𝐴𝐶).4/ Tìm dạng chuẩn tắc tuyển (DCTT) và dạng chuẩn tắc hội (DCTH) của các công thức saua/ P  X  (Y  X )  (Y  ( H  Z ))b/ P1  (( A  B)  ( A  C )  (C  D))  ( B  D)I.7: 1/ Cho p(x, y) là vị từ phụ thuộc vào hai biến x, y lấy giá trị trên tập {1, 2, 3} Dùng phép hội và phép tuyểnviết các mệnh đề sau:a- x: p(x, 3)b- y: p(1, y)c- x y: p(x, y)d- x y: p(x, y)e- x y: p(x, y)f- x y: p(x, y)2/ Cho p(x, t) là phát biểu “x + t = 0” phụ thuộc vào hai biến x, t lấy giá trị trên tập các số thực R. Hãy chobiết chân trị (giá trị chân lý) của các mệnh đề sau và viết mệnh đề phủ định của nó:a/ p(2, 3)b/ p(10, -10)c/ t x : p(x, t)d/ x t : p(x, t)3/ Cho p(u, v) là phát biểu “u2 – v2 = 0” phụ thuộc vào hai biến u, v lấy giá trị trên tập các số thực R. Hãy chobiết chân trị của các mệnh đề sau và viết mệnh đề phủ định của nó:a/ p(4, 5)b/ p(6, -6)c/ v u : p(u, v)d/ u v : p(u, v)1 BT TRRMĐ4/ Cho p(x, y, z) là phát biểu “x + y = z” phụ thuộc vào ba biến x, y, z lấy giá trị trên tập các số thực R. Hãyxác định chân trị của các mệnh đề:x y z: p(x, y, z) vàz x y: p(x, y, z)I.8: Chứng minh các mệnh đề sau:1/ “Nếu n là số lẻ thì n2 cũng lẻ” , bằng chứng minh trực tiếp2/ “Nếu 3n + 2 là số lẻ thì n cũng lẻ”, bằng chứng minh phản chứng3/ “Nếu số nguyên n khơng chia hết cho 3 thì n2 1 (mod3), bằng chứng minh phân theo các trường hợp4/ “Nếu n là một số nguyên lớn hơn 1 và p là ước số nguyên dương lớn hơn 1 nhỏ nhất của n thì p là một sốngun tố”5/ “Có ít nhất một trong các số thực a1, a2, …, an lớn hơn hay bằng trung bình cộng của các số này”.6/ Cho x, y là hai số thực khi đó: Max(x, y) + Min(x, y) = x + yI.9: Chứng minh hay bác bỏ rằng:1/ Có ba số nguyên dương lẻ liên tiếp là các số nguyên tố2/ Tích hai số vô tỷ là một số vô tỷ3/ (n2 –n + 41) là một số nguyên tố khi n là số nguyên dươngI.10: Bằng qui nạp toán học hãy chứng minhn(n  1)( n  2)1/ 1.2  2.3  ...  n(n  1) , với n là số nguyên dương32/ 1.2 0  2.21  3.2 2  ...  n.2 n 1  (n  1).2 n  1 ; với n là số nguyên dương(n  1)( 2n  1)( 2n  3)3/ 12  32  52  ...  (2n  1) 2 , với n là số nguyên không âm31  ( 7) n 14/ 2  2.7  2.7 2  ...  2.(7) n , với n là số nguyên không âm45/ 1.1!2.2!...  n.n!  (n  1)!1, với n là số nguyên dương111n6/, với n là số nguyên dương ... 1.2 2.3n.(n  1) n  17/ 2 n  n 3, với số nguyên n=10, 11, 12, . . . a 08/ Cho ma trận A   , với a, b  R. 0 ba n 0 Chứng minh rằng: A  , với n là số nguyên dươngn0 b I. 111/ Cho dãy số {an} được xác định bằng đệ qui như saua0 = 1, an = an – 1 + n , với n > 0Chứng minh rằng: an = 1 + n(n+1)/2 , với n là số nguyên không âm2/ Cho dãy số {an} được xác định bằng đệ qui như saua0 = 1, an = 3an – 1 + 1 , với n > 03n 1  1Chứng minh rằng: an =, với n là số nguyên không âm23/ Cho dãy số {an} được xác định bằng đệ qui như saua0 = 4, an = an – 1 + 2n + 3 , với n > 0Chứng minh rằng: an = n2+ 4n + 4 , với n là số nguyên không âm4/ Cho dãy số {an} được xác định bằng đệ qui như saua2 = 6 ; a3 = 9, an = 2an – 1 – an – 2 , với n > 3Chứng minh rằng: an = 3n , với n =2, 3, 4, …n2 BT TRRMĐ5/ Cho dãy số {an} được xác định bằng đệ qui như saua0 = 0 ; a1 = 4, an = 8an – 1 – 16an – 2 , với n > 1Chứng minh rằng: an = n.4n , với n là số nguyên không âmI.12: Giải các hệ thức đệ quy truy hồi tuyến tính sau:a/ an = 5an−1 − 6an−2, với n ≥ 2, a0 = 1, a1 = 0.b/ an = −4an−1 − 4an−2, với n ≥ 2, a0 = 6, a1 = 8c/ an = an−2/4 , với n ≥ 2, a0 = 1, a1 = 0d/ an = 7an−2 + 6an−3, với n ≥ 3, a0 = 9, a1 = 10, a2 = 32.e/ an = 6an−1 − 11an−2 + 6an−3, với n ≥ 3, a0 = 2, a1 = 5, a2 = 15.f/ an = 5an−2 − 4an−4, với n ≥ 4, a0 = 3, a1 = 2, a2 = 6, a3 = 8.I.13: Một nhà máy sản xuất ô tô thể thao theo đơn đặt hàng với tốc độ ngày càng tăng. Tháng đầu chỉ sản xuấtmột chiếc; tháng thứ hai làm được hai chiếc và cứ như vậy tháng thứ n sản xuất được n chiếc.a/ Hãy tìm cơng thức truy hồi tính số ơ tơ sản suất được trong n tháng đầu của nhà máy.b/ Có bao nhiêu ơ tơ sản xuất được trong năm đầu tiên.c/ Hãy tìm cơng thức tường minh tính số ơ tơ sản xuất được trong n tháng đầu tiên của nhà máy.I.14: (Tháp Hà Nội). Một trị chơi xếp hình rất phổ cập vào cuối thế kỷ 19 gọi là Tháp Hà Nội. Tương truyềnrằng, tại một ngơi tháp Hà Nội có một tấm đế bằng đồng trên đó có ba cái cọc bằng kim cương. Trên mộttrong ba cái cọc thượng đế đã để 64 chiếc đĩa bằng vàng với đường kính giảm dần. Ngày đêm các nhà Sư dịchchuyển đĩa sang một chiếc cọc khác theo quy tắc: mỗi lần chỉ được dịch chuyển một đĩa, mỗi đĩa có thể dịchchuyển từ một cọc này sang cọc khác bất kỳ, nhưng không được để một chiếc đĩa lên trên một đĩa khác cóđường kính nhỏ hơn. Với thời gian bao lâu thì tất cả các đĩa được chuyển sang một chiếc cọc khác (nếu mỗilần dịch chuyển mất một giây)?3 BT TRRMĐII/ Các phương pháp đếmII.1:1/ Có bao nhiêu xâu nhị phân khác nhau có độ dài bằng 10 và có bis đầu là 1 và bis cuối cùng là 02/ Có bao nhiêu số chẵn khác nhau gồm 10 chữ số được tạo thành từ hai chữ số 1 và 23/ Có bao nhiêu xâu nhị phân khác nhaua- Có độ dài bằng 9b- Có độ dài bằng 9 có bis đầu tiên là 1 và bis cuối cùng là 04/ Có bao nhiêu số điện thoại khác nhaua- Gồm 7 chữ số và khơng có số 0 đứng đầub- Gồm 7 chữ số khác nhau và khơng có số 0 đứng đầu5/ Có bao nhiêu tập con có khơng q 2 phần tử của một tập gồm có 10 phần tử6/ Có bao nhiêu tập con có ít nhất 8 phần tử của một tập gồm có 10 phần tử7/ Một đội tuyển bóng đá gồm 15 cầu thủ có khả năng như nhaua- Có bao nhiêu cách chọn 11 cầu thủ vào chơi trận khai mạcb- Trong 11 cầu thủ đó có bao nhiêu cách chọn 1 Thủ môn và 1 Đội trưởng8/ Đội tuyển văn nghệ của lớp có 10 nam và 15 nữ. Hỏi có bao nhiêu cách chọn một tốp 6 người của đội lênbiểu diễn trong đó số nam bằng số nữ9/ Một phiếu trắc nghiệm gồm 10 câu hỏi, mỗi câu hỏi có 4 phương án trả lờia- Có bao nhiêu cách điền 1 phiếu trắc nghiệm, nếu mọi câu hỏi đều được trả lờib- Có bao nhiêu cách điền 1 phiếu trắc nghiệm, nếu có thể bỏ trống10/ Một cuộc thi trắc nghiệm gồm có 100 câu hỏi điền vào ơ đúng/sai. Hỏi có bao nhiêu cách khác nhau màsinh viên có thể điền vào .a- Nếu khơng cho phép câu hỏi nào để ô trốngb- Nếu cho phép để ô trống11/ Có bao nhiêu số nguyên dương gồm đúng 3 chữ sốa- Chia hết cho 7b- Chia hết cho 3c- Chia hết cho 4d- Chia hết cho 3 và 4 e- Chia hết cho 3 hoặc 4f- Chia hết cho 3 nhưng không chia hết cho 4g- không chia hết cho 412/ Xét tất cả các ánh xạ từ tập A gồm k phần tử vào tập B gồm n phần tử.a/ Có bao nhiêu ánh xạ từ A vào Bb/ Có bao nhiêu đơn ánh từ A vào BII. 2:1/ Giả sử nhóm thực hành có 9 sinh viêna- Chứng tỏ rằng trong nhóm có ít nhất 5 sinh viên nam hoặc ít nhất 5 sinh viên nữb- Chứng tỏ rằng trong nhóm có ít nhất 3 sinh viên nam hoặc ít nhất 7 sinh viên nữ2/ Lớp CNTT có 93 sinh viên dự thi tốn rời rạc.Hỏi có ít nhất bao nhiêu sinh viên đạt điểm thi bằng nhau, nếu thang điểm được chấm gồm 10 bậc: 1, 2,.. ,10.3/ Trung tâm đào tạo xét học bổng cho 26 sinh viên CNTT với 5 mức học bổng là 200 nghìn đồng ; 400 nghìnđồng , 600 nghìn đồng, 800 nghìn đồng và 1 triệu đồng. Hỏi có ít nhất bao nhiêu sinh viên sẽ nhận được sốtiền học bổng như nhau4/ Chứng minh rằng mọi tập con A có ít nhất 11 phần tử của tập X = {1, 2, …,18, 19} sẽ có hai trong số cácphần tử có tổng bằng 20.5/ Trong một kỳ thi tin học có 6 thí sinh được vào chung kết. Thể lệ của cuộc thi như sau: Mỗi thí sinh phảigiải 5 bài tốn. Mỗi bài tốn đúng được tính 4 điểm. Mỗi bài tốn sai hoặc khơng làm được đều bị trừ 2 điểm,nhưng số điểm bị trừ lớn hơn số điểm đạt được thì số điểm của thí sinh đó coi như bằng 0. Hãy chứng tỏ rằngtrong 6 thí sinh đó có ít nhất 2 thí sinh bằng điểm nhau.4 BT TRRMĐIII/ Cấu trúc đại sốIII. 1:1/ Trên tập hợp các số thực R, xét quan hệ 2 ngôi  được xác định như saua, b  R , a  b nếu và chỉ nếu (a – b) là một số nguyêna- Chứng minh rằng  là một quan hệ tương đương trên Rb- Tìm các lớp tương đương chứa : 0 ; 0,52/ Trên tập hợp các số nguyên Z, xét quan hệ 2 ngôi R được xác định như saua, b  Z, aRb nếu và chỉ nếu a = ba- Chứng minh rằng R là một quan hệ tương đương trên Z .b- Xác định lớp tương đương chứa: 0;12; - 4.3/ Trên tập các số nguyên Za- Chứng minh rằng: quan hệ R = { (a, b) \ a = b + 3k , với k  Z } làmột quan hệ tương đương trên Z.b- Xác định lớp tương đương: chứa 7,chứa -14/ Trên tập các số nguyên Za- Chứng minh rằng: quan hệ R = { (a, b) \ a  b ( mod4) } là một quan hệ tương đương trên Z.b- Xác định lớp tương đương: chứa 7, chứa -25/ Trên tập các số nguyêna- Chứng minh rằng: quan hệ R = { (a, b) \ a + b là một số chẵn } là một quan hệ tương đương trên Z.c- Quan hệ R = { (a, b) \ a + b là một số lẻ } có là một quan hệ tương đương hoặc quan hệ thứ tựtrên Z hay không ?6/ Cho X = {1, 2, 3, 4, 5, 6, 7, 8 } . Trên X ta định nghĩa quan hệ R như sau:x, y X: xRy  x – y = 2k, kZ.a/ CMR R là một quan hệ tương đương trên X.b/ Tìm phân hoạch tương đương trên X do R sinh ra.III. 2:1/ Trong tập số thực R, quan hệ hai ngôi  như saua  b  a 3  b3  a  bChứng minh rằng  là một quan hệ tương đương trên R. Tìm phân hoạch tương đương trên R do  sinh ra.2/ Ta ký hiệu B  Z  N và quan hệ hai ngôi R trên B như sau m, n  R  p, q   mq  npChứng minh rằng R là quan hệ tương đương trên B. Xác định các lớp tương đương.III. 3:1/ Cho tập X = {a, b, c, d} và R là một quan hệ 2 ngơi trên X có ma trận biểu diễn như sau1 0 0 01 1 0 0MR  1 1 1 10 0 0 1a- Liệt kê tất cả các phần tử của R. Chứng tỏ rằng R là một quan hệ thứ tự trên Xb- Vẽ biểu đồ Hasse của (X,R)2/ Cho tập X={1, 2, 3, 4} và quan hệ 2 ngôi R trên X có ma trận biểu diễn như sau:1 0 0 01 1 1 1MR  0 0 1 10 0 0 1a- Liệt kê tất cả các phần tử của R. Chứng tỏ rằng R là một quan hệ thứ tự trên X5 BT TRRMĐb- Vẽ biểu đồ Hasse của (X, R)3/ Trên tập Z+ tất cả các số nguyên dương với quan hệ “chia hết” ký hiệulà được xác định như sau: a, b  Z+, ab nếu và chỉ nếu có k Z+ sao cho b= k.aa- Chứng minh rằng quan hệ  là một quan hệ thứ tự trên Z+b- Xét tập con A = {1, 2, 4, 5, 12, 20} của tập Z+. Hãy tìm phần tử lớn nhất, nhỏ nhất (nếu có), phần tửtối tiểu, tối đại của tập A4/ Cho tập X = {1, 2, 4, 5, 12, 20} với quan hệ thứ tự “chia hết” ký hiệu là a- Liệt kê tất cả các phần tử của .b- Hãy vẽ biểu đồ Hasse của (X, ), từ đó chỉ ra các phần tử lớn nhất, nhỏ nhất (nếu có), tối đại, tốitiểu của X5/ Cho tập X = {1, 3, 6, 5, 12, 20} với quan hệ thứ tự “chia hết” ký hiệu là a- Liệt kê tất cả các phần tử của .b- Hãy vẽ biểu đồ Hasse của (X, ), từ đó chỉ ra các phần tử lớn nhất, nhỏ nhất (nếu có), tối đại, tốitiểu của X6/ Cho tập X = { 2, 4, 3, 8, 6, 12, 24} với quan hệ thứ tự “chia hết” ký hiệu là a- Liệt kê tất cả các phần tử của .b- Hãy vẽ biểu đồ Hasse của (X, ), từ đó chỉ ra các phần tử lớn nhất, nhỏ nhất (nếu có), tối đại, tốitiểu của X7/ Cho tập X = { 3, 6, 5, 10, 12, 30, 60} với quan hệ thứ tự “chia hết” ký hiệu là a- Liệt kê tất cả các phần tử của .b- Hãy vẽ biểu đồ Hasse của (X, ), từ đó chỉ ra các phần tử lớn nhất, nhỏ nhất (nếu có), tối đại, tốitiểu của X8/ Cho tập E ={1, 2, 3}a/ Hãy liệt kê tất cả các tập con của tập Eb/ Hãy vẽ biểu đồ Hasse của tập có thứ tự (P (E),  ). Trong đó P(E) là tập tất cả các tập con của E và là quan hệ bao hàm trong trên các tập hợpIII. 4Cho tập E, S = {A: A  E}. Chứng minh rằng S cùng với 2 phép tốn hai ngơi hợp  , giao  và phép tốnmột ngơi bù – trên S là một đại số Bool.III. 51/ Với giá trị nào của các biến Bool x, y, z ta có:a- x + y + z = xyzb- x(y + z) = x + yz c- x y z  x  y  z2/ Tìm giá trị của các biến Bool x và y thỏa mãn phương trìnha- x. y  x  yb- x.y = x + y3/ Chứng minh rằngax + xy = xbt y  yu  tu  t y  yu  t u4/ Vẽ mạch logic thực hiện các hàm Bool :a- f ( x, y )  ( x  y ) x b- f ( x, y )  ( x  y )xc- f ( x, y )  xy  x yd- f ( x, y )  x y  x ye- f ( x, y, z )  x( y  z )5/ Hãy tìm dạng chính tắc tuyển của hàm Bool saua- f ( x, y, z )  xy  zb- f ( x, y, z )  x y  xzf- f ( x, y, z )  ( x  y ). zc- f ( x, y, z)  x y  zd- f ( x, y, z )  xy  ze- f ( x, y, z )  ( x  y ). zf- f ( x, y, z )  x y  xz6/ Khai triển cực tiểu của tổng các tích:abxy  x yx y  xy  x yc-xy z  x y z  x yz  x y zd-x yz  x y z  x yz  x yz  x y z6 BT TRRMĐIV/ Lý thuyết đồ thịIV. 11/ Có bao nhiêu cạnh trong đồ thị có 8 đỉnh, mỗi đỉnh có bậc là 4?2/ Cho biết các đỉnh của đồ thị có bậc là 3, 3, 2, 2, 2. Tìm số cạnh của đồ thị và vẽ đồ thị này.3/ Có thể tồn tại đồ thị 15 đỉnh, mỗi đỉnh có 5 bậc khơng? Hãy chỉ ra đồ thị có 5 đỉnh với các bậc: 3, 3, 3, 3, 2là tồn tại.4/ Tìm bậc vào và bậc ra của mỗi đỉnh trong đồ thị G có hướng sau đây:abcdeIV. 2Cho G=<V, E> là một đơn đồ thị, R là một quan hệ hai ngôi trên V gồm các cặp đỉnh (x, y) sao cho có đườngđi từ x tới y hoặc x=y. Chứng tỏ rằng R là một quan hệ tương đương trên V.IV. 31/ Hãy chỉ ra rằng nếu đơn đồ thị G có k thành phần liên thơng và các thành phần liên thơng này tương ứng cón1, n2, …, nk đỉnh thì số các cạnh của G khơng vượt quá ∑𝑘𝑖=1 𝐶𝑛2𝑖 cạnh.2/ Cho đồ thị G như hình vẽ sau:123Hãy chỉ ra nó là đồ thị phân đơi4576IV. 41/ Đồ thị nào trên các hình sau đây có đường Eluer? Nếu có hãy chỉ ra 1 đườngabdcagffbG1cbaecgdeG2G3d2/ Đồ thị nào trên các hình sau đây có chu trình Euler? Có hãy chỉ ra, nếu khơng thì có đường Eluer khơng?nếu có hãy chỉ ra 1 đường Euler.baabfececdG17d BT TRRMĐG2IV. 5Đồ thị nào trên các hình sau đây có chu trình Hamilton? Có hãy chỉ ra, nếu khơng thì có đường Hamiltonkhơng? nếu có hãy chỉ ra 1 đường Hamilton.babagceedG1cIV. 61/ Tìm sắc số của các đồ thị trong các hình dưới đây:efdG2ihnobaaefdcbG1jgmkclG2d2/ Hãy xây dựng đồ thị đối ngẫu với mỗi bản đồ sau đây và tìm số mầu cần tơ các bản đồ đó:BFAA CDEBDB1B2ECDIV. 71/ Trình bày thuật tốn Dijsktra để tìm đường đi ngắn nhất từ đỉnh a đến đỉnh h, và từ đỉnh m đến đỉnh a trongđồ thị có trọng số sau:4ab13e2f3j1138kd2g21i1233c3h23m4 BT TRRMĐ2/ Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh b của các đồ thị sau:a/X1X2aX3X4X5X8bX7X6X1b/X1X2X2X3aaX4X5X4X5bbX8X8X3X7X7X6X63/ Cho đồ thị có trọng số G = < X, U > sau:13a112c21ef112bk32m112g112211h3n3d1pa/ Dùng thuật toán Prim và thuật toán Kruskal để tìm cây khung bé nhất.b/ Tìm cây khung cực đại theo thuật toán tựa Kruskalc/ Dùng thuật toán Prim để tìm cây khung bé nhất có chứa cạnh (k, m) và cạnh (d, p).IV. 81/ 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ểxếp được 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?2/ Một quần đảo có n (𝑛 ≥ 2) hòn đảo mà 2 hòn đảo bất kỳ thuộc quần đảo này đều có số đầu mối đườngngầm tới một trong các hịn đảo trên quần đảo đều khơng nhỏ hơn n. Chứng minh rằng từ một hòn đảo tùy ýthuộc quần đảo ta có thể đi đến một hòn đảo bất kỳ khác của quần đảo bằng đường ngầm.3/ Chứng minh rằng đồ thị đầy đủ gồm 5 đỉnh không phải là đồ thị phẳng?4/ Hãy lập lịch thi các mơn Tốn 1, Tốn 2, Tốn 3, Tốn 4, Tin 1, Tin 2, Tin 3, Tin 4 với số ít nhất các đợtthi, nếu khơng có sinh viên nào thi cả hai mơn Tốn 1 và Tin 2, Toán 2 và Tin 1, Toán 4 và Tin 1, Toán 4 vàTin 2, Toán 3 và Tin 2, Toán 1 và Toán 2, Toán 1 và Toán 3, Toán 3 và Tốn 4, nhưng có sinh viên thi trongmọi tổ hợp khác của các môn.………………………………………………….9 BT TRRMĐMỘT SỐ BÀI TẬP DẠNG LÝ THUYẾT1/ Chứng minh rằng: Nếu đơn đồ thị G =<X, U> có đúng 2 đỉnh bậc lẻ thì 2 đỉnh này phải liên thông.2/ Chứng minh rằng: Nếu đồ thị vô hướng G =<X, U> có khơng q 2 đỉnh bậc lẻ thì G có đường Euler.3/ Chứng minh rằng: Đồ thị G =<X, U> có cây khung khi và chỉ khi G là đồ thị liên thông.4/ Chứng minh rằng Một đồ thị đầy đủ với n đỉnh có sắc số bằng n. Hãy cho một thí dụ5/ Cho đồ thị vơ hướng G =<X, U> , có n đỉnhChứng minh rằng Nếu G là một cây thì G là đồ thị liên thơng và có n – 1 cạnh.……………………………..10