Luận văn Ứng dụng đồ thị tìm ước số và xác định tập đồng dư

Nội dung tài liệu: Luận văn Ứng dụng đồ thị tìm ước số và xác định tập đồng dư

1. ĐẠI HÅC QUÈC GIA HÀ NËI TRƯỜNG ĐẠI HÅC KHOA HÅC TỰ NHIÊN ------------------ PHẠM THỊ THỦY ỨNG DỤNG ĐỒ THỊ TÌM ƯỚC SÈ VÀ XÁC ĐỊNH TẬP ĐÇNG DƯ 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 01 13 NGƯỜI HƯỚNG DẪN KHOA HÅC: GS.TS. ĐẶNG HUY RUẬN Hà Nëi - N«m 2013
2. Mục lục MÐ ĐẦU 2 1 MËT SÈ KHÁI NIỆM CƠ BẢN 4 1.1 C¡c kh¡i ni»m cơ b£n . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Định nghĩa đồ thị . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Biºu di¹n đồ thị b¬ng h¼nh học . . . . . . . . . . . . . . . 6 1.1.3 X½ch, chu tr¼nh, đường và váng . . . . . . . . . . . . . . . 7 1.1.4 Đồ thị li¶n thông và chu sè . . . . . . . . . . . . . . . . . 10 1.2 Đồ thị được g¡n nh¢n . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Nguồn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 CÂY SINH ƯỚC 16 2.1 C¥y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.2 Đặc điểm cõa c¥y và c¥y có hướng . . . . . . . . . . . . . . 18 2.2 C¥y sinh ước . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.2 Thuªt to¡n x¥y dựng c¥y sinh ước . . . . . . . . . . . . . . 22 2.2.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3 NGUÇN ĐỒNG DƯ 27 3.1 Nguồn đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.1 Định nghĩa nguồn đồng dư . . . . . . . . . . . . . . . . . . 27 3.1.2 Định nghĩa Euclid . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.3 Thuªt to¡n x¥y dựng nguồn đồng dư . . . . . . . . . . . . . 28 3.2 Nguồn giao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 K¸t luªn .................................... 49 Tài li»u tham kh£o ............................. 51 1
3. MÐ ĐẦU To¡n học rời r¤c nghi¶n cùu c¡c c§u trúc có t½nh ch§t rời r¤c không li¶n tục. To¡n rời r¤c bao gồm c¡c lĩnh vực như quan h», lý thuy¸t đồ thị, logic to¡n, ngôn ngú h¼nh thùc . . . , trong đó lý thuy¸t đồ thị là mët bë phªn trọng t¥m với nhi·u khèi lượng ki¸n thùc kh¡ lý thú và đưñc nghi¶n cùu nhi·u nh§t. Lý thuy¸t đồ thị là mët chuy¶n ngành to¡n học hi»n đại đã được ùng dụng vào nhi·u ngành khoa học, kỹ thuªt kh¡c nhau, bởi v¼ lý thuy¸t đồ thị là phương ph¡p khoa học có t½nh kh¡i qu¡t cao và có t½nh ên định vúng ch­c v¼ th¸ thông qua đồ thị có thº m¢ hóa c¡c mèi quan h» cõa c¡c đối tượng được nghi¶n cùu. Vªn dụng lý thuy¸t đồ thị để mô h¼nh hóa c¡c mèi quan h» trong gi£ng d¤y s³ chuyºn thành phương ph¡p d¤y học đặc thù và n¥ng cao được hi»u qu£ gi£ng d¤y thúc đẩy qu¡ tr¼nh tự học, tự nghi¶n cùu cõa học sinh theo hướng tèi ưu hóa. Đặc bi»t vi»c vªn dụng lý thuy¸t đồ thị trong gi£ng d¤y cán nh¬m r±n luy»n n«ng lực h» thèng hóa ki¸n thùc và n«ng lực s¡ng t¤o cõa học sinh. Tø nhªn thùc tr¶n, đề tài "Ứng dụng đồ thị t¼m ước sè và x¡c định tªp đồng dư" không nhúng là nhi»m vụ em ph£i thực hi»n trong kỳ b£o v» luªn v«n tèt nghi»p, mà thực sự là đề tài em r§t quan t¥m và say m¶ nghi¶n cùu. “Ứng dụng đồ thị t¼m ước sè và tªp đồng dư” là đề tài mang t½nh nghi¶n cùu lý thuy¸t, có t¦m quan trọng và ý nghĩa thi¸t thực cao. Luªn v«n bao gồm ph¦n mở đầu và ba chương: Chương 1. Mët sè kh¡i ni»m cơ b£n Nh¬m tr¼nh bày nhúng kh¡i ni»m cơ b£n nh§t v· đồ thị, là cơ sở t¼m hiºu s¥u s­c hơn c¡c v§n đề ti¸p theo. Méi ph¦n gồm: Định nghĩa, định lý và c¡c t½nh ch§t cơ b£n cõa đồ thị. Ngoài ra, trong chương này cán tr¼nh bày mët sè phương ph¡p biºu di¹n đồ thị, méi phương ph¡p đều có nhúng ưu và nhược điểm ri¶ng, v¼ vªy c¦n lựa chọn phương ph¡p, sao cho phù hñp với đặc điểm tøng bài to¡n và đạt được hi»u qu£ v· thuªt to¡n. 2
4. MÐ ĐẦU Chương 2. C¥y sinh ước C¥y là mët trường hñp ri¶ng cõa đồ thị, để nghi¶n cùu h¸t c¡c t½nh ch§t, kh¡i ni»m v· c¥y c¦n c£ mët khèi lượng ki¸n thùc đồ së và đã có nhúng đề tài nghi¶n cùu s¥u v· c¥y. Trong chương này ch¿ đề cªp tới nhúng điểm ch½nh nh§t, cơ b£n nh§t v· c¥y và tªp trung khai th¡c nhúng ùng dụng cõa nó. Nhúng ùng dụng cõa c¥y th¼ r§t nhi·u, trong chương ch¿ đề cªp tới nhúng ùng dụng cơ sở nh§t, nhưng cũng thi¸t thực nh§t. Đó là ùng dụng cõa c¥y để gi£i c¡c bài to¡n t¼m ước sè. Chương 3. Nguồn đồng dư Đây là chương cuèi cùng và là chương s³ đề cªp tới nhi·u ùng dụng nh§t. Trong chương này s³ nh­c l¤i thuªt to¡n kh¡ g¦n gũi với cuëc sèng. Đó là thuªt to¡n x¥y dựng đồ thị x¡c định tªp đồng dư, được gọi t­t là nguồn đồng dư. Tø c¡ch x¥y dựng tªp đồng dư ta có thº th§y được ùng dụng cõa nó vào vi»c chuyºn c¡c bài to¡n phùc t¤p trong t½nh to¡n v· c¡c bài to¡n gi£i đơn gi£n. Hà Nëi, th¡ng 11 n«m 2013. 3
5. Chương 1 MËT SÈ KHÁI NIỆM CƠ BẢN 1.1 C¡c kh¡i ni»m cơ b£n Hai chú “đồ thị” v¨n thường xuy¶n xu§t hi»n trong đời sèng to¡n học và c£ trong đời sèng hàng ngày. Trong c¡c giờ to¡n, chúng ta tøng nói tới đồ thị cõa c¡c hàm sè. Hay trong c¡c công sở, c¡c nh¥n vi¶n ph£i lªp c¡c biºu đồ theo dãi lượng ti¶u thụ điện. Nói chung, kh¡i ni»m đồ thị là mët kh¡i ni»m kh¡ quen thuëc với chúng ta nh¬m biºu di¹n tương quan qua l¤i giúa hai hoặc nhi·u đối tượng to¡n học kh¡c nhau. Ð đây, kh¡i ni»m đồ thị v¨n được dùng theo nghĩa đó nhưng nó mang t½nh trøu tượng hơn. 1.1.1 Định nghĩa đồ thị Tªp hñp X 6= ? c¡c đối tượng và bë E c¡c cặp s­p thù tự và không s­p thù tự c¡c ph¦n tû cõa X được gọi là mët đồ thị,đồng thời được ký hi»u b¬ng G(X; E) hoặc b¬ng G = (X; E) hoặc b¬ng G(X). C¡c ph¦n tû cõa X được gọi là đỉnh. Cặp đỉnh không s­p thù tự gọi là c¤nh, cặp đỉnh s­p thù tự được gọi là c¤nh có hướng hay cung. Đồ thị ch¿ chùa c¡c c¤nh được gọi là đồ thị vô hướng, cán đồ thị ch¿ chùa c¡c cung đưñc gọi là đồ thị có hướng. N¸u đồ thị chùa c£ c¤nh l¨n cung th¼ nó được gọi là đồ thị hén hñp hay đồ thị hén t¤p. Mët cặp đỉnh có thº được nèi với nhau b¬ng hai hoặc nhi·u hơn hai c¤nh (hai hoặc nhi·u hơn hai cung và hướng). C¡c c¤nh (cung) này được gọi là c¡c c¤nh (cung) bëi. 4
6. Chương 1. MËT SÈ KHÁI NIỆM CƠ BẢN Mët cung hay mët c¤nh có thº b­t đầu và k¸t thúc t¤i cùng mët đỉnh. Cung hay c¤nh lo¤i này được gọi là khuy¶n hay nút. Cặp đỉnh x; y được nèi với nhau b¬ng c¤nh (cung) a th¼ x; y được gọi là c¡c đỉnh hay hai đầu cõa c¤nh (cung) a, và a được gọi là c¤nh (cung) thuëc đỉnh x; y. N¸u cung b xu§t ph¡t tø đỉnh u và đi vào đỉnh v, th¼ u được gọi là đỉnh đầu, cán v được gọi là đỉnh cuèi cõa cung b. Cặp đỉnh x; y được gọi là hai đ¿nh k· nhau, n¸u x 6= y và là hai đầu cõa cùng mët c¤nh hay mët cung. Đối với mọi đ¿nh x dùng D(x) để ch¿ tªp đỉnh, mà méi đỉnh này được nèi với x b¬ng ½t nh§t mët c¤nh; D+ (x) để ch¿ tªp đỉnh, mà méi đỉnh này tø x có cung đi tới; D− (x) dùng để ch¿ tªp đỉnh mà méi đỉnh này có cung đi tới x. Hai c¤nh (cung) a; b được gọi là k· nhau n¸u chúng kh¡c nhau và có chung đỉnh (n¸u a; b là cung th¼ không phụ thuëc vào đỉnh chung đó là đỉnh đầu hay đỉnh cuèi cõa cung a, đỉnh đầu hay đỉnh cuèi cõa cung b). V½ dụ 1.1. Cho đồ thị hén hñp có khuy¶n G(X; E) với tªp đỉnh: X= fx1; x2; x3; x4; x5; x6; x7g, Tªp c¤nh và cung: E= f(x1; x2) ; (x2; x3) ; (x4; x6) ; (x5; x6) ; (x3; x3) ; (x1; x6) ; (x5; x5)g = { a1 , a2 , a3, a4 , a5 , b1 , b2 } Trong đó a1; a2; a3; a4; a5- c¡c c¤nh, b1; b2- c¡c cung, cung b1 có x1 là đỉnh đầu, x6 là đỉnh cuèi. Đồ thị G(X; E) không có khuy¶n và méi cặp đỉnh được nèi với nhau b¬ng không qu¡ mët c¤nh, được gọi là đồ thị đơn hay đơn đồ thị và thông thường gọi là đồ thị. Đồ thị G(X; E) không có khuy¶n và có ½t nh§t mët cặp đỉnh được nèi với nhau tø hai c¤nh trở l¶n được gọi là đa đồ thị. Đa đồ thị vô hướng là mët bë G(X; E), trong đó: (1) X 6= ; là tªp hñp húu h¤n gồm c¡c đỉnh cõa đồ thị. (2) E là mët họ c¡c cặp không có thù tự cõa X gọi là c¡c c¤nh. Đa đồ thị có hướng là mët bë G(X; E), trong đó: (1) X 6= ; là tªp hñp húu h¤n gồm c¡c đỉnh cõa đồ thị. (2) E là mët họ c¡c cặp có thù tự cõa X gọi là c¡c cung. Mët đồ thị hay đa đồ thị có khuy¶n, th¼ nó được gọi là đồ thị hay đa đồ thị có khuy¶n. 5
7. Chương 1. MËT SÈ KHÁI NIỆM CƠ BẢN Đồ thị vô hướng (có hướng) G(X; E) được gọi là đồ thị đầy đủ, n¸u méi cặp đỉnh đưñc nèi với nhau b¬ng đúng mët c¤nh (mët cung với chi·u tùy ý). Đồ thị (đa đồ thị) G(X; E) được gọi là húu h¤n n¸u sè đỉnh cõa nó húu h¤n, tùc tªp X có lực lượng húu h¤n. Gi£ sû G(X; E) là mët đồ thị hay đa đồ thị có hướng hoặc không có hướng. Sè c¤nh và cung thuëc đỉnh x được gọi là bªc cõa đ¿nh x và ký hi»u b¬ng m(x). Đỉnh có bªc b¬ng 0 gọi là đỉnh bi»t lªp. Đỉnh có bªc b¬ng 1 gọi là đỉnh treo. C¤nh (cung) có ½t nh§t mët đầu là đỉnh treo được gọi là c¤nh (cung) treo. 1.1.2 Biºu di¹n đồ thị b¬ng h¼nh học Đồ thị có nhi·u c¡ch biºu di¹n, nhưng trong ph¦n này ch¿ tr¼nh bày c¡ch biºu di¹n b¬ng h¼nh học. Gi£ sû có đồ thị G(X; E) Để có d¤ng biºu di¹n h¼nh học cõa G ta c¦n biºu di¹n đỉnh và c¤nh. Biºu di¹n đỉnh: L§y c¡c điểm tr¶n mặt ph¯ng hay trong không gian tương ùng với c¡c ph¦n tû cõa tªp X và dùng ngay ký hi»u c¡c ph¦n tû này để ghi tr¶n c¡c điểm tương ùng. Biºu di¹n c¤nh: N¸u c¤nh với hai đỉnh đầu là x; y th¼ nó được biºu di¹n b¬ng mët đoạn th¯ng hay mët đoạn cong nèi giúa hai điểm x; y và không đi qua c¡c điểm tương ùng trung gian kh¡c. Biºu di¹n cung: N¸u cung có đỉnh đầu là x, đ¿nh cuèi là y, th¼ nó được biºu di¹n b¬ng mët đo¤n th¯ng hoặc mët đoạn cong được định hướng đi tø x sang y và không qua c¡c điểm tương ùng trung gian kh¡c. H¼nh nhªn được gọi là d¤ng biºu di¹n h¼nh học cõa đồ thị G(X; E). Đôi khi người ta cũng gọi d¤ng biºu di¹n h¼nh học là đồ thị. 6
8. Chương 1. MËT SÈ KHÁI NIỆM CƠ BẢN V½ dụ 1.2. D¤ng biºu di¹n h¼nh học cõa đồ thị G(X, E) cho trong v½ dụ 1.1: 1.1.3 X½ch, chu tr¼nh, đường và váng Đối với đồ thị (đa đồ thị) vô hướng có kh¡i ni»m x½ch (d¥y chuy·n) và chu tr¼nh, cán đối với đồ thị (đa đồ thị) có hướng tồn t¤i kh¡i ni»m đường và váng. Tuy vªy, người ta v¨n thường dùng kh¡i ni»m đường cho c£ đồ thị và đa đồ thị vô hướng. 1.1.3.1. X½ch, chu tr¼nh Gi£ sû G(X; E) là mët đồ thị hay đa đồ thị vô hướng. D¢y α c¡c đỉnh cõa G (X; E) : α = [x1; x2; :::; xi; xi+1; :::; xn−1; xn] được gọi là mët x½ch hay mët d¥y chuy·n, n¸u 8i (1 ≤ i ≤ n − 1) cặp đỉnh xi; xi+1 k· nhau (có c¤nh nèi với nhau). C¡c đỉnh x1; xn được gọi là hai đỉnh đầu cõa x½ch α được gọi là độ dài cõa x½ch α, đồng thời được ký hi»u b¬ng jαj. C¡c đỉnh x1; xn được gọi là hai đỉnh đầu cõa x½ch α. Ngoài ra, cán nói r¬ng x½ch α nèi giúa c¡c đỉnh x1 và xn. Để ch¿ rã đỉnh đ¦u và đỉnh cuèi ta cán ký hi»u α b¬ng α [x1; xn]. Mët x½ch với hai đầu trùng nhau, được gọi là mët chu tr¼nh. X½ch (chu tr¼nh) α được gọi là x½ch (chu tr¼nh) đơn (sơ c§p hay cơ b£n) n¸u nó đi qua méi c¤nh (méi đỉnh) không qu¡ mët l¦n. 7
9. Chương 1. MËT SÈ KHÁI NIỆM CƠ BẢN V½ dụ 1.3. Cho đồ thị: α1 = x1x2x3x4x5x6 là x½ch đơn và sơ c§p. α2 = x2x3x4x5x1x2x5 là x½ch đơn, nhưng không sơ c§p. α3 = x1x2x4x5x6x1 là chu tr¼nh đơn và sơ c§p. α4 = x1x5x2x4x5x6x1 là chu tr¼nh đơn, nhưng không là chu tr¼nh sơ c§p. 1.1.3.2. Đường, váng Gi£ sû G(X; E) là đồ thị hay đa đồ thị có hướng. D¢y đỉnh β cõa G(X; E) β = [x1; x2; :::; xi; xi+1; :::; xm−1; xm] được gọi là mët đường hay mët đường đi, n¸u 8i (1 ≤ i ≤ m − 1) đỉnh xi là đỉnh đầu, cán xi+1 là đỉnh cuèi cùng mët cung nào đó tø xi ! xi+1. Têng sè vị tr½ cõa t§t c£ c¡c cung xu§t hi»n trong β được gọi là độ dài cõa đường β, đồng thời được ký hi»u b¬ng jβj. Đỉnh x1 được gọi là đỉnh đầu, đỉnh xm được gọi là đỉnh cuèi cõa đường β. Người ta cán nói r¬ng, đường β xu§t ph¡t tø đỉnh x1 và đi tới đỉnh xm. Đường β cán được ký hi»u b¬ng β [x1; xm]. Mët đường có đỉnh đầu và đỉnh cuèi trùng nhau được gọi là mët váng. Đường (váng) β được gọi là đường (váng) đơn (sơ c§p hay cơ b£n), n¸u nó đi qua méi c¤nh (méi đỉnh) không qu¡ mët l¦n. 8
10. Chương 1. MËT SÈ KHÁI NIỆM CƠ BẢN V½ dụ 1.4. Cho đồ thị có hướng: β = [x1x2x3x4x5x6] là đường đơn và đường sơ c§p. β1 = [x2x3x4x5x7x6x2] là váng đơn và váng sơ c§p. β2 = [x7x2x3x4x5x7x6] là đường đơn, nhưng không là đường sơ c§p. β3 = [x1x2x3x4x2] không là đường. β4 = [x1x7x2x5x7x2x4] không là đường đơn, nhưng không là váng sơ c§p. β5 = [x1x7x2x5x7x6x1] là váng đơn, nhưng không là váng sơ c§p. Hai x½ch (chu tr¼nh) được gọi là rời nhau, n¸u chúng không có c¤nh chung. Hai đường (váng) gọi là rời nhau n¸u chúng không có c¤nh chung. Để d¹ h¼nh dung ta gọi chu tr¼nh có độ dài 3, 4, 5, ..., n là chu tr¼nh tam gi¡c, tù gi¡c, ngũ gi¡c, ..., n gi¡c. 1.1.3.3. Mët sè t½nh ch§t Định lý 1.1. Trong mët đồ thị vô hướng với n (n ≥ 3) đỉnh và c¡c đỉnh đều có bªc không nhỏ hơn 2 luôn luôn tồn t¤i chu tr¼nh sơ c§p. Chùng minh. V¼ đồ thị húu h¤n, mà méi x½ch sơ c§p đi qua tøng đỉnh không qu¡ mët l¦n, n¶n sè x½ch sơ c§p trong đồ thị G(X; E) là mët sè húu h¤n. Bởi vªy luôn luôn x¡c định được x½ch sơ c§p có độ dài cực đại trong đồ thị G(X; E). Gi£ sû α = [x1; x2; :::; xk−1; xk] là mët trong nhúng x½ch sơ c§p có độ dài cực đại. Do bªc cõa méi đỉnh thuëc G không nhỏ hơn 2, n¶n x1 ph£i k· với mët đỉnh y nào đó kh¡c x2. Ngược l¤i, n¸u đỉnh y kh¡c với đ¿nh xi (3 ≤ i ≤ k) th¼ x½ch sơ c§p 9