Suppose 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
5 phương ánCó giải thích
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
elseselect 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 D, created by above algorithm?
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: "D, B, D, C, B, A, D". Đa đồ thị có các cạnh A–B, A–D, B–C, hai cạnh song song B–D và cạnh C–D, mọi đỉnh bậc chẵn nên tồn tại chu trình Euler. Chạy thuật toán từ D: đẩy D, chọn đỉnh kề nhỏ nhất theo chữ cái là A rồi xoá cạnh D–A; từ A chỉ còn B nên đẩy B; từ B còn C và hai cạnh tới D nên chọn C; từ C còn D nên đẩy D; từ D còn hai cạnh tới B nên đẩy B; từ B còn một cạnh tới D nên đẩy D. Ngăn xếp từ đáy lên là D, A, B, C, D, B, D, và lúc này đỉnh trên cùng đã hết cạnh nên mảng kết quả nhận các đỉnh theo đúng thứ tự lấy ra: D, B, D, C, B, A, D. Dãy "D, A, B, C, D, B, D" chính là thứ tự các đỉnh được đẩy vào, còn mảng kết quả được ghi khi lấy ra nên đảo lại. Dãy "D, B, C, D, B, A, D" đòi lúc đứng ở B lần đầu phải đẩy sang D trong khi cạnh B–C vẫn còn, trái luật chọn đỉnh kề nhỏ nhất theo chữ cái. Dãy "D, C, B, D, B, A, D" cũng bỏ qua C ở lần đứng tại B đầu tiên. Dãy "D, A, B, C, D" chỉ dùng bốn cạnh, bỏ sót hai cạnh B–D nên không phải chu trình Euler.
Cùng phần 5
Suppose 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ỏiGiven 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?Có lời giảiCâu hỏiWhat data structure is used for breadth first traversal of a graph?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