Deck 12: Graphs

Question 1

In 1736, Euler represented the Königsberg bridge problem as a graph, marking (as recorded) the birth of graph theory.

Answer 1

True

Question 2

A graph can be shown pictorially.

Answer 2

True

Question 3

An edge incident on a single vertex is called a degree.

Answer 3

False

Question 4

To write programs that process and manipulate graphs, the graphs must be stored in computer memory.

Question 5

A graph can be represented in computer memory in only one way.

Question 6

How a graph is represented in computer memory depends on the specific application.

Question 7

The labeling of the vertices of a graph depends on a specific application.

Question 8

A graph is empty if the number of vertices is 1.

Question 9

Processing a graph requires the ability to traverse the graph.

Question 10

Traversing a graph is different than traversing a binary tree.

Question 11

In the breadth first traversal of a graph, all the nodes at any level, i, are visited after visiting the nodes at level i + 1.

Question 12

The breadth first traversal traverses the graph from each vertex that is not visited.

Question 13

In breadth first traversal, starting at the first vertex, the graph is traversed as little as possible.

Question 14

If the graph represents a highway structure, the weight can represent the distance between two places or the travel time from one place to another.

Question 15

The shortest path algorithm, also called a greedy algorithm, was developed by Dijkstra.

Question 16

A weight free tree T is a simple graph such that if u and v are two vertices in T, there is a unique path from u to v.

Question 17

A tree T is called a spanning tree of graph G if T is a subgraph of G such that V(T) = V(G), that is, all the vertices of G are in T.

Question 18

A graph G has a spanning tree if and only if G is connected; from this it follows that to determine a spanning tree of a graph, the graph must be connected.

Question 19

The topological sort algorithm can be implemented either using the depth first traversal or the breadth first traversal.

Question 20

In the breadth first topological ordering, we first find a vertex that has a predecessor vertex and place it first in the topological ordering.

Question 21

The breadth first traversal algorithm is similar to traversing a binary tree level-by-level.

Question 22

In the breadth first traversal algorithm, the root node is visited last.

Question 23

____ are used to model electrical circuits, chemical compounds, highway maps, and so on.

A) Trees
B) Pictures
C) Graphs
D) Models

Question 24

The symbol ''____'' means ''Cartesian product.''

A) *
B) ×
C) +
D) %

Question 25

Let V(G) denote the set of vertices, and E(G) denote the set of edges of a graph G, then if the elements of E are ordered pairs, G is called a directed graph or ____.

A) bigraph
B) d-graph
C) dir-graph
D) digraph

Question 26

When drawing a graph, the vertices are drawn as ____.

A) circles
B) squares
C) triangles
D) lines

Question 27

When drawing a graph, a ____ inside the circle represents the vertex.

A) name
B) block
C) vision
D) label

Question 28

In an undirected graph, the edges are drawn using ____.

A) circles
B) lines
C) arrows
D) triangles

Question 29

In a directed graph, the edges are drawn using ____.

A) lines
B) circles
C) arrows
D) triangles

Question 30

A ____ is a path in which all the vertices, except possibly the first and last vertices, are distinct.

A) simple path
B) first path
C) complex path
D) best path

Question 31

A ____ in G is a simple path in which the first and last vertices are the same.

A) circle
B) loop
C) cycle
D) recursion

Question 32

Let G be an undirected graph. G is called ____ if there is a path from any vertex to any other vertex.

A) attached
B) converted
C) completed
D) connected

Question 33

Let G be an undirected graph. A maximal subset of connected vertices is called a ____ of G.

A) component
B) property
C) solution
D) technique

Question 34

Let G be an undirected graph. G is called ____ if any two vertices in G are connected.

A) weakly connected
B) completely connected
C) strongly connected
D) inversely connected

Question 35

The statement ____ declares graphIt to be an iterator.

A) linkedListIterator graphIt<int>;
B) linkedListIterator<int> graphIt;
C) linkedListIterator.int graphIt;
D) linkedListIterator<int> graphIt<int>;

Question 36

The breadth first traversal of a graph is similar to traversing a binary tree ____.

A) node-by-node
B) branch-by-branch
C) root-to-leaf
D) level-by-level

Question 37

Let G be a weighted graph, let u and v be two vertices in G, and let P be a path in G from u to v. The weight of the path P is the ____ of all the edges on the path P.

A) sum of the edges
B) product of the weights
C) sum of the weights
D) product of the edges

Question 38

Let G be a weighted graph, a minimum (minimal) spanning tree of G is a spanning tree with the ____.

A) maximum weight
B) minimum weight
C) maximum height
D) minimum height

Question 39

There are two well-known algorithms, ____ algorithm and Kruskal's algorithm, for finding a minimum spanning tree of a graph.

A) Prim's
B) Newton's
C) Euler's
D) Orwell's

Question 40

Let G be a directed graph and V(G) = {v₁, v₂, . . ., v_n}, where n >= 0. A(n) ____ of V(G) is a linear ordering v_i1, v_i2, . . ., v_in of the vertices such that, if v_ij is a predecessor of v_ik, j does not equal k, 1 <= j <= n, 1 <= k <= n, then v_ij precedes v_ik, that is, j < k in this linear ordering.

A) ontological ordering
B) orthogonal ordering
C) topological ordering
D) typographical ordering

Question 41

A ____ is a path of nonzero length from a vertex u to u with no repeated edges.

A) cycle
B) unit of work
C) circuit
D) transit

Question 42

A circuit in a graph that includes all the edges of the graph is called a(n) ____.

A) Euler circuit
B) Newton circuit
C) Einstein circuit
D) Prim circuit

Question 43

A graph G is said to be ____ if either G is a trivial graph or G has an Euler circuit.

A) Newtonian
B) Orwellian
C) Euclidian
D) Eulerian