Unit 7 Flashcards
In an blank, the edges are unordered pairs of vertices, which is useful for modeling relationships that are symmetric.
undirected graph
A graph is blank if the vertex set is finite.
finite
A single element of V is called a blank and is usually represented pictorially by a dot with a label.
vertex
If there is an edge between two vertices, they are said to be blank
adjacent.
Vertices b and e are the blank of edge {b, e}.
endpoints
The edge {b, e} is blank to vertices b and e.
incident
A vertex c is a blank of vertex b if {b, c} is an edge.
neighbor
In a simple graph, the blank of a vertex is the number of neighbors it has.
degree
The blank of a graph is the sum of the degrees of all of the vertices.
total degree
In a blank, all the vertices have the same degree
regular graph
In a blank, all the vertices have degree d
d-regular graph
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.
subgraph
blank are multiple edges between the same pair of vertices.
Parallel edges
A graph can also have a blank which is an edge between a vertex and itself.
self-loop
If a graph does not have parallel edges or self-loops, it is said to be a blank.
simple graph
Let G=(V, E) be an undirected graph. Then blank the number of edges is equal to the total degree:
twice
Kn is called the blank on n vertices. Kn has an edge between every pair of vertices.
complete graph
Kn is sometimes called a blank of size n or an n-blank.
clique
Cn is called a blank on n vertices. The edges connect the vertices in a ring.
cycle
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.
n-dimensional hypercube
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.
vertices
In an undirected graph, the total degree of the graph G is blank the number of edges in G.
2 times
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.
adjacency list representation
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.
matrix representation
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
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
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
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
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
The degree sequence of a graph is blank.
preserved under isomorphism
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
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
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
If two graphs have either a different number of edges or a different number of vertices, they are not blank.
isomorphic
blank of two isomorphic graphs that remain the same for every isomorphism defined between them are called properties preserved under isomorphism.
Structural properties
The number and degree of vertices, number of edges, and degree sequence are blank of graphs.
structural properties
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
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
The blank is l, the number of edges in the walk.
length of a walk
An blank is a walk in which the first and last vertices are not the same.
open walk
A blank is a walk in which the first and last vertices are the same.
closed walk
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
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
A blank is an open walk in which no edge occurs more than once.
trail
A blank is a closed walk in which no edge occurs more than once.
circuit
A blank is a trail in which no vertex occurs more than once
path
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
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
The number of blank is referred to as the length of the walk
edges
A walk where no blank is repeated is called a path.
vertex
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
If the first vertex is the same as the last vertex, the walk is called a blank. For example, <a,b,c,b,a>.
circuit
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, <a,b,c,d,a>.
cycle
If <v,w,x,s> is a walk in an blank, then so is <s,x,w,v> because the edges have no defined direction. If <v,w,x,s> is a walk in a blank, <s,x,w,v> is not necessarily a walk.
undirected graph
directed graph
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.
A set of vertices in a graph is said to be blank if every pair of vertices in the set is connected.
connected
A graph is said to be connected if every pair of vertices in the graph is connected, and is blank otherwise.
disconnected
A disconnected graph can be blank into more than one connected component.
divided
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
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
An undirected graph G is blank if the graph remains connected after any k - 1 vertices are removed from the graph.
k-vertex-connected
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
The vertex connectivity of a graph is the minimum number of vertices whose removal disconnects the graph into blank
more than one connected component.
An undirected graph G is blank if it remains connected after any k - 1 edges are removed from the graph.
k-edge-connected
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
The blank of a graph is the minimum number of edges whose removal disconnects the graph into more than one connected component.
edge connectivity
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
A set of vertices in a graph is blank if there is a path between every pair of vertices in that set.
connected
A graph is connected if its entire blank is connected, otherwise it is disconnected.
vertex set
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
An blank is one that is not connected to any other vertex.
isolated vertex
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
Graph connectivity is an blank
equivalence relation.
A blank is an undirected graph that is connected and has no cycles.
tree
A blank has no particular organization of the vertices and edges.
free tree
A tree that appears to grow from a single vertex, the root, is called a blank.
rooted tree
The blank of a vertex is its distance away from the root
level
blank is measured by the number of edges of the shortest path between the vertices.
Distance
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
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
Every vertex in a rooted tree has only blank to the root.
one path
The blank of a vertex v is the first vertex encountered on a path from v to the root.
parent
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
If u is the parent of v, then v is a blank of u.
child
If u is an ancestor of v, then v is a blank of u.
descendent
Vertices with no children are called blank.
leaves
Vertices with the same parent are called blank.
siblings
A blank rooted at vertex v is the tree consisting of v and all v’s descendants.
subtree
There is a blank between every pair of vertices in a tree.
unique path
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
A vertex is an blank if the vertex has degree at least two.
internal vertex
Any free tree with at least two vertices has at least blank.
two leaves
A blank is a graph that has no cycles and that is not necessarily connected.
forest
Sn is called a blank. It consists of a vertex connected to n vertices by a single edge.
star graph
A forest with c components and n vertices has blank edges where n ≥ c.
n - c
If G is an undirected graph with n vertices and m edges and if m < n - 1, then G is not blank.
connected
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
In a blank, a vertex is visited before its descendants.
pre-order traversal
In a blank, a vertex is visited after its descendants.
post-order traversal
Scanning every blank in a tree is called a tree traversal.
vertex
A tree traversal that visits a vertex blank its descendants is called a pre-order traversal.
BEFORE
A tree traversal that visits a vertex blank its descendants is called a post-order traversal.
AFTER
The tree traversal algorithms are how the computer blanks the data encoded in the tree.
reads
The post-order traversal is useful to count the number of blank in a tree.
leaves
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
There are two common methods for finding spanning trees in a graph: blank and blank
Breadth-First Search and Depth-First Search.
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
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
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
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
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
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
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)
blank finds a minimum spanning tree of the input weighted graph.
Prim’s algorithm
All spanning trees with n vertices has blank edges.
n - 1
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
The weight of a graph, or a subgraph, is the blank of the weights for each edge.
sum
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)
An blank is not necessarily unique. That is, there can be more than one blank in a graph.
MST
