Ứng dụng graph để giải một số bài toán tiểu học

PHƯƠNG PHÁP ỨNG DỤNG GRAPH

KHÁI NIỆM:

Graph là hình vẽ biểu diễn mối quan hệ giữa các đối tượng. Trong đó, mỗi đối tượng là một điểm và mối quan hệ giữ chúng bằng các đoạn thẳng hoặc mũi tên. Các điểm còn gọi là đỉnh và các đoạn thẳng hoặc mũi tên gọi là cạnh của Graph.

Graph được ứng dụng để giải các bài toán suy luận.

MỘT SỐ VÍ DỤ:

Ví Dụ 1: Trong cuộc thi đấu cầu lông ngày hội quê em các đấu thủ đến dự đều bắt tay nhau. Người ta đếm được tất cả 15 cái bắt tay. Hỏi có mấy đấu thủ dự thi.

Phân tích: Ta đánh dấu hai điểm A, B và nối chúng với nhau bằng một đoạn thẳng. Mỗi điểm đại diện cho một đấu thủ và mỗi đoạn thẳng là một cái bắt tay. Như vậy, cứ hai đấu thủ thì đếm được một cái bắt tay, cũng như có hai điểm thì có 1 đoạn thẳng nối chúng với nhau.

Ta vẽ thêm điểm C và nối với A, B thì được tất cả 3 đoạn thẳng.

1

Lấy thêm điểm D và nối với A, B, C thì được tất cả 3 + 3 = 6 đoạn thẳng.

1

Lấy thêm điểm E và nối với A, B, C, D thì được tất cả 6 + 4 = 10 đoạn thẳng.

1

Lấy thêm điểm F và nối với A, B, C, D, E thì được tất cả 10 + 5 = 15 đoạn thẳng.

1

Nhận thấy, với 2 điểm thì có một đoạn thẳng. Thêm điểm thứ ba thì có thêm 2 đoạn thẳng nối với 2 điểm ban đầu tức là có 1 + 2 = 3 đoạn thẳng. Thêm điểm thứ 4 thì có thêm ba đoạn thẳng nối với 3 điểm đã cho, lúc này có: 1 + 2 + 3 = 6 đoạn thẳng….Với cách suy luận như vậy ta có thể tính được số điểm khi biết số đoạn thẳng và ngược lại.

Giải

Ta đánh dấu trên hình vẽ mối đấu thủ là một điểm và mỗi cái bắt tay giữa các cầu thủ là một đoạn thẳng nối hai điểm. Với 2 điểm kẻ được một đoạn thẳng, với 3 điểm kẻ được 3 đoạn thẳng, với 4 điểm kẻ được 6 đoạn thẳng, với 5 điểm kẻ được 10 đoạn thẳng và với 6 điểm kẻ được 15 đoạn thẳng. Vậy có 6 đối thủ dự thi.

Ví Dụ 2: Nhân ngày 20 – 11 ba cô giáo An, Hà, Lan ở ba tường Lê Lợi, Quang Trung, Nguyễn Trãi dạy mẫu ba giờ Toán, Tiếng Việt và Khoa Học. Biết rằng:

– Cô An không dạy ở trường Lê Lợi, còn cô Lan không dạy ở trường Quang Trung.

– Cô giáo ở trường Lê Lợi không dạy Khoa Học.

– Cô giáo ở trường Quang Trung dạy Toán.

– Cô Hà không dạy Tiếng Việt.

Hỏi mỗi cô giáo ở trường nào và dạy môn gì?

Phân Tích: Bài toán này có thể giải bằng phương pháp suy luận logic. Ở đây ta trình bày cách giản bằng phương pháp ứng dụng Grap.

Ở bài toán này có ba nhóm đối tượng: Một là tên các cô giáo: An, Hà, Lan; Hai là tên các trường: Lê Lợi, Quang Trung, Nguyễn Trãi; Ba là tên các môn: Toán, Tiếng Việt, Khoa Học. Ta phải tìm sự tương ứng giữa các đối tượng của ba nhóm này để xem cô giáo đó ở trường nào và dạy môn gì. Muốn vậy ta xây dựng Grap như sau:

Nhóm thứ nhất, ta vẽ 3 chấm A; H, L để ký hiệu 3 cô giáo An, Hà, Lan. Nhóm thứ hai vẽ 3 chấm: LL, QT, NT để ký hiệu các trường: Lê Lợi, Quang Trung, Nguyễn Trãi. Nhóm thứ ba vẽ ba chấm: T; TV; KH để ký hiệu các môn: Toán, Tiếng Việt và Khoa Học. Ta sẽ biểu diễn mối quan hệ giữa các đối tượng của ba nhóm này bằng nét đứt nếu quan hệ đó là sai và bằng nét liền nếu quan hệ đó là đúng.

Giải

Từ giả thiết, ta vẽ các nét đứt nối: A – LL, L – QT, LL – KH, H – TV và nét liền nối: QT – T. Bài toán đưa về việc xác định nét liền nối 3 đối tượng ở 3 nhóm thành những tam giác.

1

Nhận xét: Từ 1 đối tượng nối với 3 đối tượng của một nhóm khác bằng 3 đoạn thẳng thì trong đó bao giờ cũng có 2 đoạn thẳng là nét đứt và 1 đoạn thẳng là nét liền, bởi vì theo giả thiết mỗi đối tượng luôn luôn chỉ có một quan hệ với một đối tượng khác nhóm mà thôi. Ta suy luận ra trình tự các quan hệ trên như sau:

Cô giáo trường Lê Lợi không dạy Khoa Học nên sẽ dạy Tiếng Việt: LL – TV nét liền.

1

Cô giáo dạy trường Nguyễn Trãi dạy Khoa Học: NT – KH nét liền.

1

Cô Hà không dạy Tiếng Việt nên cô Hà không dạy ở Lê Lợi: H – LL nét đứt, cũng có được: L – LL nét liền và L – TV nét liền.

1

Đến đây ta thấy 2 trường hợp:

TH1: H – QT nét liền, H – T nét liền, A – NT nét liền, A – KH nét liền

TH2: H – NT nét liền, H – KH nét liền, A – QT nét liền, A – T nét liền

Đều thỏa mãn. Vậy bài toán có hai đáp án:

– Cô An ở trường Quang Trung và dạy Toán, cô Hà ở trường Nguyễn Trãi và dạy Khoa Học, cô Lan ở trường Lê Lợi và dạy Tiếng Việt

– Cô An ở trường Nguyễn Trãi và dạy Khoa Học, cô Hà ở trường Quang Trung và dạy Toán, cô Lan ở trường Lê Lợi và dạy Tiếng Việt.

Ví Dụ 3: Trong kì thi học sinh giỏi 4 bạn Tùng, Cúc, Mai, Lan đạt 4 giải Nhật, Nhì, Ba, Khuyến Khích. Biết rằng:

– Mai không được giải Nhất và cũng không đạt giải Khuyến Khích.

– Cúc đạt giải Nhì.

– Tùng không đạt giải Khuyến Khích.

Hỏi giải đạt được của mỗi bạn?

Phân tích: Ở bài toán này gồm hai nhóm đối tượng: Một là tên các bạn, hai là tên các giải. Ta phải tìm sự tương ứng giữa các đối tượng ở hai nhóm này để xem bạn nào đạt giải gì. Muốn vậy ta xây dựng graph như sau:

Nhóm thứ nhất vẽ 4 điểm: T, C, M, L để ký hiệu cho 4 bạn Tùng, Cúc, Mai, Lan; nhóm thứ hai vẽ 4 điểm: N, NN, B, KK để ký hiệu cho 4 giải: Nhất, Nhì, Ba, Khuyến Khích. Ta sẽ nối hai chấm ở hai nhóm này với nhau bằng nét đứt nếu giữa chúng không có sự tương ứng nào, nét liền nếu giữa chúng có sự tương ứng.

Giải

Từ giải thiết ta có các nét đứt: M – N; M – KK; T – KK và nét liền: C – N:

1

Nhìn vào Graph ta thấy: M – B là nét liền, suy luận tiếp ta có được T – N nét liền và L – KK nét liền:

2

Vậy ta đi đến kết luận như sau: Tùng đạt giải Nhất, Cúc đạt giải Nhì, Mai đạt giải Ba và Lan đạt giải Khuyến Khích.

BÀI TẬP TỰ LUYỆN:

Bài 1: Trong dịp 8 – 3, mỗi bạn Hồng, Ly, Sen mua các loại hoa hồng, ly, sen để tặng me. Bạn mua hoa sen nói với Hồng: “Thế là trong chúng ta chẳng có ai mua loại hoa trùng vứi tên mình cả”. Hỏi ai đã mua hoa nào để tặng mẹ.

Bài 2: Ở cửa hàng bán dầu hỏa có một bình 7l và một bình 5l. Hỏi làm thế nào để đong được 4l từ thùng dầu để bán cho khách hàng?

Bài 3: Trong hội trại của huyện tổ chức 4 bạn Anh, Dương, Minh, Toàn đến từ bốn xã khác nhau của huyện. Trong khi 4 bạn đang vui vẻ làm quen với nhau thì anh Bí Thư Đoàn Thanh Niên đến hỏi: “Các em có thể cho anh biết, các em đến từ xã nào trong huyện không nhỉ?” thì 4 bạn trả lời như sau:

– Anh: “Em đến từ xã Quyết Tiến, còn Dương đến từ xã Đoàn Kết”.

– Dương: “Em đến từ xã Quyết Tiến, Toàn đến từ xã Tiền Phong”

– Minh: “Em mới là người đến từ xã Quyết Tiến, còn Toàn đến từ xã Vĩnh Phúc”.

– Toàn: “Ba bạn này vui tính lắm ạ, nhưng trong mỗi câu trả lời đền có một phần đúng, một phần sai”.

Dựa vào câu nói thành thật của Toàn, anh Bí Thư đã biết được ai đến từ xã nào. Em hãy thử xem anh Bí Thư suy luận ra sao?

Bài 4: Ba bạn Linh, Nhung, Yến mặc 3 áo màu trắng, xanh, hồng và cặp tóc cũng 3 màu ấy Biết rằng chỉ Linh là có màu áo và màu cặp tóc trùng nhau, còn áo và cặp tóc của Nhung đều không phải là màu trắng, Yến mang cặp tóc màu xanh. Hãy xác định màu áo và màu cặp tóc của mỗi bạn.

Bài 5: Đội tuyển trường Hồng Hà đã đấu 3 trận bóng đá. Sau 3 trận đấu kết quả như sau:

Trong trận đầu tiên, đội tuyển đã ghi được một số bàn thắng bằng một nửa số bàn thắng ở trận thứ hai và cộng thêm 1 bàn. Trong trận thứ hai, đội lại ghi được số bàn thắng bằng nửa số bàn thắng trận thứ ba cộng thêm 1. Ở trận thứ ba, đội ghi được nửa số bàn thắng ở trận thứ nhất cộng thêm 1. Hỏi trong cả 3 trận đấu, đội đã ghi được tất cả bao nhiêu bàn thắng.