Luận văn Lý thuyết đồ thị và ứng dụng để giải Toán sơ cấp

Nội dung tài liệu: Luận văn Lý thuyết đồ thị và ứng dụng để giải Toán sơ cấp

1. ĐẠI HÅC QUÈC GIA HÀ NËI TRƯỜNG ĐẠI HÅC KHOA HÅC TỰ NHIÊN NGUYỄN NGÅC HẢI LÝ THUYẾT ĐỒ THỊ VÀ ỨNG DỤNG ĐỂ GIẢI TOÁN SƠ CẤP LUẬN VĂN THẠC SĨ TOÁN HÅC HÀ NËI, NĂM 2014
2. ĐẠI HÅC QUÈC GIA HÀ NËI TRƯỜNG ĐẠI HÅC KHOA HÅC TỰ NHIÊN NGUYỄN NGÅC HẢI LÝ THUYẾT ĐỒ THỊ VÀ ỨNG DỤNG ĐỂ GIẢI TOÁN SƠ CẤP LUẬN VĂN THẠC SĨ TOÁN HÅC Chuy¶n ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP M¢ sè: 60 46 40 NGƯỜI HƯỚNG DẪN KHOA HÅC: GS. TS. ĐẶNG HUY RUẬN HÀ NËI, NĂM 2014
3. Mục lục Mở đầu .................................. 5 1 C¡c kh¡i ni»m và định lý cơ b£n 7 1.1 C¡c v½ dụ v· đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Định nghĩa đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Biºu di¹n đồ thị b¬ng h¼nh học . . . . . . . . . . . . . . . . . . 12 1.4 Mët sè d¤ng đồ thị đặc bi»t . . . . . . . . . . . . . . . . . . . . 13 1.5 Phương ph¡p đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 Đồ thị và mët sè bài to¡n phê thông 16 2.1 Bài to¡n li¶n quan đến bªc cõa đồ thị . . . . . . . . . . . . . . . 16 2.1.1 Bªc cõa đỉnh . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.2 Nûa bªc . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.3 Mët sè t½nh ch§t . . . . . . . . . . . . . . . . . . . . . . 17 2.1.4 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Bài to¡n li¶n quan đến chu tr¼nh . . . . . . . . . . . . . . . . . 28 2.2.1 X½ch, Chu tr¼nh . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.2 Đường, Váng . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.3 Mët sè t½nh ch§t . . . . . . . . . . . . . . . . . . . . . . 29 2.2.4 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3 Bài to¡n li¶n quan đến t½nh li¶n thông . . . . . . . . . . . . . . 38 2.3.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.3.2 Mët sè t½nh ch§t . . . . . . . . . . . . . . . . . . . . . . 39 2.3.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.4 Đồ thị Euler - Đồ thị Hamilton . . . . . . . . . . . . . . . . . . 50 3
4. 2.4.1 Đường đi Euler và đồ thị Euler . . . . . . . . . . . . . . 50 2.4.2 Đường đi Hamilton và đồ thị Hamilton . . . . . . . . . . 55 2.4.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.5 Bài to¡n li¶n quan đến đồ thị tô màu . . . . . . . . . . . . . . . 70 2.5.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 70 2.5.2 T½nh ch§t . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.5.3 Thuªt to¡n t¼m s­c sè . . . . . . . . . . . . . . . . . . . 74 2.5.4 Lớp đồ thị có chu tr¼nh tam gi¡c cùng màu . . . . . . . . 75 2.5.5 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 77 2.6 Bài to¡n v· c¥y . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 2.6.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 85 2.6.2 Đặc điểm cõa c¥y và bụi . . . . . . . . . . . . . . . . . . 85 2.6.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Lời k¸t .................................. 91 Tài li»u tham kh£o ........................... 93 4
5. Mở đầu Lý thuy¸t đồ thị (lý thuy¸t graph) là mët ngành to¡n học hi»n đại, mët lĩnh vực kh¡ tr´ cõa to¡n học mặc dù nhúng v§n đề cõa lý thuy¸t đồ thị đã có tø vài tr«m n«m trước đây. Nhúng ý tưởng cơ b£n v· lý thuy¸t đồ thị được đưa ra vào n«m 1736 bởi nhà to¡n học Thụy Sĩ Leonhard Euler với bài to¡n nêi ti¸ng v· 7 c¥y c¦u ở thành phè K¨onigsberg. Nhúng công tr¼nh nghi¶n cùu v· lý thuy¸t đồ thị g­n li·n với nhúng t¶n tuêi c¡c nhà to¡n học lớn như Euler, Hamilton,... Cuèn s¡ch gi¡o khoa đầu ti¶n v· lý thuy¸t đồ thị được K¨onigvi¸t và xu§t b£n t¤i Leipzig n«m 1936. M¢i 22 n«m sau, cuèn s¡ch gi¡o khoa thù hai v· đồ thị mới được ra đời bởi nhà to¡n học Berge vi¸t và in t¤i Paris. V£ l¤i, do đặc trưng r§t “gần gũi” với thực t¸ cõa m¼nh, lý thuy¸t đồ thị ngày càng kh¯ng định được vị tr½ quan trọng trong vi»c ¡p dụng để gi£i c¡c bài to¡n trong cuëc sèng. Nó có nhi·u ùng dụng quan trọng trong nhi·u ngành khoa học, kĩ thuªt hi»n đại: vªt lý, hóa học, sinh học, tin học,... Ngày nay, lý thuy¸t đồ thị đã trở thành mët công cụ không thº thi¸u được khi ph£i gi£i quy¸t nhúng v§n đề có t½nh ch§t ph£i xem x²t c£ têng thº. Được sự hướng d¨n tªn t¥m, sự ch¿ b£o tªn t¼nh và nhúng bài gi£ng t¥m huy¸t cõa NGND.GS.TS Đặng Huy Ruªn. T¡c gi£ xin đóng góp mët ph¦n nhỏ t¼m hiºu cõa b£n th¥n v· lý thuy¸t đồ thị qua luªn v«n: “Lý thuy¸t đồ thị và ùng dụng để gi£i to¡n sơ cấp”. Luªn v«n gồm ph¦n mở đầu, k¸t luªn, tài li»u tham kh£o và 2 chương. Chương 1. C¡c kh¡i ni»m và định lý cơ b£n. Chương 1 tr¼nh bày mët sè bài to¡n d¨n đến kh¡i ni»m đồ thị, mët sè kh¡i ni»m và định lý hay dùng trong lý thuy¸t đồ thị. C¡c lý thuy¸t này đã được GS.TS Đặng Huy Ruªn t½ch lũy trong cuèn s¡ch “Lý thuy¸t đồ thị và ùng dụng” bao gồm: - Kh¡i ni»m v· lý thuy¸t đồ thị. - C¡c c¡ch biºu di¹n đồ thị. 5
6. - Mët sè d¤ng đồ thị đặc bi»t. Chương 2. Đồ thị và mët sè bài to¡n phê thông. Chương 2 tr¼nh bày mët sè ùng dụng cõa lý thuy¸t đồ thị để gi£i quy¸t 6 d¤ng to¡n: 1. C¡c bài to¡n li¶n quan đến bªc cõa đồ thị. 2. C¡c bài to¡n li¶n quan đến chu tr¼nh. 3. C¡c bài to¡n li¶n quan đến đồ thị li¶n thông. 4. C¡c bài to¡n ùng dụng đồ thị Euler và đồ thị Hamilton. 5. C¡c bài to¡n ùng dụng đồ thị tô màu. 6. C¡c bài to¡n ùng dụng c¥y. T¡c gi£ xin bày tỏ láng bi¸t ơn s¥u s­c đ¸n NGND.GS.TS Đặng Huy Ruªn, người Th¦y đã tªn t¼nh hướng d¨n, giúp đỡ t¡c gi£ trong suèt qu¡ tr¼nh học tªp và hoàn thành luªn v«n. K½nh chúc th¦y m¤nh kho´, h¤nh phúc để th¸ h» học trá chúng con được học hỏi nhi·u hơn núa tø t§m gương cõa th¦y. T¡c gi£ xin ch¥n thành c£m ơn Ban gi¡m hi»u, Pháng đào t¤o Sau đại học, Khoa To¡n - Cơ - Tin học, c¡c th¦y gi¡o, cô gi¡o và c¡c b¤n cõa seminar “Phương ph¡p To¡n sơ cấp” Trường Đại học Khoa học Tự nhi¶n - ĐHQGHN đã giúp đỡ và góp ý cho luªn v«n được hoàn ch¿nh. Do tr¼nh độ cán h¤n ch¸, ch­c ch­n luªn v«n không tr¡nh khỏi thi¸u sót. T¡c gi£ mong nhªn được nhi·u đóng góp tø c¡c b¤n đọc để luªn v«n được hoàn thi»n hơn. Xin tr¥n trọng c£m ơn. Học vi¶n Nguy¹n Ngọc H£i 6
7. Chương 1 C¡c kh¡i ni»m và định lý cơ b£n 1.1 C¡c v½ dụ v· đồ thị V½ dụ 1.1.1. Mët đoàn kh¡ch du lịch đến Hà Nëi và muèn đi th«m c¡c danh lam th­ng c£nh cõa Hà Nëi. Sơ đồ c¡c danh lam th­ng c£nh cũng như h» thèng giao thông ở Hà Nëi cho ph²p đi tø địa điểm này sang địa điểm kh¡c được cho theo sơ đồ ở h¼nh 1.1. Trong đó c¡c điểm biºu thị c¡c nơi kh¡ch c¦n đến, c¡c đo¤n th¯ng biºu thị c¡c con đường có thº đi được. B¤n h¢y giao cho Công ty du lịch Hà Nëi lªp hành tr¼nh sao cho kh¡ch có thº đi tới th«m mọi địa điểm, méi địa điểm đi qua không qu¡ mët l¦n và ch¿ đi theo c¡c đường có trong sơ đồ. Th¶m vào đó con đường b­t đầu tø A và k¸t thúc ở K. H¼nh 1.1 Theo sơ đồ th¼ đến C và E, méi điºm ch¿ có hai con đường. V¼ th¸ hành tr¼nh tho£ m¢n y¶u c¦u bài to¡n ph£i đi đến b¬ng mët đường và ra b¬ng con đường cán l¤i. Do vªy mët đoạn hành tr¼nh khi đến C ph£i là I ! C ! B hoặc B ! C ! I. Tương tự hành tr¼nh qua E ph£i là B ! E ! F hoặc 7
8. F ! E ! B. Nhưng trong hành tr¼nh, méi địa điểm ch¿ đi qua không qu¡ mët l¦n n¶n mët đoạn cõa hành tr¼nh ph£i là I ! C ! B ! E ! F hoặc ngược l¤i F ! E ! B ! C ! I (h¼nh 1.2). Do con đường b­t đầu tø A n¶n mët đoạn đầu cõa hành tr¼nh là A ! I ! C ! B ! E ! F . H¼nh 1.2 Đoạn cán l¤i ch¿ có thº là F ! M ! H ! D ! K. Vªy hành tr¼nh ph£i t¼m là: A ! I ! C ! B ! E ! F ! M ! H ! D ! K: Tø lời gi£i suy ra r¬ng hành tr¼nh tho£ m¢n bài ra là duy nh§t. V½ dụ 1.1.2. Mët m£nh gi§y được x² làm 3 ph¦n nhỏ. Đến lượt thù hai ta l¤i x² mët vài m£nh gi§y nhỏ, méi l¦n mët m£nh gi§y nhỏ được x² làm 3 ph¦n nhỏ hơn. Ti¸p tục lặp l¤i qu¡ tr¼nh đó. Chùng minh r¬ng, sau k (với k là sè nguy¶n dương) l¦n x² ta thu được sè m£nh gi§y là mët sè l´. Ta biºu thị méi m£nh gi§y như mët d§u ch§m ch§m trán. Sự ki»n méi m£nh gi§y sau méi l¦n x² được thành ba m£nh, mô t£ tr¶n h¼nh 1.3, trong đó d§u ch§m trán đen biºu thị m£nh gi§y ban đầu không cán núa và d§u ch§m trán tr­ng biºu thị c¡c m£nh gi§y nhªn được. H¼nh 1.3 giúp ta th§y r¬ng sau méi l¦n x² được th¶m hai m£nh gi§y (3 m£nh gi§y mới thay cho m£nh gi§y cũ) và mët v½ dụ cho 4 l¦n x². • Lượt thù nh§t x² m£nh ban đầu: được 3 m£nh gi§y nhỏ. 8
9. H¼nh 1.3 • Lượt thù hai x² 2 m£nh: được 7 m£nh gi§y nhỏ. • Lượt thù ba x² 4 m£nh: được 15 m£nh gi§y nhỏ. • Lượt thù tư x² 1 m£nh: được 17 m£nh gi§y nhỏ. Có được 17 d§u ch§m trán tr­ng, tương ùng 17 m£nh gi§y được nhªn. Khi mët m£nh gi§y bị x² thành 3 m£nh gi§y nhỏ hơn, ta th§y r¬ng méi m£nh gi§y m§t đi ta được th¶m 2 m£nh gi§y mới. Cù như vªy, sau k l¦n x², m§t đi l m£nh gi§y, ta được sè m£nh gi§y s³ là: 2l + 1. Vªy sè m£nh gi§y là mët sè l´. V½ dụ 1.1.3. Có thº có mët nhóm 5 người mà méi người quen đúng với hai người kh¡c trong nhóm hay không ? H¼nh 1.4 Biºu thị méi mët người là mët điểm cán n¸u hai người quen nhau th¼ ta nèi hai điểm tương ùng l¤i, n¸u không quen nhau th¼ giúa hai điểm không được nèi. 9
10. X²t mët ngũ gi¡c thông thường tr¶n h¼nh 1.4. Rã ràng méi đỉnh ngũ gi¡c được nèi với đúng hai đỉnh kh¡c. V¼ th¸ có thº có 5 người mà méi người quen với đúng hai người kh¡c trong sè 4 người cán l¤i. Trong bài to¡n này có thº thay sè 5 bởi mët sè tự nhi¶n n > 2 tuỳ ý. Lúc đó tương ùng thay ngũ gi¡c bởi đa gi¡c n c¤nh. Tuy nhi¶n ta cũng có thº thû suy nghĩ xem có hay không mët nhóm 5 người mà méi người quen đúng với 3 người cán l¤i trong nhóm ? V½ dụ 1.1.4. H¢y ph¥n nhóm học tªp cho lớp học sao cho nhúng người trong cùng mët nhóm là b¤n th¥n với nhau. Chọn đỉnh cõa sơ đồ c¦n lªp là nhúng em học sinh trong lớp. Trong sơ đồ biºu di¹n, ta nèi nhúng cặp hai em học sinh th¥n nhau b¬ng mët đoạn th¯ng (hoặc mët đo¤n cong). B¬ng c¡ch như vªy, ta s³ có mët sơ đồ gồm c¡c đỉnh (c¡c em học sinh) và c¡c c¤nh (c¡c đường nèi hai em khi và ch¿ khi hai em này th¥n nhau). Nhúng mô h¼nh quy v· c¡c tªp đỉnh và c¡c c¤nh nèi đỉnh là nhúng đồ thị. V½ dụ 1.1.5. B©y c¥y c¦u ở thành phè K¨onigsberg n«m 1736 (theo [1]). Thành phè K¨onigsberg cõa nước Đức (b¥y giờ là thành phè Kaliningrad cõa li¶n bang Nga) có dáng sông Pregel ch£y qua, giúa sông có cù lao Kneiphof và 7 c¥y c¦u như H¼nh 1.5a H¼nh 1.5 Tø khi xu§t hi»n 7 c¥y c¦u, người d¥n ở đây đã đặt ra v§n đề: “Liệu có c¡ch nào đi qua được c£ b©y c¥y c¦u và qua méi c¥y c¦u đúng mët l¦n được không ?”. 10