TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN
==***==

NGUYỄN THỊ HOA

ỨNG DỤNG TÍNH CHẤT CỦA TẬP LỒI GIẢI MỘT SỐ BÀ
HÌNH HỌC TỔ HỢP
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Hình học

HÀ NỘI - 2012


TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN
==***==

NGUYỄN THỊ HOA

ỨNG DỤNG TÍNH CHẤT CỦA TẬP LỒI GIẢI MỘT SỐ BÀ
HÌNH HỌC TỔ HỢP
TÓM TẮT KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Hình học
Người hướng dẫn khoa học
ThS.GVC. Phan Hồng Trường

HÀ NỘI - 2012


LờI CảM ƠN
Để hoàn thành khóa luận này, trớc hết em xin đợc bày tỏ
lòng biết ơn sâu sắc đến các thầy cô giáo tổ Hình học,

Chng 1: Hình lồi......................................................................................2
1.1. Các định nghĩa............................................................................. 2
1.2. Bao lồi và bao lồi đóng................................................................3
1.3. Nón lồi.................................................................................................5
Chơng 2: Một số vấn đề của hình học tổ hợp.............................7
2.1.....................Định lí Kelli trong không gian một chiều R1
7
2.2......................Định lí Kelli trong không gian hai chiều R2
8
2.3................................................................................ Ví dụ
10
Chng 3: Một số bài toán của hình học tổ hợp............................13
3.1.................................. Một số phơng pháp giải thông thờng
13
3.1.1................................Phơng pháp sử dụng định lí Kelli
13
3.1.2. Phơng pháp lấy bao lồi.......................................................16
3.2.................................................. Một số bài toán thờng gặp
28
Kết luận....................................................................................................... 39
Tài liệu tham khảo.................................................................................. 40



Mở đầu
1.
Lí do
chọn đề tài

Hình học là một môn học


- Tìm
hiểu sâu
hơn các
kiến thức
về tập
lồi.

pháp sử dụng tính chất của
tập lồi.
4.

Nhiệm vụ nghiên cứu
- Trình bày cơ sở lí thuyết về
tập lồi.

- Làm rõ

- Đề xuất một số phơng pháp

tính u việt của

giải bài toán hình học tổ

việc ứng dụng

hợp giải bằng phơng pháp sử

tính chất của
tập lồi giải một

số bài
toán
hình
học tổ
hợp giải
bằng phơng
8


CHƯƠNG 1: hình lồi
Giả sử X là không gian tuyến tính, R là tập số
thực.
1.1. Các định nghĩa:
Định nghĩa 1.1.1: Cho a, b X , khi đó đoạn thẳng
nối a với b là tập tất cả
những
điểm

x
thỏa mãn:
với t [0;1] .

x = ta
X
+ (1 t)b

Nhận xét 1.1.1: Nếu trong En có hệ tọa độ trực chuẩn O,
x , x , , x và
1


X

]

thỏa
mãn:

1.1.2:

P X,
P

đợc gọi là tập lồi
nếu

x = ta
th x P .
+ (1 t)b ì

Quy ớc: Tập là tập lồi.
Ví dụ 1.1.2: Đoạn thẳng [a;b] là tập lồi.
Định lí 1.1.1: Giao của các tập lồi bất kì là tập
lồi, tức: Nếu Pi


X (i
I ) là

các tập lồi, với I là tập chỉ số
bất kì thì

Nhận xét 1.1.2: Nếu P1, P2 là tập lồi thì P1 P2 cha
chắc đã là tập lồi.


Thật
vậy:

H1 =

A.

{A}, H 2 = {a} với a là đờng thẳng không qua
L
B H . AB H1 H 2 .
ấ
Khi đó
y
Định nghĩa
1.1.3: Cho

x1, x2 ,..., xn X .

Ta gọi vectơ
n

n

x1, x2 ,..., xn nếu ti 0 : i
= 1, n; t i = 1 sao cho
i =1

Chứng minh: Ta chứng minh bằng quy nạp.
+) Với
m=2. Với

t1,t2 0 : t1 + t2 = 1; x1, x2 A .

Theo định nghĩa 1.1.2 ta có:

t1x1 + t2 x2 A . Vậy khẳng định đúng với m =

2.
+) Giả sử khẳng
định đúng với

m k . Ta chứng minh

khẳng định đúng với
k +1

k +1

k+1, tức là: x1, x2 ,..., xk +1 A; ti 0, i = 1,
k +1; t i = 1: x = t i xi A .
i=1

Nếu tk +1 = 1 thì
t1 = t2 = ... = tk
= 0

N

+
+, k )
1
+
.



k

B
ởi
v
ì

t

i
=1

t

i

= 1 cho

nên

1theo giả


c A ,
đi
ta có 1
ể tk +1
m> 0;(1

lồi chứa , với I là
tập chỉ số. Khi đó
Kí hiệu co .

P = đợc gọi là bao lồi

i

iI

của tập .


Ví dụ 1.2.1: Trong B(O, r ) = {x : d (O; x ) r}. Khi đó co
E2 cho
B(O,1) = B (O,1) .
Nhận xét 1.2.1: a) co là tập
lồi nhỏ nhất chứa .
b) lồi


= co .

Định lí 1.2.1:


Ví dụ 1.2.2:
Trong ví dụ 2.1.1
ta cũng có
coB(O,1) = B(O,1) .
N
h
ậ
n
x
é
t
1.
2.
2:

là tập lồi đóng.
Đó là tập lồi
đóng nhỏ nhất
chứa .

co



M
A lồi. Khi đó:
ện
h
đ


ta có co = co .

X

Chứng
minh:
Ta có
là tập đóng, chứa
là tập .
lồi suy
ra co
Do đó co co .
(1)
Mco
ặ
t
co

bởi vì co là giao của
tất cả các tập lồi (không
cần

k
h
á
c

đóng) chứa . Vì vậy
co co .

n
E

thỏa
mãn:

a K ,t 0
t
V (a) K , với

V

là phép vị
tự

t
O

tâm O tỉ số k,
với O E n

O

đợc gọi là nón có đỉnh tại O.

Mệnh đề 1.3.1:
Ki (i I ) là các nón lồi có đỉnh tại O, với
Giả sử
I là tập chỉ số
bất kì. Khi


Do K là nón lồi có đỉnh tại O, ta lại có: a + b = 2c K .
b)Ngợc lại, với

a K
a K . Vậy K là một
, > 0 , ta có nón có đỉnh
tại O.
Với 0 < < 1, a, b K , ta có: và (1 )a + b K
(1 )a K , b K
.

Khi = 0 hoặc = 1 ta vẫn có
(1 )a + b K . Vậy K là nón

lồi có đỉnh tại O.
K
Hệ quả

1.3.1: Tập
X

n


i =1

i

xi K.


K A = A =
A}.
0

{a

X : a = b, 0,b


Chơng 2: một số vấn đề của hình học tổ hợp
Một câu hỏi đợc đặt ra là nếu cho trớc một họ các hình
lồi thì khi nào họ hình lồi này khác rỗng ?
Trong không gian một chiều, câu hỏi này đợc trả lời
bằng việc chứng minh định lí sau:
2.1. Định lí Kelli trong không gian một chiều R1.
Định lí 2.1: Trên đờng thẳng cho n hình lồi (n 3).
Biết rằng giao của hai hình lồi bất kì trong chúng khác
rỗng. Khi đó giao của cả n hình lồi cũng khác rỗng.
Chứng minh:
Ta thấy hình lồi trên đờng thẳng chỉ có thể là
đoạn thẳng [a; b], khoảng (a;b), hay [a; b), (a; b] (ở đây a
có thể là -, còn b có thể là +).
Ta chỉ xét với các hình lồi là các đoạn thẳng, các trờng hợp còn lại chứng minh hoàn toàn tơng tự.
Giả sử có n đoạn thẳng [ai; bi], i = 1, n có tính chất
sau: Bất kì giao của hai đoạn thẳng nào trong chúng cũng
khác rỗng, tức là: [ai; bi] [ai; bi] ,
n

[ai , bi ]


§¶o l¹i, gi¶ sö max{ai; aj} ≤ min{bi; bj}. Khi ®ã
ta cã thÓ chän c sao cho max{ai; aj} ≤ c ≤ min{bi;
bj}

(1)

⇒ c ∈ [ai; bi]
⇒ c ∈ [aj; bj]

Tõ (1) suy ra ai ≤ c ≤ bi
a j ≤ c ≤ bj

⇒ [ai; bi] ∩ [aj; bj] ≠ ∅ . Bæ ®Ò ®îc chøng
minh.


Tõ bæ ®Ò trªn
suy ra

min bi
≥ max ai

(2)

1≤i≤n

1≤i≤n

Tõ

∈
[
ai
;
b
i]
,
∀
i
=
1,
n

h
a
y

[ai
;bi


]

tron



g

i=1

mặt phẳng cho n
hình lồi (n 4).
Biết rằng giao của
ba hình lồi bất kì
trong

chúng

khác

rỗng. Khi đó giao
của



n

hình

lồi

cũng khác rỗng.
Chứng minh:
Ta chứng minh
bằng quy nạp theo
số n các hình lồi.
1. Xét khi n 4.
Gọi F1, F2, F3, F4
là 4 hình lồi sao
cho giao của ba

F
1


F
2


F
4

A
4


F
1


F
2


F
3


Có hai trờng hợp xảy
ra:
a.Nếu bốn điểm A1,

A

í
A1
F2
F4
F2
F3

Vậy kết luận của
định lí Kelli
đúng khi n = 4.

n
h
l
à
t
ứ

b. A1, A2,
A3, A4 là

g

bốn

i

điểm

Do A1 F2 F3
F4 nên A1 F3
A2 F1 F3
F4 nên A2 F3
Vì F3 lồi, mà A1 F3, A2 F3 nên [A1,A2] F3. Do đó
O F3
Lập luận tơng tự suy ra O F1, O F2 , O F4
4

Nghĩa là O
i=1

4



Fi . Do đó
i=1

F

i



b2) Bao lồi của chúng là tam giác chứa một điểm còn
lại bên trong. Không giảm tính tổng quát ta có thể
giả sử A1A2A3 thuộc F4
Vì A1, A2, A3 đều thuộc
F4, mà F4 lồi. Mặt khác: A4


=F
Fn-1




n-1

Fn = Fn ∩ Fn+1

’

Râ rµng Fi lµ h×nh låi ∀i
= 1, n −1 (v× Fi

’

= Fi)

’

Fn còng lµ låi v× nã lµ giao cña hai h×nh låi Fn vµ Fn+1
’

’

’

’


Từ đó
= Fi Fj Fn Fn+1.
Fi
Fj Fk
Vì giao của 3 hình lồi trong các hình lồi Fi, Fj, Fn,
Fn+1 là khác rỗng (giả thiết) nên theo trờng hợp n = 4, ta
có Fi Fj Fn Fn+1






Vậy với hình lồi F1 , F2 ,
, Fn

thỏa mãn điều kiện giao của 3
hình lồi

bất kì
trong chúng khác rỗng
nên theo giả thiết quy nạp suy ra






F1 F2 Fn . Nghĩa là: F1 F2