Xem Nhiều 5/2022 # Bài Tập Toán Rời Rạc Có Lời Giải # Top Trend

Xem 15,048

Cập nhật thông tin chi tiết về Bài Tập Toán Rời Rạc Có Lời Giải mới nhất ngày 23/05/2022 trên website Caffebenevietnam.com. Hy vọng nội dung bài viết sẽ đáp ứng được nhu cầu của bạn, chúng tôi sẽ thường xuyên cập nhật mới nội dung để bạn nhận được thông tin nhanh chóng và chính xác nhất. Cho đến thời điểm hiện tại, bài viết này đã đạt được 15,048 lượt xem.

--- Bài mới hơn ---

  • Bài Tập Tổng Hợp Nguyên Lý Kế Toán Có Đáp Án
  • Bài Tập Nguyên Lý Kế Toán Có Lời Giải
  • Giải Bài 1, 2, 3 Trang 38 Vở Bài Tập Toán 4 Tập 1
  • Giải Vở Bài Tập Toán 4 Bài 65: Luyện Tập Chung
  • Giải Vở Bài Tập Toán 4 Bài 65 : Luyện Tập Chung
  • Links downloaded from Caffebenevietnam.com 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ó 10

    7

    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,2

    000.000.10

    000.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ó

    5

    10 trường hợp. Theo nguyên lý Dirichlet, số serial

    X tối thiểu phải thỏa mãn:

    100

    000.100

    000.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à:

    10

    000.100

    000.000.1

    =

    .

    Cách hiểu 2: (serial là 02 ký tự NN đầu tiên)

    Bốn ký tự NNNN sẽ có 10

    4

    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à: 10

    4

    *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ó

    8

    2 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ó

    8

    2 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ó

    6

    2 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 Caffebenevietnam.com tap toan roi rac co giai

    BT Toan roi rac

    2

    4486451222*

    2

    68

    =−=−=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à: 2

    6

    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à: 27040160150

    1

    =−+=−+== 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:

    24540285

    2

    =−=−= 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:

    n

    62

    Số password không có chữ số:

    n

    52

    Suy ra số password có ít nhất 01 chữ số:

    nn

    n

    n 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.167526252625262

    887766

    876

    =−+−+−=++= 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.263626362636

    887766

    876

    =−+−+−=++= 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 Caffebenevietnam.com 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ì

    ] [

    65

    10

    =

    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 −−

    +=

    nnn

    fff

    Các điều kiện đầu:

    2

    1

    =f , 3

    2

    =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 Caffebenevietnam.com 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à:

    nn

    n

    a 3)2(35 −−+=

    Bài 13:

    Tìm hệ thức truy hồi và

    n

    r . Với

    n

    r 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 Caffebenevietnam.com tap toan roi rac co giai

    BT Toan roi rac

    5

    Với n đường t

    hẳ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: nrr

    nn

    +=

    −1

    .

    Các điều kiện đầu là:

    n = 0: r

    0

    = 1.

    n = 1: r

    1

    = 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 tre

    o). 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

    n

    K (đơ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 Caffebenevietnam.com 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 Caffebenevietnam.com tap toan roi rac co giai

    BT Toan roi rac

    9

    Số 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:

    2e

    mM

    v

    ≤≤

    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)

    4

    v

    e ≤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 Caffebenevietnam.com 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 7

    2

    4

    3

    8

    Links downloaded from Caffebenevietnam.com 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 K

    3,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 K

    3,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à K

    3,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 = 3

    n-1

    ,

    o Hai đỉnh không liền kề, n chẵn: m = 3

    n-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

    14

    Bà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 ≤

    v

    e2

    ≤ 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 ≤ v

    2

    /4.

    BT Toan roi rac

    15

    Câ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 K

    3,3

    với mỗi

    giá trị của n sau:

    a) n=2, b) n=3, c) n=4, d) n=5.

    u

    1

    Links downloaded from Caffebenevietnam.com 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 2

    12 1 122 1 122 12

    ()0 2 0 2 4dd d ddd d ddd dd− ≥⇔− +≥⇔+ +≥

    Câu 4:

    Links downloaded from Caffebenevietnam.com tap toan roi rac co giai

    Links downloaded from Caffebenevietnam.com tap toan roi rac co giai

    Links downloaded from Caffebenevietnam.com tap toan roi rac co giai

    BT Toan roi rac

    20

    Câ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 Caffebenevietnam.com tap toan roi rac co giai

    b/

    Hai đồ thị có hướng G

    1

    , G

    2

    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ị G

    1

    ,G

    2

    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 K

    3,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à K

    3,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 = 3

    n-1

    ,

    (II) (I)

    1 4

    3

    2

    5

    6

    Links downloaded from Caffebenevietnam.com tap toan roi rac co giai

    BT Toan roi rac

    22

    o Hai đỉnh không liền kề, n chẵn: b = 3

    n-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. K

    n

    b. C

    n

    c. W

    n

    d. Q

    nGiải:

    Bài 2:

    Với các giá trị nào của m và n thì đồ thị phân đôi đầy đủ K

    m,n

    có:

    a. Chu trình Euler.

    b. Đường đi Euler.

    Giải

    a. Vì các đỉnh của đồ thị phân đôi đủ K

    m,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 Caffebenevietnam.com tap toan roi rac co giai

    BT Toan roi rac

    23

    Bài 3:

    Với giá trị nào của m và n thì đồ thị phân đôi đầy đủ K

    m,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

    2

    n

    thì G

    là một đồ thị Hamilton. Với K

    m,n

    các đỉnh có bậc m hoặc n, nên để đồ thị đầy đủ K

    m,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 Q

    n

    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 Q

    3

    .

    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 5

    6

    7

    Links downloaded from Caffebenevietnam.com 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) a

    c

    b

    s

    r

    f

    e

    d

    g

    h

    1

    3 2

    1 2

    3

    4

    6

    5

    --- Bài cũ hơn ---

  • Dạng Bài Tập Về Phép Quay 90 Độ Cực Hay, Có Lời Giải
  • Mệnh Đề Và Suy Luận Toán Học
  • Tài Liệu Toán Lớp 10 Mệnh Đề Tập Hợp Mệnh Đề Và Mệnh Đề Chứa Biến Tóm Tắt Lý Thuyết + Bài Tập Có Lời Giải File Word
  • 253 Bài Tập Trắc Nghiệm Mệnh Đề
  • Các Dạng Toán Về Phân Thức Đại Số Và Bài Tập Vận Dụng
  • Bạn đang xem bài viết Bài Tập Toán Rời Rạc Có Lời Giải trên website Caffebenevietnam.com. Hy vọng những thông tin mà chúng tôi đã chia sẻ là hữu ích với bạn. Nếu nội dung hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất. Chúc bạn một ngày tốt lành!

  • Web hay
  • Links hay
  • Push
  • Chủ đề top 10
  • Chủ đề top 20
  • Chủ đề top 30
  • Chủ đề top 40
  • Chủ đề top 50
  • Chủ đề top 60
  • Chủ đề top 70
  • Chủ đề top 80
  • Chủ đề top 90
  • Chủ đề top 100
  • Bài viết top 10
  • Bài viết top 20
  • Bài viết top 30
  • Bài viết top 40
  • Bài viết top 50
  • Bài viết top 60
  • Bài viết top 70
  • Bài viết top 80
  • Bài viết top 90
  • Bài viết top 100