Đồ thị: Một biểu đồ bao gồm các nút và cạnh.

Node: Các "đối tượng" mà đồ thị kết nối được gọi là các nút. Trong Spider Web, các nút là các vòng tròn.

Edge: Một cạnh là một kết nối trong biểu đồ giữa hai nút. Trong Spider Web, các cạnh là các đường.

Đường dẫn: Đường dẫn là một chuỗi các cạnh được kết nối với nút bắt đầu và nút kết thúc.

Đường dẫn Eulerian: Đây là một đường dẫn sử dụng mỗi cạnh trong đồ thị chính xác một lần.

Mục tiêu trong trò chơi này là tìm ra một con đường Eulerian.

Những con đường Euler trong cuộc sống hàng ngày là gì?

Cái tên "Euler" nghe có quen thuộc không?

Chu kỳ: Chu kỳ là một đường dẫn kết thúc trên nút mà nó bắt đầu.

Chu kỳ Eulerian: Đây là một con đường Euler cũng là một chu kỳ. Chọn "Chu kỳ" trong trò chơi của chúng tôi ở trên và giải pháp sẽ luôn là Chu kỳ Eulerian!

Chu kỳ: Con đường chiến thắng sẽ luôn kết thúc trên nút mà chúng bắt đầu.

Đường dẫn: Đường dẫn chiến thắng sẽ không kết thúc trên nút mà chúng bắt đầu.

Ngẫu nhiên: Đồ thị có thể cho phép một chu kỳ Euler hoặc một đường đi Eulerian. Con đường chiến thắng có thể hoặc không thể kết thúc trên nút mà chúng bắt đầu.

Thách thức: Đồ thị thủ công nơi các cạnh đi qua và do đó các cây cầu không rõ ràng để phát hiện.

Hãy nghĩ về mỗi lần di chuyển như "ra" khỏi nút bạn đến và "vào" nút bạn đi đến. Hầu hết các nút sẽ tuân theo mô hình ghép nối này, vì vậy chúng sẽ có mức độ chẵn.

Khi bạn bắt đầu trò chơi, cạnh đầu tiên bạn đánh dấu là di chuyển "ra" khỏi nút bắt đầu. Điều này vẫn chưa được ghép nối khi bạn chơi trò chơi.

Để tạo chu kỳ Eulerian, cạnh cuối cùng bạn đánh dấu là di chuyển "vào" nút bắt đầu. Điều này tạo ra một cặp với bước di chuyển đầu tiên, có nghĩa là nút bắt đầu có mức độ chẵn.

Nếu Đường dẫn Eulerian của đồ thị không phải là một chu kỳ, cạnh cuối cùng bạn đánh dấu là một di chuyển không ghép nối "vào" một nút không phải là nút bắt đầu. nút bắt đầu vẫn ở mức độ lẻ và nút kết thúc cũng sẽ có mức độ lẻ.

Không.

Tại sao?

Khi nào một con đường hoặc chu kỳ Euler tồn tại?

Vâng, một cái gì đó có thể đi sai. Ví dụ:

     2   4  
    / \ / \ 
   1---3---5

Mức độ của tất cả các nút là 2 ngoại trừ nút 3 có độ 4. Vì vậy, tất cả các mức độ đều đồng đều và chúng ta có thể bắt đầu ở bất cứ đâu. Chúng ta hãy bắt đầu từ nút 1 và đi đến nút 3 và chúng ta hãy thả tất cả các cạnh đã được đi qua.

     2   4  
    / \ / \ 
   1   3---5

Cạnh 3-2 trở thành cây cầu. Vượt qua và loại bỏ cạnh này 3-2 tạo ra một biểu đồ bị ngắt kết nối

     2   4  
    /   / \ 
   1   3---5

mà không thể hoàn toàn vượt qua được nữa. Do đó, người ta nên tiếp tục từ 3 đến 4 hoặc đến 5 để hoàn thành chu kỳ Eulerian.

Làm thế nào người ta có thể ngăn chặn việc đi qua một cây cầu?

Có thuật toán nào hiệu quả hơn không?

     2   4  
    / \ / \ 
   1---3---5

Bởi vì khi một người đến một nút độ chẵn, thì một số lẻ các cạnh đính kèm đã được sử dụng.

Tại sao?

Chẵn − lẻ = lẻ, do đó còn lại một số lẻ các cạnh không sử dụng. Một số lẻ luôn không phải là số không, vì vậy có ít nhất một cạnh không sử dụng có thể được sử dụng để rời khỏi nút đó. Do đó, người ta sẽ tự động kết thúc ở nút độ lẻ cho dù tất cả các cạnh đã được sử dụng hay chưa.

Tất nhiên, người ta có thể kiểm tra mức độ của mỗi nút cho đến khi người ta tìm thấy một nút mức độ lẻ. Đây là một cách mà không cần đếm.

Người ta có thể chọn bất kỳ nút nào. Nếu mức độ của nó là kỳ lạ, thì người ta đã tìm thấy một. Nếu không, thì người ta bắt đầu tại nút này để vẽ một chu kỳ. Nó sẽ kết thúc ở một nút độ lẻ, sau đó người ta đã tìm thấy một nút bậc lẻ hoặc một nút sẽ kết thúc ở nút bắt đầu. Nếu vậy, thì người ta bỏ qua tất cả các cạnh được sử dụng và thực hiện lại điều đó, tức là chọn một nút và vẽ một đường dẫn hoặc chu kỳ. Điều này tiếp tục cho đến khi người ta tìm thấy một nút độ lẻ hoặc không còn các cạnh không sử dụng nữa. Sau đó, tất cả các nút có một mức độ chẵn.