Transcription
Rồi, hello, chào cả lớp. Ngày hôm nay thì thầy sẽ à trình bày với các em, chia sẻ với các em một cái bài toán thầy nghĩ rằng cũng rất nhiều bạn đang thắc mắc và rất nhiều bạn đang muốn, đó là học lại từ đầu. Đó là bài toán lý thuyết về đồ thị hay là đường đi ngắn nhất. Đây là bài toán có thể nói là ừ dạng toán tư duy logic, cũng là một dạng toán ở trên đại học. Sau này các em sẽ gặp lại nhá. Sau này chúng ta sẽ gặp lại nếu như bạn nào học về những ngành liên quan đến công nghệ thông tin hoặc là về toán tin. Được chưa? Rồi.
Vậy thì với dạng bài toán đường đi ngắn nhất hay là bài toán lý thuyết đồ thị như thế này thì trong chương trình của các em, đó là để thi tốt nghiệp trung học phổ thông quốc gia ấy, thì nó sẽ có mấy dạng bài? Thì thầy tóm tắt lại, chúng ta chỉ có ba dạng bài thôi. Tránh việc rất nhiều bạn chúng ta không thể nhận diện được đâu là bài toán nào nhá. Vậy thì mình chỉ có ba dạng bài thôi. Dạng thứ nhất, đó là quãng đường ngắn nhất đi từ A đến B. Đấy, ví dụ người ta cho một cái đồ thị và người ta yêu cầu đó là tìm quãng đường ngắn nhất hoặc là quãng đường tối ưu từ điểm A đến điểm B. Không có cần điều kiện gì cả nhá. Chỉ cần tìm quãng đường ngắn nhất thôi từ điểm A đến điểm B.
Dạng toán thứ hai là bài toán liên quan đến chu trình Euler. Vậy thì các em phải nhận diện khi nào mình sẽ áp dụng chu trình Euler vào bài toán. Vậy các em phải hiểu thế nào gọi là chu trình Euler đã, đặc biệt là chu trình Euler. Và tương tự, đó là dạng toán thứ ba, đó là bài toán liên quan đến chu trình Hamiton. Vậy mình cũng phải hiểu thế nào gọi là chu trình Hamiton. Okay không nào? Rồi, cái dạng thứ nhất, đó là quãng đường ngắn nhất đi từ A đến B thì thầy sẽ trình bày ngay, không cần phải lý thuyết đâu nhá. Rồi, mình đi vào dạng thứ nhất là tìm quãng đường ngắn nhất đi từ A đến B. Tất nhiên là người ta có thể biến tấu quãng đường thành gì ạ? Thời gian, thành cái chi phí đúng không? Thì tất cả mình đều quy về đó là bài toán tối ưu về quãng đường.
Rồi, mình đọc đề bài và thầy sẽ hướng dẫn các em luôn. Ờ, bạn Hóa muốn leo núi với địa điểm xuất phát từ A và kết thúc tại B với bản đồ đường đi được minh họa như hình vẽ dưới này. Trong đó các đường đi là các đoạn thẳng và thời gian di chuyển tính bằng phút. Được chưa? Vậy đây không phải là độ dài đường đi mà đây là thời gian để đi. Hãy xác định thời gian ngắn nhất để bạn Hóa hoàn thành chuyến đi từ A đến B. Vậy cũng là bài toán tối ưu đi từ A đến B thôi. Làm sao để tổng các số nó nhỏ nhất là được. Rồi, vậy để giải quyết các bài toán liên quan đến tối ưu quãng đường từ A đến B thì các em nhớ cho thầy hai cái, gọi là hai cái định nghĩa sau. Thứ nhất, đó là nhãn tạm thời. Và cái thứ hai đó là nhãn cố định. Rồi, nhãn tạm thời và nhãn cố định các em nhé. Để mà làm được bài toán tối ưu này, chúng ta luôn luôn phải cố gắng biến đổi nhãn tạm thời về nhãn cố định. Thế thì nhãn tạm thời là gì và nhãn cố định là gì? Đó là mỗi điểm này này, nó luôn có các trạng thái nhãn tạm thời và nhãn cố định. Và thầy sẽ dạy cho các em đó là làm thế nào để tìm được nhãn cố định của nó. Khi các em tìm được nhãn cố định của từng điểm rồi thì tức là bài toán đã hoàn thành nhá. Ok.
Đi vào ví dụ luôn để các em hiểu này. Ờ, khi mà người ta yêu cầu đi xuất phát từ A ấy thì các em luôn luôn đặt cho thầy cái thời điểm hoặc là cái mốc đó là bằng 0. Và thằng này luôn luôn có nhãn cố định luôn là bằng 0. Cái điểm xuất phát luôn có nhãn cố định bằng 0 các em nhá. Bởi vì đã đi đâu đâu đúng không ạ? Chưa mất cái gì cả. Như vậy bằng 0. Tiếp theo này, từ cái điểm đang có nhãn cố định chúng ta hãy xem xem nó có kết nối tới điểm nào. Tức là nó có thể đi được đến đâu nhá. Từ A thầy có thể đi được tới C, có thể đi được tới E. Như vậy thầy lấy cái nhãn cố định hiện tại của nó thầy cộng với chi phí: 0 + 15. Vậy C tạm thời có nhãn là 15. Rồi, A có thể đi tới E nữa. Rồi, 0 + 10. Vậy E tạm thời là 10. Bây giờ khi mà đã tìm được tất cả các nhãn tạm thời từ A đi tới rồi, chúng ta sẽ xem xem thằng nào có nhãn tạm thời bé nhất. Ở đây chỉ có hai cái nhãn tạm thời thôi. Và thằng bé nhất là thằng này. Thằng E có nhãn tạm thời là 10. Như vậy bé nhất thì nó sẽ là nhãn cố định tiếp theo. Xong chưa? Thằng E là nhãn cố định tiếp theo. Bây giờ chúng ta sẽ đi tìm xem E có thể đến được những điểm nào. Tất nhiên không đi lùi nhá. E có thể đi đến đó là điểm C và có thể đi đến điểm F đúng không? Lấy nhãn cố định của E cộng thêm chi phí này: 10 + 3 là 13. À, tuy nhiên thằng C đang có một nhãn tạm thời là 15 rồi. Chúng ta chỉ lấy những nhãn nhỏ hơn thôi. Vậy tạm thời chúng ta xóa thằng 15 đi và sẽ lưu lại cái nhãn hiện tại của C đang là 13. Vẫn là nhãn tạm thời nhá. Thằng E đang là 10 này. Cộng thêm 15 ra thằng F. Như vậy 10 + 15 ra 25. Hết chưa? Thằng E không thể đến điểm nào khác nữa. Vậy bây giờ chúng ta đang có hai nhãn tạm thôi nhở. So sánh xem nhãn tạm thời nào bé nhất thì em lấy. Vậy đây, thằng 13, nhãn tạm thời bé nhất nó sẽ là nhãn cố định tiếp theo. Đúng chưa? Xong nhé. Bây giờ nhãn cố định lại về C. Chúng ta lại xem xem C có thể đến những điểm nào. Có thể đến được D và C có thể đến được F. Tính cho thầy xem tại điểm D sẽ là bao nhiêu. Lấy 13 cộng cho 7 ra 20. Tiếp tục này. C đến được thằng F. 13 + 9 là ra 22 đúng không? Như vậy em sẽ xóa đi 25. Nhớ là luôn luôn lấy những nhãn tạm thời bé hơn nhá. Thằng F bây giờ phát sinh thằng 22 thì xóa thằng to là 25 đi. Ok. Xong. Tiếp tục hết. Thằng C bây giờ chỉ có thể đi đến hai điểm này nữa thôi bởi vì thằng này đã có nhãn cố định rồi. Trong hai nhãn tạm thời hiện tại, thằng nào bé hơn? Thằng D bé hơn. Vậy đây sẽ là nhãn cố định tiếp theo. Xong chưa? Rồi, tiếp tục. Từ D em có thể đi đến đâu? Từ D em có thể đi tới F, em có thể đi tới B. Vậy D mà đi tới F: 20 + 4 ra 24. Tất nhiên bạn nào mà làm nhanh rồi chúng ta thấy là có 22 nhỏ hơn nên em không viết 24 vào nữa. Tiếp tục. D mà tới gì ạ? D mà tới B. 20 + 20 là ra 40. Rồi bây giờ trong hai nhãn tạm thời hiện tại chúng ta có thằng F bé hơn đúng không? 22 bé hơn 40. Vậy thì nhãn cố định tiếp theo là 22. Chấm hết. Tiếp tục khi mà chuyển thằng cố định về đây rồi thì tiếp tục em tìm cho thầy xem là thằng F chỉ đi đến B được nữa thôi. 22 + 7 là 29. Tất nhiên 29 thì bé hơn 40 thì em xóa bỏ thằng 40 đi nha. Và bây giờ chẳng còn thằng nhãn tạm thời nào nữa để so sánh với B. Vậy đây chắc chắn là nhãn cuối cùng của B là nhãn cố định. Khi em tìm được cái điểm cần tới là điểm B có nhãn cố định là 29 rồi thì đáp án quãng đường bé nhất chính là cái nhãn đó. Vậy đáp án là 29. Được chưa?
Để mà tìm được cái cái gì ạ? Truy ngược lại quãng đường thì em dễ dàng thôi. Em có 29 này trừ 20 thì không ra 20. Vậy không phải đường này. 29 - 7 ra 22. À, sorry các em. 22 + 7 ra 29 nhá. Nhầm đấy. Đây là 29 các em nhé. Đó, thầy xin lỗi. Kết quả là 29 cơ. Ok. Giờ chúng ta sẽ truy ngược lại cái quãng đường nào. Mình đi đường nào đây? 29 - 20 không ra 20. Không phải. 29 - 7 ra 22. Vậy đúng rồi. Đây. Ở đây là 22. 22 - 4 không ra 20. Như vậy không phải. 22 - 9 ra 13. Chính xác là đường này rồi. Được chưa? Tiếp tục. Ở đây là 13. 13 không trừ được 15. 13 - 3 ra 10. Vậy là cái đường này. Đó. Và cuối cùng chắc chắn đây này. 10 - 10 ra 0. Ok. Rồi. Vậy em tìm được đáp án là 29 và quãng đường là A, E, C, F đến B xong nhá. Thì đấy, khi mà chúng ta tìm được nhãn tạm thời thì em nhớ rằng so sánh tất cả những nhãn tạm thời hiện tại để tìm thằng bé nhất và gán cho nó là nhãn cố định là xong. Rồi chúng ta sẽ sang ví dụ thứ hai để mình thực hành nhá.
Ví dụ thứ hai như sau này. Nhà thời gian ở P và trường Đại học Bách Khoa Hà Nội ở Q, tìm đường đi ngắn nhất từ nhà thời gian tới trường, tức là từ P. Bài này phức tạp hơn bởi vì nhiều đường hơn thôi, nhiều đoạn hơn. Nhưng mà cứ theo quy tắc của thầy, điểm đầu tiên, điểm xuất phát luôn luôn gán nhãn cố định là bằng 0. Rồi bây giờ từ cái điểm đang có nhãn cố định xem xem nó có thể đi được tới những điểm nào để gán cho nó nhãn tạm thời. P được tới A, tới B và tới C. 0 + 3 vậy A tạm thời là 3. 0 + 1 vậy B tạm thời là bằng 1. Và 0 + 5. Vậy C tạm thời là 5. Hết rồi. P chỉ đi được ba điểm này thôi. Vậy trong ba nhãn đang có tạm thời như vậy em tìm cho thầy thằng nhãn tạm thời bé nhất nó chính là số 1 ở đây. Vậy nhãn tạm thời bé nhất sẽ là nhãn cố định tiếp theo. B sẽ là nhãn cố định tiếp theo. Xong nhá. Bây giờ từ B có thể đi được đến những điểm nào? Đến A, đến C và đến L. Tìm cho thầy các cái nhãn của nhãn tạm thời nhé. 1 + 4 ra 5. À, thực ra là thầy không cần viết đâu bởi vì 5 nó lớn hơn 3 rồi. Đừng có viết vào. Vẫn lấy 3 thôi. Nhớ rằng luôn lấy những nhãn tạm thời bé hơn nhé. 1 + 3 ra 4. Ok. 4 bé hơn 5. Vậy viết 4 vào, gạch thằng 5 đi. Hiểu chưa? Đây này. 1 + 3 ra 4 bé hơn 5. Vậy lấy 4 bỏ 5. 1 + 15 ra 16, vậy L tạm thời là 16. Xong hết rồi. B tới được ba điểm này thôi. Vậy trong ba cái nhãn tạm thời em đang có trên hình ấy thì thằng nào bé nhất? Thì thằng 3 là bé nhất. Vậy đây sẽ là nhãn cố định tiếp theo. Xong nhá. Ok. Tiếp tục này. Thằng A có thể đi đến điểm nào? Thằng A chỉ có thể đi đến L thôi. Vậy 3 + 13 vẫn ra 16. Xong chưa? Ok. Thầy không điền gì nữa nhỉ? Vẫn là 16 thôi. Vậy bây giờ thầy lại đi tìm xem hai cái nhãn cố định thầy đang có. Xin lỗi, hai cái nhãn tạm thời thầy đang có thì thằng nào bé hơn? Rõ ràng thằng này bé hơn mà đúng không? Vậy đây sẽ là nhãn tạo cố định tiếp theo. Xong rồi. Nhãn cố định giờ về C. Tìm xem C tới được những điểm nào nữa. C tới được M, C tới được N. Rồi 4 + 4 ra 8. Ở đây tạm thời nhãn là 8. 4 + 7 ra 11. Tạm thời ở N. Bây giờ trên hình chúng ta đang có ba nhãn tạm thời. Tìm cho thầy nhãn tạm thời bé nhất. 16, 8, đây bé nhất. Vậy M sẽ là nhãn cố định tiếp theo. Xong nhé. Ok. M sẽ là nhãn cố định tiếp theo. Từ M có thể đi đến đâu? Từ M có thể đến L, đến N và đến Q. Tính các nhãn tạm thời tiếp theo này. 8 + 9 = 17. 8 + 9 = 17 lớn hơn 16 rồi thì thôi thầy không viết nữa, giữ nguyên thằng 16. Tuy nhiên hôm nay thầy vẫn viết vào để các em hiểu rằng là thực chất là mình có cộng nhưng nó bé hơn thì mình không lấy thôi nhá. 8 + 9 ra 17 lớn hơn 16 thì vẫn giữ 16. 8 + 2 ra 10, ô bé hơn 11 rồi. Lấy thằng 10 đấy. Xóa thằng 11 đi. Chuẩn chưa? Rồi 8 + 7 ra 15. Chuẩn chưa? Rồi bây giờ trong các nhãn tạm thời thì thằng 10 thằng bé nhất. Vậy đây sẽ là nhãn cố định tiếp theo. Xong. Bây giờ từ N chúng ta chỉ có thể đi được tới Q, bé hơn 15. Như vậy viết 14 và xóa 15 đi. Xong chưa? Ok. Chưa xong đâu. Vẫn phải so sánh các nhãn tạm thời hiện tại. À, trong hai nhãn tạm thời này, thằng 14 bé hơn. Vậy thằng này sẽ là nhãn cố định. Và thằng Q là điểm cần tới nó đã có nhãn cố định rồi. Vậy đây sẽ là đáp án của bài toán. Đáp án là bằng 14. Bây giờ mình đi truy ngược lại quãng cái cái đường đi đúng không ạ? 14 này. 14 - 4 ra 10, như vậy nó đi theo đường này. 10 này. 10 - 2 ra 8 chưa? Vậy đi theo đường này. Nhiều bạn bảo sao không đi đường này thầy? 10 - 7 đâu có ra 4 đâu. Thấy không? Rồi tiếp tục này. 8 - 4 ra 4. Đây, 4 - 3 có ra 1 không? 4 - 3 ra 1. 4 không trừ được 5 đâu nhá. 4 - 3 ra 1 về B. Và 1 - 1 = 0. Vậy đây là cái đường đi của chúng ta. P, B, C, M, N và Q. Chấm hết nhá.
Rồi, như vậy với hai ví dụ thôi thầy nghĩ rằng là chúng ta đã hiểu cách tìm quãng đường ngắn nhất đi từ A tới B rồi. Và tất nhiên ở những cái dạng bài tiếp theo, đó là dạng bài về chu trình Euler hay là Hamiton ấy thì có thể chúng ta sẽ bị lồng ghép bài toán liên quan đến cái dạng một này bởi vì dạng một là dạng cơ bản nhất nha. Rồi bây giờ thầy sẽ chuyển vào dạng thứ hai, đó là dạng chu trình Euler. Để mà làm được dạng toán này thì mình phải hiểu rằng thế nào gọi là một chu trình Euler đã. Cái định nghĩa của nó như sau này. Thầy cho các em một cái đồ thị G. Vậy một đường đi từ đỉnh A đến đỉnh B và đi qua tất cả các cạnh của G nhá. Trên hình có bao nhiêu cạnh? Phải đi qua tất cả các cạnh. Mỗi cạnh đúng một lần thôi thì được gọi là đường đi Euler từ A đến B. Đấy. Đường đi Euler từ A đến B. Vậy nếu như thầy có một cái quãng đường đi được từ A đến B mà đi qua tất cả các cạnh duy nhất một lần thì đấy là đường đi Euler. Thế chu trình Euler thì là gì? Chu trình thường thường là khép kín đúng không? Vậy thay vì đi từ A đến B, thầy sẽ gọi đó là à một chu trình xuất phát từ đỉnh A chẳng hạn này, đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần và quay lại được đỉnh A. Khép kín chưa? Khép kín, người ta gọi là chu trình Euler. Đấy, chu trình Euler nhá. Giống với đường đi Euler nhưng điểm đầu và điểm cuối trùng nhau thì gọi là chu trình Euler. Ứ. Bây giờ mình nhìn vào đây. Mình nhìn vào đây. Ờ, cái hình đầu tiên ấy thì thầy đang để ở đây là chu trình Euler. Hình thứ hai là đường đi Euler, vậy hai thằng này khác nhau cái gì? À, như thầy nói, chu trình Euler thì khép kín còn đường đi Euler thì nó không khép kín. Và sau bài này các em sẽ hiểu rằng những thằng có đường đi Euler chưa chắc đã có chu trình Euler đâu. Mình cùng tìm hiểu nhá. Ở hình đầu tiên thầy gợi ý là có chu trình Euler được chưa? Có chu trình Euler, nhưng mà chu trình Euler của nó, dấu hiệu nhận biết như nào thì lát nữa thầy nói. Bây giờ chúng ta hãy cố gắng tìm cho thầy xem cái chu trình Euler của đường đi thứ nhất thì mình đi như thế nào. Chu trình Euler tức là đi từ một đỉnh đi qua tất cả các cạnh, mỗi cạnh một lần thì nó sẽ quay trở về cái đỉnh ban đầu nhá. Thầy thử đi rồi. Đầu tiên thầy đi từ A đến B đi. Được không? Đi từ A đến B đi. Ờ, từ B đến, từ B đến D đi. Được chưa? Từ D thầy lại đi đến A. Từ A thầy lại đi đến C. Từ C thầy lại đi về B. Rồi từ B thầy đi đến E. Và cuối cùng từ E thầy đi về A. Okay chưa? Như vậy chúng ta thấy là nó xuất phát từ đỉnh A đi qua tất cả các cạnh, mỗi cạnh một lần, sau đó quay trở lại được đỉnh A. Vậy đây là chu trình Euler đấy. Đây, chúng ta có chu trình A đến C. Đây là một chu trình khác cái mà thầy vừa vẽ nhá. Nhưng mà chúng ta có thể lựa chọn nhiều chu trình. Đây, thầy gợi ý một cái là A đến C rồi từ C đến B đúng không? Rồi từ B về E. Cả đấy các em có thể tự thực hành như cái chương trình đầu tiên thầy vẽ cũng được hoặc như thế này cũng được, miễn là gì, đảm bảo đi qua được tất cả các cạnh, mỗi cạnh một lần và trở về được đỉnh ban đầu. Đây chính là cái bài toán đó là à dùng một nét có thể vẽ được một cái hình hay không đấy các em. Vậy đây chính là bài toán dùng một nét vẽ được một cái hình nhá. Rồi, chúng ta sang cái thằng thứ hai, đó là đường đi Euler. Thầy khẳng định thằng này không có chu trình Euler, vì sao? Các em thử mà xem. Ở đây có mấy cạnh nhở? Ở đây có một cạnh, hai cạnh, ba cạnh, bốn cạnh và năm cạnh. Chúng ta có năm cạnh nha. Bây giờ làm sao các em đi được từ một đỉnh đi qua tất cả các cạnh, mỗi cạnh một lần mà về được đỉnh A thì là chu trình Euler. Nhưng bài này không có đâu. Bài này chỉ có đường đi Euler, tức là nó có thể đi được từ đỉnh này đến một đỉnh nào đó và qua tất cả các cạnh, mỗi cạnh một lần. Rồi, thầy thử đi cho các em nhé. Rồi, thầy mở cái đáp án ra thì chúng ta có cái chữ cái đường đi là A đến C này. Ở đây có E à, thế ra mình không được đi như này đâu. Rồi, thầy đi lại nhá. Đi lại nhá. Thầy đi từ A đến E. Okay chưa? Rồi từ E thầy lên B. Rồi từ B thầy xuống C. Từ C thầy lên E và từ E thầy về D. Như vậy mỗi cạnh đi qua một lần rồi và nó đi từ A tới D. A đến E đến gì ạ? Đến B đến C lại về E rồi lại về D. Như vậy tất cả các cạnh, mỗi cạnh đi qua một lần nhưng không quay lại đỉnh ban đầu. Vậy đây là đường đi Euler chứ không phải chu trình Euler nha. Và thông qua hai cái hình vẽ này thầy có một cái, hai cái định lý để các em nhận biết được khi nào mà có chu trình Euler và khi nào thì chỉ có đường đi Euler thôi. Hình đầu tiên này nó có chu trình Euler. Vậy thì khi nào có chu trình Euler các em nhớ cho thầy tất cả các đỉnh của đồ thị đều là bậc chẵn. Được chưa? Thì có chu trình Euler. Con số em nhìn vào đây, thằng A có mấy kết nối ạ? Một kết nối, hai kết nối, ba kết nối và bốn kết nối. Số kết nối chính là số...
Bậc của đỉnh đó. Vậy thằng này có bậc là 4. Thằng B tương tự này, 1, 2, 3, 4, có bốn kết nối thì bậc là bằng 4. Thằng C có hai kết nối thì bậc là 2. Thằng D có hai kết nối thì bậc cũng là 2. Và thằng E cũng có hai kết nối thì bậc cũng là 2. Tất cả các bậc đều là chẵn. Chẵn thì phải lớn hơn bằng 2 nhá. Không có thằng nào bậc không đâu. Nhớ chưa ạ? Tất cả các bậc là chẵn thì có chu trình. Nhớ với nhau một điều như vậy. Rồi.
Vậy đường đi Euler thì sao? Đường đi Euler thì cũng khá tương tự, đó là chúng ta sẽ có được tất cả các đỉnh là bậc chẵn. Nhưng duy chỉ có hai đỉnh bậc lẻ thôi. Vậy nếu như một đồ thị mà có đúng hai đỉnh bậc lẻ nhá thì nó có đường đi và cái điểm đầu và điểm cuối chính là hai đỉnh bậc lẻ đó. Em nhìn chưa? Điểm đầu và điểm kết thúc chính là hai điểm bậc lẻ đó. Vừa nãy thầy có điểm đầu là A và điểm kết thúc là D. Thằng A có một kết nối thì bậc là 1. Thằng D có một kết nối thì bậc là 1. Thằng E có bốn kết nối thì bậc là 4. Thằng B có hai kết nối thì bậc là 2. Và thằng C có hai kết nối thì bậc cũng là 2. Đó. Như vậy tất cả các đỉnh là bậc chẵn, chỉ có đúng hai đỉnh bậc lẻ. Vậy thì chúng ta có đường đi từ A tới D. Đấy, từ A tới D tức là điểm đầu là A, điểm cuối là D hoặc ngược lại, điểm đầu là D, điểm cuối là A. Đúng chưa? Hiểu với nhau như thế nhá.
Rồi, khi mà nhận biết được cái đồ thị nào có chu trình và đồ thị nào có đường đi rồi thì chúng ta sẽ làm được các bài toán vận dụng. Nhớ rằng là à sau này chúng ta sẽ gặp bài toán tối ưu về người đưa thư ấy thì nó là bài toán nó phải đi qua tất cả các cung đường để phát thư. Vậy khi nào thì sẽ là tối ưu? Khi nó đi qua tất cả các cung đường này một lần đúng không? Vậy trong trường hợp nào đi qua được tất cả cung đường một lần? Khi đồ thị đó có chu trình Euler nha. Thì đấy là cái ví dụ về bài toán đưa thư. Còn giả sử cũng là bài toán đưa thư mà nó không có chu trình thì sao? Thì tí nữa thầy sẽ hướng dẫn các em giải quyết bài toán nhá. Rồi mình đi vào một số ví dụ đã.
Rồi bây giờ nhận biết cho thầy xem đồ thị này có chu trình hay không. Để mà nhận biết có chu trình hay không nhá, thì nhớ các đỉnh là bậc chẵn thì sẽ được. Nào xác định cho thầy. Đỉnh E có hai kết nối thì bậc là 2. Đỉnh A có bốn kết nối, 1, 2, 3, 4, bậc là 4. Đỉnh D có 1, 2, 3, 4 kết nối thì bậc cũng là 4. Thằng B tương tự này, 1, 2, 3, 4, bậc là 4. Và thằng C có mấy nhở? Cũng 1, 2, 3, 4, bậc là 4; thằng F thì là 2. Xong chưa? Vậy thì rõ ràng là tất cả các đỉnh bậc là chẵn rồi. Thì em suy luôn cho thầy có chu trình, có chu trình Euler, tức là có thể có một nét để vẽ được cái hình vẽ này nhá. Dùng một nét để vẽ được hình vẽ này. Tức là đi qua từ tất cả các cạnh một lần.
Nào giờ các em thử xem cái chu trình em lựa chọn đi từ đỉnh nào. Em thích chọn đỉnh nào cũng được nhá. Khi đã có chu trình thì điểm nào nó cũng thỏa mãn thôi. Thầy chọn đỉnh B đi, là đỉnh bắt đầu nhá. Đi từ B này, đã là chu trình thì nhớ là phải quay lại được B nhá. Rồi đầu tiên nó đi lên đâu? Em thích thì em lên E đi. Được chưa? B đến E. E từ đâu? E tới A chứ còn gì nữa nhá. A tới đâu? A thì lại về B. Tới A rồi lại về B. Tiếp tục này. Từ B thầy lại đi gì ạ? Thầy đi C. Từ C thầy lại đi đâu? Từ C thầy lại đi à đi F được [âm nhạc] không? Từ C thầy đi F. Từ F thầy lại đi D. Đấy. Từ F thầy lại đi D. Được không? Rồi tiếp tục. Từ D thầy đi A. Ok. Từ A thầy về về C. Từ C thầy lên D. Rồi và từ D thầy quay lại B được chưa? Quay lại điểm ban đầu. Thỏa mãn chưa? Rồi thỏa mãn. Đây chính là một chu trình, khởi đầu là B và kết thúc là B. Đi qua tất cả các cạnh, mỗi cạnh duy nhất một lần. Đấy, cách nhận biết tất cả các đỉnh bậc chẵn thì chúng ta có chu trình Euler và hoàn toàn kiểu gì em cũng sẽ có được một chu trình thỏa mãn thôi nha. Ờ mình chuyển ví dụ thứ hai nào. Hiểu chưa? Hiểu thế nào là chu trình và cách nhận biết chưa?
Rồi đến đồ thị thứ hai này. Thằng này có chu trình hay không? Liên quan đến chu trình, lại tìm bậc các đỉnh cho thầy. Đỉnh A có bậc mấy? 1, 2, 3 kết nối, bậc 3, ô, bậc lẻ mất rồi. Thằng C bậc 2. Thằng D cũng bậc 2. Thằng E cũng bậc 2. Thằng B bậc 3. Bởi vì có ba kết nối. Thì đây là đồ thị chỉ có duy nhất hai điểm có bậc bậc lẻ. Hai điểm bậc lẻ. Vậy thì nó chỉ có đường đi thôi mà không có chu trình đâu. Và cái đường đi của em sẽ là đi từ A tới B nhá. Này không có chu trình mà chỉ có đường đi thôi. Không có chu trình nhưng có đường đi, giờ em lựa chọn cho thầy xem cái đỉnh bắt đầu em thích là từ A thành B đều được. Hai đỉnh bậc lẻ này, em chọn thằng nào cũng được. Em chọn thằng A đi. Được chưa? Đi từ A. Em đi từ đâu? Em đi tới C này. Sau đó em đi về đâu ạ? Em đi lên B. Đi lên B. Rồi tiếp tục. Ờ em về D đi. Về D. Từ D em lại lên A. Từ A em lại về E ha. Từ A em lại về E. Và từ E em chỉ còn duy nhất đó là về B nữa thôi. Đấy. Như vậy đi qua tất cả các cạnh, mỗi cạnh duy nhất một lần nhưng nó không quay lại đỉnh ban đầu mà nó quay từ A đến B. Đi từ A đến B. Đấy, điểm đầu và điểm cuối này. Thấy chưa? Đúng cái định lý mà thầy cho các em rồi. Vậy thằng này có đường đi từ A tới từ A tới B nhá. Chính là hai cái đỉnh bậc lẻ của các em. Xong.
Thì ở bài toán về đường đi và chu trình Euler rồi. Chúng ta sẽ đi vào làm bài tập vận dụng liên quan đến tối ưu quãng đường. Bài số 1 của chúng ta như sau. Rồi, ở một khu phố ấy, có một khu phố, một thành phố có chín khu phố là A, B, C, D, E, F, G, H, K. Mỗi đường sẽ nối hai khu phố như hình vẽ dưới. Ok. Từ khu phố H, từ H này, Minh cần phải đi qua tất cả các con đường và trở về A. Minh cần phải đi qua tất cả các con đường và trở về từ từ nhé. Từ khu phố. Sorry các em. Đây là bài toán từ khu phố A nhé. Rồi từ khu phố A, Minh cần phải đi qua tất cả các con đường và quay trở lại A. Quãng đường ngắn nhất Minh có thể đi là bao nhiêu? Ok. Bây giờ bài toán là cần đi qua tất cả các con đường. Đi qua tất cả con đường, xuất phát từ A và trở về A. Vậy nếu như nó có chu trình thì à nó chỉ cần đi mỗi con đường một lần thôi. Ở đây đề bài là đi qua tất cả các con đường và không nói là tối thiểu bao nhiêu lần. Nhưng nếu như có chu trình thì mỗi con đường nó chỉ cần đi một lần thì nó vẫn quay trở lại được A. Thì đấy là con đường tối ưu nhất. Vậy bây giờ thử tìm xem cái đồ thị này có chu trình Euler hay không. Ở đây đỉnh A bậc là 2 nhở. Đỉnh B bậc là 4. Bốn kết nối. Đỉnh G bậc cũng là 4. Được chưa? Đỉnh K có hai kết nối, bậc là 2. Đỉnh F bốn kết nối, bậc là 4. Nhiều bạn hỏi thầy kết nối là gì đây này. Nó có bốn con đường nối vào nó thì có bốn kết nối thôi. Rồi đỉnh E có bốn kết nối, cũng là 4. 1, 2, 3, 4. Đỉnh D có hai kết nối thì bậc là 2. Đỉnh C 1, 2, 3, 4. Bốn kết nối. Và cuối cùng đỉnh H này, 1, 2, 3, 4, bốn kết nối. Xong chưa? Rồi nhìn nhanh được tất cả các đỉnh đều bậc chẵn đúng không? Tất cả các đỉnh đều bậc chẵn. Tất cả các đỉnh bậc chẵn. Như vậy suy ra đồ thị có chu trình nhá. Có chu trình. Chu trình là gì? À nếu như thầy chọn điểm đầu là điểm A thế thì nó sẽ có cách đi nào đó để đi qua tất cả các con đường này. Mỗi con đường duy nhất một lần thôi và trở về A. Và đây chính là quãng đường ngắn nhất để nó đi thỏa mãn đề bài. Được chưa? Phải suy ra quãng đường ngắn nhất đấy. Quãng đường ngắn nhất bởi vì theo chu trình thì mỗi quãng đường này tôi đi đúng một lần thôi. Tôi vẫn trở về được A rồi. Vậy thì em cộng tất cả các gì ạ? Các con đường lại. Đó là bằng tất cả các con đường cộng lại nha. Quãng đường ngắn nhất đó là bằng mỗi con đường một lần. Mỗi đoạn đường đi đúng một lần, đúng theo chu trình Euler. Được chưa? Mỗi con đường đúng một lần. Em cộng lại là xong. Bằng này, 15 + 3 + 2, em cộng tất cả lại thôi. [âm nhạc] 15, CD là bằng 3, DE = 2, CE là bằng 11. Được chưa? Rồi cộng với này 3, 4. Đấy, những cái nào thầy cộng rồi thầy viết màu vàng lại nhé. Rồi cộng với 3. Ok. Tiếp tục. Cộng với HE là bằng 1. Cộng với HF là bằng 8, cộng cho EF là bằng 3, cộng cho gì? BG = 1, lại cộng tiếp. HG = 6. Ồ nhiều quá. Rồi cộng tiếp, cộng FG = 5, cộng cho gì? FK = 7 và đoạn cuối cùng là GK = 5. Đấy. Tức là các em cộng mỗi cái mỗi quãng đường một lần. Thì đây, chu trình Euler này nhá. Bài này nếu như bạn nào không biết nhận diện thằng này có chu trình Euler thì nghĩ lâu lắm nhở. Nghĩ lâu lắm nhá. Rồi các em tự bấm máy tính nhá. Bài này tự bấm máy tính cho thầy được chưa? Bấm máy tính xem có ra giống thầy không nhá. Bấm máy tính này. Đâu rồi? Ok. 15 cộng 3 cộng 2 cộng 11 cộng cho 3 + 4 + 3 + 1 cộng 8 + 3 + 1 cộng 6 + 5 + 7 + 5 = 77. Bài toán là 77. Okay chưa? À bài toán này quãng đường tối ưu là dùng chu trình Euler, 77. Xong rồi đấy. Chúng ta chuyển sang bài số 2 nhá. Bài số 2 vẫn là bài toán liên quan đến chu trình nhưng liệu bài này nó có chu trình hay không? Câu số 2 như sau. Đấy, hi vọng là sau cái bài giảng này của thầy, tất cả những bài sau này liên quan đến tối ưu, bài tối ưu quãng đường thì em đều làm được hết. Ờ, một người đưa thư, cũng là bài toán đưa thư, xuất phát từ bưu viện ở vị trí A, là xuất phát từ A. Phải đi trên mỗi con đường ít nhất một lần để phát thư cho tất cả các điểm nằm dọc đường. Và cuối cùng quay lại điểm xuất phát, quay lại A. Độ dài các con đường như hình vẽ. Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất là bao nhiêu? Ừ, nếu như giống bài toán bên trên mà có chu trình ấy thì chắc chắn đó là em chỉ cộng cộng mỗi quãng đường một lần là thằng nào có thể quay trở về A rồi. Đấy là nếu có chu trình nhá. Xem xem thằng này có chu trình hay không. Nào, bậc của A là mấy? Bậc của A là 3. Thôi chết rồi. Đểu rồi các em ơi. Coi rồi. Đợi thầy đổi cái màu này nhé. Rồi thằng A bậc là 3, soi rồi. Bậc lẻ, thằng E bậc mấy ạ? 1, 2, 3, 4, 4 kết nối thì bậc là 4. Thằng B 1, 2, 3, 4. Thằng D này 1, 2, 3 rồi và thằng C là 2. Ok. Như vậy là em thấy chúng ta có hai thằng nó mang bậc lẻ, có thằng A và thằng D. Ứ, thằng A và thằng D. Như vậy ở đây không thể có chu trình được mà nó chỉ có đường đi từ A tới D đúng không? Nó có đường đi từ A tới D. Rồi suy ra nó có đường đi từ A tới D và khi đó thì mỗi cạnh nó đi được một lần thôi. Mỗi cạnh một lần. Mỗi cạnh đã đi một lần. Em đồng ý chưa? Có cần thầy tìm cho một cái đường đi từ A đến D không? Thôi nhá. Giống bài toán bên trên rồi. Chắc chắn em sẽ tìm được một đường đi qua tất cả các cạnh này và xuất phát từ A đến D. Khi đó được chưa? Khi đó này thằng A này nó sẽ đi đến điểm nào đó, đến điểm nào đó, đến điểm nào đó đến D. Ok. Chúng ta có mấy đỉnh đi nhở? 1, 2, 3 đỉnh nữa. Đỉnh này thầy chưa biết đỉnh nào nhé. Thầy chưa biết đỉnh nào đâu. Nó sẽ đi qua như vậy. Được chưa? Rồi. Vân vân và mây mây. Thì tạm thời với một cái đường đi ấy, em đã đi từ A tới D rồi. Đi được từ A tới D nhá. Và mỗi cạnh đi qua một lần rồi. Thỏa mãn đó là đi qua tất cả các cạnh. Xong. Bây giờ nó cần đi từ D về A nữa thì nó mới hoàn thành chu trình đúng không? Vậy bây giờ cần đi từ A về D nữa. Vậy suy ra cần đi tiếp từ D về A đúng không nào? Đúng không? Nhiều bạn là vẫn còn thắc mắc cái chỗ này, từ A đến D như thế nào thì thì bởi vì đường đi Euler mà đúng không? Đường đi Euler, bậc lẻ tất cả còn lại là bậc chẵn. Vậy thì chắc chắn sẽ có một cái đường đi Euler đi qua tất cả các cạnh này, mỗi cạnh một lần từ A tới D. Đây là hai cái đỉnh bậc lẻ này. Rồi bây giờ nó đang ở D, thầy cần phải đi về A đúng không? Vậy bây giờ để bài toán ấy nó là bài toán tối ưu hay là quãng đường nhỏ nhất. Vậy thì cái cái này này, từ D với A nó phải là quãng đường nhỏ nhất. Quãng đường nhỏ nhất. Còn cái chỗ đường đi Euler này thì nó cộng tất cả các cạnh, mỗi cạnh một lần rồi đúng không? Cái đường đi này của nó sẽ là bao nhiêu? Rồi em cộng tất cả lại nó tầm bằng 7 này. 2E đấy, cộng với thằng gì đây? Cộng 6 này. Cộng 8 này. Cộng 10 này. Cộng cho bao nhiêu? + 9 + 4 + 5 + 2 + 4 + 9 + 5 + 2. Rồi đây chính là cái đường đi Euler bắt buộc nó phải đi như này đã đúng không? Đây là cái bắt buộc nó phải đi. Xong bây giờ các em sẽ tìm cho thầy xem quãng đường nhỏ nhất từ D về A. Vậy đây chính là dạng thứ nhất. Tìm quãng đường ngắn nhất đi từ D tới A. Tìm đi các em. Thầy tạm thời xóa những cái bậc này đi nhé. Nào, vận dụng bài toán ban đầu của thầy đó là tìm quãng đường ngắn nhất đi từ A từ D tới A. Từ D tới A. Rồi nào đi từ đâu? Đi từ D. Như vậy nhãn cố định luôn là bằng 0. Ok. Nhãn cố định bằng 0 luôn. Từ D có thể về được đâu? Từ D có thể về được B, được C, được E. 0 + 2, vậy thằng này là 2. 0 + 4, thằng này là 4. 0 + 9, thằng này là 9. Hết chưa? Chỉ ba điểm này thôi. Trong ba nhãn tạm thời, thằng nào bé nhất? Thằng C bé nhất. Vậy đây sẽ là nhãn cố định tiếp theo. Rồi tiếp tục. Từ C có thể đi về đâu? Từ C chỉ có thể lên B nữa thôi. 2 + 5 ra 7. Nhưng mà 7 lớn hơn 4 rồi thì em cũng không lấy thằng 7 này làm gì nhỉ? Chấm hết. Tiếp tục. Bây giờ đi rồi thì có hai nhãn tạm thời hiện tại 4 và 9. Vậy thì em vẫn chỉ lấy gì thôi? Cái nhãn tạm thời bé hơn là nhãn cố định các em. Rồi nhãn cố định về B. Bây giờ B đi được tới đâu? B đi được tới E và B đi được tới tới A. Nào, B tới E, 4 + 10 ra 14. Nhưng mà 14 lớn hơn 9 rồi thì mình cũng không lấy thằng 14 này làm gì. Rồi 4 + 8 ra 12. Như vậy chúng ta lấy đây là 12. Thế chưa? B chỉ đến hai điểm này được thôi. Trong các nhãn tạm thời đang có là 9 và 12. Thằng bé hơn là thằng này, thằng 9. Vậy nhãn cố định sẽ về 9 nhờ. Xong nhá. Rồi từ E lại đến đâu được? Từ E chỉ có thể tới A được thôi. Vậy ở đây chúng ta có này 9 + 6 ra bao nhiêu? 9 + 6 ra 15 nhưng mà 15 lớn hơn 12 rồi cũng xóa. Tiếp tục này. 9 có thể cộng 7 ra 16, nhưng 16 vẫn lớn hơn lớn hơn 12. Chúng ta vẫn xóa. Vậy thì bây giờ nhãn cố định về A là 12. Vậy thì cái quãng đường nhỏ nhất từ D về A bằng 12. Rồi xong chưa? Nào thử xem cái đường đi đấy là bao nhiêu nhá. 12 này. 12 - 6 không ra 9 này. 12 - 8 ra 4. Ok. Vậy đây được chưa? 4 - 4 về 0. Vậy đây là đường đi ngắn nhất từ D về về A. Đấy, như thầy nói vừa nãy, nhiều bạn có thể nhìn thấy luôn nhưng mà nhiều bạn không nhìn được thì chúng ta phải làm như thầy thôi. À xong. Vậy kết quả bài toán này như sau. Là kết quả bài toán. Kết quả bài toán đó là nó phải đi một cái đường đi từ A đến D hết bằng này. Sau đó từ D nó phải đi quãng đường ngắn nhất về A là bằng 12. Em cộng hai cái đống này lại, em cộng lại. Được chưa? Vậy bằng bao nhiêu? Bấm máy tính vào: 7 + 6 + 8 + 10 + 4 + 9 + 5 + 2, em cộng cho thầy, kết quả là bằng 61 nhá. Chúng ta đã hiểu vận dụng bài toán đường đi và chu trình chưa? Ở bài toán thứ hai, thầy lưu ý lại đó là nó không có chu trình. Như vậy để mà đi qua tất cả các cạnh ít nhất một lần đúng không? Thì nó phải thực hiện cái đường đi đã. Sau đó đường đi từ A đến D rồi mà muốn quay lại A thì chúng ta phải thực hiện một quãng đường ngắn nhất từ D quay trở lại A. Thế là chúng ta có được một cái chu trình tối ưu nhất. Xong.
Ok, thầy xin phép chuyển vào phần tiếp theo, đó là dạng thứ ba liên quan đến dạng bài toán liên quan của chu trình Hamilton nhá. Nhớ đấy, là liên quan đến tất cả các cạnh, tức là bài toán có thể vẽ được một hình bằng một nét thôi. Còn Hamilton thì là bài toán như thế nào? Đi vào định nghĩa. Rồi bài toán chu trình Hamilton của chúng ta được định nghĩa như sau này. Nếu thầy cho một đồ thị G thì đường đi mà đi qua mọi đỉnh, mỗi đỉnh đúng một lần là đường đi Hamilton. Được chưa? Đường đi qua mỗi đỉnh, mỗi đỉnh đúng một lần gọi là đường đi Hamilton. Nó khá là giống đường đi Euler nhở. Không yêu cầu là phải quay trở lại nhá. Thì đấy gọi là đường đi. Nhưng chu trình thì nhớ là
Phải quay lại điểm ban đầu. Vậy nếu đường đi bắt đầu và kết thúc tại đỉnh A, đi qua mỗi đỉnh của cái đồ thị mỗi đỉnh đúng một lần, tất nhiên là trừ đỉnh A rồi, thì được gọi là chu trình Hamitơ. Được chưa? Tất nhiên là sau này những bài toán về chu trình Hamitơ thì chúng ta không cần phải nhận diện xem là thằng này có hay là không có chu trình Hamitơ đâu. Chỉ cái chúng ta mới cần nhận diện thôi. Nhưng mà thầy vẫn sẽ cho các em cái định lý để các em nhận diện được nha.
Thầy có hai cái hình vẽ như sau, đều có chương trình Hamitơ. Cái định lý đầu tiên ấy, đó là à cái hình vẽ này thì có chương trình Hamitơ, thầy khẳng định luôn. Vậy thì nó có khi nào chúng ta có một cái định lý đó là nếu như đồ thị có n đỉnh, tất nhiên là lớn hơn ba đỉnh rồi, thì mọi đỉnh đều có bậc lớn hơn bằng n/2 nhá. Tức là lớn hơn hoặc bằng số mấy đây? 1,5 là bằng 2. Đấy, bậc là phải lớn hơn bằng 2. Được chưa? Cũng thể ở đây là lớn hơn bằng 2. Đấy. Thế thì nó sẽ có chu trình. Mọi đỉnh mà có bậc lớn hơn bằng 2 thì có chu trình Hamitơ. Tất nhiên là ngược lại thì không đúng, nó chỉ suy ra thôi. Vậy thì chúng ta cùng chứng minh nhá.
Cái hình vẽ bên trái, hình vẽ đầu tiên, đỉnh A có bậc là 4. Đấy, đỉnh B cũng có bậc là 4. Đỉnh C bậc là 4. Đỉnh D bậc là 1 2 3 4. Đỉnh F là mấy đây? 1 2 3 4. Ồ 4 hết à. Và đỉnh gì? Đỉnh E. 1 2 3 4. Đúng định là 4. Ok chưa? Rồi bây giờ có bậc lớn hơn hoặc bằng n chia 2. N của em là bằng mấy nhở? Nào n bằng mấy? Chúng ta có mấy đỉnh? 1 2 3 4 5 6 đỉnh. 6 đỉnh. N bằng 6. Như vậy suy ra n chia 2 bằng 3. Nếu như tất cả các đỉnh có bậc lớn hơn hoặc bằng 3 thì có chương trình Hamitơ. 2, 4 đều lớn hơn bằng 3. Ok. Có chương trình Hamilton nhá.
Vậy thì bây giờ chu trình Hamilton là gì? Các em sẽ vẽ được một cái chu trình nào đó đi qua tất cả các đỉnh mà mỗi đỉnh chỉ một lần thôi. Thầy thử vẽ nhá. Thầy xuất phát từ đỉnh A đi chẳng hạn. Thầy đi qua đỉnh B rồi đi qua đỉnh B chưa? Thầy muốn đi qua điểm tiếp theo là đỉnh C đi. Ở đỉnh D đi. Đỉnh nữa là đỉnh E. Đỉnh nữa là đỉnh F và đỉnh nữa là đỉnh C. Đấy, như vậy đã đi qua tất cả các đỉnh, mỗi đỉnh một lần rồi nhá. Rồi bây giờ nó quay về A là thành một chu trình. Quay về A. Được chưa? Thằng A, thằng duy nhất đặc biệt bởi vì nó là điểm đầu và điểm cuối. Rồi có chương trình Hamitơ. Xong.
Thế mà nếu như em áp dụng cái định lý này cho cái hình vẽ thứ hai thì nó lại không đúng. Tức là nếu như em dùng định lý này thì em lại thấy nó, nó thằng hình thứ hai nó không có chương trình Hamitơ. Cho nên thầy mới nói là thằng này chỉ suy ra được thôi. Nếu có điều này thì suy ra nhá. Nhưng nó không bao quát được tất cả trường hợp. Vậy trường hợp này em nhìn thấy như thế nào? Đây chúng ta có 1 2 3 4 5, có 5 đỉnh. n = 5. Vậy nếu thầy áp dụng cái định lý này, n/2 là bằng 2,5. Vậy liệu rằng tất cả các đỉnh ở đây có bậc lớn hơn hoặc bằng 2,5 hay không? Thằng A có bậc là bằng 3. Thằng B có bậc là bằng 4. Thằng D có bậc là bằng 2. Thằng C bậc là bằng 4. Thằng E bậc là 3. Đấy em nhìn đấy. Rõ ràng là có thằng D bậc 2, lớn hơn hoặc bằng n/2 là 2,5. Vậy nếu theo thằng này, tức là thằng này không có chương trình Hamitơ, nhưng mà sai đấy các em. Bởi vì thằng này nó không bao quát được tất cả trường hợp nhá.
Vậy cái định lý tiếp theo của thầy đó là gì? Nếu như em nhận ra trong một đồ thị ấy có lớn hơn bằng ba đỉnh mà tất cả các cặp đỉnh không kề nhau thì mọi cặp đỉnh không kề nhau có tổng bậc lớn hơn hoặc bằng n thì sẽ có chương trình Hamitơ. Bậc, xin lỗi, đó là gì ạ? Các đỉnh không kề nhau. Cặp đỉnh không kề nhau là gì? Tức là cặp đỉnh không có kết nối với nhau. Thằng A và B kề nhau. Thằng A, E kề nhau bởi vì có kết nối, nhưng thằng E và D không kề nhau. Ở đây chúng ta có bậc của E rồi. Mọi cặp nhá. Mọi cặp bậc, xin lỗi, mọi cặp đỉnh không kề nhau. Ở đây chúng ta chỉ có một cặp là E và D thôi. Cộng bậc của D bằng mấy nhở? Bậc E là 3, bậc D là 2. Như vậy bằng 5. 3 + 2. Như vậy nó lớn hơn hoặc bằng n chưa? n chúng ta bằng 5. Lớn hơn hoặc bằng n. Rồi nó sẽ có chu trình Hamitơ. Ok không nào?
Vậy thì sau này nếu như em thử cái định lý này nhá. Định lý này mà em thấy nó chưa có chương trình Hamitơ thì em phải thử tiếp cái định lý này xem nếu nó có các cặp gì ạ? Các cặp đỉnh không kề nhau. Em cộng xem nó bằng n hay không. Đấy. Ờ bây giờ thử xem nó có chu trình Hamilton nào nhá. Từ A thầy đi về B đi. Điểm A vẫn là điểm xuất phát. Ờ đi qua B rồi. Thầy đến E, thầy đến gì ạ? Đây đi như vậy không nhỉ? Đi đến E xong đi ra C à đi về A không được, không đi qua D. Vậy thầy không đi với E nữa mà thầy đi với D đi được không? Ok. Từ D thầy đi về C. Từ C thầy đi về E. Đó. Như vậy thầy đã đi qua được tất cả các đỉnh, mỗi đỉnh một lần rồi nhé. Rồi từ C bây giờ chỉ cần đi về A nữa là xong. Thằng A, thằng ngoại lệ đúng không? Thằng A là thằng khởi đầu và kết thúc thì nó được hai lần. Tất cả các đỉnh còn lại chỉ được một lần thôi. Chấm hết. Rồi chương trình Hamilton đó là đường đi mà đi qua tất cả các đỉnh, mỗi đỉnh một lần.
Bây giờ mình cùng vào luôn bài toán đó là liên quan đến chương trình Hamilton nhá. Thầy nói lại này. Đi thi hầu như tất cả các bài mà liên quan đến chu trình Hamitơ, mình không cần nhận diện có hay không. Ok chưa? Ở bài toán số 1 chúng ta cũng có hai bài toán thôi. Bài toán số 1 này. Công ty vận tải cần giao hàng đến tất cả các thành phố A, B, C, D, E. Chi phí di chuyển giữa các thành phố được mô tả như hình vẽ và xe giao hàng của công ty xuất phát từ một trong năm thành phố trên, đi qua tất cả các thành phố còn lại đúng một lần, sau đó trở lại thành phố ban đầu. Vậy đây chính là chu trình Hamilton rồi đúng không? Đi qua tất cả các đỉnh còn lại và quay trở lại đỉnh ban đầu. Vậy nó là chu trình. Chu trình Hamitơ. Không cần nhận diện đâu. Đấy, tìm chi phí thấp nhất của xe giao hàng. Ok, để giải quyết các bài toán về chương trình Hamitơ thì thầy sẽ cho các em hai phương pháp.
Nào, bây giờ để mà, để mà gì nhỉ? Để mà có được một chu trình Hamitơ, thầy giả sử em đi từ đỉnh A đi. Em chọn đỉnh bất kỳ là đỉnh A nha. Đi từ đỉnh A này thì nó phải đi qua mấy đỉnh nữa? Có một này, có hai này, có ba, có bốn đỉnh nữa đúng không? Vậy nó sẽ đi qua đỉnh số 1, đi qua đỉnh số 2, đi qua đỉnh số 3, đi qua đỉnh số 4 và nó quay trở lên A đúng không nào? Tổng cộng có năm đỉnh mà em nhìn thấy, mỗi đỉnh sẽ có mấy bậc là mấy đây? Mỗi đỉnh sẽ có hai kết nối. Như vậy mỗi đỉnh bậc là 2. Mỗi đỉnh bậc là 2. Vậy thì bây giờ chúng ta phải làm sao để bỏ đi tất cả các cái, các cái cạnh không cần thiết để các cái đỉnh đều có bậc là 2. Vậy phương pháp một, phương pháp là phương pháp, phương pháp số 1 đó là em sẽ bỏ cạnh một cách hợp lý. Đấy, bỏ cạnh một cách hợp lý để em ra được chương trình Hamitơ. Cái phương pháp số hai đó em sẽ gì ạ? Dùng phương pháp liệt kê. Phương pháp liệt kê thì đây là cái phương pháp nó láng giềng gần nhất nhá. Láng giềng thôi, không cần nhớ được phương pháp liệt kê cho các em nhiều cái định nghĩa quá lại quên. Một là bỏ cạnh hợp lý để tìm quãng đường nhỏ nhất, hai là liệt kê. Ở bài toán này chúng ta sẽ dùng phương pháp gì đây? Ờ bài này thầy chữa bằng phương pháp bỏ cạnh hợp lý nhá. Bài sau thầy sẽ dùng phương pháp liệt kê. Ừ.
Rồi, bỏ cạnh hợp lý là gì? Bây giờ thầy phải bỏ đi các cạnh để làm sao tất cả các bậc nó phải bậc hai. Các đỉnh nó về bậc hai. Thế thì ở đây thằng A đang là đỉnh bậc 3 này. Thằng B bậc 3. Thằng C bậc 3. Thằng D bậc 3. Có thằng E bậc 4. Như vậy làm sao để thầy phải bỏ được ờ thằng A, thằng B, thằng C, thằng D một kết nối đi nhỉ? Và thằng E phải bỏ hai kết nối. Đấy. Thế với cái hình vẽ này rất quen thuộc rồi nhá. Đây là kinh nghiệm thôi. Đây là kinh nghiệm thôi. Với một cái hình nó là dạng hình tứ giác và có một đỉnh bên trong như thế này này. Chúng ta sẽ bỏ như thế nào? Chỉ có cách đó là bỏ một cạnh bên ngoài và hai cạnh bên trong đối diện thì nó mới thỏa mãn. Đó là tất cả các đỉnh bên ngoài sẽ mất đi một bậc và thằng bên trong mất đi hai bậc. Tất cả đỉnh đây là bậc ba. Nếu nó mất đi một bậc thì còn bậc hai. Và thằng này bậc 4, mất hai bậc còn bậc hai. Em nhìn vào xem. Em nhìn vào xem. Vậy chúng ta còn thằng này bậc mấy đây? Thằng này bậc hai. Thằng này còn hai kết nối là bậc hai. À thằng này còn hai kết nối là bậc hai. Thằng này còn hai kết nối là bậc hai. Và thằng E cũng chỉ còn hai kết nối là bậc hai. Đấy và em nhớ cái định dạng hình vẽ này cho thầy. Nếu có một tứ giác và một đỉnh bên trong nối với tất cả các đỉnh thì chúng ta sẽ bỏ đi một cạnh và hai cạnh đối bên trong, nó sẽ thỏa mãn để tất cả các đỉnh là bậc hai.
Rồi vậy thì thầy cần bỏ như sau. Đây này. Nhớ đấy. Một hình vẽ có nhiều chu trình và em phải lựa chọn chu trình nào nó tối ưu nhất, tức là nó nhỏ nhất. Bây giờ để mà thầy bỏ được thì như thầy nói, thầy sẽ bỏ cái cạnh AB và bỏ nốt hai cạnh đối là EC và ED. À tất nhiên đó là gì ạ? Để mà quãng đường đi ngắn nhất thì phần bỏ nó phải nhiều nhất. Vậy em tính cho thầy xem thằng này mình đã bỏ được bao nhiêu rồi. Nào bấm máy tính đi. Đây có máy tính chưa? Nhìn có rồi. Thằng AB là bằng bao nhiêu? Thằng AB bằng 7. EC bằng mấy? 6, 9. Như vậy em bỏ được 22 đúng không? Vì sao thầy phải tính ra? Bởi vì không chỉ có một cách bỏ ở đâu, chúng ta có bốn cạnh bên ngoài cơ mà. Bây giờ thầy bỏ AB, thầy bỏ BC được không? Được. Vậy cách thứ hai là thầy bỏ thằng BC. Bỏ BC thầy sẽ bỏ thêm hai cạnh đối với nó bên trong. Đấy. Như vậy đó là bỏ EA cộng với ED. Bằng bao nhiêu đây nào? BC bằng 9 cộng 6 + 9. Như vậy ở đây bỏ được 24. Ok. Tiếp tục nào. Các bạn tự làm cho thầy nhá. Chúng ta bỏ đi cạnh đó là ED. Xin lỗi, cạnh CD. Bỏ đi CD thầy sẽ bỏ thêm hai cạnh đối bên trong. Nhớ đấy. Đây là cái kinh nghiệm làm thôi. Sau này em gặp hình này thì em cứ bỏ giống thầy nhé. CD sẽ cộng với BE và cộng cho AE. 5 + 6 là 11. 11 + 10 là 21. Như vậy bỏ đi được 21. Rồi cách bỏ cuối cùng của em đó là bỏ cạnh AD kết hợp với cạnh BE và EC. AD cộng cho BE cộng cho EC mình được là bao nhiêu nhỉ? Như vậy thầy bỏ được đó là 7 + 10 là 17. 17 + 6 = 23. Rồi, chung ghi lại, thầy có bốn cách bỏ các cạnh để được chu trình Hamilton. Nhưng mà cách bỏ được nhiều nhất chính là cách này. Bỏ được nhiều nhất như vậy còn lại ít nhất. Còn lại ít nhất tức là quãng đường tối ưu nhất. Vậy suy ra thỏa mãn chu trình. Rồi như vậy thầy lựa chọn đó là bỏ BC, EA. BC, E, bỏ thằng này đi. Bỏ thằng này đi. Bỏ thằng này đi nhá. Thầy được chu trình như sau. Chương trình của mình sẽ đó là đi từ A đến B. Đi từ B tới E. Đi từ E tới C. Đi từ C tới D và đi từ D tới A. Được chưa? Đấy, chương trình của mình như thế. Chương trình tối ưu nhất là từ A đến B tới E, từ C tới D tới A. Tổng quãng đường của nó bằng bao nhiêu? 7 cộng 6 + 5 cộng 7. Đấy. 7 + 10 + 6 + 5 + 7 bằng 35 à. 7 + 10 + 6 + 5 + 7 à kết quả là 35. Được chưa? Xong rồi đấy.
Vậy đây là cách đầu tiên nhá, nhá. Cách đầu tiên là cách bỏ, bỏ cạnh hợp lý. Vậy nếu sau này em gặp một cái hình như này em không cần phải dùng phương pháp liệt kê mà em cứ bỏ cạnh cho thầy. Đấy, bỏ cạnh làm sao để đưa được về tất cả là bậc hai. Tuy nhiên có những cái bài ấy, hình vẽ nó rất phức tạp và rất khó bỏ. Vậy thì chúng ta phải nghĩ đến phương pháp tiếp theo là phương pháp liệt kê nhá. Phương pháp một các em hiểu bỏ như thế nào rồi. Sang bài thứ hai thầy sẽ nói vì sao thầy không thể bỏ được mà thầy phải dùng liệt kê.
Rồi, sang bài thứ hai. Bài cuối cùng. Đề bài này. Một trò chơi điện tử có quy định như sau: có sáu trụ A, B, C, D, E, F với số lượng các thử thách. Đây, các thử thách nhá. Được mô tả trên hình vẽ. Người chơi xuất phát từ một đỉnh trụ nào đó phải đi qua tất cả các trụ còn lại. Mỗi khi đi qua một trụ thì sẽ bị phá hủy và không thể quay trở lại. Được chưa? Nhưng người chơi vẫn phải trở về trụ ban đầu. Như vậy cái trụ ban đầu thầy gọi giả sử bằng A đi. Em tích trụ nào cũng được nhá. Thầy cứ gọi là A cho dễ. Đấy, nó đi qua, cứ đến đâu nó bị phá hủy mất và nó phải đi qua tất cả các trụ cuối cùng. Giả sử nó về đây thì nó phải quay trở lại thằng A. Được chưa? Vậy đây chính là bài toán đi qua các đỉnh duy nhất một lần và là chu trình Hamitơ, chu trình. Đấy, chương trình Hamilton thì mình lại, để mà tìm được chu trình Hamilton tối ưu ấy, em lại có hai phương pháp. Phương pháp một em dùng bỏ cạnh. Phương pháp hai của em đó là em sẽ liệt kê. Vẫn chưa biết liệt kê là gì đúng không? Bài này sẽ biết. Bài này sẽ biết. Rồi tắt cái máy tính đi cái nhé.
Rồi, phương pháp liệt kê. Bỏ cạnh là gì? Bỏ cạnh là làm sao để tất cả các cái đỉnh này này nó về bậc hai. Rồi ở đây em có đỉnh ở B là bậc mấy nhở? Đỉnh B là bậc như này cho dễ này. Em đi từ đỉnh A nhá. Em đi từ đỉnh A chúng ta có bao nhiêu đỉnh nhở? Còn 1 2 3 4 5 đỉnh nữa. Vậy em phải qua đỉnh số 1 này, đỉnh số 2 này, đỉnh số 3 này, đỉnh số 4 này, đỉnh số 5 này. Vậy em quay lại đỉnh A. Em đếm xem em cần bao nhiêu cạnh. Cần một cạnh, hai cạnh, ba cạnh, bốn cạnh. 1 2 3 4 5, em cần sáu cạnh. Cần sáu cạnh mà trên hình vẽ này em đang có bao nhiêu? Em đang có một cạnh, hai cạnh, ba cạnh, bốn cạnh, năm cạnh, sáu cạnh, bảy cạnh, tám cạnh, chín cạnh, mười cạnh. Vậy em cần bỏ mấy cạnh? Có 10 cạnh. Như vậy em cần bỏ đi bốn. Bỏ bốn cạnh có dễ không nào. Đứa nào bỏ dễ nào. Khó lắm các em ạ. Không thể nào bỏ được cạnh trong bài toán này. Khó lắm. Không biết là nên bỏ như nào cho hợp lý. Như vậy với những bài toán mà các em không nhận diện được cần bỏ cạnh nào thì chúng ta sẽ sang phương pháp thứ hai đó là phương pháp liệt kê nha.
Rồi thầy dùng phương pháp liệt kê giải. Thầy dùng phương pháp liệt kê. Ở phương pháp liệt kê là gì? Thầy sẽ liệt kê theo đỉnh. Ở đây có 1 2 3 4 5 6 đỉnh. Có sáu đỉnh, thầy sẽ liệt kê sáu trường hợp. Thầy có sáu đỉnh. Thầy sẽ liệt kê sáu trường hợp. Vừa nãy thầy bỏ thì bỏ bốn trường hợp đúng không? Nói chung bài toán nào cũng sẽ có các trường hợp thôi. À liệt kê thì bằng số đỉnh nha. Rồi vậy thì liệt kê theo đỉnh. Đầu tiên thầy liệt kê trường hợp đỉnh là A. Thầy đi từ A. Ừ cái thuật toán ở đây đó là thuật toán láng giềng gần nhất nhé. Em sẽ dùng thuật toán láng giềng gần nhất. Bây giờ thầy phải nói này, láng giềng gần nhất. Đây là phương pháp để thầy tìm được cái chu trình từ một đỉnh nó tối ưu nhất. Bây giờ từ đỉnh A này, nhìn vào đây tập trung này. Láng giềng gần nhất là gì? Tức là em lựa chọn cho thầy cái thằng nào mà liên quan đến đỉnh A nó nhỏ nhất. Rồi bây giờ thầy đi từ đỉnh A có những láng giềng nào? Láng giềng tức là những thằng kết nối với nó. Ở đây có đỉnh B, đỉnh D và đỉnh C. À xin lỗi, đỉnh E, nó có ba láng giềng. Thế láng giềng nào gần nó nhất tức là bé nhất? Thì ở đây có thằng B là bé nhất. Được chưa? Vậy láng giềng với đỉnh A bé nhất là thằng B. Vậy thầy đi từ A đến B. Rồi đến B rồi. Thầy lại lựa chọn láng giềng gần nhất của B. Nào, nó có láng giềng là C là gì ạ? Là D. Có mỗi hai thằng thôi. Thằng nào bé hơn? Thằng 5 bé hơn. Như vậy thầy chọn láng giềng là thằng C nhở. Vậy từ B đi tới C rồi. Thằng C có thể có những cái điểm nào đi tới tiếp theo? Tức là láng giềng của nó là những điểm nào? Đấy, nó có D, nó có F và nó có E. Như vậy thầy sẽ lựa chọn thằng nào nhỉ? Nào thầy sẽ lựa chọn thằng nào? À thằng 7, 8, 9, 7 là nhỏ nhất. Như vậy thầy chọn thằng 7 thôi đúng không? Vậy thì nó đến gì ạ? Nó đến D. Ok, đến D rồi. Thằng D có láng giềng nào? Thằng này còn mỗi láng giềng là F thôi. Mặc định phải đi F. Xong chưa? Thằng F bây giờ chỉ còn mỗi láng giềng là thằng gì thôi? Còn mỗi láng giềng là thằng E. Làm sao về C được nữa? Còn mỗi láng giềng là E. Vậy đi E. Và từ E em lại ngược trở lại A. Xong chưa? Một chu trình Hamitơ. Rồi từ D nhá tới F và từ F tới E và từ E về A. Em tính được quãng đường này bằng bao nhiêu? Em nhập các số vào máy tính này rồi bấm những thằng màu vàng nhá. 4 + 5 cộng à 7 cộng 3 cộng 10 cộng cho 5 bằng 34. Được chưa? Vậy chu trình Hamilton tối ưu nhất với thằng A nhé. Chu trình Hamilton tối ưu nhất với đỉnh A là 34. Tiếp tục thầy sẽ đi tìm chu trình Hamilton tối ưu nhất với đỉnh B thông qua thuật toán láng giềng gần nhất. Ta xóa
Thằng này đi. Đấy. Liệt kê trường hợp thứ hai là với đỉnh B. Xuất phát từ đỉnh B. Láng giềng gần nhất của nó đâu? Nó có A này, có D này, có C này, nhưng láng giềng lớn nhất của nó là số, nhất là 4. Vậy đi đến A. Rồi từ A có những láng giềng nào? Nó có D và nó có E. Vậy láng giềng gần nhất của nó là số 5 này này là E đấy. Vậy từ A đi tới E. Được chưa? Từ E có những láng giềng nào? Nó có F và có C đúng không? Láng giềng gần nhất là thằng nhỏ hơn là 9. Vậy đi C. Rồi từ C có những láng giềng nào? Từ C nó có láng giềng D và F nữa thôi đúng không ạ? Không thể về B. B mất rồi nhá. Đi rồi. Như vậy chúng ta lựa chọn láng giềng gần nhất nó phải là thằng nào đây? Nó phải là thằng D hay F nhỉ? Nhiều bạn sẽ lựa chọn đó là thằng D bởi vì thằng này nhỏ hơn 8. Nhưng giả sử nhá, giả sử thì đi về đây đúng không? Thì chắc chắn thầy phải đi qua thằng F nữa bởi vì mỗi đỉnh phải đi qua một lần. Đấy. Vậy nếu khi mà thầy đi tới đỉnh F thầy không thể trở về B được nữa. Vậy nó không phải là chương trình 20. Vậy đến trường hợp này thuật toán láng giềng gần nhất nó không cho phép em làm nữa rồi thì em phải đi cố gắng làm sao để được 20. Vậy trường hợp này khi mà tới đây tới C nhá, chọn láng giềng gần nhất thì nó không thỏa mãn 20. Vậy mình không làm như vậy nữa. Chúng ta bắt buộc chỉ có còn một cách đó là đi F về D và B nó mới thỏa mãn là 24. Được chưa? Vậy thầy phải đi F rồi tới D sau đó trở lại gì ạ? Sau đó trở lại trở lại B. Ok chưa các em nhá? Tới C bắt buộc thầy phải đi F. Đấy. Từ F bắt buộc về D và từ D bắt buộc sẽ về về B. Được chưa? Vậy đây là chu trình tối ưu nhất nhá. Với đỉnh B em bấm xem được là bao nhiêu. Cộng thằng màu vàng này. 4 + 6 cộng 3 cộng 8 cộng 9. Ô thiếu này. Ờ đúng chưa nhỉ? À đúng rồi. Cộng 9. 4 + 6 + 3 + 8 + 9 + 5 bằng 35. Đấy em đếm cho thầy đủ sáu cạnh là được. Đủ sáu cạnh chưa? 1 2 3 4 5 6 đúng sáu cạnh rồi đấy nha. Xong đến thằng B tiếp tục thầy sẽ đi gì ạ? Liệt kê với thằng C. Mệt nhờ. Từ thằng C nào, thuật toán láng giềng gần nhất như sau. Nó có mấy thằng? Nó có bốn thằng láng giềng. Thằng gần nhất là thằng 5 là B. Đấy. Sau bài này làm nhanh nhá. Đến B này. Từ B chúng ta có thể đi A hoặc D. Vậy láng giềng gần nhất là thằng A. Vậy từ B đến A. Từ A nó có thể đi D, nó có thể đi E. Như vậy thầy sẽ chọn láng giềng gần nhất? Đó là thằng năm này này. Nó về E. Ờ từ E bây giờ thuật toán láng giềng gần nhất nó không thỏa mãn rồi bởi vì nếu em chọn láng giềng gần nhất thì nó quay về C là 0,2. Vậy bắt buộc em phải DF. Ứ, bắt buộc em phải DF. Và từ F em bắt buộc phải đi D thì mới về C được đúng không? Bắt buộc phải đi D thì mới về C được. Đó. Từ D về C. Đó. Vậy chương trình này em bấm cho thầy xem đúng sáu cạnh chưa? 1 2 3 4 5 6 đúng sáu cạnh rồi. Bấm máy tính xem được bao nhiêu. 4 + 5 + 7 cộng 3 cộng được bằng 34. Ô nó bằng thằng đầu tiên nhỉ. Được chưa? Rồi. Liệt kê được đến thằng à thằng gì rồi? Liệt kê được đến thằng C rồi chúng ta liệt kê tiếp theo đó là thằng E nhá. Đến thằng E này. E này láng giềng gần nhất đâu? Đây 5. Xong chưa? Đó. Vậy đến A này, đi thi các em chỉ cần lấy cái gì ạ? Lấy cái bút màu màu thôi, màu vàng thôi. Em tô vào những cái cạnh mà chúng ta đi. Ấy rồi đến A này. Láng giềng gần nhất đâu? Là số 4 đây này. Vậy về B đến thằng B rồi. Láng giềng gần nhất của em đâu? Nó có thằng 5 này là nhỏ hơn 6 đúng không? 5. Như vậy nó phải về C. Rồi nếu như thầy đi như thế nhá. Nếu đi thầy đi như thế. Từ thằng C thầy đi như nào để về được thằng E thì thầy phải đi D sau đó về F và về E. Được chưa? Ok. Đang ngược C. Bây giờ bắt buộc không có thuật toán láng giềng gì nữa. Nó chỉ còn một cách là đi D, đi F và V thôi. Đấy. Đi D, D đi F và V. Rồi cộng tất cả màu vàng lại khi mà chúng ta làm quen rồi thì em liệt kê một cạnh một đỉnh nó cực kỳ nhanh thôi nhá. 4 + 5 cộng 7 cộng 3 cộng 10 cộng 5 bằng 34. Đấy lại được 34 rồi đấy. Em liệt kê được bốn cái đỉnh ở ngoài rồi nhá. 1 2 3 4 em được là bao nhiêu rồi? Em được là nhỏ nhất là 34. Chúng ta đang muốn tính chu trình nhỏ nhất. Bây giờ tiếp tục chúng ta còn hai thằng D và F thôi. Em liệt kê nốt sau. Ở cái đáp án bài toán này thì là 34 đấy. Bởi vì khi em lựa chọn D và F thì kết quả nó vẫn không nhỏ hơn được 34. Rồi thầy sẽ tiếp tục với thằng gì ạ? Thằng gì đây? Thằng D nhá. Thằng D. Bây giờ láng giềng gần nhất của nó là gì? Láng giềng gần nhất là 3. Ok. D tới F. Láng giềng gần nhất của F chúng ta có là số 8. Như vậy đó tới C. Được chưa? C là láng giềng gần nhất của nó là gì? Là số 5 này tức là tới đỉnh B. Từ B này. Từ B chúng ta bây giờ phải làm gì đây? Nhớ rằng chúng ta đang xuất phát từ đỉnh D các em ạ. Đúng không? Đang xuất phát từ đỉnh D. Bây giờ nếu như vừa nãy thầy đến đỉnh B nhá thì còn cách nào để quay trở lại được đỉnh D không? B chắc chắn bây giờ chỉ còn có thể đi được A. A thì chỉ còn đi đến E. Như vậy nó không thỏa mãn để quay trở lại được đỉnh D. Vậy thầy sẽ không đi tới đỉnh B nữa. Đúng không? Đỉnh đỉnh B là không thỏa mãn được 2 rồi. Thầy không đi tới đỉnh B. Được chưa? Chỗ này thầy không đi tới đỉnh B nhé. Ok chưa? Không đi tới đỉnh B. Rõ ràng thằng C này khi mà tới đỉnh B nó không thỏa mãn thì chỉ còn cách duy nhất là tới đỉnh E thôi. Đấy. Tới đỉnh E rồi bây giờ không có láng giềng gần nhất gì cả. Chỉ có đến đây, đến đây và về đây thôi thì mới được 20 thôi nhỉ. Vậy thì chắc chắn nó phải từ E về A. Từ A đến đâu? Từ A đến B. Và từ B quay trở lại D chấm hết. À bấm cho thầy máy tính xem chu trình này được là bao nhiêu nhé. Bấm tất cả những ông màu vàng thì được như sau này. 4 + 6 + 3 cộng 8 cộng 9 + 5 em được kết quả là 35. Đấy em thấy cứ đủ sáu cạnh là được. Được chưa? 35. Rồi giờ thầy thử thằng cuối cùng thằng F đúng không? Giết thằng F cho thử thôi. F láng giềng gần nhất của nó là đâu? Láng giềng gần nhất của F là D. Rồi D. D láng giềng gần nhất đâu? Chỉ có số 6 này thôi. Rồi B, thằng B bây giờ láng giềng gần nhất đâu? Thằng B láng giềng gần nhất của nó là A bởi vì chỉ còn 4 và 5 thôi. Vậy nếu như là A nhá, nếu như là A, nếu như là A này thì nó sẽ như thế nào? Nó sẽ tiếp tục về E. Về E rồi lên C. A về lại được F thỏa mãn chọn luôn. Vậy tới A thỏa mãn rồi. B tới A. Từ A chỉ còn cách là đi tới E thôi. Từ E chỉ còn cách lên C thôi. Và từ C chắc chắn là về được về được F. Được chưa? Chương trình 24 từ đỉnh S, bấm máy tính tất cả những ông màu vàng này 4 + 6 + 3 cộng 8 + 9 bằng 35. Rồi đây là tất cả những chương trình Hamilton tối ưu nhất với từng đỉnh mà thầy đã liệt kê ra. Thì em xem xem cái chu trình nào nó bé nhất. Ở đây có chu trình bé nhất là 34. Vậy em suy ra luôn chu trình bé nhất, chu trình ờ tối ưu nhất kết quả là 34. Đấy. Trong trường hợp thầy giải thích lại một lần nữa. Trong trường hợp bài toán này có 10 cạnh mà cần bỏ đi bốn cạnh để được sáu cạnh thì nó rất là khó. Thì chúng ta sẽ dùng phương pháp liệt kê với thuật toán láng giềng gần nhất. Chọn một đỉnh trong tất cả các đỉnh này rồi đi láng giềng gần nhất để lựa chọn đỉnh tiếp theo nhá. Chúng ta có sáu đỉnh thì phải sáu trường hợp và chọn trường hợp nào nó bé nhất là được. Ok chưa các em? Rồi. Bài giảng ngày hôm nay thầy xin phép dừng tại đây. Thầy đã đi qua phần lý thuyết đồ thị với ba dạng bài chính. Đó là quãng đường ngắn nhất đi từ A tới B, các bài toán liên quan đến chương trình Euler và các bài toán liên quan đến chương trình Hamilton. Thì đây là ba dạng bài duy nhất nha. Ba dạng bài này phục tất cả các bài tập liên quan đến quãng đường ngắn nhất rồi thì các em chỉ cần xem lại và làm bài tập là xong. Chúc các em sẽ học tốt trong cái dạng bài này và hẹn gặp lại ở trong những nội dung tiếp theo.