10.2 Graph Terminology and Special Types of Graphs Flashcards
Adjacent vertices?
Incident edge?
Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u
and v are endpoints of an edge e of G. Such an edge e is called incident with the vertices u
and v and e is said to connect u and v.
Neighbourhood :
The set of all neighbors of a vertex v of G = (V, E), denoted by N(v), is called the neighborhood of v. If A is a subset of V, we denote by N(A) the set of all vertices in G that are adjacent
to at least one vertex in A. So,
N(A) = ⋃v∈A N(v).
Degree of vertex:
The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the
vertex v is denoted by deg(v).
Isolated vertex:
A vertex of degree zero is called isolated. It follows that an isolated vertex is not adjacent
to any vertex.
Pendant
A vertex is pendant if and only
if it has degree one. Consequently, a pendant vertex is adjacent to exactly one other vertex.
THE HANDSHAKING THEOREM
Let G = (V, E) be an undirected graph with m
edges. Then
2m = ∑ deg(v).
v∈V
(Note that this applies even if multiple edges and loops are present.)
What do we get when we add the degrees of all the vertices of a graph G = (V, E)? Each edge contributes two to the sum of the degrees of the vertices because an edge is incident with exactly two (possibly equal) vertices.
analogy between an edge having two endpoints and a handshake involving two hands.
Theorem 2:
undirected graph, magnitude of vertices with a certain kind of parity of degree.
and proof:
An undirected graph has an even number of vertices of odd degree.
Let V1 and V2 be the set of vertices of even degree and the set of vertices of odd degree,
respectively, in an undirected graph G = (V, E) with m edges. Then
2m = ∑ deg(v) = ∑ deg(v) + ∑ deg(v).
v∈V v∈V1 v∈V2
Because deg(v) is even for v ∈ V1, the first term in the right-hand side of the last equality is
even. Furthermore, the sum of the two terms on the right-hand side of the last equality is even,
because this sum is 2m. Hence, the second term in the sum is also even. Because all the terms in
this sum are odd, there must be an even number of such terms. Thus, there are an even number
of vertices of odd degree.
Terminology for directed edges:
- Adjacent
and 2 more terms.
When (u, v) is an edge of the graph G with directed edges, u is said to be adjacent to v and v
is said to be adjacent from u. The vertex u is called the initial vertex of (u, v), and v is called
the terminal or end vertex of (u, v). The initial vertex and terminal vertex of a loop are the
same.
degrees for directed edges:
In a graph with directed edges the in-degree of a vertex v, denoted by deg−(v), is the number
of edges with v as their terminal vertex. The out-degree of v, denoted by deg+(v), is the
number of edges with v as their initial vertex. (Note that a loop at a vertex contributes 1 to
both the in-degree and the out-degree of this vertex.)
Directed graph number of edges and degrees Theorem:
Let G = (V, E) be a graph with directed edges. Then
∑ deg−(v) = ∑ deg+(v) = |E|.
v∈V v∈V
Underlying undirected graph :
There are many properties of a graph with directed edges that do not depend on the direction
of its edges. Consequently, it is often useful to ignore these directions. The undirected graph that
results from ignoring directions of edges is called the underlying undirected graph.
A graph
with directed edges and its underlying undirected graph have the same number of edges.
Some Special Simple Graphs
- Complete Graphs
- Cycles
- Wheels
- n-Cubes
Complete Graphs:
A complete graph on n vertices, denoted by Kn, is a simple graph
that contains exactly one edge between each pair of distinct vertices.
Non complete:
A simple graph for which there is at least one pair
of distinct vertex not connected by an edge is called noncomplete.
Cycles
A cycle Cn, n ≥ 3, consists of n vertices v1, v2, … , vn and edges {v1, v2}, {v2, v3}, … ,
{vn−1, vn}, and {vn, v1}.
Wheels:
We obtain a wheel Wn when we add an additional vertex to a cycle Cn, for n ≥ 3, and
connect this new vertex to each of the n vertices in Cn, by new edges.
n-Cubes
An n-dimensional hypercube, or n-cube, denoted by Qn, is a graph that has vertices
representing the 2^n bit strings of length n. Two vertices are adjacent if and only if the bit strings
that they represent differ in exactly one bit position.
construct the (n + 1)-cube Qn+1
Note that you can construct the (n + 1)-cube Qn+1 from the n-cube Qn by making two copies
of Qn, prefacing the labels on the vertices with a 0 in one copy of Qn and with a 1 in the other
copy of Qn, and adding edges connecting two vertices that have labels differing only in the first
bit.
Bipartite Graphs
Definition 6:
A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint
sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2
(so that no edge in G connects either two vertices in V1 or two vertices in V2). When this
condition holds, we call the pair (V1, V2) a bipartition of the vertex set V of G.
Theorem 4 provides a useful criterion for determining whether a graph is bipartite.
and prove it
A simple graph is bipartite if and only if it is possible to assign one of two different colors to
each vertex of the graph so that no two adjacent vertices are assigned the same color.
[ Graph Colourings ]
Another useful criterion for determining whether a graph is bipartite is based on the notion
of a path
A graph is bipartite if and only if it is not possible
to start at a vertex and return to this vertex by traversing an odd number of distinct edges. We
will make this notion more precise when we discuss paths and circuits in graphs in Section 10.4
(see Exercise 63 in that section).
Complete Bipartite Graphs
A complete bipartite graph Km,n is a graph that has its vertex
set partitioned into two subsets of m and n vertices, respectively with an edge between two
vertices if and only if one vertex is in the first subset and the other vertex is in the second
subset.
see figures for all types of graphs.
Matching?
Matched in matching M ?
Maximum Matching ?
matching M in a simple graph G = (V, E) is a subset of the set E of
edges of the graph such that no two edges are incident with the same vertex.
In other words, a
matching is a subset of edges such that if {s, t} and {u,v} are distinct edges of the matching, then s, t, u, and v are distinct.
A vertex that is the endpoint of an edge of a matching M is said to
be matched in M; otherwise it is said to be unmatched.
A maximum matching is a matching
with the largest number of edges.
Matching M in a bipartite graph G = (V, E) with bipartition (V1, V2) is a complete matching from V1 to V2 if
if every vertex in V1 is the
endpoint of an edge in the matching, or equivalently, if |M| = |V1|.
To assign employees to all jobs we
seek a complete matching from the set of jobs to the set of employees.
