Given the graph G = (V,E) and X is a vertex of G. Suppose there exists at least one Hamilton Cycle for the graph. The following is a backtracking algorithm for finding the first Hamilton cycle from the vertex X: declare an empty array H (which will contain Hamilton cycle) (1) Put the vertex X to H (2) Check if H is a Hamilton cycle then stop, else go to (3) (3) Consider the last vertex Y in H, if there is/are vertex(es) adjacent to Y, select the first adjacent vertex Z (by alphabet order) and put it to H. If there no adjacent vertex, remove Y from H and denote it as a bad selection (so you do not select it in the same way again). Go to (2). Suppose a G is given below (view picture). Which of the followings is the Hamilton cycle from the vertex A, created by above algorithm?
5 phương ánCó giải thích
Các phương án trả lời
Chọn một phương ánLời giảiChọn phương án để mở
Đáp án đúng: "a, b, c, d, e, a". Thuật toán luôn lấy đỉnh kề chưa dùng đứng đầu theo thứ tự chữ cái và chỉ quay lui khi bế tắc. Đồ thị có các cạnh a–b, a–c, a–e, b–c, b–e, c–d, c–e, d–e. Bắt đầu H chỉ có a; đỉnh kề của a là b, c, e nên chọn b; đỉnh kề của b là a, c, e, bỏ a đã có nên chọn c; đỉnh kề của c là a, b, d, e nên chọn d; đỉnh kề của d là c, e nên chọn e; lúc này H đủ năm đỉnh và e kề a nên chu trình đóng lại, không phải quay lui lần nào. "a, c, d, e, b, a" bỏ b ngay bước đầu dù b đứng trước c theo chữ cái. "a, b, c, e, d, a" chọn e trước d tại c, trái thứ tự chữ cái, và d lại không kề a nên còn không đóng được chu trình. "a, b, e, d, c, a" chọn e tại b dù c đứng trước e. "a, e, d, c, b, a" chọn e ngay tại a dù b và c đều đứng trước.
Cùng phần 5
Given a weighted graph below and you are using the Dijkstra algorithm to find the shortest path from the vertex A to the vertex F. What is the label of the vertex E when the shortest path from A to F is determined?Có lời giảiCâu hỏiGiven a graph below. What is the output of depth-first traversal from vertex B? (visit nodes in ABC order if there are some nodes having the same selection ability).Có lời giảiCâu hỏiSuppose the graph G = (V,E) satisfies the conditions for the existence of an Eulerian cycle. The following is an algorithm for finding Euler cycle from the vertex X using stack:
declare a stack S of characters (a vertex is labeled by a character)
declare an empty array E (which will contain Euler cycle)
push the vertex X to S
while(S is not empty)
{ch = top element of the stack S
if ch is isolated then remove it from the stack and put it to E
else
select the first vertex Y (by alphabet order), which is adjacent
to ch,push Y to S and remove the edge (ch,Y) from the graph
}
the last array E obtained is an Euler cycle of the graph
Suppose a multigraph G is given below (view picture). Which of the followings is the Euler cycle from the vertex B, created by above algorithm?Có lời giảiCâu hỏiCả 48 câu của chủ đề48 câu
Xuất hiện trong 1 bộ đề
Đi tiếp từ đây