Lý thuyết đồ thị và một số dạng toán thi olympic

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

NÔNG THANH LOAN

LÝ THUYẾT ĐỒ THỊ VÀ

MỘT SỐ DẠNG TOÁN THI OLYMPIC

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2016

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

NÔNG THANH LOAN

LÝ THUYẾT ĐỒ THỊ VÀ

MỘT SỐ DẠNG TOÁN THI OLYMPIC

Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP

Mã số : 60.46.01.13

LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn khoa học: TS. TRẦN NGUYÊN AN

THÁI NGUYÊN - 2016

Mục lục

Lời mở đầu 1

1 Một số khái niệm, kết quả cơ bản và ứng dụng 3

1.1 Các định nghĩa cơ bản và ứng dụng . . . . . . . . . . . . 3

1.2 Hành trình, đường, chu trình, vết và mạch . . . . . . . . 16

1.3 Tô màu đồ thị và ứng dụng . . . . . . . . . . . . . . . . 24

2 Một số lớp đồ thị đặc biệt và ứng dụng 37

2.1 Cây và ứng dụng . . . . . . . . . . . . . . . . . . . . . . 37

2.2 Đồ thị Euler và ứng dụng . . . . . . . . . . . . . . . . . 43

2.3 Đồ thị Hamilton và ứng dụng . . . . . . . . . . . . . . . 47

2.4 Đồ thị phẳng và ứng dụng . . . . . . . . . . . . . . . . . 55

Kết luận 61

i

LỜI MỞ ĐẦU

Lý thuyết đồ thị là một ngành toán học hiện đại, tuy có lịch sử phát

triển mới hơn một thế kỷ nhưng có ứng dụng quan trọng vào nhiều

ngành khoa học, kĩ thuật hiện đại: Vật lí, hoá học, sinh học, tin học,

điều khiển học, vv... Trên thực tế có nhiều bài toán liên quan tới một

tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải

đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn

ngữ kí hiệu, đó là đồ thị. Trong khoảng mấy chục năm gần đây, người

ta đã quan tâm nhiều tới lý thuyết đồ thị và các ứng dụng của nó. Đó là

do lý thuyết đồ thị đã chứng tỏ được là một mô hình hữu hiệu cho tính

toán tối ưu. Lý thuyết đồ thị còn là đối tượng nghiên cứu của Hình học

đại số và Đại số giao hoán. Ngày nay khái niệm lý thuyết đồ thị đã xâm

nhập không chỉ vào các lĩnh vực khoa học tự nhiên truyền thống như

toán học, vật lý học hay hoá học, mà còn vào nhiều lĩnh vực khoa học

tự nhiên và xã hội khác. Các bài toán đồ thị ngày càng xuất hiện nhiều

hơn trong các kì thi Olympic Toán của các quốc gia cũng như các kì thi

Toán quốc tế. Thông thường đây là các bài toán khó không chỉ với học

sinh Việt Nam mà cả đối với cả học sinh quốc tế nói chung. Đề tài “Lý

thuyết đồ thị và một số dạng toán thi Olympic” nhằm tìm hiểu một số

vấn đề về lý thuyết đồ thị và ứng dụng, đặc biệc là ứng dụng trong việc

giải một số dạng toán thi học sinh giỏi.

Luận văn được viết dựa chủ yếu trên tài liệu chính để tham khảo là

[6] và một số đề thi Olympic của các nước ... Bên cạnh việc tìm hiểu

ứng dụng của lý thuyết đồ thị trong toán sơ cấp thì việc tìm hiểu những

vấn đề cơ bản của lý thuyết đồ thị cũng là một mục đích chính của luận

văn. Luận văn là sự tổng hợp, phân tích các dạng toán, sưu tầm các ví

dụ từ nhiều nguồn tài liệu. Cấu trúc luận văn gồm hai chương:

1

Chương 1 Một số khái niệm, kết quả cơ bản và ứng dụng. Chương

1 trình bày tóm tắt một số khái niệm, kết quả cơ bản và ứng dụng, các

định nghĩa cơ bản và ứng dụng, hành trình, đường, chu trình, vết và

mạch, tô màu đồ thị và ứng dụng.

Chương 2 Một số lớp đồ thị đặc biệt và ứng dụng. Chương 2 trình

bày một số lớp đồ thị đặc biệt như cây, đồ thị Euler, đồ thị Hamilton,

đồ thị phẳng và ứng dụng chủ yếu trong các bài toán Olympic.

Trong suốt quá trình làm luận văn, tác giả nhận được sự hướng dẫn

và giúp đỡ tận tình của Tiến sĩ Trần Nguyên An. Tác giả xin bày tỏ lòng

biết ơn chân thành và sâu sắc nhất tới thầy.

Tác giả xin gửi lời cảm ơn chân thành đến quý thầy cô giảng dạy lớp

Cao học toán khoá 8 đã truyền thụ đến cho tác giả nhiều kiến thức và

kinh nghiệm nghiên cứu khoa học.

Tác giả xin chân thành cảm ơn bạn bè, đồng nghiệp và gia đình đã

tạo mọi điều kiện giúp đỡ, động viên tác giả trong suốt quá trình học

tập và hoàn thành luận văn này.

Thái Nguyên, tháng 5 năm 2016

Tác giả

Nông Thanh Loan

2

Chương 1

Một số khái niệm, kết quả cơ bản

và ứng dụng

Trong chương này, ta sẽ đề cập tới các mô hình đồ thị khác nhau,

các khái niệm cơ bản trong lý thuyết đồ thị như hành trình, đường, chu

trình, liên thông và một vài ứng dụng trong giải toán phổ thông.

Lý thuyết đồ thị được bắt đầu như một lĩnh vực toán học từ những

lập luận nổi tiếng của Euler về bảy chiếc cầu ở K¨onigsberg trong một

bài báo công bố vào năm 1736. Nhưng bài báo này của Euler là công

trình duy nhất về lý thuyết đồ thị trong suốt gần một trăm năm sau đó.

Khoảng giữa thế kỷ 19 người ta mới quay trở lại với các vấn đề của lý

thuyết đồ thị, đặc biệt là ở nước Anh. Nguyên nhân của sự quay trở lại

đó xuất phát từ những nghiên cứu về mạng điện, về các mô hình tinh

thể và về các cấu trúc phân tử của các chất. Sự phát triển của logic

hình thức đã đẩy đến việc nghiên cứu các quan hệ hai ngôi dưới dạng lý

thuyết đồ thị. Sau đó nhiều bài toán khác cũng đã được phát triển trên

ngôn ngữ lý thuyết đồ thị.

1.1 Các định nghĩa cơ bản và ứng dụng

Như ta đã thấy ở trên, khái niệm đồ thị xuất hiện từ nhiều lĩnh vực

khác nhau trong cuộc sống. Trong mỗi lĩnh vực riêng của mình, người

ta cần tới một kiểu đồ thị nào đó. Vì vậy mà cũng xuất hiện nhiều loại

3