Exploring Graphs and Networks

Which of the following statements best describes a directed graph?

• A graph where edges have no direction and can be traversed both ways.

• A graph where each edge has a direction, going from one vertex to another.

• A graph where all vertices are connected to each other.

• A graph with no cycles.

In a network, what is the shortest path algorithm commonly used to find the minimum distance between two nodes in a weighted graph with non-negative edge weights?

• Kruskal’s algorithm

• Dijkstra’s algorithm

• Prim’s algorithm

• Depth-first search

Which property is true for all undirected graphs?

• The sum of the degrees of all vertices is twice the number of edges.

• The sum of the degrees of all vertices is equal to the number of edges.

• Every undirected graph is a tree.

• Every undirected graph is connected.

What is the main difference between a tree and a general graph?

• A tree can have cycles, but a graph cannot.

• A tree is always directed, but a graph is not.

• A tree is a connected acyclic graph, while a general graph may have cycles and may not be connected.

• A tree must have weighted edges, but a graph does not.

Which of the following is NOT a property of a simple graph?

• No loops (edges connecting a vertex to itself)

• No multiple edges between the same pair of vertices

• Every vertex has the same degree

• Edges connect pairs of distinct vertices

In network analysis, what does the term “degree” of a vertex refer to in an undirected graph?

• The number of edges in the graph

• The number of vertices adjacent to the vertex

• The number of cycles passing through the vertex

• The total weight of all edges in the graph

Which algorithm is most suitable for finding a path between two nodes in a graph where all edges have equal weight?

• Dijkstra’s algorithm

• Breadth-first search (BFS)

• Prim’s algorithm

• Bellman-Ford algorithm

Which of the following best describes a connected graph?

• A graph where every vertex has the same degree.

• A graph where there is a path between every pair of vertices.

• A graph with no cycles.

• A graph with only one vertex.

In a network, what is a “cycle”?

• A path that starts and ends at the same vertex, with all edges and vertices (except the start/end) distinct.

• A path that visits every vertex exactly once.

• A set of edges with no common vertices.

• A path that includes every edge in the graph.