Question 1

For an undirected graph, symmetric entries are required.

Accepted Answer

In an undirected graph, if there is an edge between vertex A and vertex B, then there is also an edge from vertex B to vertex A, making the adjacency matrix symmetric.

Question 2

In a breadth first search, the nodes that are lower down in the picked-up graph are visited before nodes that are higher up in the graph.

Accepted Answer

In a breadth-first search (BFS), the algorithm starts at the root (or any arbitrary node) and explores the neighbor nodes first, before moving to the next level neighbors. Thus, nodes higher up are visited before nodes that are lower down.

Question 3

Edges can be represented by an array of lists called weighted lists.

Accepted Answer

False

Question 4

Any graph that is connected and contains no cycles can be viewed as a tree by picking one of its vertices as the root.

Accepted Answer

A connected graph with no cycles is by definition a tree, and any vertex in a tree can serve as the root.

Question 5

If the set of vertices is empty, the set of edges must also be empty.

Accepted Answer

In graph theory, an edge connects two vertices. If there are no vertices, there can't be any edges.

Question 6

A(n) ____________________ is data structure that consists of a set of vertices (or nodes) and a set of edges between the pairs of vertices.

Accepted Answer

The answer of A(n) ____________________ is data structure that consists...

Question 7

____________________ represent paths or connections between vertices.

Accepted Answer

The answer of ____________________ represent paths or connections between vertices....

Question 8

The edges of a graph are ____________________ if the existence of an edge from A to B does not necessarily guarantee that there is a path in both directions.

Accepted Answer

The answer of The edges of a graph are ____________________...

Question 9

A graph that contains undirected edges is known as a(n) ____________________ graph.

Accepted Answer

The answer of A graph that contains undirected edges is...

Question 10

Directed ____________________ are represented as lines with an arrow on one end.

Accepted Answer

The answer of Directed ____________________ are represented as lines with...

Question 11

The edges of a graph may have values associated with them known as their ____________________.

Accepted Answer

The answer of The edges of a graph may have...

Question 12

A graph with weighted edges is known as a(n) ____________________ graph.

Accepted Answer

The answer of A graph with weighted edges is known...

Question 13

A(n) ____________________ is a sequence of vertices in which each successive vertex is adjacent to its predecessor.

Accepted Answer

The answer of A(n) ____________________ is a sequence of vertices...

Question 14

An undirected graph is called a(n) ____________________ if there is a path from every vertex to every other vertex.

Accepted Answer

The answer of An undirected graph is called a(n) ____________________...

Question 15

The ____________________ matrix uses a two-dimensional array to represent the graph.

Accepted Answer

The answer of The ____________________ matrix uses a two-dimensional array...

Question 16

A(n) ____ is one in which |E| is close to but less than |V|².

Accepted Answer

A dense graph is one in which the number of edges |E| is close to the maximum number of edges possible, which is |V|^2 for a graph with |V| vertices.

Question 17

A(n) ___ is one in which |E| is much less than |V|².

Accepted Answer

A sparse graph is characterized by having a number of edges (|E|) that is much less than the number of vertices squared (|V|^2), indicating a low density of connections between vertices.

Question 18

In a(n) ____ search, we visit the start node first, then all nodes that are adjacent to it next, then all nodes that can be reached by a path from the start node containing two edges, three edges, and so on.

Accepted Answer

This description matches a breadth-first search, where nodes are visited level by level from the start node. Depth-first search would involve exploring as far as possible along each branch before backtracking, which is not described here.

Question 19

The following is an algorithm for a(n) ____.
Take an arbitrary start vertex, mark it identified and place it in a queue.
While the queue is not empty
Take a vertex, u, out of the queue and visit u.
For all vertices, v, adjacent to this vertex u
If v has not been identified or visited
Mark it identified
Insert vertex v into the queue.
We are now finished visiting u.

Accepted Answer

This algorithm describes the process of a breadth-first search (BFS), which uses a queue to explore vertices level by level, ensuring that all vertices at the current level are explored before moving to the next level.

Question 20

The following is an algorithm for a(n) ____.
Mark the current vertex, u, visited and enter it in the discovery order list
For each vertex, v, adjacent to the current vertex, u
If v has not been visited
Set parent of v to u.
Recursively apply this algorithm starting at v.
Mark u finished and enter u into the finish order list.

Accepted Answer

This algorithm describes a depth-first search (DFS). DFS explores as far as possible along each branch before backtracking, which is indicated by the recursive application of the algorithm for each unvisited adjacent vertex and the use of discovery and finish order lists.

Quiz 10: Graphs