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 m

    • V
      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 = [1103 2011 0200 1102]\begin{bmatrix} 1 & 1 & 0 & 3 \ 2 & 0 & 1 & 1 \ 0 & 2 & 0 & 0 \ 1 & 1 & 0 & 2 \end{bmatrix}

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