Tạp chí Thông tin toán học - Tập 11 Số 4 Tháng 12 Năm 2007

Về Hình học và Tôpô đại số: Có một sợi dây liên kết chính là Công thức Euler, cho ta một mối liên hệ giữa số cạnh, số đỉnh và số mặt của một đa diện. Công thức tổng quát là: F - E + V = 2, trong đó F là số mặt, E là số đỉnh, V là số cạnh. Định lý đúng cho mọi đa diện phẳng. Đối với các đồ thị không phẳng, có một biểu thức tổng quát hơn.

Về Đồ thị: Năm 1736, Ông giải được bài toán nổi tiếng về 7 chiếc cầu của thành phố Konigsberg (nay thuộc thành phố Kaliningrad, Nga). Cụ thể

Ông chứng minh được rằng không thể đi bộ qua 7 cái cầu trên, mỗi cầu đúng một lần và trở lại đúng địa điểm đã xuất phát. Đây có thể xem như là ứng dụng đầu tiên của Lý thuyết đồ thị.

pdf32 trang | Chia sẻ: Hải Khánh | Ngày: 22/10/2024 | Lượt xem: 9 | Lượt tải: 0download
Bạn đang xem trước 20 trang mẫu tài liệu Tạp chí Thông tin toán học - Tập 11 Số 4 Tháng 12 Năm 2007, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
 2 3, ,u u u lµ c¸c 
biÕn ®éc lËp, cßn 1 2,x x lµ c¸c biÕn phô thuéc vµo c¸c gi¶ thiÕt BH vu«ng gãc víi AC 
vµ CH vu«ng gãc víi AB. Ta cã: BH ⊥ AC ⇔ 1 1 2 1 2 3: ( ) 0f x u u x u= − + = ; CH 
⊥ AB ⇔ 2 2 1 1 3 2: ( ) 0f u x u u x= − + = ; AH ⊥ BC ⇔ 1 2 1: ( ) 0g u u x= − = . 
Do ®ã, ®Ó chøng minh AH vu«ng gãc víi BC b»ng Maple, chóng ta chØ cÇn kiÓm 
tra c¬ së Groebner cña i®ªan 1 2( , ,1 )f f gy− chøa ®¬n vÞ 1. 
B−íc 2. NhËp c¸c c©u lÖnh sau 
> with (Groebner); 
> with (Ore_algebra): 
> A:=poly-algebra (u_1,u_2,u_3,x_1,x_2,y): 
>WL:=[x_1*u_2-u_1*x_1+x_2*u_3, u_2*x_1-u_2*u_1+u_3*x_2, (1-y*u_1 
*u_2+y*u_1*x_1)]: 
> GB:= gbasis(WL,tdeg(x_1,x_2,y)); 
 13
Maple cho kÕt qu¶ i®ªan 1 2( , ,1 )f f gy− chøa ®a thøc 1 vµ ta cã ®iÒu cÇn 
chøng minh. 
Trong tr−êng hîp c¬ së Groebner cña i®ªan ( )1 2, , , ,1sf f f gy−K kh«ng 
chøa ®a thøc 1 ®−îc xÐt nh− ë hai vÝ dô sau. 
VÝ dô 2 (§Ò thi Olimpic To¸n quèc tÕ lÇn thø 35). Cho ABC lµ mét tam gi¸c c©n víi AB 
= AC. Gi¶ sö M lµ trung ®iÓm cña BC vµ O lµ ®iÓm trªn ®−êng th¼ng AM sao cho OB vu«ng 
gãc víi AB. Q lµ ®iÓm tuú ý thuéc ®o¹n BC, kh¸c víi B vµ C. E lµ mét ®iÓm trªn ®−êng th¼ng 
AB, F lµ mét ®iÓm trªn ®−êng th¼ng AC sao cho E, Q, F ph©n biÖt vµ th¼ng hµng. Chøng minh 
r»ng OQ vu«ng gãc víi EF khi vµ chØ khi QE = QF. 
Sau ®©y lµ lêi gi¶i h×nh häc th«ng th−êng: 
§iÒu kiÖn cÇn. Gi¶ sö OQ vu«ng gãc víi 
EF . Ta chøng minh QE = QF. V× tam gi¸c 
ABC c©n t¹i A; vµ O thuéc trung trùc cña 
BC mµ OB AB⊥ nªn OC AC⊥ . Ta 
cã tø gi¸c OBEQ néi tiÕp nªn 
· ·EOQ EBQ= . Tø gi¸c OQCF néi tiÕp 
nªn · ·QOF ACQ= , mµ · ·EBQ ACQ= 
nªn · ·EOQ FOQ= . Do ®ã tam gi¸c OEF 
cã OQ võa lµ ®−êng cao, võa lµ ®−êng 
ph©n gi¸c nªn lµ ®−êng trung truyÕn. Do 
®ã QE = QF. 
§iÒu kiÖn ®ñ. Gi¶ sö QE = QF, ta chøng 
minh OQ vu«ng gãc víi EF. Qua Q kÎ 
®−êng th¼ng vu«ng gãc víi OQ c¾t AB, AC 
lÇn l−ît t¹i E’ vµ F’. Theo ®iÒu kiÖn cÇn ta cã 
Q lµ trung ®iÓm cña E’F’. V× Q lµ trung 
®iÓm cña EF, cho nªn nÕu E kh«ng trïng víi 
E’ (kÐo theo F kh«ng trïng F’), ta cã ngay 
EE’ || FF’. §iÒu nµy m©u thuÉn víi EE’ 
n»m trªn AB cßn FF’ n»m trªn AC. VËy 
'E E≡ , 'F F≡ vµ ta cã OQ EF⊥ . 
Lêi gi¶i bµi to¸n trªn kh«ng dµi nh−ng ®· cã nhiÒu häc sinh giái kh«ng gi¶i 
®−îc mÆc dï c¸c em ®· ®−îc trang bÞ ®Çy ®ñ c¸c kiÕn thøc c¬ së h×nh häc ph¼ng, lý 
do bëi v× muèn gi¶i ®−îc nã ®ßi hái nhiÒu sù l¾t lÐo, mÑo mùc. Sö dông lý thuyÕt C¬ 
së Groebner, chóng ta cã thÓ h−íng dÉn häc sinh gi¶i bµi to¸n nµy trªn Maple, mµ 
kh«ng ®ßi hái vÒ sù hiÓu biÕt vÒ lËp tr×nh m¸y tÝnh: 
B−íc 1. 
Chän hÖ to¹ ®é: B(0,0), C(u1,0), 
A(u1/2,u2), M(u1/2,0), O(u1/2,x1), E(x2,x3), 
F(x4,x5), Q(u3,0). Víi viÖc chän hÖ to¹ ®é 
nh− trªn, ta ®· cã M lµ trung ®iÓm cña 
BC, O thuéc trung trùc cña BC, AB = AC 
vµ A, M, O th¼ng hµng. 
§iÒu kiÖn A, E, B th¼ng hµng: 2x2/u1 = 
x3/u2 hay 1 2 2 3 1: 2f x u x u= − . 
§iÒu kiÖn A, C, F th¼ng hµng: 
(x4  u1)/x5 = -u1/(2u2) hay 
2 2 4 2 1 5 1: 2 2 0f u x u u x u= − + = . 
 14
§iÒu kiÖn Q, E, F th¼ng hµng: 
(x4  u3)/x5= (x2-u3)/x3 hay 
3 4 3 3 3 2 5 3 5: 0f x x u x x x u x= − − + = . 
§iÒu kiÖn AB vu«ng gãc víi BO: (u1/2) 
(u1/2) + x1u2 = 0 
hay 24 1 1 2: 4 0f u x u= + = . 
§iÒu kiÖn OQ vu«ng gãc víi EF : 
( )1 3 4 2 1 5 3/2 ( ) ( ) 0u u x x x x x− − + − = 
hay 
1 1
5 4 2 3 4 3 2 1 5 1 3: 02 2
u u
f x x u x u x x x x x= − − + + − = . 
§iÒu kiÖn QE = QF lµ : 
2 2 2 2
2 3 3 4 3 5( ) ( )x u x x u x− + = − + hay 
2 2 2 2
2 2 3 3 4 5 4 3: 2 2 0g x x u x x x x u= − + − − + = . 
B−íc 2. TiÕn hµnh ch¹y trªn Maple. Chóng ta nhËp c¸c c©u lÖnh sau 
> with (Groebner); 
> with(Ore_algebra); 
> A:=poly-algebra(u_1,u_2,u_3,x_1,x_2,x_3,x_4,x_5,y): 
> WL:=[2*x_2*u_2-x_3*u_1, 2*u_2*x_4-2*u_2*u_1+x_5*u_1,x_4*x_3- u_3 
*x_3-x_2*x_5+u_3*x_5, u_1*u_1+4*x_1*u_2,u_1*x_4/2-u_1*x_2/2 -u_3 
*x_4 +u_3*x_2+x_1*x_5-x_1*x_3,(1-y*x_2*x_2+2*y*x_2*u_3-y 
*x_3*x_3+y*x_4 * x_4 +y*x_5*x_5-2*y*x_4*u_3)] : 
> GB:= gbasis(WL,plex(y,x_1,x_2,x_3,x_4,x_5,u_1,u_2,u_3)); 
 Maple cho ta ®a thøc 21 2 3 3 2c u u u u u= − thuéc c¬ së Groebner cña i®ªan 
1 2 3 4 5( , , , , ,1 )f f f f f gy− chØ chøa c¸c biÕn ®éc lËp. Do ®ã, theo quy tr×nh ta cã ®iÒu 
cÇn ph¶i chøng minh. 
VÝ dô 3 (§Þnh lÝ Pappus). Trªn mét ®−êng th¼ng lÊy ba ®iÓm A, B, C vµ trªn ®−êng 
th¼ng kh¸c lÊy ba ®iÓm A’, B’, C’. Gäi P, Q, R lÇn l−ît lµ giao ®iÓm cña c¸c cÆp 
®−êng th¼ng (A’B, AB’), (AC’, CA’), (BC’, B’C). Chøng minh r»ng P, Q, R th¼ng 
hµng. 
 Chøng minh truyÒn thèng cña ®Þnh lý nµy kh¸ phøc t¹p. Sö dông lý thuyÕt C¬ së 
Groebner ta cã thÓ chøng minh ®Þnh lý Pappus trªn Maple nh− sau: 
B−íc 1. 
Chän hÖ to¹ ®é nh− sau: A(0,0), B(u1,0), 
C(u2,0), A(u3,,u4), B(u5,u6), P(x1,x2), 
Q(x3,x4), R(x5,x6), C(x7,x8). Víi c¸ch chän 
to¹ ®é nh− thÕ, ta ®· cã A, B, C th¼ng hµng. 
§iÒu kiÖn A’, B’, C’ th¼ng hµng: 
3 5 3 7
4 6 4 8
u u u x
u u u x
− −=− − hay 
1 4 7 3 6 5 8 3 8 4 5 6 7: 0f u x u u u x u x u u u x= + + − − − = . 
§iÒu kiÖn A, P, B’ th¼ng hµng: 
5 6
1 2
u u
x x
= hay 2 5 2 6 1: 0f u x u x= − = . 
§iÒu kiÖn A’, P, B th¼ng hµng: 
3 1 4
1 1 2
u u u
x u x
− =− hay 
3 3 2 1 2 1 4 1 4: 0f u x u x x u u u= − − + = . 
§iÒu kiÖn A, Q, C’ th¼ng hµng: 
 15
7 8
3 4
x x
x x
= hay 4 7 4 8 3: 0f x x x x= − = . 
§iÒu kiÖn A’, Q, C th¼ng hµng: 
3 2 4
3 2 4
x u x
u u u
− =− hay 
5 3 4 2 4 3 4 2 4: 0f x u u u u x u x= − − + = . 
§iÒu kiÖn B, R, C’ th¼ng hµng: 
5 1 6
7 1 8
x u x
x u x
− =− hay 
6 5 8 1 8 7 6 1 6: 0f x x u x x x u x= − − + = . 
§iÒu kiÖn C, R, B’ th¼ng hµng: 
5 2 6
5 2 6
x u x
u u u
− =− hay 
7 5 6 2 6 5 6 2 6: 0f x u u u u x u x= − − + = . 
§iÒu kiÖn cÇn chøng minh P, Q, R th¼ng 
hµng: 3 1 4 2
5 1 6 2
x x x x
x x x x
− −=− − hay 
3 6 3 2 1 6 5 4 5 2 1 4: 0g x x x x x x x x x x x x= − − − + + =
B−íc 2. TiÕn hµnh ch¹y trªn Maple. Chóng ta nhËp c¸c c©u lÖnh sau 
> with (Groebner); 
> with (Ore_algebra); 
>A:=poly-algebra(u_1,u_2,u_3,u_4,u_5,u_6,x_1,x_2,x_3,x_4, 
x_5,x_6,x_7,x_8,y): 
> WL:=[ u_4*x_7+u_3*u_6+u_5*x_8-u_3*x_8-u_4*u_5-u_6*x_7, u_5* x_2-
u_6*x_1, u_3*x_2-u_1*x_2-x_1*u_4+u_1*u_4,x_7*x_4-x_8*x_3, x_3*u_4-
u_2*u_4-u_3*x_4+u_2*x_4, x_5*x_8-u_1*x_8-x_7*x_6+u_1*x_6,x_5*u_6-
u_2*u_6-u_5*x_6+u_2*x_6, (1-y*x_3*x_6+y*x_3*x_2+y* 
x_1*x_6+y*x_4*x_5-y*x_5*x_2-y*x_1*x_4)]; 
>GB:=gbasis(WL,tdeg(x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,y,u_1, 
u_2,u_3,u_4,u_5,u_6)); 
 Maple cho ta ®a thøc 1 6 3 6 4 5c u u u u u u= − + thuéc c¬ së Groebner cña i®ªan 
1 7( ,..., ,1 )f f gy− , chØ phô thuéc vµo c¸c biÕn ®éc lËp. §Þnh lÝ Pappus ®−îc chøng minh. 
4. KÕt luËn 
 Tãm l¹i, Maple cho ta mét c«ng cô hiÖu qu¶ thùc hiÖn mét sè chøng minh h×nh häc nh− ®· 
tr×nh bµy ë trªn. §©y lµ mét ph−¬ng tiÖn hiÖu qu¶ ®Ó ng−êi thÇy thiÕt lËp c«ng cô hç trî cho 
ph−¬ng ph¸p vµ phong c¸ch gi¶ng d¹y h×nh häc cña m×nh. Trong thêi gian tíi, víi c¸c kh¶ 
n¨ng tÝnh to¸n vµ biÓu diÔn tuyÖt vêi cña c¸c phÇn mÒm tin häc, céng víi c«ng søc vµ tµi n¨ng 
s− ph¹m cña ng−êi thÇy gi¸o, chóng ta hy väng sÏ gãp phÇn t¹o ra nh÷ng ®æi míi c¬ b¶n vµ 
toµn diÖn gi¸o dôc to¸n häc phæ th«ng vµ ®¹i häc ë n−íc ta. Bµi viÕt nµy cña chóng t«i mong 
®−îc ®ãng gãp mét phÇn v« cïng nhá bÐ trong c«ng cuéc vËn ®éng hÕt søc to lín ®ã. 
Tµi liÖu tham kh¶o 
[1] Ph¹m Huy §iÓn, TÝnh to¸n, lËp tr×nh vµ gi¶ng d¹y to¸n häc trªn Maple, NXB Khoa häc vµ Kü 
thuËt, Hµ Néi, 2002. 
[2] Lª TuÊn Hoa, §¹i sè m¸y tÝnh C¬ së Groebner, NXB §H Quèc gia Hµ Néi, 2003. 
[3] Ph¹m Minh Hoµng, Maple vµ c¸c bµi to¸n øng dông, NXB Khoa häc vµ Kü thuËt, TP. Hå ChÝ 
Minh, 2005. 
[4] Hµ Huy Kho¸i, Ph¹m Huy §iÓn, Sè häc thuËt to¸n, NXB §H Quèc gia Hµ Néi, 2003. 
[5] Ng« ViÖt Trung, C¬ së Groebner trong H×nh häc vµ §¹i sè, Th«ng tin To¸n häc, TËp 3 Sè 1, 
1999. 
[6] A. Heck, Introduction to Maple, Edition Springer Verlag, Berlin Heidenberg, 1997. 
 16
Héi nghÞ §¹i sè - H×nh Häc - T«p« 
Vinh, 17 - 20/12/2007 
NguyÔn Thµnh Quang (§¹i häc Vinh) 
Nh− th«ng lÖ, Héi nghÞ §¹i sè - 
H×nh häc - T«p« ®−îc tæ chøuc hai n¨m 
mét lÇn. LÇn nµy Héi nghÞ do §¹i häc 
Vinh phèi hîp víi ViÖn To¸n häc tæ 
chøc. Môc ®Ých cña Héi nghÞ lµ t¹o ®iÒu 
kiÖn ®Ó c¸c c¸n bé gi¶ng d¹y vµ nghiªn 
cøu ë c¸c tr−êng ®¹i häc, cao ®¼ng vµ 
c¸c viÖn nghiªn cøu trong c¶ n−íc gÆp 
gì, th«ng b¸o vµ trao ®æi vÒ c¸c kÕt qu¶ 
nghiªn cøu ®¹t ®−îc gÇn ®©y trong c¸c 
lÜnh vùc §¹i sè - H×nh häc - T«p«. Ban 
Tæ chøc gåm Hµ Huy Kho¸i (ViÖn TH, 
®ång Tr−ëng ban), Ng« Sü Tïng (§H 
Vinh, ®ång Tr−ëng ban), TrÇn §¹o Dâng 
(§H HuÕ), NguyÔn ViÖt Dòng (ViÖn 
TH), N«ng Quèc Chinh (§H Th¸i 
Nguyªn), Phan D©n (§H Giao th«ng VT 
TP. HCM), NguyÔn V¨n Sanh (§H 
Mahidol, Th¸i Lan). Ban Ch−¬ng tr×nh 
gåm NguyÔn Tù C−êng (ViÖn TH, 
Tr−ëng ban), NguyÔn H÷u ViÖt H−ng 
(§H KHTN - §HQG Hµ Néi), Lª TuÊn 
Hoa (ViÖn TH), §ç Ngäc DiÖp (ViÖn 
TH), §ç §øc Th¸i (§HSP Hµ Néi), §µo 
Träng Thi (UBTV Quèc héi), Lª V¨n 
ThuyÕt (§H HuÕ). 
§Ó chuÈn bÞ cho Héi nghÞ, §H Vinh 
®· thµnh lËp Ban Tæ chøc ®Þa ph−¬ng 
gåm Ng« Sü Tïng (Tr−ëng ban), TrÇn 
V¨n ¢n (Phã ban), NguyÔn Thµnh 
Quang (Phã ban), NguyÔn V¨n Qu¶ng, 
Bïi V¨n Dòng, Lª Quèc H¸n, NguyÔn 
Duy B×nh, Chu Träng Thanh, NguyÔn 
ThÞ Hång Loan, Lª V¨n Thµnh, TrÇn 
Anh NghÜa, ThiÒu §×nh Phong. 
Héi nghÞ ®· diÔn ra tõ ngµy 
17/12/2007 ®Õn ngµy 20/12/2007. Cã 
kho¶ng 200 nhµ to¸n häc, gi¶ng viªn, 
nghiªn cøu sinh, häc viªn sau ®¹i häc 
®Õn tõ c¸c viÖn nghiªn cøu, tr−êng ®¹i 
häc, cao ®¼ng trong c¶ n−íc. §Æc biÖt 
tham dù Héi nghÞ nµy cã c¸c nhµ to¸n 
häc ®Õn tõ Nga, Hoa Kú, Trung Quèc, 
NhËt B¶n, Th¸i Lan. T¹i Héi nghÞ cã 6 
b¸o c¸o mêi 45 phót cña GS. §inh V¨n 
Huúnh (Ohio University, USA), GS. M. 
Oka (NhËt B¶n), GS. Lª TuÊn Hoa, PGS. 
Lª V¨n ThuyÕt, PGS. NguyÔn V¨n Ch©u, 
TS. Phã §øc Tµi vµ 2 b¸o c¸o mêi 30 
phót cña GS. L. A. Bokut (Nga), GS. Y. 
Chen (Trung Quèc). Cã kho¶ng 40 b¸o 
c¸o ng¾n (15 phót) ®· tr×nh bµy trong 3 
ngµy ho¹t ®éng chuyªn m«n cña Héi 
 17
nghÞ, th«ng b¸o c¸c kÕt qu¶ míi thu ®−îc 
trong thêi gian gÇn ®©y vÒ c¸c lÜnh vùc 
§¹i sè, 

File đính kèm:

  • pdftap_chi_thong_tin_toan_hoc_tap_11_so_4_thang_12_nam_2007.pdf