›
›

Giáo trình Toán rời rạc - Nghề: Lập trình máy tính - Trình độ: Cao đẳng - Trường Cao đẳng nghề cơ giới Ninh Bình

pdf 51 trang Gia Huy 17/05/2022 2130
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Nghề: Lập trình máy tính - Trình độ: Cao đẳng - Trường Cao đẳng nghề cơ giới Ninh Bình", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_toan_roi_rac_nghe_lap_trinh_may_tinh_trinh_do_cao.pdf

Nội dung text: Giáo trình Toán rời rạc - Nghề: Lập trình máy tính - Trình độ: Cao đẳng - Trường Cao đẳng nghề cơ giới Ninh Bình

  1. BỘ NÔNG NGHIỆP VÀ PHÁT TRIỂN NÔNG THÔN TRƯỜNG CAO ĐẲNG NGHỀ CƠ GIỚI NINH BÌNH GIÁO TRÌNH MÔN HỌC: TOÁN RỜI RẠC NGÀNH/NGHỀ: LẬP TRÌNH MÁY TÍNH TRÌNH ĐỘ: CAO ĐẲNG Ban hành kèm theo Quyết định số: /QĐ-TCGNB ngày .tháng năm 201 của Trường cao đẳng nghề Cơ giới Ninh Bình Ninh Bình, năm 2018 1
  2. TUYÊN BỐ BẢN QUYỀN Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể được phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo. Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh doanh thiếu lành mạnh sẽ bị nghiêm cấm. 2
  3. LỜI GIỚI THIỆU Toán rời rạc là một lĩnh vực của toán học nghiên cứu các đối tượng rời rạc, đặc biệt vai trò của Toán rời rạc trong lĩnh vực tin học. Khi phải đếm các đối tượng rời rạc, khi nghiên cứu quan hệ giữa các đối tượng rời rạc và đặc biệt là việc cất giữ và sử lý thông tin trên máy tính. Cuốn sách nhằm giới thiệu các kiến thức cơ bản về: Lý thuyết tổ hợp, lý thuyết đồ thị nhằm giúp các em ngành Lập trình có tài liệu tham khảo, đồng thời cũng là tài liệu học tập cho các em. Tài liệu này được biên soạn gồm 5 chương: Chương 1. Trình bày các vấn đề của lý thuyết tổ hợp, soay quanh các bài toán cơ bản: Bài toán đếm, bài toán tồn tại. Nội dung chương I không những giúp nâng cao tư duy toán học mà còn làm quen với thuật toán để giải quyết các bài toán trong thực tế. Chương 2. Trình bày các kiến thức cơ bản về lý thuyết đồ thị. Chương này cung cấp các kiến thức cơ bản về lý thuyết đồ thị, giúp người học có kiến thức cơ sở để nghiên cứu về đồ thị trong các chương tiếp theo. Chương 3. Biểu diễn đồ thị trên máy tính và các thuật toán tìm kiếm. Sau khi người học đã tìm hiểu những kiến thức cơ bản về đồ thị thì tiến hành xây dựng cấu trúc dữ liệu để biểu diễn đồ thị trên máy tính, đồng thời xây dựng các thuật toán tìm kiếm đồ thị được tổ chức trên máy tính. Chương 4. Trình bày các kiến thức về cây và cây khung của đồ thị, cách xây dựng chu trình của đồ thị. Chương 5. Giúp người học xây dựng đường đi, tìm đường đi ngắn nhất trong đồ thị. Mặc dù tác giả đã cố gắng rất nhiều nhưng tài liệu cũng không tránh khỏi những thiếu sót. Tác giả rất mong nhận được ý kiến đóng góp của bạn đọc quan tâm để tài liệu ngày càng hoàn thiện hơn. Ninh Bình, ngày tháng năm 2018 Tham gia biên soạn 1. Nguyễn Văn Thái 2. Nguyễn Xuân Khôi 3. Vũ Ánh Dương 3
  4. MỤC LỤC TRANG Lời giới thiệu 3 Chương 1. Lý thuyết tổ hợp 6 1. Sơ lược về tổ hợp 6 2. Bài toán đếm và phương pháp giải 8 3. Bài toán tồn tại và phương pháp giải 17 Chương 2. Các khái niệm cơ bản của lý thuyết đồ thị 20 1. Định nghĩa đồ thị 20 2. Các thuật ngữ cơ bản 20 3. Đường đi, chu trình đồ thị liên thông 21 Chương 3. Biểu diễn đồ thị và các thuật toán tìm kiếm 25 1. Ma trận kề, ma trận trọng số 25 2. Danh sách cạnh, danh sách liên kết 26 3. Tìm kiếm theo chiều rộng và chiều sâu 27 4. Một số ứng dụng 30 5. Bài tập 33 Chương 4. Cây và cây khung của đồ thị 34 1. Cây và các tính chất của cây 34 2. Cây khung nhỏ nhất 37 3. Đồ thị Euler và đồ thị Hamilton 40 4. Bài tập 44 Chương 5. Đường đi ngắn nhất 46 1. Các khái niệm mở đầu 46 2. Thuật toán Dijkstra 47 3. Thuật toán Floy 49 4. Bài tập 50 4
  5. GIÁO TRÌNH MÔN HỌC Tên môn học: Toán rời rạc Mã môn học: MH12 Vị trí, tính chất, ý nghĩa và vai trò của môn học/mô đun: - Vị trí: Đây là môn học bắt buộc giúp người học có kiến thức để học các môn về lập trình và các môn có tính logic. - Tính chất: Môn học này là môn học dựa trên nền tảng toán học và kiến thức về lập trình căn bản. - Ý nghĩa và vai trò của môn học/mô đun: Toán rời rạc là nền tảng của thuật toán và nhiều mô hình quan trọng trong máy tính (Logic, đại số bool, lý thuyết đồ thị, xác suất, tổ hợp ). Nó là cái nền toán học quan trọng của máy tính. Mục tiêu của môn học: - Về kiến thức: Vận dụng các kiến thức đã sinh viên viên xây dựng các thuật toán tính : tổ hợp, hoán vị, giải hệ phương trình, phương trình, tính tích phân. - Về kỹ năng: + Sử dụng các kiến thức đã sinh viên viên xây dựng thuật toán quay lại, các bài toán tối ưu, bài toán tồn tại; + Là nền tảng để sinh viên học môn cấu trúc dữ liệu và giải thuật, cài đặt các thuật toán trong tin học. - Về năng lực tự chủ và trách nhiệm: Có khả năng tổ chức, thực hiện các nhiệm vụ và chịu trách nhiệm đối với kết quả công việc của mình. Nội dung môn học: 5
  6. CHƯƠNG 1: LÝ THUYẾT TỔ HỢP Mã chương: Mh12.1 Giới thiệu: Trình bày các vấn đề của lý thuyết tổ hợp, soay quanh các bài toán cơ bản: Bài toán đếm, bài toán tồn tại. Mục tiêu: - Trình bày được các khái niệm của tổ hợp; - Thực hiện được các bài toán về lý thuyết tổ hợp; - Nghiêm túc trong học tập, đảm bảo an toàn cho người và trang thiết bị. Nội dung chính: 1. S¬ l•îc vÒ tæ hîp Tæ hîp nh• lµ mét lÜnh vùc cña to¸n häc rêi r¹c, xuÊt hiÖn vµo ®Çu thÕ kû 17. HiÖn nay lý thuyÕt tæ hîp ®•îc ¸p dông trong nhiÒu lÜnh vùc kh¸c nhau: lý thuyÕt sè, h×nh häc, thèng kª x¸c suÊt, 1.1. ChØnh hîp lÆp §Þnh nghÜa: Mét chØnh hîp lÆp chËp k cña n phÇn tö lµ mét bé cã thø tù gåm cã k thµnh phÇn, mçi thµnh phÇn lÊy tõ tËp n phÇn tö ®· cho tr•íc vµ cã thÓ k k trïng nhau. K/h: An n VÝ dô: TÝnh sè d·y nhÞ ph©n ®é dµi 3 Gi¶i: Mçi d·y nhÞ ph©n ®é dµi 3 lµ mét bé gåm 3 thµnh phÇn (mçi thµnh phÇn chØ nhËn mét trong hai gi¸ trÞ 0 hoÆc 1) Sè x©u nhÞ ph©n ®é dµi 3 lµ 23 Suy réng: sè d·y nhÞ ph©n cã ®é dµi n lµ 2n 1.2. ChØnh hîp kh«ng lÆp Mét chØnh hîp kh«ng lÆp chËp k cña n phÇn tö lµ mét bé cã thø tù gåm k phÇn tö, mçi phÇn tö lÊy tõ tËp n phÇn tö cho tr•íc vµ kh«ng trïng nhau k n! k/h: P n (n k)! 1.3. Tæ hîp §Þnh nghÜa: Mét tæ hîp chËp k cña n phÇn tö (k n) lµ tËp hîp k phÇn tö k n! chän tõ tËp n phÇn tö cho tr•íc. k/h : C n k!(n k)! Chøng minh: XÐt tËp c¸c chØnh hîp kh«ng lÆp chËp k cña n phÇn tö, tËp n! nµy cã (n k)! phÇn tö vµ chia thµnh c¸c líp. Mµ mçi líp gåm c¸c bé cã thø tù 6
  7. n! kh¸c nhau sè phÇn tö trong mçi líp lµ k! sè líp b»ng còng k!(n k)! chÝnh lµ tæ hîp. k n k TÝnh chÊt: - Cn Cn k k 1 k - Cn Cn 1 Cn 1 * C¸c sè tæ hîp cã quan hÖ víi biÓu thøc khai triÓn nhÞ thøc Newton n n 0 n 1 n 1 1 2 n 2 2 n 1 1 n 1 n n i n i i (x y) Cn x Cn x y Cn x y Cn x y Cn y Cn x y i 0 3 7 10 3 7 VÝ dô: TÝnh hÖ sè khai triÓn cña x y cña (x+y) lµ: C10 C10 1.4. Ho¸n vÞ lÆp VÝ dô: Cho ch÷ ACCESS Hái cã bao c¸ch s¾p xÕp tÊt c¶ c¸c ch÷ c¸i thµnh c¸c ch÷ kh¸c nhau? Gi¶i: Ch÷ ACCESS gßm cã 6 ch÷ ®•îc ®¸nh thø tù nh• sau: A C C E S S 1 2 3 4 5 6 1 - Ta thÊy trong chuçi ACCESS, cã 1 ch÷ A cã C6 c¸ch ®Æt ch÷ A vµo mét trong 6 vÞ trÝ 2 - Ta thÊy trong chuçi ACCESS, cã 2 ch÷ C cã C5 c¸ch ®Æt ch÷ C vµo 5 vÞ trÝ cßn l¹i 1 - Ta thÊy trong chuçi ACCESS, cã 1 ch÷ E cã C3 c¸ch ®Æt ch÷ A vµo 3 vÞ trÝ cßn l¹i 2 - Cuèi cïng cßn l¹i 2 ch÷ S ®Æt vµo 2 vÞ trÝ cßn l¹i cã C2 c¸ch ®Æt ch÷ S vµo vÞ trÝ 1 2 1 2 Nh• vËy: Cã C6.C5 .C3.C2 =180 c¸ch Tæng qu¸t: n1 sè phÇn tö lo¹i 1 n2 sè phÇn tö lo¹i 2 Cho n phÇn tö trong ®ã cã: n3 sè phÇn tö lo¹i 3 víi n1 n2 n3 nm n  nm sè phÇn tö lo¹i m 7
  8. n! Sè ho¸n vÞ lÆp = Cn1 .Cn2 Cnm n n n1 (n n1 nm ) n1!.n2! nm! 1.5. Tæ hîp lÆp Tæng qu¸t: CÇn lÊy ra k vËt tõ tËp n lo¹i (phÇn tö) k Sè c¸ch lÊy= Cn 1 k VÝ dô: Cho ph•¬ng tr×nh x1 x2 x3 10 ®Õm sè nghiÖm nguyªn cña ph•¬ng tr×nh. Gi¶i: Ta cã: víi mçi c¸ch lÊy nghiÖm øng víi viÖc lÊy ra x1 phÇn tö lo¹i 1; x2 phÇn tö lo¹i 2; x3 phÇn tö lo¹i 3; 12! Sè lÇn chän lµ 10 Sè c¸ch lÊy: C10 66 10 (3 1) 10!.2! 2. Bµi to¸n ®Õm vµ ph•¬ng ph¸p gi¶i 2.1. Nguyªn lý céng Quy t¾c céng: Gi¶ sö cã A c«ng viÖc A1, A2, , Ak. C¸c viÖc nµy cã thÓ lµm t•¬ng øng b»ng n1, n2, , nk c¸ch vµ gi¶ sö kh«ng cã hai viÖc nµo cã thÓ lµm ®ång thêi. Khi ®ã sè c¸ch lµm mét trong k viÖc ®ã lµ n1+n2+ + nk. VÝ dô: 1. Mét sinh viªn cã thÓ chän bµi thùc hµnh m¸y tÝnh tõ mét trong ba danh s¸ch t•¬ng øng cã 23, 15 vµ 19 bµi. V× vËy, theo quy t¾c céng cã 23 + 15 + 19 = 57 c¸ch chän bµi thùc hµnh. 2. Gi¸ trÞ cña biÕn m b»ng bao nhiªu sau khi ®o¹n ch•¬ng tr×nh sau ®•îc thùc hiÖn? m := 0 for i1 := 1 to n1 m := m+1 for i2 :=1 to n2 m := m+1 for ik := 1 to nk m := m+1 8
  9. Gi¸ trÞ khëi t¹o cña m b»ng 0. Khèi lÖnh nµy gåm k vßng lÆp kh¸c nhau. Sau mçi b•íc lÆp cña tõng vßng lÆp gi¸ trÞ cña k ®•îc t¨ng lªn mét ®¬n vÞ. Gäi Ti lµ viÖc thi hµnh vßng lÆp thø i. Cã thÓ lµm Ti b»ng ni c¸ch v× vßng lÆp thø i cã ni b•íc lÆp. Do c¸c vßng lÆp kh«ng thÓ thùc hiÖn ®ång thêi nªn theo quy t¾c céng, gi¸ trÞ cuèi cïng cña m b»ng sè c¸ch thùc hiÖn mét trong sè c¸c nhiÖm vô Ti, tøc lµ m = n1+n2+ + nk. Quy t¾c céng cã thÓ ph¸t biÓu d•íi d¹ng cña ng«n ng÷ tËp hîp nh• sau: NÕu A1, A2, , Ak lµ c¸c tËp hîp ®«i mét rêi nhau, khi ®ã sè phÇn tö cña hîp c¸c tËp hîp nµy b»ng tæng sè c¸c phÇn tö cña c¸c tËp thµnh phÇn. Gi¶ sö Ti lµ viÖc chän mét phÇn tö tõ tËp Ai víi i =1,2, , k. Cã |Ai| c¸ch lµm Ti vµ kh«ng cã hai viÖc nµo cã thÓ ®•îc lµm cïng mét lóc. Sè c¸ch chän mét phÇn tö cña hîp c¸c tËp hîp nµy, mét mÆt b»ng sè phÇn tö cña nã, mÆt kh¸c theo quy t¾c céng nã b»ng | A1|+|A2|+ +|Ak|. Do ®ã ta cã: |A1  A2   Ak| = |A1| + |A2| + + |Ak|. Tæng qu¸t: Cho hai tËp A, B  X vµ A  B =  khi ®ã N(A B) = N(A) + N(B) 2.2. Nguyªn lý nh©n 2.2.1 Nguyªn lý: Gi¶ sö mét nhiÖm vô T nµo ®ã ®•îc t¸ch ra thµnh k viÖc T1, T2, , Tk. NÕu viÖc Ti cã thÓ lµm b»ng ni c¸ch sau khi c¸c viÖc T1, T2, Ti-1 ®· ®•îc lµm, khi ®ã cã n1.n2 nk c¸ch thi hµnh nhiÖm vô ®· cho. 2.2.2. VÝ dô: 2.2.2.1. Ng•êi ta cã thÓ ghi nh·n cho nh÷ng chiÕc ghÕ trong mét gi¶ng ®•êng b»ng mét ch÷ c¸i vµ mét sè nguyªn d•¬ng kh«ng v•ît qu¸ 100. B»ng c¸ch nh• vËy, nhiÒu nhÊt cã bao nhiªu chiÕc ghÕ cã thÓ ®•îc ghi nh·n kh¸c nhau? Thñ tôc ghi nh·n cho mét chiÕc ghÕ gåm hai viÖc, g¸n mét trong 26 ch÷ c¸i vµ sau ®ã g¸n mét trong 100 sè nguyªn d•¬ng. Quy t¾c nh©n chØ ra r»ng cã 26.100=2600 c¸ch kh¸c nhau ®Ó g¸n nh·n cho mét chiÕc ghÕ. Nh• vËy nhiÒu nhÊt ta cã thÓ g¸n nh·n cho 2600 chiÕc ghÕ. 2.2.2.2. Cã bao nhiªu x©u nhÞ ph©n cã ®é dµi n. Mçi mét trong n bit cña x©u nhÞ ph©n cã thÓ chän b»ng hai c¸ch v× mçi bit hoÆc b»ng 0 hoÆc b»ng 1. Bëi vËy theo quy t¾c nh©n cã tæng céng 2n x©u nhÞ ph©n kh¸c nhau cã ®é dµi b»ng n. 2.2.2.3. Cã thÓ t¹o ®•îc bao nhiªu ¸nh x¹ tõ tËp A cã m phÇn tö vµo tËp B cã n phÇn tö? 9
  10. Theo ®Þnh nghÜa, mét ¸nh x¹ x¸c ®Þnh trªn A cã gi¸ trÞ trªn B lµ mét phÐp t•¬ng øng mçi phÇn tö cña A víi mét phÇn tö nµo ®ã cña B. Râ rµng sau khi ®· chän ®•îc ¶nh cña i - 1 phÇn tö ®Çu, ®Ó chän ¶nh cña phÇn tö thø i cña A ta cã n c¸ch. V× vËy theo quy t¾c nh©n, ta cã n.n n =nm ¸nh x¹ x¸c ®Þnh trªn A nhËn gi¸ trÞ trªn B. 2.2.2.4. Cã bao nhiªu ®¬n ¸nh x¸c ®Þnh trªn tËp A cã m phÇn tö vµ nhËn gi¸ trÞ trªn tËp B cã n phÇn tö? NÕu m > n th× víi mäi ¸nh x¹, Ýt nhÊt cã hai phÇn tö cña A cã cïng mét ¶nh, ®iÒu ®ã cã nghÜa lµ kh«ng cã ®¬n ¸nh tõ A ®Õn B. B©y giê gi¶ sö m n vµ gäi c¸c phÇn tö cña A lµ a1,a2, ,am. Râ rµng cã n c¸ch chän ¶nh cho phÇn tö a1. V× ¸nh x¹ lµ ®¬n ¸nh nªn ¶nh cña phÇn tö a2 ph¶i kh¸c ¶nh cña a1 nªn chØ cã n - 1 c¸ch chän ¶nh cho phÇn tö a2. Nãi chung, ®Ó chän ¶nh cña ak ta cã n - k + 1 c¸ch. Theo quy t¾c nh©n, ta cã n! n(n 1)(n 2) (n m + 1) = ®¬n ¸nh tõ tËp A ®Õn tËp B. (n m)! 2.2.2.5. Gi¸ trÞ cña biÕn k b»ng bao nhiªu sau khi ch•¬ng tr×nh sau ®•îc thùc hiÖn? m := 0 for i1 := 1 to n1 for i2 := 1 to n2 for ik := 1 to nk k := k+1 Gi¸ trÞ khëi t¹o cña k b»ng 0. Ta cã k vßng lÆp ®•îc lång nhau. Gäi Ti lµ viÖc thi hµnh vßng lÆp thø i. Khi ®ã sè lÇn ®i qua vßng lÆp b»ng sè c¸ch lµm c¸c viÖc T1, T2, , Tk. Sè c¸ch thùc hiÖn viÖc Tj lµ nj (j=1, 2, , k), v× vßng lÆp thø j ®•îc duyÖt víi mçi gi¸ trÞ nguyªn ij n»m gi÷a 1 vµ nj. Theo quy t¾c nh©n vßng lÆp lång nhau nµy ®•îc duyÖt qua n1.n2 nk lÇn. V× vËy gi¸ trÞ cuèi cïng cña k lµ n1.n2 nk. Tãm l¹i: Nguyªn lý nh©n th•êng ®•îc ph¸t biÓu b»ng ng«n ng÷ tËp hîp nh• sau. NÕu A1, A2, , Ak lµ c¸c tËp h÷u h¹n, khi ®ã sè phÇn tö cña tÝch Descartes 10
  11. cña c¸c tËp nµy b»ng tÝch cña sè c¸c phÇn tö cña mäi tËp thµnh phÇn. Ta biÕt r»ng viÖc chän mét phÇn tö cña tÝch Descartes A1 x A2 x x Ak ®•îc tiÕn hµnh b»ng c¸ch chän lÇn l•ît mét phÇn tö cña A1, mét phÇn tö cña A2, , mét phÇn tö cña Ak. Theo quy t¾c nh©n ta cã: |A1 x A2 x x Ak| = |A1|.|A2| |Ak|. Tæng qu¸t: N(A.B) = N(A).N(B) 2.3. Nguyªn lý bï trõ: Khi hai c«ng viÖc cã thÓ ®•îc lµm ®ång thêi, ta kh«ng thÓ dïng quy t¾c céng ®Ó tÝnh sè c¸ch thùc hiÖn nhiÖm vô gåm c¶ hai viÖc. §Ó tÝnh ®óng sè c¸ch thùc hiÖn nhiÖm vô nµy ta céng sè c¸ch lµm mçi mét trong hai viÖc råi trõ ®i sè c¸ch lµm ®ång thêi c¶ hai viÖc. Ta cã thÓ ph¸t biÓu nguyªn lý ®Õm nµy b»ng ng«n ng÷ tËp hîp. Cho A1, A2 lµ hai tËp h÷u h¹n, khi ®ã |A1  A2| = |A1| + |A2| |A1  A2|. Tõ ®ã víi ba tËp hîp h÷u h¹n A1, A2, A3, ta cã: |A1  A2  A3| = |A1| + |A2| + |A3| |A1  A2| |A2  A3| |A3  A1| + |A1  A2  A3| vµ b»ng quy n¹p, víi k tËp h÷u h¹n A1, A2, , Ak ta cã: k-1 | A1  A2   Ak| = N1 N2 + N3 + ( 1) Nk, Trong ®ã Nm (1 m k) lµ tæng phÇn tö cña tÊt c¶ c¸c giao m tËp lÊy tõ k tËp ®· cho, nghÜa lµ: Nm = | A  A   A |  i1 i2 im 1 i1 i2 im k B©y giê ta ®ång nhÊt tËp Am (1 m k) víi tÝnh chÊt Am cho trªn tËp vò trô h÷u h¹n U nµo ®ã vµ ®Õm xem cã bao nhiªu phÇn tö cña U sao cho kh«ng tháa m·n bÊt kú mét tÝnh chÊt Am nµo. Gäi N lµ sè cÇn ®Õm, N lµ sè phÇn tö cña U. Ta cã: k N = N | A1  A2   Ak| = N N1 + N2 + ( 1) Nk trong ®ã Nm lµ tæng c¸c phÇn tö cña U tháa m·n m tÝnh chÊt lÊy tõ k tÝnh chÊt ®· cho. C«ng thøc nµy ®•îc gäi lµ nguyªn lý bï trõ. Nã cho phÐp tÝnh N qua c¸c Nm trong tr•êng hîp c¸c sè nµy dÔ tÝnh to¸n h¬n. VÝ dô: Cã n l¸ th• vµ n phong b× ghi s½n ®Þa chØ. Bá ngÉu nhiªn c¸c l¸ th• vµo c¸c phong b×. Hái x¸c suÊt ®Ó x¶y ra kh«ng mét l¸ th• nµo ®óng ®Þa chØ. 11
  12. Mçi phong b× cã n c¸ch bá th• vµo, nªn cã tÊt c¶ n! c¸ch bá th•. VÊn ®Ò cßn l¹i lµ ®Õm sè c¸ch bá th• sao cho kh«ng l¸ th• nµo ®óng ®Þa chØ. Gäi U lµ tËp hîp c¸c c¸ch bá th• vµ Am lµ tÝnh chÊt l¸ th• thø m bá ®óng ®Þa chØ. Khi ®ã theo c«ng thøc vÒ nguyªn lý bï trõ ta cã: n N = n! N1 + N2 + ( 1) Nn, trong ®ã Nm (1 m n) lµ sè tÊt c¶ c¸c c¸ch bá th• sao cho cã m l¸ th• ®óng ®Þa chØ. NhËn xÐt r»ng, Nm lµ tæng theo mäi c¸ch lÊy m l¸ th• tõ n l¸, víi mçi c¸ch lÊy m l¸ th•, cã (n-m)! c¸ch bá ®Ó m l¸ th• nµy ®óng ®Þa chØ, ta nhËn ®•îc: m n! 1 1 n 1 Nm = C (n - m)! = vµ N = n!(1 + + ( 1) ), n k! 1! 2! n! n! trong ®ã C m = lµ tæ hîp chËp m cña tËp n phÇn tö (sè c¸ch chän m n m!(n m)! 1 1 ®èi t•îng trong n ®èi t•îng ®•îc cho). Tõ ®ã x¸c suÊt cÇn t×m lµ: 1 + 1! 2! 1 + ( 1)n . Mét ®iÒu lý thó lµ x¸c suÊt nµy dÇn ®Õn e -1 (nghÜa lµ cßn > 1 ) khi n! 3 n kh¸ lín. Sè N trong bµi to¸n nµy ®•îc gäi lµ sè mÊt thø tù vµ ®•îc ký hiÖu lµ Dn. D•íi ®©y lµ mét vµi gi¸ trÞ cña Dn, cho ta thÊy Dn t¨ng nhanh nh• thÕ nµo so víi n: n 2 3 4 5 6 7 8 9 10 11 Dn 1 2 9 44 265 1854 14833 133496 1334961 14684570 2.4. Nguyªn lý Dirichlet 2.4.1. Më ®Çu: Gi¶ sö cã mét ®µn chim bå c©u bay vµo chuång. NÕu sè chim nhiÒu h¬n sè ng¨n chuång th× Ýt nhÊt trong mét ng¨n cã nhiÒu h¬n mét con chim. Nguyªn lý nµy dÜ nhiªn lµ cã thÓ ¸p dông cho c¸c ®èi t•îng kh«ng ph¶i lµ chim bå c©u vµ chuång chim. MÖnh ®Ò (Nguyªn lý): NÕu cã k +1 (hoÆc nhiÒu h¬n) ®å vËt ®•îc ®Æt vµo trong k hép th× tån t¹i mét hép cã Ýt nhÊt hai ®å vËt. Chøng minh: Gi¶ sö kh«ng cã hép nµo trong k hép chøa nhiÒu h¬n mét ®å vËt. Khi ®ã tæng sè vËt ®•îc chøa trong c¸c hép nhiÒu nhÊt lµ b»ng k. §iÒu nµy tr¸i gi¶ thiÕt lµ cã Ýt nhÊt k + 1 vËt. 12
  13. Nguyªn lý nµy th•êng ®•îc gäi lµ nguyªn lý Dirichlet, mang tªn nhµ to¸n häc ng•êi §øc ë thÕ kû 19. ¤ng th•êng xuyªn sö dông nguyªn lý nµy trong c«ng viÖc cña m×nh. 2.4.2. VÝ dô: 1) Trong bÊt kú mét nhãm 367 ng•êi thÕ nµo còng cã Ýt nhÊt hai ng•êi cã ngµy sinh nhËt gièng nhau bëi v× chØ cã tÊt c¶ 366 ngµy sinh nhËt kh¸c nhau. 2) Trong kú thi häc sinh giái, ®iÓm bµi thi ®•îc ®¸nh gi¸ bëi mét sè nguyªn trong kho¶ng tõ 0 ®Õn 100. Hái r»ng Ýt nhÊt cã bao nhiªu häc sinh dù thi ®Ó cho ch¾c ch¾n t×m ®•îc hai häc sinh cã kÕt qu¶ thi nh• nhau? Theo nguyªn lý Dirichlet, sè häc sinh cÇn t×m lµ 102, v× ta cã 101 kÕt qu¶ ®iÓm thi kh¸c nhau. 3) Trong sè nh÷ng ng•êi cã mÆt trªn tr¸i ®Êt, ph¶i t×m ®•îc hai ng•êi cã hµm r¨ng gièng nhau. NÕu xem mçi hµm r¨ng gåm 32 c¸i nh• lµ mét x©u nhÞ ph©n cã chiÒu dµi 32, trong ®ã r¨ng cßn øng víi bit 1 vµ r¨ng mÊt øng víi bit 0, th× cã tÊt c¶ 232 = 4.294.967.296 hµm r¨ng kh¸c nhau. Trong khi ®ã sè ng•êi trªn hµnh tinh nµy lµ v•ît qu¸ 5 tØ, nªn theo nguyªn lý Dirichlet ta cã ®iÒu cÇn t×m. 2.4.3. Nguyªn lý Dirichlet tæng qu¸t: MÖnh ®Ò: NÕu cã N ®å vËt ®•îc ®Æt vµo trong k hép th× sÏ tån t¹i mét hép N N chøa kh«ng Ýt h¬n ®å vËt.(hay tån t¹i hép cã Ýt nhÊt ®å vËt) k k (ë ®©y, [x] ®ã lµ sè nguyªn nhá nhÊt cã gi¸ trÞ lín h¬n hoÆc b»ng x. Kh¸i niÖm nµy ®èi ngÉu víi [x] gi¸ trÞ cña hµm sµn hay hµm phÇn nguyªn t¹i x lµ sè nguyªn lín nhÊt cã gi¸ trÞ nhá h¬n hoÆc b»ng x.) N Chøng minh: Gi¶ sö mäi hép ®Òu chøa Ýt h¬n vËt. Khi ®ã tæng sè ®å k N vËt tèi ®a lµ k. ®å vËt k §iÒu nµy m©u thuÈn víi gi¶ thiÕt lµ cã N ®å vËt cÇn xÕp. VËy ta cã ®iÒu ph¶i chøng minh VÝ dô: 1. Chøng minh r»ng trong 100 ng•êi, cã Ýt nhÊt 9 ng•êi sinh cïng mét th¸ng. 13
  14. XÕp nh÷ng ng•êi sinh cïng th¸ng vµo mét nhãm. Cã 12 th¸ng tÊt c¶. VËy theo nguyªn lý Dirichlet, tån t¹i mét nhãm cã Ýt nhÊt ]100/12[= 9 ng•êi. 2. Cã n¨m lo¹i häc bæng kh¸c nhau. Hái r»ng ph¶i cã Ýt nhÊt bao nhiªu sinh viªn ®Ó ch¾c ch¾n r»ng cã Ýt ra lµ 6 ng•êi cïng nhËn häc bæng nh• nhau. Gäi N lµ sè sinh viªn, khi ®ã ]N/5[ = 6 khi vµ chØ khi 5 < N/5 6 hay 25 < N 30. VËy sè N cÇn t×m lµ 26. 3. Sè m· vïng cÇn thiÕt nhá nhÊt ph¶i lµ bao nhiªu ®Ó ®¶m b¶o 25 triÖu m¸y ®iÖn tho¹i trong n•íc cã sè ®iÖn tho¹i kh¸c nhau, mçi sè cã 9 ch÷ sè (gi¶ sö sè ®iÖn tho¹i cã d¹ng 0XX - 8XXXXX víi X nhËn c¸c gi¸ trÞ tõ 0 ®Õn 9). Cã 107 = 10.000.000 sè ®iÖn tho¹i kh¸c nhau cã d¹ng 0XX - 8XXXXX. V× vËy theo nguyªn lý Dirichlet tæng qu¸t, trong sè 25 triÖu m¸y ®iÖn tho¹i Ýt nhÊt cã ]25.000.000/10.000.000[ = 3 cã cïng mét sè. §Ó ®¶m b¶o mçi m¸y cã mét sè cÇn cã Ýt nhÊt 3 m· vïng. 2.4.4. Mét sè øng dông cña nguyªn lý Dirichlet. L•u ý: Trong nhiÒu øng dông cña nguyªn lý Dirichlet, kh¸i niÖm ®å vËt vµ hép cÇn ph¶i ®•îc lùa chän mét c¸ch kh«n khÐo. VÝ dô 1. Trong mét phßng häp cã n ng•êi, bao giê còng t×m ®•îc 2 ng•êi cã sè ng•êi quen trong sè nh÷ng ng•êi dù häp lµ nh• nhau. Sè ng•êi quen cña mçi ng•êi trong phßng häp nhËn c¸c gi¸ trÞ tõ 0 ®Õn n 1. Râ rµng trong phßng kh«ng thÓ ®ång thêi cã ng•êi cã sè ng•êi quen lµ 0 (tøc lµ kh«ng quen ai) vµ cã ng•êi cã sè ng•êi quen lµ n 1 (tøc lµ quen tÊt c¶). V× vËy theo sè l•îng ng•êi quen, ta chØ cã thÓ ph©n n ng•êi ra thµnh n 1 nhãm. VËy theo nguyªn lý Dirichlet tån tai mét nhãm cã Ýt nhÊt 2 ng•êi, tøc lµ lu«n t×m ®•îc Ýt nhÊt 2 ng•êi cã sè ng•êi quen lµ nh• nhau. VÝ dô 2. Trong mét th¸ng gåm 30 ngµy, mét ®éi bãng chuyÒn thi ®Êu mçi ngµy Ýt nhÊt 1 trËn nh•ng ch¬i kh«ng qu¸ 45 trËn. Chøng minh r»ng t×m ®•îc mét giai ®o¹n gåm mét sè ngµy liªn tôc nµo ®ã trong th¸ng sao cho trong giai ®o¹n ®ã ®éi ch¬i ®óng 14 trËn. Gäi aj lµ sè trËn mµ ®éi ®· ch¬i tõ ngµy ®Çu th¸ng ®Õn hÕt ngµy j. Khi ®ã 1 a1 < a2 < < a30 < 45 15 a1+14 < a2+14 < < a30+14 < 59. S¸u m•¬i sè nguyªn a1, a2, , a30, a1+ 14, a2 + 14, , a30+14 n»m gi÷a 1 vµ 59. Do ®ã theo nguyªn lý Dirichlet cã Ýt nhÊt 2 trong 60 sè nµy b»ng nhau. V× vËy 14
  15. tån t¹i i vµ j sao cho ai = aj + 14 (j < i). §iÒu nµy cã nghÜa lµ tõ ngµy j + 1 ®Õn hÕt ngµy i ®éi ®· ch¬i ®óng 14 trËn. VÝ dô 3. Chøng tá r»ng trong n + 1 sè nguyªn d•¬ng kh«ng v•ît qu¸ 2n, tån t¹i Ýt nhÊt mét sè chia hÕt cho sè kh¸c. k j Ta viÕt mçi sè nguyªn a1, a2, , an+1 d•íi d¹ng aj = 2 qj trong ®ã kj lµ sè nguyªn kh«ng ©m cßn qj lµ sè d•¬ng lÎ nhá h¬n 2n. V× chØ cã n sè nguyªn d•¬ng lÎ nhá h¬n 2n nªn theo nguyªn lý Dirichlet tån t¹i i vµ j sao cho qi = qj = q. Khi k k j ®ã ai= 2 i q vµ aj = 2 q. V× vËy, nÕu ki kj th× aj chia hÕt cho ai cßn trong tr•êng hîp ng•îc l¹i ta cã ai chia hÕt cho aj. VÝ dô cuèi cïng tr×nh bµy c¸ch ¸p dông nguyªn lý Dirichlet vµo lý thuyÕt tæ hîp mµ vÉn quen gäi lµ lý thuyÕt Ramsey, tªn cña nhµ to¸n häc ng•êi Anh. Nãi chung, lý thuyÕt Ramsey gi¶i quyÕt nh÷ng bµi to¸n ph©n chia c¸c tËp con cña mét tËp c¸c phÇn tö. VÝ dô 4. Gi¶ sö trong mét nhãm 6 ng•êi mçi cÆp hai hoÆc lµ b¹n hoÆc lµ thï. Chøng tá r»ng trong nhãm cã ba ng•êi lµ b¹n lÉn nhau hoÆc cã ba ng•êi lµ kÎ thï lÉn nhau. Gäi A lµ mét trong 6 ng•êi. Trong sè 5 ng•êi cña nhãm hoÆc lµ cã Ýt nhÊt ba ng•êi lµ b¹n cña A hoÆc cã Ýt nhÊt ba ng•êi lµ kÎ thï cña A, ®iÒu nµy suy ra tõ nguyªn lý Dirichlet tæng qu¸t, v× ]5/2[ = 3. Trong tr•êng hîp ®Çu ta gäi B, C, D lµ b¹n cña A. nÕu trong ba ng•êi nµy cã hai ng•êi lµ b¹n th× hä cïng víi A lËp thµnh mét bé ba ng•êi b¹n lÉn nhau, ng•îc l¹i, tøc lµ nÕu trong ba ng•êi B, C, D kh«ng cã ai lµ b¹n ai c¶ th× chøng tá hä lµ bé ba ng•êi thï lÉn nhau. T•¬ng tù cã thÓ chøng minh trong tr•êng hîp cã Ýt nhÊt ba ng•êi lµ kÎ thï cña A. 2.5. Bµi tËp 2.5.1. Trong tæng sè 2504 sinh viªn cña mét khoa c«ng nghÖ th«ng tin, cã 1876 theo häc m«n ng«n ng÷ lËp tr×nh Pascal, 999 häc m«n ng«n ng÷ Fortran vµ 345 häc ng«n ng÷ C. Ngoµi ra cßn biÕt 876 sinh viªn häc c¶ Pascal vµ Fortran, 232 häc c¶ Fortran vµ C, 290 häc c¶ Pascal vµ C. NÕu 189 sinh viªn häc c¶ 3 m«n Pascal, Fortran vµ C th× trong tr•êng hîp ®ã cã bao nhiªu sinh viªn kh«ng häc m«n nµo trong 3 m«n ng«n ng÷ lËp tr×nh kÓ trªn. 2.5.2. Mét cuéc häp gåm 12 ng•êi tham dù ®Ó bµn vÒ 3 vÊn ®Ò. Cã 8 ng•êi ph¸t biÓu vÒ vÊn ®Ò I, 5 ng•êi ph¸t biÓu vÒ vÊn ®Ò II vµ 7 ng•êi ph¸t biÓu vÒ vÊn 15
  16. ®Ò III. Ngoµi ra, cã ®óng 1 ng•êi kh«ng ph¸t biÓu vÊn ®Ò nµo. Hái nhiÒu l¾m lµ cã bao nhiªu ng•êi ph¸t biÓu c¶ 3 vÊn ®Ò. 2.5.3. Trong tËp sè nguyªn {1, 2, , 100} cã bao nhiªu sè kh«ng chia hÕt cho bÊt kú sè nµo trong c¸c sè 3, 4, 7 2.5.4. Cã bao nhiªu a. X©u cã ®é dµi 4 b. X©u cã ®é dµi 4 vµ kh«ng chøa ch÷ x 2.5.5. Cã bao nhiªu x©u gåm 3 ch÷ sè thËp ph©n? a. Kh«ng chøa cïng mét ch÷ sè 3 lÇn b. B¾t ®Çu b»ng ch÷ sè lÎ c. Cã ®óng hai ch÷ sè 4 2.5.6. Cã bao nhiªu x©u nhÞ ph©n ®é dµi 10 hoÆc b¾t ®Çu b»ng 000 hoÆc kÕt thóc b»ng 111 2.5.7. Cã bao nhiªu sè nguyªn kh«ng lín h¬n 1000 chia hÕt cho 7 hoÆc 11 2.5.8. Trong sè c¸c sè nguyªn d•¬ng cã 3 ch÷ sè, cã bao nhiªu sè: a. Chia hÕt cho 7 e. Kh«ng chia hÕt cho 4 b. LÎ f. Chia hÕt cho 3 hoÆc 4 c. Cã 3 ch÷ sè ®«I mét kh¸c nhau g. Kh«ng chia hÕt cho 3 hoÆc cho 4 d. Chia hÕt cho 3 vµ cho 4 h. Chia hÕt cho 3 nh•ng kh«ng chia hÕt cho 4 2.5.9. Cã bao nhiªu x©u nhÞ ph©n ®é dµi 7 chøa mét sè ch½n c¸c bit 0 2.5.10. T×m hÖ sè cña x5y8 trong khai triÓn (x + y)13 2.5.11. Cã bao nhiªu x©u kh¸c nhau cã thÓ lËp ®•îc tõ c¸c ch÷ c¸i trong tõ ACCESS, yªu cÇu ph¶i dïng tÊt c¶ c¸c ch÷? 2.5.12. Mét gi¸o s• cÊt bé s•u tËp gåm 40 sè b¸o to¸n häc vµo 4 chiÕc ng¨n tñ, mçi ng¨n ®ùng 10 sè. Cã bao nhiªu c¸ch cã thÓ cÊt c¸c tê b¸o vµo c¸c ng¨n nÕu: 1) Mçi ng¨n ®•îc ®¸nh sè sao cho cã thÓ ph©n biÖt ®•îc; 2) C¸c ng¨n lµ gièng hÖt nhau? 16
  17. 3. Bµi to¸n tån t¹i vµ ph•¬ng ph¸p gi¶i Khi nghiªn cøu vÒ bµi to¸n ®Õm, c«ng viÖc chñ yÕu cña chóng ta lµ ®Õm sè cÊu h×nh tho¶ ®iÒu kiÖn bµi to¸n ®Æt ra, vµ c¸c bµi to¸n ®ã sù tån t¹i cña c¸c cÊu h×nh lµ hiÓn nhiªn. Tuy nhiªn trong rÊt nhiÒu bµi to¸n viÖc chØ ra sù tån t¹i cña mét cÊu h×nh lµ rÊt khã kh¨n. ViÖc chØ ra cÊu h×nh tho¶ ®iÒu kiÖn cña bµi to¸n th× tr•íc hÕt cÇn ph¶i x¸c ®Þnh xem cÊu h×nh ®ã cã tån t¹i hay kh«ng. D•íi ®©y ta sö dông mét sè ph•¬ng ph¸p ®Ó gi¶i quyÕt bµi to¸n 3.1. Ph•¬ng ph¸p ph¶n chøng VÝ dô: CÇn t×m mét c¸ch kÕt nèi 15 m¸y tÝnh víi nhau sao cho mçi m¸y ®•îc kÕt nèi víi ®óng 5 m¸y kh¸c. Ta chøng minh kh«ng cã c¸ch nµo kÕt nèi ®•îc Gi¶ sö tån t¹i mét c¸ch nèi tho¶ yªu cÇu 15*5 Sè ®•êng nèi: Z m©u thuÉn 2 VËy kh«ng t×m ®•îc c¸ch nèi nµo sao cho mçi m¸y kÕt nèi ®•îc víi ®óng 5 m¸y. 3.2. Ph•¬ng ph¸p sö dông nguyªn lý Dirichlet * Nguyªn Lý: Bá n +1 ®å vËt vµo trong n c¸i lä tån t¹i mét hép chøa nhiÒu h¬n 1 ®å vËt * Nguyªn lý tæng qu¸t: Bá n.k + 1 ®å vËt vµo n hép tån t¹i mét hép chøa nhiÒu h¬n k ®å vËt. VÝ dô 1: Mét líp häc cã 45 häc sinh. Chia líp ra lµm 4 tæ. Chøng minh lu«n tån t¹i mét tæ cã Ýt nhÊt 12 häc sinh. Gi¶i: ThËt vËy, líp häc cã 45 häc sinh, nÕu chia ®Òu ra c¸c tæ th× mçi tæ sÏ cã 11 häc sinh vµ d• 1 häc sinh. Häc sinh nµy sÏ ®•îc sÕp vµo 1 trong 4 tæ, khi ®ã nÕu ®•îc sÕp vµo tæ nµo th× tæ ®ã sÏ cã 12 häc sinh. VËy cã ®iÒu ph¶i chøng minh VÝ dô 2: LÊy n +1 sè nguyªn tuú ý. Chøng minh r»ng t×m ®•îc hai sè cã hiÖu cña chóng chia hÕt cho n. Gi¶i: gäi c¸c sè lµ: x1, x2, , xn+1 xi ai(mod n) 0 ai n 1 theo nguyªn lý Dirichlet: i, j : ai a j xi x j  0(modn) 3.3. Mét sè bµi to¸n 17
  18. Bài toán 1) Nèi 6 ®iÓm víi nhau tõng cÆp thµnh c¸c ®o¹n th¼ng t« mµu xanh hoÆc ®á. CMR t×m ®•îc mét tam gi¸c cã 3 c¹nh cïng mµu. Ta lÊy mét ®iÓm tuú ý (gi¶ sö A) A KÎ 5 ®o¹n th¼ng tõ A ®Õn 5 ®iÓm cßn l¹i vµ ®•îc t« mµu xanh hoÆc ®á B Theo Dirichlet: cã Ýt nhÊt 3 ®o¹n th¼ng cïng mµu, gi¶ sö lµ AB, AC, AD. C D NÕu mét trong c¸c ®o¹n th¼ng BC, CD, BD mµu xanh th× ta ®•îc tam gi¸c t•¬ng øng ®Ønh A toµn xanh ng•îc l¹i, ta ®•îc tam gi¸c BCD ®á Bài toán 2) Trong mét phßng häp bao giê còng t×m ®•îc hai ng•êi cã sè ng•êi quen trong sè nh÷ng ng•êi dù häp lµ b»ng nhau. Gi¶i: Gäi sè ng•êi dù häp lµ n sè ng•êi quen cña mét ng•êi ni nµo ®ã ={0, n-1}. Ta thÊy: mét ng•êi kh«ng thÓ ®ång thêi cã sè ng•êi quen lµ 0 hoÆc n -1 ph©n sè ng•êi quen trong phßng ra thµnh n -1 nhãm => VËy cã n ng•êi, ph©n thµnh n -1 nhãm ph¶i cã Ýt nhÊt hai ng•êi cã cïng sè ng•êi quen. Bài toán 3) Chøng minh r»ng kh«ng thÓ nèi 31 m¸y vi tÝnh thµnh mét m¹ng sao cho mçi m¸y ®•îc nèi víi ®óng 5 m¸y kh¸c Gi¶i: Gi¶ sö ta lu«n t×m ®•îc c¸ch nèi 31 m¸y tÝnh l¹i thµnh m¹ng sao cho mçi m¸y ®•îc nèi víi ®óng 5 m¸y kh¸c. Khi ®ã sè l•îng c¸c d©y nèi lµ 31 5* 75,5 m©u thuÉn (v× sè d©y nèi kh«ng thÓ lÎ) Vëy ®iÒu cÇn chøng minh 2 lµ ®óng. 3.4. Bµi tËp n k n 1 3.4.1. Chøng minh r»ng kCn n2 k 1 3.4.2. Chøng minh r»ng víi m, n, r lµ c¸c sè nguyªn kh«ng ©m, vµ r kh«ng v•ît qu¸ m, n ta r r k r k cã: Cm n Cn Cm k 0 18
  19. 3.4.3. ChØ ra r»ng cã Ýt nhÊt 4 ng•êi trong sè 25 triÖu ng•êi cã cïng tªn hä viÕt t¾t b»ng 3 ch÷ c¸i sinh cïng ngµy trong n¨m (kh«ng nhÊt thiÕt trong cïng mét n¨m). 3.4.4. Mét tay ®« vËt tham gia thi ®Êu giµnh chøc v« ®Þch trong 75 giê. Mçi giê anh ta cã Ýt nhÊt mét trËn ®Êu, nh•ng toµn bé anh ta cã kh«ng qu¸ 125 trËn. Chøng tá r»ng cã nh÷ng giê liªn tiÕp anh ta ®· ®Êu ®óng 24 trËn. 3.4.5. Cho n lµ sè nguyªn d•¬ng bÊt kú. Chøng minh r»ng lu«n lÊy ra ®•îc tõ n sè ®· cho mét sè sè h¹ng thÝch hîp sao cho tæng cña chóng chia hÕt cho n. 3.4.6. Trong mét cuéc lÊy ý kiÕn vÒ 7 vÊn ®Ò, ng•êi ®•îc hái ghi vµo mét phiÕu tr¶ lêi s½n b»ng c¸ch ®Ó nguyªn hoÆc phñ ®Þnh c¸c c©u tr¶ lêi t•¬ng øng víi 7 vÊn ®Ò ®· nªu. Chøng minh r»ng víi 1153 ng•êi ®•îc hái lu«n t×m ®•îc 10 ng•êi tr¶ lêi gièng hÖt nhau. 3.4.7. Cã 17 nhµ b¸c häc viÕt th• cho nhau trao ®æi 3 vÊn ®Ò. Chøng minh r»ng lu«n t×m ®•îc 3 ng•êi cïng trao ®æi mét vÊn ®Ò. 3.4.8. Trong kú thi kÕt thóc häc phÇn to¸n häc rêi r¹c cã 10 c©u hái. Cã bao nhiªu c¸ch g¸n ®iÓm cho c¸c c©u hái nÕu tæng sè ®iÓm b»ng 100 vµ mçi c©u Ýt nhÊt ®•îc 5 ®iÓm. 3.4.9. Ph•¬ng tr×nh x1 + x2 + x3 + x4 + x5 = 21 cã bao nhiªu nghiÖm nguyªn kh«ng ©m? 3.4.10. Cho n lµ mét sè nguyªn d•¬ng. Chøng tá r»ng trong mäi tËp n sè nguyªn d•¬ng liªn tiÕp cã ®óng mét sè chia hÕt cho n 3.4.11. Trong mét m¹ng m¸y tÝnh, mçi m¸y nèi trùc tiÕp hoÆc kh«ng nèi víi c¸c m¸y kh¸c. ChØ ra r»ng cã Ýt nhÊt hai m¸y mµ sè c¸c m¸y kh¸c nèi víi chóng lµ b»ng nhau. 3.4.12.Trong kh«ng gian cho 9 ®iÓm cã to¹ ®é nguyªn, Chøng tá r»ng bao giê còng cã mét cÆp ®iÓm cã trung ®iÓm nguyªn 3.4.13. Chøng minh r»ng trong 5 sè chän tõ 8 sè nguyªn ®Çu tiªn tån t¹i mét cÆp sè cã tæng b»ng 9. §iÒu kh¼ng ®Þnh nµy cßn ®óng nÕu chän 4 chø kh«ng ph¶i chän 5 3.4.14. Chøng minh r»ng trong 7 sè chän tõ 10 sè nguyªn ®Çu tiªn tån t¹i mét cÆp sè cã tæng b»ng 11. §iÒu kh¼ng ®Þnh nµy cßn ®óng nÕu chän 6 chø kh«ng ph¶i chän 7 19
  20. ch•¬ng 2: c¸c kh¸i niÖm c¬ b¶n cña lý thuyÕt ®å thÞ M· ch•¬ng: Mh12.2 Giới thiệu: Trình bày các kiến thức cơ bản về lý thuyết đồ thị. Cung cấp các kiến thức cơ bản về lý thuyết đồ thị, giúp người học có kiến thức cơ sở để nghiên cứu về đồ thị trong các chương tiếp theo. Mục tiêu: - Trình bày được các khái niệm của đố thị - Xác định được các loai đồ thị, chu trình, đồ thị liên thông. - Nghiêm túc trong học tập, đảm bảo an toàn cho người và trang thiết bị. Nội dung chính: 1. §Þnh nghÜa ®å thÞ §å thÞ lµ mét cÊu tróc rêi r¹c bao gåm c¸c ®Ønh vµ c¸c c¹nh nèi c¸c ®Ønh nµy l¹i víi nhau. §å thÞ G lµ mét cÆp G = (V,E) Trong ®ã V  lµ tËp hîp c¸c ph©n tö nµo ®ã gäi lµ ®Ønh cña ®å thÞ. E: Lµ tËp c¸c cÆp (u,v) nµo ®ã (gäi lµ c¹nh cña ®å thÞ) víi u,v V,(u,v) E (v,u) E vµ coi (u,v) (v,u): + §å thÞ G gäi lµ v« h•íng nÕu  u,v V: (u,v) E (v,u) E + §å thÞ G gäi lµ cã h•íng nÕu  u,v V: (u,v) (v,u) quy •íc: NÕu bµi to¸n chØ nãi ®å thÞ mµ kh«ng nãi râ lµ v« h•íng hay cã h•íng th× ta ngÇm hiÓu lµ ®å thÞ v« h•íng. + §å thÞ G gäi lµ ®¬n ®å thÞ nÕu V = u,v,x,y,z E = (u,x),(u,y),(u,v),(u,z)  2. C¸c thuËt ng÷ c¬ b¶n + §å thÞ G = (V,E) víi ®Ønh v V, e = (u,v) E Khi ®ã: u,v lµ hai ®Ønh ®Çu, cuèi cña c¹nh e e _ c¹nh liªn thuéc u,v + Hai ®Ønh u,v cña ®å thÞ v« h•íng G = (V,E) ®•îc gäi lµ kÒ nhau nÕu (u,v) lµ c¹nh cña ®å thÞ . + BËc cña ®Ønh: BËc cña ®Ønh u V lµ sè c¹nh liªn th•éc víi u kÝ hiÖu deg(u) 20
  21. a b c d j i k h e g f Deg (a) =4 Deg (e) =4 Deg (i) =2 Deg(b) = 3 Deg(f) = 3 Deg(j) = 2 Deg(c) = 5 Deg(g) = 5 Deg(k) = 0 Deg(d) = 3 Deg(h) = 3 * §Þnh lý: Ký hiÖu E lµ sè c¹nh cña ®å thÞ G = (V,E) khi ®ã 2 E d e g(v) v V Chøng minh: TÝnh tæng bËc c¸c ®Ønh cña G th«ng qua c¸c c¹nh: Ta thÊy méi c¹nh e = (u,v) øng víi mét bËc cña v v HÖ qu¶: Sè ®Ønh bËc lÎ cña ®å thÞ v« h•íng lµ sè ch½n. Chøng minh: Gäi O vµ U t•¬ng óng lµ tËp ®Ønh bËc lÎ vµ tËp ®Ønh bËc ch½n cña ®å thÞ Ta cã 2 E deg(v) deg(v) deg(v) v V v O v U Do deg(v) ( tøc lµ tæng sè ®Ønh bËc ch½n) – ch½n deg(v) - ch½n (®pcm) v U v O 3. §•êng ®i, chu tr×nh ®å thÞ liªn th«ng. * Cho ®å thÞ G = (V,E) 3.1. §•êng ®i: Mét ®•êng ®i ®é dµi n tõ u tíi v lµ mét d·y x0, x1, xn sao cho x0 u, xn v (xi, xi 1) E,i 0,n 1 ®Ønh u gäi lµ ®Ønh ®Çu, ®Ønh v gäi lµ ®Ønh cuèi ®•êng ®i trªn gäi lµ ®¬n nÕu kh«ng cã c¹nh nµo lÆp l¹i Vd: Cho ®å thÞ 2 5 1 1 §¸p ¸n: 1 6 +, 1 2 3 4 6 +, 1 3 5 4 +, 1 2 5 4 3 4 3 1 21
  22. T×m ®•êng ®i ®é dµi 3 tõ ®Ønh 1 ®Ønh 4 3.2. chu tr×nh: Lµ mét ®•êng ®i cã ®Ønh ®Çu vµ ®Ønh cuèi trïng nhau. Chu tr×nh ®¬n: lµ mét chu tr×nh mµ ®•êng ®i cña nã kh«ng cã c¹nh nµo lÆp l¹i. Vd: Cho ®å thÞ §¸p ¸n: a b c a. - d e a b e f b - d a e f c b a - a d e f c b a (chu tr×nh) d e f b. T×m ®•êng ®i ®é dµi 3 tõ ®Ønh 1 ®Ønh 4 - d e f c b a d 3.3. §å thÞ liªn th«ng: §å thÞ G lµ liªn th«ng nÕu víi bÊt kú hai ®Ønh u,v V lu«n t×m ®•îc ®•êng ®i tõ u tíi v. Thµnh phÇn liªn th«ng v V: Thµnh phÇn liªn th«ng cña ®å thÞ G chøa v lµ tËp c¸c ®Ønh cña G liªn th«ng víi v (cã ®•êng ®i tíi v) L(v) = V cã ®•êng ®i tõ u v Mét ®å thÞ kh«ng liªn th«ng cã thÓ coi lµ mét sè tæ hîp thµnh phÇn liªn th«ng 3.4. Mét sè d¹ng ®å thÞ 3.4.1. §å thÞ ®Çy ®ñ: Kh¸i niÖm: Mét ®å thÞ ®•îc gäi lµ ®Çy ®ñ (k/h kn) nÕu ®å thÞ cã n ®Ønh, mçi ®Ønh kÒ víi mçi ®Ønh cßn l¹i VÝ dô: K2 K4 K5 K3 3.4.2. §å thÞ vßng (Cn): Kh¸i niÖm: Cn lµ ®å thÞ cã n ®Ønh, n c¹nh liªn th«ng, mçi ®Ønh ®Ò cã bËc hai C3 C4 Cã bao nhiªu ®å thÞ kh¸c nhau cã 9 ®Ønh, mçi ®Ønh chØ cã bËc 2 ? 22
  23. 3.4.3. §å thÞ b¸nh xe (Wn): nhËn ®•îc tõ Cn b»ng c¸ch thªm mét ®Ønh míi kÒ víi tÊt c¶ c¸c ®Ønh cßn l¹i v1 v1 v2 v1 v5 v2 v5 v6 v4 v4 v3 v3 v2 v4 v3 3.4.4. §å thÞ hai phÝa: G = (V,E) lµ ®å thÞ hai phÝa nÕu: X Y V • Cã thÓ t×m ®•îc X, Y V , X Y  u X,(u,v) E v Y • Vµ mäi v Y,(u,v) E u X v1 v2 v1 v2 v3 v3 v4 v5 v6 v4 v5 v6 K3,3 K2,3 3.5. Bµi tËp 3.5.1. Cho ®å thÞ G= nh• h×nh vÏ. X¸c ®Þnh bËc cña tÊt c¶ c¸c ®Ønh cña ®å thÞ ®· cho? A F G B H E C D 3.5.2. Cho ®å thÞ G = . H·y chØ ra ®•êng ®i tõ: a. §Ønh 1 ®Õn ®Ønh 7 vµ ®i qua ®Ønh 9? b. §Ønh 4 ®Õn ®Ønh 2 cã ®é dµi 5 c. §Ønh 6 ®Õn ®Ønh 1 mµ ®i qua ®Ønh 5 vµ ®Ønh 7 vµ cã ®é dµi 10 §•êng ®i ®ã cã ph¶i lµ ®•êng ®i ®¬n kh«ng 23
  24. 3.5.3. Cho c¸c ®å thÞ. Hái ®å thÞ cã liªn th«ng hay kh«ng 1 2 3 A B D C E 7 6 4 X F G1 5 G2 24
  25. Ch•¬ng 3: BiÓu diÔn ®å thÞ Vµ c¸c thuËt to¸n t×m kiÕm Giới thiệu: §Ó l•u tr÷ ®å thÞ trªn m¸y tÝnh vµ thùc hiÖn c¸c thu©t to¸n kh¸c nhau cÇn ph¶i t×m nh÷ng cÊu tróc d÷ liÖu thÝch hîp ®Ó m« t¶ ®å thÞ. ViÖc chän cÊu tróc d÷ liÑu ®Ó biÓu diÔn ®å thÞ cã t¸c ®éng rÊt lín ®Õn hiÖu qu¶ cña thuËt to¸n. D•íi ®©y ta nghiªn cøu mét sè c¸ch tæ chøc ®å thÞ trªn m¸y tÝnh Mục tiêu: - Biễu điễn được đố thị trên máy tính; - Cài đặt được các thuật toán tìm kiếm; - Nghiêm túc trong học tập, đảm bảo an toàn cho người và trang thiết bị. 1. Ma trËn kÒ - ma trËn träng sè XÐt ®¬n ®å thÞ v« h•íng G = (V,E), V = n Ta gäi Ma trËn kÒ cña ®¬n ®å thÞ G lµ mét ma trËn vu«ng A[n.n] Víi c¸c phÇn tö ®•îc x¸c ®Þnh theo quy t¾c nh• sau: Ai, j 0 nÕu (i,j) E víi i, j 1,2, n lµ c¸c ®Ønh cña ®å thÞ Ai, j 1 nÕu (i,j) E 1 2 3 4 5 2 1 0 1 0 1 1 1 1 0 1 1 0 3 A= 2 3 0 1 0 0 0 5 4 1 1 0 1 1 4 5 1 0 0 1 0 NhËn xÐt: + Ma trËn kÒ lµ ma trËn ®èi xøng  i,j: Ai, j= A + Tæng c¸c sè ë dßng i = deg(i) ¦u ®iÓm: KiÓm tra 2 ®Ønh i,j cã kÒ nhau kh«ng chØ cÇn kiÓm tra xem A =1 kh«ng Nh•îc ®iÓm: L·ng phÝ bé nhí. *Ma trËn träng sè 25
  26. §å thÞ cã träng sè lµ ®å thÞ: øng víi mçi c¹nh (u,v) E g¸n 1 gi¸ trÞ C(u,v) nµo ®ã gäi lµ träng sè cña (u,v) C(i, j) nÕu i, j E Ma trËn träng sè An x n, trong ®ã gi¸ trÞ Ai, j =  nÕu i, j E Trong ®ã  ®•îc x¸c ®Þnh tuú theo ®Ò bµi to¸n cô thÓ, th•êng gÆp lµ - , 0, + VÝ dô: Cho ®å thÞ G = . H·y x¸c ®Þnh ma trËn träng sè cña ®å thÞ. A 5 2 5 C 9 1 1 6 10 3 4 D G 2 F 2 E 2. Danh s¸ch c¹nh, Danh s¸ch liªn kÕt 2.1. Danh s¸ch c¹nh: Dïng trong tr•êng hîp ®å thÞ cã Ýt c¹nh, sè c¹nh m <6n, víi n lµ sè ®Ønh Tæ chøc d÷ liÖu: Dïng hai m¶ng mét chiÒu Dau[1 m] Cuoi[1 m] NÕu e=(u,v) Dau[e]=u; Cuoi[e]=v Dau = A C C A C D D A   E Cuoi = B B A D D E B (ThÝch hîp biÓu diÔn ®å thÞ Ýt c¹nh, nh•ng kh«ng thuËn tiÖn kiÓm tra hai C ®Ønh kÒ nhau) H×nh 2. For (e E) If(Dau(e) = u and Cuoi(e)=v ) OR (Dau(e)=v and Cuoi(e)=u) Kenhau=true; 2.2. Danh s¸ch liªn kÕt: Víi mçi ®Ønh u, t¹o ra mét danh s¸ch c¸c ®Ønh kÒ víi u A B C D E 26
  27. VÝ dô danh s¸ch liên kết theo ®å thÞ (h×nh 2) A B C D B A C C D A B D A C E E D 3. T×m kiÕm theo chiÒu réng vµ chiÒu s©u 3.1. T×m kiÕm chiÒu s©u (Depth-First Search) NÕu trong thuËt to¸n trªn, danh s¸ch DS ®•îc tæ chøc theo kiÓu stack (danh s¸ch vµo sau - ra tr•íc LIFO) th× ta cã ph•¬ng ph¸p duyÖt theo chiÒu s©u. Trong ph•¬ng ph¸p nµy mçi lÇn duyÖt mét ®Ønh ta duyÖt ®Õn tËn cïng mçi nh¸nh råi míi chuyÓn sang duyÖt nh¸nh kh¸c. ý t•ëng: Gi¶ sö trong qu¸ tr×nh duyÖt ®ang dõng l¹i ë ®Ønh v - NÕu cã u kÒ víi v vµ u ch•a ®•îc v th¨m th× th¨m u vµ tiÕp tôc nh• vËy víi u u1 - NÕu kh«ng cã ®Ønh nµo kÒ v ch•a u2 ®•îc th¨m th× quay l¹i ®Ønh th¨m tr•íc khi th¨m v u3 u4 u5 u6 u7 Gi¶ sö G = (V, E) lµ mét ®å thÞ v« h•íng. ThuËt to¸n. Void DFS (v) ; // duyÖt theo chiÒu s©u xuÊt ph¸t tõ ®Ønh v Stack S = newStack(); //S = ; S.Push(v) ; // N¹p v vµo ng¨n sÕp While ( S  ) { x=S.Pop(); tham(x); 27
  28. For( u ke(x)) If (!tham(u)) { S.Push(u); } }  Void Main(); // Ch•¬ng tr×nh chÝnh for (v V) { tham [v] := false ; } for (v V) if (! Tham(v)); { DFS(v) ;}  §é phøc t¹p cña thËt to¸n lµ: O(n +m) VÝ dô 1: §å thÞ ®•îc duyÖt theo chiÒu s©u. Thø tù cña c¸c ®Ønh ®•îc duyÖt theo chiÒu s©u 3.2. T×m kiÕm theo chiÒu réng (Breadth-First Search) NÕu trong thuËt to¸n duyÖt ®å thÞ cÊu tróc danh s¸ch ®•îc tæ chøc theo kiÓu hµng ®îi (danh s¸ch vµo tr•íc - ra tr•íc FIFO ) th× ta cã ph•¬ng ph¸p duyÖt theo chiÒu réng. Trong ph•¬ng ph¸p nµy viÖc duyÖt cã tÝnh chÊt lan réng. Mét ®Ønh ®•îc duyÖt xong, ta ®· xÐt duyÖt hÕt tÊt c¶ c¸c ®Ønh kÒ víi nã. §Ønh ®•îc xÐt cµng sím th× sím trë thµnh duyÖt xong. 28
  29. ý t•ëng thuËt to¸n (DuyÖt ®å thÞ theo chiÒu réng): Tõ ®Ønh v ®ang ( th¨m) dõng l¹i, th¨m tÊt c¶ c¸c ®Ønh kÒ víi ®Ønh v Sau ®ã øng víi mçi ®Ønh kÒ víi v lÆp l¹i quy tr×nh t•¬ng tù Tæ chøc d÷ liÖu b»ng hµng ®îi Void BFS (v) ; // duyÖt theo chiÒu réng xuÊt ph¸t tõ ®Ønh v { Queue Q = newQueue(); //Q := ; Push(v,Q) ; // N¹p v vµo cuèi hµng ®îi Q While ( Q  ) { Pop(Q,x); For( u ke(x)) If (!tham(u)) { Push(u,Q); Tham(u); } } } Void main(); // ch•¬ng tr×nh chÝnh { for (v V) tham(v) := false ; for v V do if (! tham (v)) BFS(v) ; } ThuËt to¸n nµy còng cã ®é phøc t¹p lµ: O(n+m) VÝ dô 2: §å thÞ trong VÝ dô 1 ®•îc duyÖt theo chiÒu réng. 29
  30. 4. Mét sè øng dông 4.1. Bµi to¸n t×m ®•êng ®i Gi¶ sö a vµ b lµ hai ®Ønh nµo ®ã cña ®å thÞ v« h•íng G. H·y t×m ®•êng ®i (nÕu cã) tõ ®Ønh a ®Õn ®Ønh b. Theo c¸c ph•¬ng ph¸p duyÖt ®å thÞ, c¸c lêi gäi thñ tôc DFS(a) hoÆc BFS(a) cho phÐp th¨m tÊt c¶ c¸c ®Ønh thuéc cïng thµnh phÇn liªn th«ng víi ®Ønh a. V× vËy, sau khi thùc hiÖn xong thñ tôc nÕu tham(b) = false th× kh«ng cã ®•êng ®i tõ ®Ønh a ®ªn ®Ønh b ng•îc l¹i th× ®Ønh b thuéc cïng m¶ng liªn th«ng víi ®Ønh a, hay nãi mét c¸ch kh¸c, cã ®•êng ®i tõ a ®Õn b. §Ó kh«i phôc ®•êng ®i ta dïng thªm mét biÕn m¶ng Truoc. Thµnh phÇn Truoc [u] ghi l¹i ®Ønh ®Õn tr•íc ®Ønh u trªn ®•êng duyÖt tõ a tíi u. Khi ®ã, trong thñ tôc DFS (v) cÇn söa ®æi c©u lÖnh nh• sau: Void DFS (v) ; // duyÖt theo chiÒu s©u xuÊt ph¸t tõ ®Ønh v Tham (v) ; for (u ke(v) ) if (! Tham(u)) Truoc [u] := v; DFS(u) ;  cßn trong thñ tôc BFS (v) th× cÇn söa c©u lÖnh if lµ: Void BFS (v) ; // duyÖt theo chiÒu réng xuÊt ph¸t tõ ®Ønh v { Queue Q = newQueue(); //Q := ; Push(v,Q) ; // N¹p v vµo cuèi hµng ®îi Q While ( Q  ) { Pop(Q,x); For( u ke(x)) If (!tham(u)) { Push(u,Q); Tr•¬c(u)=z; 30
  31. Tham(u); } } } Chó ý: §•êng ®i t×m ®•îc theo thuËt to¸n duyÖt theo chiÒu réng lµ ®•êng ®i ng¾n nhÊt tõ ®Ønh a ®Õn ®Ønh b. 4.2. Bµi to¸n t×m c¸c m¶ng liªn th«ng Cho ®å thÞ G, h·y t×m sè m¶ng liªn th«ng p cña ®å thÞ nµy vµ x¸c ®Þnh xem mçi m¶ng liªn th«ng bao gåm nh÷ng ®Ønh nµo. Do c¸c thñ tôc DFS(v) hoÆc BFS(v) cho phÐp duyÖt tÊt c¶ c¸c ®Ønh thuéc cïng m¶ng liªn th«ng víi ®Ønh v nªn sè m¶ng liªn th«ng p cña ®å thÞ G chÝnh b»ng sè lÇn gäi ®Õn c¸c thñ tôc nµy trong ch•¬ng tr×nh chÝnh. §Ó ghi nhËn c¸c ®Ønh trong tõng m¶ng liªn th«ng, ta dïng thªm biÕn m¶ng Mang[v] ®Ó ghi chØ sè cña m¶ng liªn th«ng chøa ®Ønh v. ChØ sè nµy t¨ng tõ 1 ®Õn p. Ta dïng biÕn p ®Ó ®Õm sè m¶ng liªn th«ng cña ®å thÞ vµ g¸n chØ sè cho c¸c m¶ng liªn th«ng t×m ®•îc. B¾t ®Çu nã ®•îc khëi t¹o gi¸ trÞ b»ng 0. Thñ tôc Th¨m (v) trong c¸c thñ tôc DFS(v) vµ BFS(v) lµm thªm nhiÖm vô g¸n: Mang [v] := p ; Cßn ch•¬ng tr×nh chÝnh cña thuËt to¸n duyÖt cÇn ®•îc söa l¹i nh• sau: Void main(); // ch•¬ng tr×nh chÝnh { for (v V) tham(v) := false ; P=0; for v V do if (! tham (v)) { P = p+1; BFS(v) ; // hoÆc (DFS) } 31
  32. } Khi ch•¬ng tr×nh kÕt thóc, biÕn p sÏ cho sè m¶ng liªn th«ng cña ®å thÞ cßn c¸c gi¸ trÞ cña biÕn m¶ng Mang[v] , v V cho phÐp liÖt kª tÊt c¶ c¸c ®Ønh trong tõng m¶ng liªn th«ng cña ®å thÞ. 32
  33. 5. Bµi tËp 5.1: H·y vÏ c¸c ®å thÞ v« h•íng ®•îc biÓu diÔn bëi ma trËn kÒ sau: 0 1 3 0 4 1 2 0 1 1 2 3 1 2 1 3 0 2 0 3 0 a) 2 0 4 , b) , c) 3 1 1 0 1 . 0 3 1 1 3 4 0 0 3 0 0 2 1 0 1 0 4 0 1 2 3 5.2: Cho ®å thÞ sau: a b. x y z w v u a. BiÓu diÔn ®å thÞ trªn b»ng ma trËn kÒ, danh s¸ch c¹nh b. LiÖt kª qu¸ tr×nh duyÖt ®å thÞ theo hai thuËt to¸n DFS vµ BFS 33
  34. Ch•¬ng 4: c©y vµ c©y khung cña ®å thÞ M· ch•¬ng: Mh12.4 Mét ®å thÞ liªn th«ng vµ kh«ng cã chu tr×nh ®•îc gäi lµ c©y. 1. C©y vµ c¸c tÝnh chÊt cña c©y Kh¸i niÖm c©y ®•îc Cayley ®•a ra ®Çu tiªn vµo n¨m 1857, khi nhµ to¸n häc Anh tªn lµ Arthur Cayley dïng c©y ®Ó x¸c ®Þnh nh÷ng d¹ng kh¸c nhau cña hîp chÊt ho¸ häc. Tõ ®ã c©y ®· ®•îc dïng ®Ó gi¶i nhiÒu bµi to¸n trong nhiÒu lÜnh vùc kh¸c nhau. C©y rÊt hay ®•îc sö dông trong tin häc. Ch¼ng h¹n, ng•êi ta dïng c©y ®Ó x©y dùng c¸c thuËt to¸n rÊt cã hiÖu qu¶ ®Ó ®Þnh vÞ c¸c phÇn tö trong mét danh s¸ch. C©y còng dïng ®Ó x©y dùng c¸c m¹ng m¸y tÝnh víi chi phÝ rÎ nhÊt cho c¸c ®•êng ®iÖn tho¹i nèi c¸c m¸y ph©n t¸n. C©y còng ®•îc dïng ®Ó t¹o ra c¸c m· cã hiÖu qu¶ ®Ó l•u tr÷ vµ truyÒn d÷ liÖu. Dïng c©y cã thÓ m« h×nh c¸c thñ tôc mµ ®Ó thi hµnh nã cÇn dïng mét d·y c¸c quyÕt ®Þnh. V× vËy c©y ®Æc biÖt cã gi¸ trÞ khi nghiªn cøu c¸c thuËt to¸n s¾p xÕp. 1.1. §Þnh nghÜa: C©y lµ mét ®å thÞ v« h•íng liªn th«ng, kh«ng chøa chu tr×nh vµ cã Ýt nhÊt hai ®Ønh. (§å thÞ G lµ c©y nÕu G liªn th«ng vµ kh«ng chøa chu tr×nh) VÝ dô: §å thÞ sau lµ mét c©y Mét ®å thÞ v« h•íng kh«ng chøa chu tr×nh vµ cã Ýt nhÊt hai ®Ønh gäi lµ mét rõng. Trong mét rõng, mçi thµnh phÇn liªn th«ng lµ mét c©y VÝ dô: Rõng sau cã 4 c©y: i m a d c f g h j l q b e k n 1.2. §Þnh lý: Cho G lµ mét ®å thÞ cã n 2 ®Ønh. C¸c ®iÒu sau lµ t•¬ng ®•¬ng: 34
  35. 1. G lµ mét c©y. 2. G liªn th«ng vµ cã n 1 c¹nh. 3. G kh«ng chøa chu tr×nh vµ cã n 1 c¹nh. 4. G liªn th«ng vµ nÕu bá ®i mét c¹nh bÊt kú th× mÊt tÝnh lªn th«ng (mçi c¹nh lµ cÇu.) 5. Gi÷a hai ®Ønh ph©n biÖt bÊt kú cña G lu«n cã duy nhÊt mét ®•êng ®i ®¬n. 6. G kh«ng chøa chu tr×nh nh•ng khi thªm mét c¹nh míi th× cã ®•îc mét chu tr×nh duy nhÊt. 1.3. C©y khung (c©y bao trïm) G_ lµ ®å thÞ liªn th«ng víi G = (V, E). C©y khung cña ®å thÞ G lµ mét ®å thÞ con T = (V, F). Trong ®ã: F  E sao cho T_ c©y VÝ dô: Cho ®å thÞ sau: Mét sè c©y khung cña ®å thÞ C©y bao trïm cã nhiÒu øng dông trong c¸c bµi to¸n ®iÒu khiÓn giao th«ng, nèi c¸c m¹ng ®iÖn §Þnh lý 1: §å thÞ v« h•íng G cã c©y bao trïm khi vµ chØ khi G liªn th«ng. Chøng minh: : HiÓn nhiªn, v× c©y bao trïm liªn th«ng suy ra G liªn th«ng.  : Chän a lµ mét ®Ønh bÊt kú trong ®å thÞ G. Ký hiÖu d(x) lµ ®é dµi cña ®•êng ®i ng¾n nhÊt nèi ®Ønh a víi ®Ønh x. LÇn l•ît x©y dùng c¸c tËp hîp D0 = {a} 35
  36. Di = {x d(x) = i} víi i 1. §Þnh lý 2: Sè c©y khung cña ®å thÞ v« h•íng n ®Ønh lµ nn-2 VÝ dô: Cho ®å thÞ sau: B D A F C E Mét sè c©y khung: (®•êng kÎ ®Ëm) B D B D A F A F C E C E * ThuËt to¸n t×m c©y khung Sö dông 2 thuËt to¸n DFS, BFS Trong qu¸ tr×nh duyÖt, mçi khi th¨m 1 ®Ønh míi th× thªm c¹nh t•¬ng øng vµo tËp c¹nh cña c©y khung. Gi¶ sö •u tiªn chän theo thø tù t¨ng dÇn. - NÕu DFS(B) - NÕu BFS (B) B D B D A F A F C E C E 36
  37. 2. C©y khung nhá nhÊt Bµi to¸n t×m c©y khung nhá nhÊt cña ®å thÞ lµ mét trong sè nh÷ng bµi to¸n tèi •u trªn ®å thÞ t×m ®•îc øng dông trong nhiÒu lÜnh vùc kh¸c nhau cña ®êi sèng. Trong phÇn nµy ta sÏ cã hai thuËt to¸n c¬ b¶n ®Ó gi¶i bµi to¸n nµy. Tr•íc hÕt, néi dung cña bµi to¸n ®•îc ph¸t biÓu nh• sau. Cho G=(V,E) lµ ®å thÞ v« h•íng liªn th«ng cã träng sè, mçi c¹nh e E cã träng sè C(e) 0. Gi¶ sö T=(VT,ET) lµ c©y khung cña ®å thÞ G (VT=V). Ta gäi ®é dµi C(T) cña c©y khung T lµ tæng träng sè cña c¸c c¹nh cña nã: C(T)= C(e). e ET Bµi to¸n ®Æt ra lµ trong sè tÊt c¶ c¸c c©y khung cña ®å thÞ G, h·y t×m c©y khung cã ®é dµi nhá nhÊt. C©y khung nh• vËy ®•îc gäi lµ c©y khung nhá nhÊt cña ®å thÞ. §Ó gi¶i quyÕt bµi to¸n nµy ta ®i t×m hiÓu mét sè thuËt to¸n sau: 2.1. ThuËt to¸n Kruskal ý t•ëng cña thuËt to¸n: ThuËt to¸n Kruskal ¸p dông cho ®å thÞ cµi ®Æt b»ng danh s¸ch c¹nh. Tr•íc hÕt s¾p xÕp c¸c c¹nh cña ®å thÞ G theo thø tù kh«ng gi¶m cña träng sè. B¾t ®Çu tõ ET=, ë mçi b•íc ta sÏ lÇn l•ît duyÖt trong danh s¸ch c¹nh ®· s¾p xÕp, tõ c¹nh cã ®é dµi nhá ®Õn c¹nh cã ®é dµi lín h¬n, ®Ó t×m ra c¹nh mµ viÖc bæ sung nã vµo tËp ET kh«ng t¹o thµnh chu tr×nh trong tËp nµy. ThuËt to¸n sÏ kÕt thóc khi ta thu ®•îc tËp ET gåm n 1 c¹nh. ThuËt to¸n: B•íc 1: s¾p xÕp c¸c c¹nh cña ®å thÞ theo thø tù träng sè t¨ng dÇn B•íc 2: Thùc hiÖn lÆp - Chän c¹nh cã träng sè nhá nhÊt ch•a xÐt - NÕu c¹nh nµy kh«ng t¹o thµnh chu tr×nh víi c¸c c¹nh ®· chän th× bæ xung c¹nh nµy vµo c©y khung T B•íc 3: LÆp l¹i b•íc 2 cho ®Õn khi |T| = n- 1 VÝ dô 1: Thùc hiÖn thuËt to¸n Kruskal, t×m c©y khung nhá nhÊt cña ®å thÞ 20 sau: v2 v4 33 8 16 v1 18 9 v6 17 4 14 v3 v5 37
  38. B1: S¾p xÕp c¸c c¹nh theo thø tù t¨ng dÇn: v3v5 ;v4v6 ;v5v4 ;v5v6 ;v3v4 ;v3v1;v2v3;v2v4 ;v1v2 B2: LÆp v3v5;v4v6;v4v5;v1v3;v2v3 B3: |T| = 5 = n-1 20 v2 v 33 4 8 16 C©y khung thu ®•îc: v1 18 9 v6 (®•êng kÎ ®Ëm) 17 4 14 v3 v5 NhËn xÐt: - ViÖc kiÓm tra c¹nh ®ang xÐt cã t¹o thµnh chu tr×nh hay kh«ng lµ t•¬ng ®èi khã kh¨n - Trong qu¸ tr×nh x©y dùng c©y khung T cã thÓ kh«ng liªn th«ng. 2.2. ThuËt to¸n Prim ThuËt to¸n Kruskal lµm viÖc kÐm hiÖu qu¶ ®èi víi nh÷ng ®å thÞ dµy (®å thÞ cã sè c¹nh m n(n 1)/2). Trong tr•êng hîp ®ã, thuËt to¸n Prim tá ra hiÖu qu¶ h¬n. ThuËt to¸n Prim cßn ®•îc gäi lµ ph•¬ng ph¸p l©n cËn gÇn nhÊt. ThuËt to¸n: B•íc 1: XuÊt ph¸t tõ mét ®Ønh bÊt kú B•íc 2: Thùc hiÖn lÆp - T×m ®Ønh ch•a chän cã kho¶ng c¸ch nhá nhÊt víi tËp c¸c ®Ønh ®· chän - Gi¶ sö e lµ c¹nh t•¬ng øng víi kho¶ng c¸ch nhá nhÊt - Bæ sung ®Ønh v vµo tËp c¸c ®Ønh ®· chän - Bæ sung c¹nh e vµo c©y khung T B•íc 3: Tíi khi |T| = n – 1 Void Prim(v); { VT = v ; T = ; For ( u V \ VT) { d[v] = C[v,u]; truoc[u]=v; } 38
  39. // thùc hiÖn b•íc lÆp Stop = false; While (!stop ) { T×m k V \ VT sao cho D[k] = min( d[u]); VT = VT + k; T = T + e ; //víi c¹nh e = (k,truoc[k]) If(| VT | = n ) Stop = true; Else For( u V \ VT) If(d[u] > C[u,k]); { d[u] = C[u,k]; truoc[u]=k; } } } VÝ dô: T×m c©y khung nhá nhÊt b»ng thuËt to¸n Prim cña ®å thÞ gåm c¸c ®Ønh A, B, C, D, E, F, H, I ®•îc cho bëi ma trËn träng sè sau A B C D E F H I A 15 16 19 23 20 32 18 B 15 33 13 34 19 20 12 C 16 33 13 29 21 20 19 D 19 13 13 22 30 21 11 E 23 34 29 22 34 23 21 F 20 19 21 30 34 17 18 H 32 20 20 21 23 17 14 I 18 12 19 11 21 18 14 B•íc lÆp A B C D R F H I VT t Khëi t¹o [A,15] [A,16] [A,19] [A,23] [A,20] [A,32] [A,18] A  1 [A,16] [B,13] [A,23] [B,19] [B,20] [B,12] A, B (A,B) 2 [A,16] [I,11] [I,21] [I,18] [I,14] A, B, I (A,B), (B,I) 3 [D,13] [I,21] [I,18] [I,14] A, B, I, D (A,B), (B,I), (I,D) 39
  40. B•íc lÆp A B C D R F H I VT t 4 [I,21] [I,18] [I,14] A, B, I, D, C (A,B), (B,I), (I,D), (D,C) A, B, I, D, C, (A,B), (B,I), (I,D), 5 [I,21] [H,17] H (D,C), (I,H) A, B, I, D, C, (A,B), (B,I), (I,D), 6 [I,21] H, F (D,C), (I,H), (H,F) A, B, I, D, C, (A,B), (B,I), (I,D), 7 H, F, E (D,C), (I,H), (H,F), (I,E) VËy ®é dµi c©y khung nhá nhÊt lµ: 15 + 12 + 11 + 13 + 14 + 17 + 21 = 103. 43. §å thÞ Euler vµ ®å thÞ Hamilton 3.1. §å thÞ Euler 3.1.1. §Þnh nghÜa: Chu tr×nh ®¬n trong ®å thÞ G ®i qua tÊt c¶ c¸c c¹nh, mçi c¹nh ®óng mét lÇn gäi lµ chu tr×nh Euler. §•êng ®i ®¬n trong G ®i qua tÊt c¶ c¸c c¹nh, mçi c¹nh ®óng mét lÇn gäi lµ ®•êng ®i Euler. §å thÞ G ®•îc gäi lµ ®å thÞ Euler nÕu cã chu tr×nh Euler vµ gäi lµ ®å thÞ nöa Euler nÕu nã cã ®•êng ®i Euler. 3.1.2. §Þnh lý: §å thÞ v« h•íng liªn th«ng G lµ ®å thÞ Euler khi vµ chØ khi tÊt c¶ c¸c ®Ønh cña G ®Ò cã bËc ch½n Chøng minh: ChiÒu thuËn : Gi¶ sö G lµ ®å thÞ Euler Trong G cã chu tr×nh Euler. ®Ønh v V. Ta ®i tÝnh bËc cña v. V× G liªn th«ng v thuéc mét c¹nh e nµo ®ã. Coi v lµ ®Ønh xuÊt ph¸t cña chu tr×nh Euler. Mçi khi chu tr×nh ®i qua v th× bËc cña v t¨ng lªn 2 ®¬n vÞ (1 øng víi xuÊt ph¸t, 1 øng víi quay l¹i) Deg(v) _ Ch½n. ChiÒu nghÞch : Gi¶ sö v V cã deg(v) ch½n. Ta cÇn chøng minh G_Euler - Chøng minh G cã chu tr×nh Euler V× G liªn th«ng  v V deg(v)>0 V× v V, deg(v)_ch½n deg(v) 2. - LÊy ®Ønh v tïy ý, xÐt ®•êng ®i x v x1 x2 trong ®ã xi xi 2 v× deg(xi) 2 Theo Dirichlet tån t¹i i, j sao cho xi = xj ®•êng ®i lµ chu tr×nh 3.1.3. HÖ qu¶: §å thÞ G lµ nöa Euler khi vµ chØ khi G cã kh«ng qu¸ hai ®Ønh bËc lÎ. 40
  41. Chøng minh: NÕu G lµ nöa Euler th× tån t¹i mét ®•êng ®i Euler trong G tõ ®Ønh u ®Õn ®Ønh v. Gäi G lµ ®å thÞ thu ®•îc tõ G b»ng c¸ch thªm vµo c¹nh (u,v). Khi ®ã G lµ ®å thÞ Euler nªn mäi ®Ønh trong G ®Òu cã bËc ch½n (kÓ c¶ u vµ v). V× vËy u vµ v lµ hai ®Ønh duy nhÊt trong G cã bËc lÎ. §¶o l¹i, nÕu cã ®óng hai ®Ønh bËc lÎ lµ u vµ v th× gäi G lµ ®å thÞ thu ®•îc tõ G b»ng c¸ch thªm vµo c¹nh (u,v). Khi ®ã mäi ®Ønh cña G ®Òu cã bËc ch½n hay G lµ ®å thÞ Euler. Bá c¹nh (u,v) ®· thªm vµo ra khái chu tr×nh Euler trong G ta cã ®•îc ®•êng ®i Euler tõ u ®Õn v trong G hay G lµ nöa Euler. 3.1.4. ThuËt to¸n t×m mét chu tr×nh Euler Void Euler_Cycle { - KiÓm tra: - G – liªn th«ng - TÊt c¶ c¸c dØnh bËc ch½n - Dïng ng¨n xÕp s - XuÊt ph¸t tõ mét ®Ønh u tïy ý addStack(u,s); CE =  While( !isEmpty(s )) { x = removeStack(s); if (ke(x) ) { y = 1 ®Ønh ke(x); addStack(y,s); Ke(x) = ke(x) \ {y}; Ke(y) = ke(y \ {x}; } Else { removeStack(S,x); CE = CE + {x}; } } } 41
  42. VÝ dô: ¸p dông thuËt to¸n trªn cho ®å thÞ v« h•íng víi c¸c ®Ønh bËc ch½n d•íi ®©y. H×nh . §å thÞ v« h•íng víi c¸c ®Ønh bËc ch½n Ta nhËn ®•îc chu tr×nh Euler lµ: [1, 2, 3, 4, 5, 6, 7, 2, 8, 6, 9, 7, 8, 5, 3, 1]. 3.2. §å thÞ Hamilton Năm 1857, nhà toán học người Ailen là Hamilton(1805-1865) đưa ra trò chơi “đi vòng quanh thế giới” như sau: Cho một hình thập nhị diện đều (đa diện đều có 12 mặt, 20 đỉnh và 30 cạnh), mỗi đỉnh của hình mang tên một thành phố nổi tiếng, mỗi cạnh của hình (nối hai đỉnh) là đường đi lại giữa hai thành phố tương ứng. Xuất phát từ một thành phố, hãy tìm đường đi thăm tất cả các thành phố khác, mỗi thành phố chỉ một lần, rồi trở về chỗ cũ. Trò chơi trên dẫn tới việc khảo sát một lớp đồ thị đặc biệt, đó là đồ thị Hamilton. 3.2.1. Đường đi Hamilton: Trong đồ thị G = (V,E) đường đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần được gọi là đường đi Hamilton. Ví dụ: Đồ thị có đường đi Hamilton là a b c d a b d c Hình 2.1. Đồ thị có đường đi Hamilton, không có chu trình Hamilton 3.2.2. Chu trình Hamilton. Chu trình bắt đầu từ một đỉnh v nào đó qua tất cả các đỉnh còn lại mỗi đỉnh đúng một lần rồi quay trở về v được gọi là chu trình Hamilton. 3.2.3. Đồ thị Hamilton. Đồ thị G được gọi là đồ thị Hamilton nếu nó chứa chu trình Hamilton và gọi là đồ thị nửa Hamilton nếu nó có đường đi Hamilton. 42
  43. Rõ ràng đồ thị Hamilton là nửa Hamilton, nhưng điều ngược lại không còn đúng. Ví dụ về đồ thị Hamilton: Đồ thị Hamilton Bài toán chu trình Hamilton (HC) được phát biểu như sau: Instance: Một đồ thị G = (V,E). Question: G có chu trình Hamilton hay không? Bài toán HC đã được Karp (1972, [15]) chứng minh là bài toán NP-C (NP- đầy đủ), chính vì thế mà không tồn tại thuật toán đa thức xác định sự tồn tại của chu trình Hamilton trong đồ thị cho trước. Cho đến nay chúng ta vẫn chưa tìm ra điều kiện cần và đủ để kiểm tra xem một đồ thị cho trước có là Hamilton hay không, và vấn đề này vẫn còn là một vấn đề mở. Hiện tại mới chỉ có các điều kiện đủ để một đồ thị là đồ thị Hamilton hay có đường đi Hamilton. 3.2.4. Định lý: Giả sử G là đồ thị Hamilton. Khi đó: a) Mọi đỉnh của đồ thị G phải có bậc không nhỏ hơn 2 b) Nếu một đỉnh có bậc bằng 2 thì hai cạnh của nó phải nằm trên bất kỳ một chu trình Hamilton của G c) Nếu một đỉnh có bậc lớn hơn 2 và hai cạnh liền kề của nó nằm trên một chu trình Hamilton thì các cạnh còn lại của nó không nằm trên chu trình Hamilton đó. 43
  44. 4. Bµi tËp 4.1. Cã thÓ t×m ®•îc mét c©y cã 8 ®Ønh vµ tho¶ ®iÒu kiÖn d•íi ®©y hay kh«ng? NÕu cã, vÏ c©y ®ã ra, nÕu kh«ng, gi¶i thÝch t¹i sao? a) Mäi ®Ønh ®Òu cã bËc 1. b) Mäi ®Ønh ®Òu cã bËc 2. c) Cã 6 ®Ønh bËc 2 vµ 2 ®Ønh bËc 1. d) Cã ®Ønh bËc 7 vµ 7 ®Ønh bËc 1. 4.2. Cho c¸c ®å thÞ sau. a. a b c d e f g h i j b. a b c d e g f i j h k l c. 42 a b 4 10 14 3 3 1 11 c d e f 5 20 9 15 7 g h - T×m c©y khung nhá nhÊt cña ®å thÞ theo thuËt to¸n Kruskal - T×m c©y khung nhá nhÊt cña ®å thÞ theo thuËt to¸n Prim. M« t¶ b»ng b¶ng gi¸ trÞ? 44
  45. 4.3. T×m c©y khung nhá nhÊt b»ng thuËt to¸n Prim, m« t¶ b»ng b¶ng gi¸ trÞ cña ®å thÞ gåm c¸c ®Ønh A, B, C, D, E, F, H, I ®•îc cho bëi ma trËn träng sè sau. A B C D E F G H A 16 15 23 19 18 32 20 B 16 13 33 24 20 19 11 15 13 13 29 21 20 19 C D 23 33 13 22 30 21 12 E 19 24 29 22 34 23 21 F 18 20 21 30 34 17 14 G 32 19 20 21 23 17 18 H 20 11 19 12 21 14 18 4.4. DuyÖt c¸c c©y sau ®©y lÇn l•ît b»ng c¸c thuËt to¸n DFS vµ BFS a. b. 1 1 2 6 3 2 3 4 7 5 4 6 7 5 8 12 11 10 9 8 10 9 12 14 15 17 16 45
  46. Ch•¬ng 5: ®•êng ®I ng¾n nhÊt M· ch•¬ng: Mh12.5 Giới thiệu: Giúp người học xây dựng đường đi, tìm đường đi ngắn nhất trong đồ thị. Mục tiêu: - Trình bày được khái niệm về đường đi ngăn nhất; - Tìm được đường đi ngắn nhất trên một đồ thị; - Áp dụng được thuật toán Dikstra, Floyd tìm đường đi ngắn nhất; - Nghiêm túc trong học tập, đảm bảo an toàn cho người và trang thiết bị. Nội dung chính: 1. C¸c kh¸i niÖm më ®Çu Tr•íc mçi chuyÕn xuÊt hµnh, chóng ta th•êng ph¶i suy nghÜ vµ chän ra cho m×nh mét hµnh tr×nh tiÕt kiÖm nhÊt theo nghÜa tèn Ýt thêi gian, tèn Ýt nhiªn liÖu hoÆc tèn Ýt tiÒn nhÊt Lý thuyÕt §å thÞ sÏ gióp chóng ta t×m ra gi¶i ph¸p ®ã. Bµi to¸n 1: Cho ®å thÞ G = (V, E) vµ hai ®Ønh a, b. T×m ®•êng ®i ng¾n nhÊt (nÕu cã) ®i tõ ®Ønh a ®Õn ®Ønh b trong ®å thÞ G. ý nghÜa thùc tÕ: Bµi to¸n nµy gióp chóng ta chän c¸c hµnh tr×nh tiÕt kiÖm nhÊt (qu·ng ®•êng, thêi gian, chi phÝ ) trong giao th«ng, lËp lÞch thi c«ng c¸c c«ng tr×nh mét c¸ch tèi •u, xö lý trong truyÒn tin VÝ dô 1 (Bµi to¸n con sãi, con dª vµ c¸i b¾p c¶i): Mét con sãi, mét con dª vµ mét c¸i b¾p c¶i ®ang ë bê s«ng. Ng•êi l¸i ®ß ph¶i ®•a chóng sang s«ng. Nh•ng thuyÒn qu¸ bÐ nªn mçi chuyÕn chØ chë ®•îc mét hµnh kh¸ch th«i. V× nh÷ng lý do mµ ai còng biÕt, kh«ng thÓ bá mÆc sãi víi dª hoÆc dª víi b¾p c¶i mµ kh«ng cã ng•êi tr«ng. VËy ng•êi l¸i ®ß ph¶i xö trÝ thÕ nµo mµ vÉn ®•a ®•îc sãi, dª vµ b¾p c¶i sang bªn kia s«ng. X©y dùng ®å thÞ v« h•íng víi c¸c ®Ønh thÓ hiÖn c¸c hµnh kh¸ch cßn l¹i bªn phÝa xuÊt ph¸t t¹i mçi thêi ®iÓm kh¸c nhau. C¹nh nèi hai ®Ønh thÓ hiÖn mét chuyÕn ®ß qua s«ng. L•u ý: L _ ng•êi l¸i ®ß S _ sãi D _ Dª B _ B¾p c¶i 46
  47. Hµnh tr×nh qua s«ng cña sãi, dª vµ b¾p c¶i Bµi to¸n ®•a vÒ viÖc t×m ®•êng ®i ng¾n nhÊt tõ ®Ønh a ®Õn ®Ønh b trªn ®å thÞ. §•êng ®i nh• thÕ ®•îc chØ ra bëi c¸c mòi tªn ë h×nh trªn. §Þnh nghÜa: §å thÞ G ®•îc gäi lµ ®å thÞ cã träng sè nÕu trªn mçi c¹nh (i, j) cña ®å thÞ ®•îc g¸n mét sè nguyªn kh«ng ©m c(i,j). Nh·n c(i,j) trªn c¹nh (i,j) cña ®å thÞ th•êng biÓu diÔn chi phÝ thùc tÕ ®Ó ®i qua c¹nh nµy. Ta th•êng ký hiÖu ®å thÞ cã träng sè lµ (G, c). §é dµi cña ®•êng ®i trong ®å thÞ cã träng sè b»ng tæng c¸c träng sè cña c¸c c¹nh trªn ®•êng ®i ®ã. Bµi to¸n: Cho ®å thÞ cã träng sè (G, c) vµ hai ®Ønh a, b thuéc G. H·y t×m ®•êng ®i cã träng sè bÐ nhÊt (nÕu cã) ®i tõ ®Ønh a ®Õn ®Ønh b. §é dµi ®•êng ®i ng¾n nhÊt tõ ®i ®Ønh a ®Õn ®Ønh b cßn ®•îc gäi lµ kho¶ng c¸ch tõ ®Ønh a ®Õn ®Ønh b trong ®å thÞ. NÕu kh«ng cã ®•êng ®i tõ a ®Õn b th× ®Æt kho¶ng c¸ch b»ng . 2. ThuËt to¸n Dijkstra N¨m 1959 E. W. Dijkstra ®•a ra mét thuËt to¸n rÊt hiÖu qu¶ ®Ó gi¶i bµi to¸n ®•êng ®i ng¾n nhÊt. ThuËt to¸n thùc hiÖn viÖc g¸n vµ gi¶m gi¸ trÞ cña nh·n l(i) t¹i mçi ®Ønh I cña ®å thÞ G nh• sau: ThuËt to¸n 4.2 (T×m ®•êng ®i ng¾n nhÊt): 1. Víi ®Ønh xuÊt ph¸t a, g¸n nh·n l(a) := 0. 2. NÕu cã c¹nh (i,j) mµ ®Ønh i ®· ®•îc g¸n nh·n vµ ®Ønh j ch•a ®•îc g¸n nh·n hoÆc ®Ønh j ®· ®•îc g¸n nh·n nh•ng l(i) + c(i,j) < l(j) th× gi¶m nh·n l(j) := l(i) + c(i,j). 3. LÆp l¹i b•íc 2. cho ®Õn khi kh«ng g¸n hoÆc gi¶m nh·n ®•îc n÷a. Void Dijkstra(a) ; { for (j V ) { L[j] := C[a, j] ; Truoc[j] := a; 47
  48. } T := V \ {a} ; while ( T  ) { chän ®Ønh i T mµ L[i] = min(L[j] sao cho j T); T := T \ i ; for ( j T ) if ( L[j] > L[i] + C[i, j] ) { L[j] := L[i] + C[i, j] ; Truoc[j] := i ; } } } BiÕn m¶ng Truoc dïng ®Ó kh«i phôc ®•êng ®i. VÝ dô: T×m kho¶ng c¸ch d(a,v) tõ a ®Õn mäi ®Ønh v cña ®å thÞ vµ t×m ®•êng ®i ng¾n nhÊt tõ a ®Õn v cho trong ®å thÞ G sau. 4 6 b c d 1 1 2 2 2 2 3 4 3 a e g h 3 5 1 2 3 3 n m k 6 3 Theo thuËt to¸n Dijkstra ta cã ®•êng ®i ng¾n nhÊt tõ ®Ønh a tíi tÊt c¶ c¸c ®Ønh nh• s¬ ®å sau: 48
  49. 3. ThuËt to¸n Floyd Cho G=(V,E) lµ mét ®å thÞ cã h•íng, cã träng sè. §Ó t×m ®•êng ®i ng¾n nhÊt gi÷a mäi cÆp ®Ønh cña G, ta cã thÓ ¸p dông thuËt to¸n Dijkstra nhiÒu lÇn hoÆc ¸p dông thuËt to¸n Floyd ®•îc tr×nh bµy d•íi ®©y. Gi¶ sö V={v1, v2, , vn} vµ cã ma trËn träng sè lµ W  W0. ThuËt to¸n Floyd x©y dùng d·y c¸c ma trËn vu«ng cÊp n lµ Wk (0 k n) nh• sau: private X¸c ®Þnh Wn { for (i = 1;i<=n; i++) for (j = 1;j<=n; j++) W[i,j] := m(vi,vj) ; //W[i,j] lµ phÇn tö dßng i cét j cña ma trËn W0 for (k = 1;k<=n; k++) if (W[i,k] +W[k,j] < W[i,j]) W[i,j] := W[i,k] +W[k,j]; //W[i,j] lµ phÇn tö dßng i cét j cña ma trËn Wk } 49
  50. 4. Bµi tËp 4.1. Dïng thuËt to¸n Dijkstra t×m ®•êng ®i ng¾n nhÊt tõ ®Ønh a ®Õn c¸c ®Ønh kh¸c trong ®å thÞ sau: 4 c 2 2 d b 3 7 12 k e 5 4 4 1 3 5 2 h 7 11 a g 4.2. Dïng thuËt to¸n Dijkstra t×m ®•êng ®i ng¾n nhÊt tõ ®Ønh a ®Õn c¸c ®Ønh kh¸c trong ®å thÞ sau: 4 b f 1 1 10 2 5 4 10 c g 2 1 a 6 4 5 8 k 3 3 d h 5 2 6 3 8 e i 4.3. Cho ®å thÞ cã träng sè nh• h×nh d•íi ®©y. H·y t×m ®•êng ®i ng¾n nhÊt tõ ®Ønh A ®Õn ®Ønh N. 7 3 8 3 A B C D E 4 2 2 6 2 2 3 5 2 3 1 F 4 G H 2 I 3 5 4 2 2 4 3 3 J K L M N 2 9 5 7 50
  51. 4.4. T×m ®•êng ®i ng¾n nhÊt tõ B ®Õn c¸c ®Ønh kh¸c cña ®å thÞ cã ma trËn träng sè sau: A B C D E F G A 3 6 B 3 2 4 C 6 2 1 4 2 D 4 1 2 4 E 4 2 2 1 F 2 2 4 G 4 1 4 51