mở đầu về lí thuyết đồ thị một cách đơn giản mà một HS lớp 7, 8 có thể tiếp nhận được, do đó chúng tôi dựa vào cách tiếp cận của tác giả để trình bày một số khái niệm cơ bản liên quan đến lí thuyết đồ thị. Đồng thời chúng tôi cũng tham khảo thêm sách Lý thuyết đồ thị của tác giả Trần Đan Thư - Dương Anh Đức và Discrete mathematics and its applications: with combinatorics and graph theory (7th edition) của tác giả Kenneth H. Rosen để nêu các nội dung liên quan đến thuật toán tìm đường đi ngắn nhất. Trong cuốn sách Graph và giải toán phổ thông tác giả sử dụng t “Graph”, dịch t tiếng anh có nghĩa là “đồ thị”.
Tuy nhiên, vì sợ người đọc nhầm lẫn “đồ thị” ở đây là “đồ thị hàm số” nên tác giả đã để nguyên bản t “graph”. Trong luận văn này, chúng tôi sử dụng t “đồ thị” để phù hợp với nội dung chương trình GDPT 2018. Một số khái niệm cơ bản Khái niệm đồ thị Để giới thiệu và nêu về định nghĩa đồ thị, trong Graph và giải toán phổ thông đã trình bày như sau: Trong nhiều tình huống, chúng ta thường vẽ những sơ đồ gồm những điểm biểu thị các đối tượng được xem xét (người, tổ chức, đội bóng, thành 10 phố,…) và nối một số điểm với nhau bằng những đoạn đường cong (thẳng) hay những mũi tên, tượng trưng cho một quan hệ nào đó giữa các đối tượng. Các sơ đồ như vậy được dùng ở khắp nơi: sơ đồ mạch điện, sơ đồ tổ chức, sơ đồ giao thông,… Đó là những thí dụ về đồ thị.
Định nghĩa 1 - Một đồ thị là một tập hợp hữu hạn các điểm (gọi là đỉnh của đồ thị) cùng với tập hợp các đoạn đường cong hay thẳng (gọi là cạnh của đồ thị) có các đầu mút tại các đỉnh của đồ thị. Các đỉnh của đồ thị sẽ được kí hiệu bằng các chữ ; cạnh có đầu mút tại các đỉnh (cạnh nối hai đỉnh ) được kí hiệu là hay ; khi hai đầu mút của cạnh trùng nhau tại đỉnh thì ta gọi cạnh ấy là một khuyên, kí hiệu .9) Tác giả đã đưa ra một số ví dụ về hình ảnh của đồ thị trong thực tế. Cách tiếp cận của tác giả về khái niệm của đồ thị khiến cho người đọc dễ hình dung, nhất là đối với HS, điều này giúp người đọc tránh trường hợp nhầm lẫn với đồ thị của hàm số - kiến thức mà ai cũng đã t ng học trong môn Toán cấp 2,3. Trong định nghĩa ở trên, đồ thị mà tác giả nhắc đến ở đây là đồ thị vô hướng, trong định nghĩa về đồ thị vô hướng này điều quan trọng là đỉnh và cạnh của đồ thị.
Sau khi nêu định nghĩa tác giả đã đưa ra hai ví dụ sau: Hình 1. cho ta một đồ thị có 4 đỉnh và 5 cạnh và. 11 Theo định nghĩa của đồ thị, các cạnh của đồ thị thẳng hay cong, dài hay ngắn, các đỉnh ở vị trí nào đều không phải là điều quan trọng, mà điều bản chất là đồ thị có bao nhiêu đỉnh, bao nhiêu cạnh và đỉnh nào được nối với đỉnh nào. Vì vậy, đồ thị ở hình 1.1a có thể biểu diễn cách khác như trong các hình 1.
Ta nói: ba hình 1.1a, b, c biểu diễn cũng một đồ thị.2a cho ta một đồ thị có 4 đỉnh và 4 cạnh. Đồ thị này có thể biểu diễn cách khác nhau như các hình 1.2a, b, c, d biểu diễn cùng một đồ thị.9-10) Hai ví dụ trên tác giả muốn nhấn mạnh ở chỗ: Bản chất của đồ thị là đồ thị có bao nhiêu đỉnh, bao nhiêu cạnh và đỉnh nào được nối với đỉnh vào, trong hình 1.2 mặc dù nhìn vào ta thấy các đồ thị khác nhau nhưng thực chất đều biểu diễn cùng một đồ thị. Bậc của đỉnh Trong Graph và giải toán phổ thông đã trình bày định nghĩa bậc của đỉnh như sau: Định nghĩa - Một đỉnh của đồ thị được gọi là đỉnh bậc nếu nó là đầu mút của cạnh. Trong hình , và là các đỉnh bậc , các đỉnh có bậc ; 12 trong hình , các đỉnh có bậc , đỉnh có bậc ; trong hình , đều là đỉnh bậc (cô lập).
Đỉnh có bậc (mà không phải đầu mút của một khuyên) được gọi là đỉnh treo; cạnh có đầu mút ở đỉnh treo gọi là cạnh treo. Trong hình , và là các đỉnh treo, còn và là các cạnh treo.13-14) Tác giả nêu định nghĩa bậc của đỉnh dựa trên số đầu mút nối với các cạnh, thêm vào đó dựa trên các ví dụ mà tác giả đã nêu giúp người đọc cũng dễ hình dung hơn, đây một khái niệm dễ hiểu nhưng rất quan trọng. Ngoài ra còn các khái niệm liên quan như đỉnh cô lập, đỉnh treo, cạnh treo được trình bày đầy đủ trong phần phụ lục. Đường đi Định nghĩa - Trong một đồ thị , mỗi dãy cạnh nối tiếp (hai cạnh nối tiếp là hai cạnh có chung một đầu mút) được gọi là đường đi nối với , kí hiệu .9, là một đường đi nối với ; là một đường đi khác nối với , còn là một đường đi nối với.
Đường đi nối với là một đường đi hai chiều: đó là đường đi từ đến và cũng là đường đi từ đến. Khi coi đó là đường đi t đến thì là đầu đường, là cuối đường.16-17) Định nghĩa về đường đi là một định nghĩa quan trọng được sử dụng trong các khái niệm mới sau này như đường đi Euler, đường đi Hamilton… 1. Đường đi Euler Định nghĩa về đường đi Euler xuất phát t bài toán cây cầu nổi tiếng ở Nga, đó là một tình huống có thật, có hai vùng bị ngăn cách bởi một dòng sông và có hai đảo ở giữa sông, bảy cây cầu nối những vùng này với nhau như hình dưới: Người dân thách đố nhau xem thử có thể nào xuất phát t một vùng đi dạo qua khắp các cây cầu, mỗi cây cầu chỉ đi qua đúng một lần và trở về nơi xuất phát. Nhà toán học Euler đã mô hình bài toán này bằng một đồ thị, mỗi vùng là một đỉnh, mỗi cây cầu là một cạnh nối các đỉnh.
Bài toán được phát biểu lại: Hãy tìm một đường đi trong đồ thị đi qua tất cả các cạnh, mỗi cạnh đúng một lần sau đó trở về đỉnh xuất phát. Euler đã giải bài toán này và t đó đề xuất các định lí để kiểm tra xem có hay không một đường đi như vậy. Trong Graph và giải toán phổ thông, tác giả đã giới thiệu định nghĩa đường đi Euler như sau: Cho một đa đồ thị Định nghĩa - Một đường đi đơn giản t đỉnh đến đỉnh và chứa 14 mọi cạnh của (tức là đường đi chứa mọi cạnh của , mỗi cạnh chỉ một lần) được gọi là một đường đi Euler t đến .44) Ngoài ra trong sách Lý thuyết đồ thị của Trần Đan Thư – Dương Anh Đức các tác giả giới thiệu định nghĩa như sau: Xét đồ thị ( )1 Đường đi Euler là đường đi qua tất cả các cạnh của đồ thị và mỗi cạnh được đi qua đúng một lần (nếu là đồ thị có hướng thì phải tôn trọng hướng cạnh).97) Trong định nghĩa này tác giả không yêu cầu phải là đa đồ thị. (Định nghĩa về đa đồ thị được trình bày trong phần phụ lục) Điều kiện để có đồ thị có đường đi Euler được trình bày dưới định lí sau: Định lí 2 - Một đa đồ thị có một đường đi Euler t đến khi và chỉ khi là liên thông và mọi đỉnh của nó đều có bậc chẵn, chỉ tr khi và có bậc lẻ.44) Định lí 2 Cho ( ) là một đồ thị vô hướng.
Khi đó G có chứa dây chuyền2 Euler và không chứa chu trình Euler khi và chỉ khi: liên thông và có chứa đúng hai đỉnh bậc lẻ.44) Định lí 2 là điều kiện cần và đủ để một đồ thị có đường đi Euler, trong sách Lý 1 Trong sách Lý thuyết đồ thị tác giả giới thiệu định nghĩa đồ thị vô hướng ( ) trong đó là tập hợp các đỉnh, là tập hợp các cạnh của đồ thị. 2 Dây chuyền ở đây đồng nghĩa với đường đi trong sách Graph và giải toán phổ thông của Hoàng Chúng. 15 thuyết đồ thị tác giả không đề cập đến đa đồ thị. Hình 1 Hình 2 Trong đồ thị trên, hình có đỉnh bậc lẻ là và nên có đường đi Euler bắt đầu và kết thúc tại hoặc , hình tất cả các đỉnh đều bậc lẻ nên không có đường đi Euler.
Đường đi Hamilton Định nghĩa về đường đi Hamilton có nguồn gốc t bài toán: Tìm đường đi trên hình thập nhị diện đều sao cho mỗi đỉnh đi qua đúng một lần và sau đó trở về đỉnh xuất phát. Các bài tập liên quan đến việc tìm đường đi và chu trình Hamilton khá khó bởi vì đến nay vẫn chưa có nhiều định lí nêu được điều kiện cần và đủ để có đường đi và chu trình Hamilton. Trong Graph và giải toán phổ thông, tác giả nói rằng: Đường đi Hamilton tương tự với đường đi Euler trong cách phát biểu: đường đi Euler qua mọi cạnh của đồ thị v a đúng một lần; đường đi Hamiton qua mọi đỉnh của đồ thị v a đúng một lần. Tuy nhiên nếu như bài toán tìm đường đi Euler đã giải quyết được trọn vẹn, thì bài toán tìm đường đi Hamilton khó khăn hơn rất nhiều.
Bài toán Hamilton có nhiều ý nghĩa thực tiễn và đã được nghiên cứu nhiều, nhưng vẫn còn những khó khăn chưa vượt qua được. Người ta chỉ mới chứng minh được một vài điều kiện đủ để một đồ thị có chu trình Hamilton.44) Trong Lý thuyết đồ thị của Trần Đan Thư – Dương Anh Đức, tác giả cũng nói 16 rằng: Không giống như đồ thị Euler, hiện nay chưa có qui tắc cần và đủ để kiểm tra xem một đồ thị có là Hamilton hay không. Các kết quả có được hiện nay chỉ là các điều kiện đủ để một đồ thị là đồ thị Hamilton hay có dây chuyền Hamilton.101) Do đó, chúng tôi xin nêu định nghĩa và các định lí liên quan như sau: Định nghĩa: Dây chuyền Hamilton là dây chuyền qua tất cả các đỉnh của đồ thị và đi qua mỗi đỉnh đúng một lần.100) Trong một số trường hợp đơn giản, ta có thể tìm đường đi (chu trình) Hamilton của , hoặc chứng minh rằng trong không có đường đi (chu trình) Hamilton, dựa vào các nhận xét sau: a) Đường đi (chu trình) Hamilton phải đi qua các cạnh có đầu mút tại những đỉnh có bậc 2.