10 pt 1
CP214: Discrete Structures - Graphs
Introduction
Lecture delivered by Dr. Shimaa Abdelmeguid.
Focus of the lecture: Chapter 10 of the textbook on graphs.
Outline of Topics Covered
Bipartite Graphs
Representing Graphs
Bipartite Graphs
Definition
A simple graph G is bipartite if the vertex set V can be partitioned into two disjoint subsets V
and V
such that:Every edge connects a vertex in V
to a vertex in V
.There are no edges that connect two vertices both in V
or both in V
.
An alternative characterization involves coloring: A bipartite graph can be colored red and blue so that no two adjacent vertices share the same color.
Example of a Bipartite Graph
Graph G:
Partitioning: V
= {a, b, c} (red vertices), V
= {c, e, f, g} (blue vertices).Valid coloring such that no adjacent vertices share the same color.
Non-example of a Bipartite Graph
Graph H:
If vertex a is colored red, then the adjacent vertices e, b, and f must be blue.
H is thus not bipartite since adjacent vertices cannot share the same color.
Examples of Bipartite Graphs
Example 1: Proving C is Bipartite
Vertex sets:
V
= {R
, V
, V
}V
= {V
, V
, V
}
Every edge connects a vertex in V
to a vertex in V
.
Example 2: Proving C
is Not Bipartite
C
(Triangle graph) has every vertex connected to every other vertex.Attempting to divide the vertex set leads to at least one subset containing two vertices, violating bipartite conditions.
Conclusion: C
is thus not bipartite.
Determining Bipartiteness
Given a graph to determine if it is bipartite, check if it is possible to assign colors (red and blue) to vertices such that no two adjacent vertices share the same color.
Complete Bipartite Graphs
Definition
A complete bipartite graph K
:Vertex set divided into two subsets:
V
of size mV
of size n
An edge exists from every vertex in V
to every vertex in V
.
Examples of Complete Bipartite Graphs
K
K
K
K
Edges tally: Each vertex in the first set connects to every vertex in the second set, yielding a total of m*n edges.
Star Graph as a Complete Bipartite Graph
A star graph is a specific case where one subset contains only a hub vertex, while the other contains all outer vertices.
Every outer vertex connects to the hub, no edges exist between outer vertices themselves.
Recognized as complete bipartite graph K
.
Bipartite Graphs and Matchings
Applications of bipartite graphs include matching elements of one set with another:
Job Assignments:
Vertices represent jobs and employees.
Edges represent training relationships linking employees to jobs.
Goal: Match jobs to employees to maximize the number of completed jobs.
New Graphs from Old
Definitions
Subgraph: A graph H = (W, F) is a subgraph of a graph G = (V, E) if:
W ⊆ V
F ⊆ E
A subgraph H of G is considered a proper subgraph if H ≠ G.
Example of a Subgraph
K graph and its example subgraph where W = {a, b, c, e}, and F = {{a, b}, {b, c}, {c, a}, {b, e}, {e, a}}.
Union of Graphs
Union of two graphs: Given two simple graphs G
= (V
, E
) and G
= (V
, E
):The union is a graph with vertex set V
∪ V
and edge set E
∪ E
.
Example Illustration:
Illustrated with vertex and edge sets from two graphs.
Representing Graphs
Methods of Representation: Adjacency List
Definition: An adjacency list represents a graph by listing vertices adjacent to each vertex.
Example of Adjacency List
For a simple graph the representation is:
Vertex | Adjacent Vertices
a | b, c, e
b | a
c | a, d, e
d | c, e
e | a, c, d
Example of Adjacency List for Directed Graph
Structure refers specifically to directed connectivity:
Template showing terminal and initial vertices.
Method of Representation: Adjacency Matrix
Definition: If G = (V, E) is a graph with |V| = n:
The adjacency matrix A (or A*G) is an n×n matrix where entry (i,j) is 1 if vertices V
i and V
j are adjacent, and 0 otherwise.
Example of Adjacency Matrix
Given a graph G with vertices a, b, c, d, the adjacency matrix representation:
A_G =
\begin{bmatrix}
0 & 1 & 1 & 1 \
1 & 0 & 0 & 1 \
1 & 0 & 0 & 0 \
1 & 1 & 0 & 0
\end{bmatrix}
Additional Note on Matrix Symmetry
Adjacency matrices for undirected graphs are symmetric due to bidirectional edges.
Handling Multiple Edges
For graphs with multiple edges, use matrices of natural numbers:
The entry at (i,j) indicates the number of edges between V
i and V
j.
Example of Adjacency Matrix for Multiple Edges
Where connections can be displayed as:
A_G =
Method of Representation: Incidence Matrix
Definition: Given G = (V, E) as an undirected graph with |V| = n and |E| = m:
The incidence matrix is an n×m zero-one matrix with entry (i,j) as 1 if edge e
j is incident with vertex V
i, otherwise 0.
Example of an Incidence Matrix
Based on G's vertices a, b, c, d and edges 1 to 6:
M =
\begin{bmatrix}
1 & 1 & 0 & 0 & 1 & 0 \
1 & 0 & 0 & 0 & 0 & 0 \
0 & 1 & 0 & 1 & 0 & 1 \
0 & 0 & 0 & 0 & 1 & 0
\end{bmatrix}
Summary of Topics
Review content covered:
Introduction to Graphs
Applications Areas
Graph Terminology
Special Graphs
Bipartite Graphs
Representing Graphs
Next Topic: Graph Isomorphism