Đồ thị: Một biểu đồ bao gồm các đỉnh (nodes) và cạnh (edges).

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

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

Path (Đường đi): Đường đi là một chuỗi các cạnh được liên kết với node bắt đầu và node kết thúc.

Đường đi Euler: Đâ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 đường đi Euler.

Những đường đi 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 trình: Chu trình là một đường đi kết thúc trên node mà nó bắt đầu.

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

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

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

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

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

Hãy nghĩ về mỗi bước di chuyển như đi "ra" khỏi node mà bạn đến từ và "vào" node mà 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ó bậc chẵn.

Khi bạn bắt đầu trò chơi, cạnh đầu tiên bạn đánh dấu là bước di chuyển "ra" khỏi node 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 trình Euler, cạnh cuối cùng bạn đánh dấu là bước di chuyển "vào" node 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ó bậc chẵn.

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

Không.

Tại sao?

Khi nào một đường đi hoặc chu trình Euler tồn tại?

Đúng, có thể xảy ra điều gì đó không ổn. Ví dụ như:

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

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

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

Cạnh 3-2 trở thành cây cầu. Đi qua và loại bỏ cạnh 3-2 này tạo ra một đồ thị không liên thông.

     2   4  
    /   / \ 
   1   3---5

mà không thể được đi ngang qua hoàn toàn 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 trình Euler.

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 node bậc chẵn, thì một số lượng 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 được sử dụng có thể được sử dụng để rời khỏi node đó. Do đó, người ta sẽ tự động kết thúc ở node bậc 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 bậc của mỗi node cho đến khi người ta tìm thấy một node bậc lẻ. Đây là một cách mà không cần đếm.

Người ta có thể chọn bất kỳ node nào. Nếu bậc của nó là lẻ, thì người ta đã tìm thấy một node. Nếu không, thì người ta bắt đầu tại node này để vẽ một chu trình. Nó sẽ kết thúc ở một node bậc lẻ, sau đó người ta đã tìm thấy một node bậc lẻ hoặc một node sẽ kết thúc ở node 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 node và vẽ một đường đi hoặc chu trình. Điều này tiếp tục cho đến khi người ta tìm thấy một node bậc lẻ hoặc không còn các cạnh không sử dụng nữa. Sau đó, tất cả các node có một bậc chẵn.