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
