Bài toán đếm, phủ và tô màu trong hình học tổ hợp

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC QUY NHƠN

NGUYỄN TUẤN KHẢI

BÀI TOÁN ĐẾM, PHỦ VÀ TÔ MÀU

TRONG HÌNH HỌC TỔ HỢP

CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ CẤP

MÃ SỐ: 8460113

Quy Nhơn - Năm 2021

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC QUY NHƠN

NGUYỄN TUẤN KHẢI

BÀI TOÁN ĐẾM, PHỦ VÀ TÔ MÀU

TRONG HÌNH HỌC TỔ HỢP

CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ CẤP

MÃ SỐ: 8460113

Người hướng dẫn khoa học

PGS.TS. LÊ CÔNG TRÌNH

Quy Nhơn - Năm 2021

i

Mục lục

Mở đầu 1

1 Bài toán đếm trong hình học tổ hợp 3

1.1 Một số tính chất tổ hợp của đa giác lồi . . . . . . . . . . . . . . . . 3

1.2 Đếm số giao điểm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Đếm tam giác . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4 Đếm đa giác . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.5 Hệ điểm và đường thẳng . . . . . . . . . . . . . . . . . . . . . . . . 18

1.6 Hệ đoạn thẳng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.7 Một số tính chất tổ hợp của đa giác không lồi . . . . . . . . . . . . 25

2 Hệ đường cong và miền 29

2.1 Chia mặt phẳng bởi các đường thẳng . . . . . . . . . . . . . . . . . 30

2.2 Chia mặt phẳng bởi các đường cong khép kín . . . . . . . . . . . . 34

2.3 Chia đa giác lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.4 Chia không gian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3 Phủ hình và bao hình 44

3.1 Phủ hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2 Phủ hình với hệ các hình tròn tương đẳng . . . . . . . . . . . . . . 49

ii

3.3 Bao hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.4 Bài toán xếp chồng . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4 Bài toán tô màu 61

4.1 Tô màu điểm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4.2 Tô màu miền . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.3 Tô màu bàn cờ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.4 Tô màu phụ trợ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Kết luận 76

1

Mở đầu

Việc nghiên cứu bài toán đếm một số đối tượng trong hình học, chẳng hạn

như đếm số giao điểm, đếm số tam giác, đếm số tứ giác, . . . thỏa mãn một số

tính chất nào đó; việc nghiên cứu các tính chất tổ hợp của mặt phẳng, đa giác,

hoặc không gian khi bị chi ra thành nhiều miền bởi các hệ đường thẳng hoặc

đường cong; việc nghiên cứu những bài toán phủ hình, bao hình, bài toán tô

màu, . . . là những vấn đề được quan tâm nghiên cứu trong hình học tổ hợp.

Luận văn tập trung nghiên cứu các bài toán cơ bản nói trên trong hình học tổ

hợp. Các kết quả trong luận này được chúng tôi tổng hợp và trình bày lại từ tài

liệu [1] và [2], các bài toán tham khảo trong các tài liệu [3], [4], [5], [6], [7].

Ngoài mở đầu, kết luận và tài liệu tham khảo, luận văn được bố cục thành

4 chương:

Chương 1: Bài toán đếm trong hình học tổ hợp

Trong chương này tác giả trình bày một số tính chất tổ hợp của các đa giác lồi

và các đa giác không lồi, cùng với một số bài toán đếm một số đối tượng hình

học.

Chương 2: Hệ đường cong và miền.

Trong chương này tác giả trình bày một số bài toán tổ hợp liên quan đến việc

chia một đối tượng hình học cho trước thành nhiều phần có "hình dạng" khác

nhau bởi một họ đường thẳng hoặc đường cong.

2

Chương 3: Phủ hình và bao hình.

Trong chương này tác giả trình bày các bài toán phủ hình (covering) và bao

hình (parking), đồng thời nghiên cứu các tình huống một đối tượng hình học

cho trước chứa một số đối tượng khác bên trong nó.

Chương 4: Bài toán tô màu.

Trong chương này tác giả trình bày một số bài toán tô màu các đối tượng hình

học, gồm tô màu điểm, tô màu miền, tô màu bàn cờ, . . .

Luận văn được hoàn thành dưới sự hướng dẫn tận tình của thầy PGS.TS. Lê

Công Trình, người luôn nhắc nhở, động viên, giúp đỡ tôi trong quá trình nghiên

cứu để tôi có thể hoàn thành luận văn này. Tôi cũng xin bày tỏ lòng biết ơn đối

với quý thầy cô trong khoa Toán và Thống kê, phòng Sau đại học trường Đại

học Quy Nhơn, đặc biệt là quý thầy cô đã trực tiếp giảng dạy cho lớp Cao học

Toán khóa 22. Cuối cùng tôi tỏ lòng biết ơn đến gia đình, người thân và bạn bè

đã luôn ủng hộ, giúp đỡ, tạo điều kiện cho tôi về mọi mặt trong suốt thời gian

tôi học thạc sĩ cũng như hoàn thành luận văn này.

Trong thời gian ngắn hoàn thành luận văn này, chắc không tránh được sai

sót. Chúng tôi rất mong nhận được những góp ý, phê bình quý báu của quý

thầy cô và các bạn đồng nghiệp.

Quy Nhơn, tháng 7 năm 2021

Học viên: Nguyễn Tuấn Khải

3

Chương 1

Bài toán đếm trong hình học tổ hợp

Trong chương này chúng tôi trình bày một số tính chất tổ hợp của các đa

giác lồi và các đa giác không lồi, cùng với một số bài toán đếm một số đối tượng

hình học thỏa mãn một số tính chất nào đó: Đếm số giao điểm, đếm số tam

giác, . . .

1.1 Một số tính chất tổ hợp của đa giác lồi

Trong phần này chúng tôi trình bày một số tính chất tổ hợp của các đa giác

lồi. Đầu tiên chúng tôi định nghĩa tập lồi.

Định nghĩa 1.1.1. Tập lồi trong mặt phẳng (trên đường thẳng, trong không

gian) là tập hợp U các điểm trong mặt phẳng (trên đường thẳng, trong không

gian) có tính chất sau: Với hai điểm phân biệt bất kì X, Y thuộc U thì mọi điểm

của đoạn thẳng XY cũng thuộc U.

Tập lồi trên đường thẳng có cấu trúc đơn giản: Ngoại trừ đường thẳng, tập

rỗng, các điểm thì các tập lồi là các tia và đoạn thẳng, có hoặc không có điểm

biên. Việc phân loại các tập lồi trong mặt phẳng rõ ràng là khó khăn, nhưng

một công cụ đáng kể trong việc xây dựng các tập lồi là giao của các tập lồi là

4

một tập lồi. Một khái niệm quan trọng đó chính là bao lồi K của U: nó là giao

của tất cả các tập lồi M thỏa mãn U ⊆ M (vì vậy K là tập lồi nhỏ nhất chứa

U).

Định nghĩa 1.1.2. Cho K = {A1, A2, . . . , An} là tập gồm n điểm phân biệt

trong mặt phẳng (n ≥ 3). Tập M được gọi là n-giác lồi A1A2 . . . An nếu M là

giao của n nửa mặt phẳng α1, α2, . . . ., αn sao cho với mỗi i = 1, 2, . . . , n đường

thẳng AiAi+1 (trong đó An+1 = A1) là biên của nửa mặt phẳng αi và mỗi điểm

Aj ∈ K\{Ai

; Ai+1} đều nằm trong αi

.

Nếu U là một tập hợp hữu hạn gồm n điểm (n ≥3) trong mặt phẳng sao cho

n điểm không cùng nằm trên một đường thẳng thì bao lồi của U là một đa giác

lồi có các đỉnh là một số (hoặc có thể là tất cả) phần tử của tập U.

Một kết quả quan trọng khác trong lý thuyết tập lồi đó là Định lý Helly.

Định lý 1.1.3 (Helly). Giả sử S là một hệ bất kì (hữu hạn hoặc vô hạn) các

tập con lồi của một mặt phẳng cho trước sao cho ba tập hợp bất kì có ít nhất

một điểm chung. Khi đó tất cả các tập con trong S đều có điểm chung.

Hai tính chất cơ bản sau đây của đa giác lồi sẽ được sử dụng thường xuyên

ở chương này.

Tính chất 1.1.4. Số đường chéo un của n-giác lồi M thỏa mãn

un =

n(n − 3)

2

.

Chứng minh. Thật vậy, n đỉnh của đa giác M được nối với nhau bởi ￾

n

2

=

n(n−1)

2

đoạn thẳng, trong đó có đúng n đoạn là các cạnh của đa giác M. Do đó ta có

un =

n(n−1)

2 − n =

n(n−3)

2