Example of Bipertite graphs

 

Examples of Bipartite Graphs

A bipartite graph is a graph whose vertices can be divided into two disjoint sets $U$ and $V$ such that every edge connects a vertex in $U$ to a vertex in $V$. No two vertices within the same set are adjacent.

---

Example 1: Simple Bipartite Graph

Consider a graph with the following sets:

• Set $U$ = {A, B, C}
• Set $V$ = {1, 2, 3}
• Edges: (A,1), (A,2), (B,2), (B,3), (C,1), (C,3)

Graph Representation

less
    A    B    C
     |  / \  |
     1    2    3

Here, edges only exist between elements in $U$ and $V$, making it bipartite.

---

Example 2: Real-Life Application - Job Assignment

• Workers: $W_1, W_2, W_3$
• Tasks: $T_1, T_2, T_3, T_4$
• Edges represent possible assignments (who can do which task):

Graph Representation

markdown
    W1   W2   W3
     |  /  \   |
    T1   T2   T3   T4

Since edges only go between workers and tasks, this is a bipartite graph.

---

Example 3: Even Cycle Graph

A cycle graph $C_n$ is bipartite if $n$ is even.
For example, $C_4$ with vertices (A, B, C, D) and edges (A-B, B-C, C-D, D-A):

Graph Representation

less
    A ----- B
    |       |
    D ----- C

• Set 1: {A, C}
• Set 2: {B, D}
• Since edges only connect vertices from different sets, this is bipartite.

---

Non-Bipartite Example

A triangle (cycle $C_3$) is not bipartite because it’s impossible to divide vertices into two sets without two vertices of the same set being connected.

---

Bipartite graphs are widely used in network flow, matchmaking, scheduling, and database systems.