Deck 20: Graphs

Question 1

Linked lists cannot be used to implement an adjacency list.

Answer 1

False

Question 2

In a directed graph,the pairs (u,v)and (v,u)represent the same edge.

Answer 2

False

Question 3

The ____ of sets A and B is the set of all elements that are in A and B.

A) intersection
B) union
C) graph
D) reunion

Answer 3

A

Question 4

If the elements of E(G)are ordered pairs,G is called a(n)____ graph.

A) undirected
B) directed
C) weighted
D) spanning

Question 5

In a(n)____ graph,the edges are drawn using arrows.

A) pointed
B) vector
C) directed
D) undirected

Question 6

A graph G is a pair,G = (V,E),where V is a finite nonempty set called the set of ____ of G,and the elements of E are the pairs of elements of V.

A) nodes
B) branches
C) vertices
D) edges

Question 7

The implementation of a breadth first graph traversal uses a stack.

Question 8

A graph might have cycles; therefore,we might not be able to traverse the entire graph from a single vertex.

Question 9

The two most common graph traversal algorithms are depth first traversal and breadth first traversal.

Question 10

Let G be an undirected graph.Let u and v be two vertices in G.Then u and v are called ____ if there is an edge from one to the other.

A) adjacent
B) weighted
C) connected
D) shortest path

Question 11

A graph H is called a(n)____ of G if V(H)is a subset of V(G)and E(H)is a subset of E(G); that is,every vertex of H is a vertex of G,and every edge in H is an edge in G.

A) matrix
B) intersection
C) subgraph
D) union

Question 12

The depth first traversal is similar to the postorder traversal of a binary tree.

Question 13

A binary tree has no cycles.

Question 14

Y is a(n)____ of X if every element of Y is also an element of X.

A) derivative
B) subset
C) inheritee
D) shallow copy

Question 15

It is possible to design Prim's algorithm so that it is of the order O(n²).

Question 16

We can always traverse an entire graph from a single vertex.

Question 17

Graph theory started in 1736 with the ____ problem.

A) Königsberg bridge
B) Tower of Hanoi
C) Westminster
D) League of Augsburg

Question 18

The ____ of sets A and B is the set of all elements that are in A or in B.

A) intersection
B) union
C) graph
D) reunion

Question 19

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

Question 20

An edge incident on a single vertex is called a(n)____.

A) block
B) cycle
C) component
D) loop

Question 21

A maximal subset of connected vertices is called a ____ of G.

A) cycle
B) union
C) subset
D) component

Question 22

A set Y is called a(n)____________________ of X if every element of Y is also an element of X.

Question 23

A graph is called a(n)____ graph if it has no loops and no parallel edges.

A) simple
B) undirected
C) directed
D) weighted

Question 24

In a(n)____________________ graph,the tail of a pictorial directed edge is the origin,and the head is the destination.

Question 25

Two well-known algorithms,Prim's algorithm and ____'s algorithm,can be used to find a minimal spanning tree of a graph.

A) Euler
B) Dekart
C) Kruskal
D) Dijkstra

Question 26

In a graph directed G,for each vertex,v,the vertices adjacent to v are called ____ successors.

A) immediate
B) adjacent
C) path
D) parallel

Question 27

In a graph G,if the edges connecting two vertices have weights assigned to them,the graph is called a ____ graph.

A) source
B) weighted
C) spanning
D) minimal

Question 28

If two edges,e? and e?,are associated with the same pair of vertices {u,v},then e? and e? are called ____ edges.

A) parallel
B) adjacent
C) connected
D) incident

Question 29

A(n)____________________ graph G is called strongly connected if any two vertices in G are connected.

Question 30

The edges connecting two vertices can be assigned a non-negative real number,called the ____ of the edge.

A) key
B) weight
C) width
D) height

Question 31

The shortest path algorithm is also called the ____ algorithm.

A) recursive
B) minimal
C) greedy
D) spanning

Question 32

Let G be an undirected graph.Let u and v be two vertices in G.A(n)____________________ in G is a simple path in which the first and last vertices are the same.

Question 33

A minimal spanning tree of G is a spanning tree with the minimum ____.

A) path
B) cycle
C) weight
D) height

Question 34

A(n)____ tree T is a simple graph such that if u and v are two vertices in T,a unique path exists from u to v.

A) rooted
B) free
C) spanning
D) weighted

Question 35

The shortest path algorithm was developed by ____.

A) Euler
B) Kruskal
C) Prim
D) Dijkstra

Question 36

A tree in which a particular vertex is designated as a root is called a(n)____ tree.

A) spanning
B) weighted
C) free
D) rooted

Question 37

In Prim's algorithm for the minimal spanning tree,we start at a designated vertex,which we call the ____ vertex.

A) index
B) source
C) root
D) destination

Question 38

Let e (u,v)be an edge in an undirected graph G.The edge e is said to be ____________________ on the vertices u and v.

Question 39

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

A) weighted
B) spanning
C) rooted
D) directed

Question 40

The shortest path is the path with the smallest ____.

A) length
B) index
C) weight
D) key

Question 41

A graph is ____________________ if the number of vertices is zero.

Question 42

A tree T is called a(n)____________________ of graph G if T is a subgraph of G such that V(T )= V(G).

Question 43

The ____________________ traversal of a graph is similar to traversing a binary tree level by level.

Question 44

A(n)____________________ ordering of the vertices of the accompanying graph is 0,1,3,4,2,5,7,8,6,9.

Question 45

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 sum of the weights of all the ____________________ on the path P.

Question 46

____________________ algorithm builds the tree iteratively by adding edges until a minimal spanning tree is obtained.

Question 47

In a(n)_______________ graph. if ,then so

Question 48

The ____________________ algorithm gives the shortest distance for a given node to every other node in the graph.

Question 49

The starting vertex of a shortest path in a graph is called the ____________________.

Question 50

A(n)____________________ ordering of the vertices of the accompanying graph is 0,1,4,3,2,5,7,8,6,9.