Unit 7 Flashcards
1
Q
In an blank, the edges are unordered pairs of vertices, which is useful for modeling relationships that are symmetric.
A
undirected graph
2
Q
A graph is blank if the vertex set is finite.
A
finite
3
Q
A single element of V is called a blank and is usually represented pictorially by a dot with a label.
A
vertex
4
Q
If there is an edge between two vertices, they are said to be blank
A
adjacent.
5
Q
Vertices b and e are the blank of edge {b, e}.
A
endpoints
6
Q
The edge {b, e} is blank to vertices b and e.
A
incident
7
Q
A vertex c is a blank of vertex b if {b, c} is an edge.
A
neighbor
8
Q
In a simple graph, the blank of a vertex is the number of neighbors it has.
A
degree
9
Q
The blank of a graph is the sum of the degrees of all of the vertices.
A
total degree
10
Q
In a blank, all the vertices have the same degree
A
regular graph
11
Q
In a blank, all the vertices have degree d
A
d-regular graph
12
Q
A graph H = (VH, EH) is a blank of a graph G = (VG, EG) if VH ⊆ VG and EH ⊆ EG. Note that any graph G is a blank of itself.
A
subgraph
13
Q
blank are multiple edges between the same pair of vertices.
A
Parallel edges
14
Q
A graph can also have a blank which is an edge between a vertex and itself.
A
self-loop
15
Q
If a graph does not have parallel edges or self-loops, it is said to be a blank.
A
simple graph
16
Q
Let G=(V, E) be an undirected graph. Then blank the number of edges is equal to the total degree:
A
twice
17
Q
Kn is called the blank on n vertices. Kn has an edge between every pair of vertices.
A
complete graph
18
Q
Kn is sometimes called a blank of size n or an n-blank.
A
clique
19
Q
Cn is called a blank on n vertices. The edges connect the vertices in a ring.
A
cycle
20
Q
The blank, denoted Qn, has 2n vertices. Each vertex is labeled with an n-bit string. Two vertices are connected by an edge if their corresponding labels differ by only one bit.
A
n-dimensional hypercube
21
Q
Kn,m has n+m blank. The vertices are divided into two sets: one with m vertices and one set with n vertices. There are no edges between vertices in the same set, but there is an edge between every vertex in one set and every vertex in the other set.
A
vertices
22
Q
In an undirected graph, the total degree of the graph G is blank the number of edges in G.
A
2 times
23
Q
In the blank of a graph, each vertex has a list of all its neighbors. Note that since the graph is undirected if vertex a is in b’s list of neighbors, then b must also be in a’s list of neighbors.
A
adjacency list representation
24
Q
The blank for a graph with n vertices is an n by n matrix whose entries are all either 0 or 1, indicating whether or not each edge is present.
A
matrix representation
25
Two graphs are said to be blank if there is a correspondence between the vertex sets of each graph such that there is an edge between two vertices of one graph if and only if there is an edge between the corresponding vertices of the second graph.
isomorphic
26
Let G = (V, E) and G'=(V',E'). G and G' are isomorphic if there is a bijection f: V → V' such that for every pair of vertices x, y ∈ V, {x, y} ∈ E if and only if {f(x), f(y)} ∈ E'. The function f is called an blank from G to G'.
isomorphism
27
A property is said to be blank if whenever two graphs are isomorphic, one graph has the property if and only if the other graph also has the property.
preserved under isomorphism
28
Consider two graphs, G and G'. Let f be an isomorphism from G to G'. For each vertex v in G, the degree of vertex v in G is equal to the degree of vertex f(v) in G'. what is this theorem?
Degree preserved under isomorphism
29
The blank of a graph is a list of the degrees of all of the vertices in non-increasing order. Non-increasing order means that each number is less than or equal to the preceding number in the sequence.
degree sequence
30
The degree sequence of a graph is blank.
preserved under isomorphism
31
The labeling of the vertices is blank preserved under isomorphism, so two graphs can be isomorphic even if the vertices have different labels.
not a property
32
Listing the degrees of each vertex of a graph G from largest to smallest is called the degree sequence of a graph. The degree sequence is a property blank.
preserved under isomorphism
33
he degree of vertex v in graph G is the same as the degree of f(v) in G' if f is an blank between G and G'. That is, the degree of a vertex is a property preserved under isomorphism for every vertex v.
isomorphism
34
If two graphs have either a different number of edges or a different number of vertices, they are not blank.
isomorphic
35
blank of two isomorphic graphs that remain the same for every isomorphism defined between them are called properties preserved under isomorphism.
Structural properties
36
The number and degree of vertices, number of edges, and degree sequence are blank of graphs.
structural properties
37
If the blank of two graphs are the same they are isomorphic. Let G = (V, E) and G'=(V',E'). G and G' are isomorphic if there is a bijection f: V → V' such that for every pair of vertices x, y ∈ V, {x, y} ∈ E if and only if {f(x), f(y)} ∈ E'. The function f is called an isomorphism from G to G'.
structural properties
38
A blank from v0 to vl in an undirected graph G is a sequence of alternating vertices and edges that starts and ends with a vertex
walk
39
The blank is l, the number of edges in the walk.
length of a walk
40
An blank is a walk in which the first and last vertices are not the same.
open walk
41
A blank is a walk in which the first and last vertices are the same.
closed walk
42
The edges in an blank do not have a particular orientation, so an edge can be traversed in either direction. If {v, w} is an edge in an undirected graph, then a walk can have vertex v followed by w or w followed by v. Thus, if the vertices in a walk are reversed, the resulting sequence is also a walk .
undirected graph
43
In blank, the endpoints of an edge have a well-defined order. An edge (x, y) in a directed graph can only be traversed from x to y. If the graph happens to have edges (x, y) and (y, x) then a walk can go from x to y or from y to x.
directed graphs
44
A blank is an open walk in which no edge occurs more than once.
trail
45
A blank is a closed walk in which no edge occurs more than once.
circuit
46
A blank is a trail in which no vertex occurs more than once
path
47
A blank is a circuit of length at least 1 in which no vertex occurs more than once, except the first and last vertices which are the same.
cycle
48
A sequence of alternating vertices and edges that begin and end with a vertex is called a blank. You can denote the walk as a sequenced list of vertices with the understanding that there is an edge connecting adjacent vertices
walk
49
The number of blank is referred to as the length of the walk
edges
50
A walk where no blank is repeated is called a path.
vertex
51
If there exists a walk between vertex a and vertex b in a graph G, then there also exists a path in G that blank and blank.
begins with vertex a and ends with vertex b
52
If the first vertex is the same as the last vertex, the walk is called a blank. For example, .
circuit
53
If the circuit is at least three lengths and contains no repeated vertex other than the beginning and end, it is called a blank. For example, .
cycle
54
If is a walk in an blank, then so is because the edges have no defined direction. If is a walk in a blank, is not necessarily a walk.
undirected graph
directed graph
55
In an undirected graph, if there is a path from vertex v to vertex w, then there is also a path from w to v. The two vertices, v and w, are said to be blank.
connected.
56
A set of vertices in a graph is said to be blank if every pair of vertices in the set is connected.
connected
57
A graph is said to be connected if every pair of vertices in the graph is connected, and is blank otherwise.
disconnected
58
A disconnected graph can be blank into more than one connected component.
divided
59
A blank is a maximal set of vertices that is connected. The word "maximal" means that if any vertex is added to a connected component, then the set of vertices will no longer be connected.
connected component
60
A vertex that is not connected with any other vertex is called an blank and is therefore a connected component with only one vertex.
isolated vertex
61
An undirected graph G is blank if the graph remains connected after any k - 1 vertices are removed from the graph.
k-vertex-connected
62
The blank of a graph is the largest k such that the graph is k-vertex-connected. The blank of a graph G is denoted κ(G).
vertex connectivity
63
The vertex connectivity of a graph is the minimum number of vertices whose removal disconnects the graph into blank
more than one connected component.
64
An undirected graph G is blank if it remains connected after any k - 1 edges are removed from the graph.
k-edge-connected
65
The blank of a graph is the largest k such that the graph is k-edge-connected. The blank of a graph G is denoted λ(G).
edge connectivity
66
The blank of a graph is the minimum number of edges whose removal disconnects the graph into more than one connected component.
edge connectivity
67
The minimum degree of any vertex (which is easy to compute) is at least an blank for both the edge and vertex connectivity of a graph.
upper bound
68
A set of vertices in a graph is blank if there is a path between every pair of vertices in that set.
connected
69
A graph is connected if its entire blank is connected, otherwise it is disconnected.
vertex set
70
If a graph is disconnected it can be divided into its connected pieces called blank. A blank is a maximally connected set of vertices, meaning that if an additional vertex is added from the set of all the vertices in G, the collection will no longer be connected.
components
71
An blank is one that is not connected to any other vertex.
isolated vertex
72
An undirected graph G is blank if the graph remains connected after any k - 1 vertices are removed from the graph. For example, a graph is 4-vertex- connected if it is still connected after removing 3 vertices from the graph.
k-vertex- connected
73
Graph connectivity is an blank
equivalence relation.
74
A blank is an undirected graph that is connected and has no cycles.
tree
75
A blank has no particular organization of the vertices and edges.
free tree
76
A tree that appears to grow from a single vertex, the root, is called a blank.
rooted tree
77
The blank of a vertex is its distance away from the root
level
78
blank is measured by the number of edges of the shortest path between the vertices.
Distance
79
The blank of the tree is the highest level of a vertex. That is, the blank is the greatest distance any vertex is away from the root.
height
80
Given any two vertices in a tree, there is only blank between them. In particular, every vertex in a rooted tree has only one path to the root.
one path
81
Every vertex in a rooted tree has only blank to the root.
one path
82
The blank of a vertex v is the first vertex encountered on a path from v to the root.
parent
83
Every vertex in the path from v to the root is called an blank. The parent is the first encountered blank on the path.
ancestor
84
If u is the parent of v, then v is a blank of u.
child
85
If u is an ancestor of v, then v is a blank of u.
descendent
86
Vertices with no children are called blank.
leaves
87
Vertices with the same parent are called blank.
siblings
88
A blank rooted at vertex v is the tree consisting of v and all v's descendants.
subtree
89
There is a blank between every pair of vertices in a tree.
unique path
90
A leaf of a free tree is a vertex of degree blank. There is one technicality: if a free tree has only one vertex, then that vertex is a leaf.
1
91
A vertex is an blank if the vertex has degree at least two.
internal vertex
92
Any free tree with at least two vertices has at least blank.
two leaves
93
A blank is a graph that has no cycles and that is not necessarily connected.
forest
94
Sn is called a blank. It consists of a vertex connected to n vertices by a single edge.
star graph
95
A forest with c components and n vertices has blank edges where n ≥ c.
n - c
96
If G is an undirected graph with n vertices and m edges and if m < n - 1, then G is not blank.
connected
97
A common procedure performed on a tree (called a blank) is to process the information stored in the vertices by systematically visiting each vertex. As each vertex is visited, a processing step is performed which might entail a computation or outputting some data.
tree traversal
98
In a blank, a vertex is visited before its descendants.
pre-order traversal
99
In a blank, a vertex is visited after its descendants.
post-order traversal
100
Scanning every blank in a tree is called a tree traversal.
vertex
101
A tree traversal that visits a vertex blank its descendants is called a pre-order traversal.
BEFORE
102
A tree traversal that visits a vertex blank its descendants is called a post-order traversal.
AFTER
103
The tree traversal algorithms are how the computer blanks the data encoded in the tree.
reads
104
The post-order traversal is useful to count the number of blank in a tree.
leaves
105
A blank of a connected graph G is a subgraph of G which contains all the vertices in G and is a tree.
spanning tree
106
There are two common methods for finding spanning trees in a graph: blank and blank
Breadth-First Search and Depth-First Search.
107
blank is a process that systematically explores all the vertices of a graph. Breadth-first search and depth-first search are used as a subroutine for traversing a graph in many other graph algorithms.
Graph traversal
108
In the blank, starting at a root vertex, scan each neighbor and its neighbors and their neighbors. Once a neighbor has no more neighbors, back track to the previous neighbor and exhaust its neighbors.
depth-first search
109
In blank, starting at a root vertex scan each neighbor before scanning their neighbors. For example, if b and c are neighbors of the root a, scan b and c before scanning the neighbors of b.
breadth-first search
110
A blank tree is likely the preferred spanning tree when you are looking for the shortest paths from the initial (source) vertex.
breadth-first search
111
An edge e belongs to every blank if and only if removing e from the graph disconnects the graph into one or more connected components.
spanning tree
112
A blank is a graph G = (V ,E), along with a function w: E → R. The function w assigns a real number to every edge.
weighted graph
113
A blank of a weighted graph, is a spanning tree T of G whose weight is no larger than any other spanning tree of G.
minimum spanning tree (MST)
114
blank finds a minimum spanning tree of the input weighted graph.
Prim's algorithm
115
All spanning trees with n vertices has blank edges.
n - 1
116
A blank is a graph G = (V, E), along with a function w: E -->
R. The function w assigns a real number to every edge. That is, each edge has assigned to it some value called a weight.
weighted graph
117
The weight of a graph, or a subgraph, is the blank of the weights for each edge.
sum
118
A blank of a weighted graph, is a spanning tree T of G whose weight is no larger than any other spanning tree of G.
minimum spanning tree (MST)
119
An blank is not necessarily unique. That is, there can be more than one blank in a graph.
MST
