2 1 3 5 4 Use Graph G above to answer questions (a to f) below: TRUE/FALSE: The

Question

                                                       2

                                             1                                  3

                                             5                          4

Use Graph G above to answer questions (a to f) below:

TRUE/FALSE: The sequence (1, 3, 4, 3, 1) in Graph G above is a Trail. ---10 points

TRUE/FALSE: The sequence (1, 3, 5, 4) in Graph G above is not a Path. ---10 points

What is the shortest-length path between 2 and 4? ---10 points

What is the longest-length path between 2 and 4? ---10 points

TRUE/FALSE: A graph is connected if there is a path between any two vertices; otherwise, the graph is disconnected. ---10 points

TRUE/FALSE: In Graph G, the longest-length circuit is the sequence (1, 2, 3, 4, 5, 3, 1). ---10 points

Explanation / Answer

Since the picture of the graph G is not given, I am giving the definitions of the trail, path and circuit.

Walk: A walk of length in a graph is an alternating sequence of vertices and edges, , which begins and ends with vertices.

Trail:  A trail is a walk in which all edges are distinct.

Path: A path is a trail in which all vertices (except possibly the first and last) are distinct.

Circuit: A circuit is a path which ends at the vertex it begins (so a loop is an circuit of length one).

Connected Graph: A graph is connected when there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices. A graph that is not connected is disconnected.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.