Simple Graph Types

Advertisements
Advertisements

 12 total views

In previous lessons, you learned about graph models and some basic graph terminologies.

In this lesson, you will learn about simple graph types, we learned earlier that a simple graph is one in which each edge has two unique vertices.

Simple Graph Types

The following is a list of simple graph types that we are going to explore.

  1. Complete Graph
  2. Cycles
  3. Wheels
  4. n-Cube
  5. Bipartite Graph
  6. Complete Bipartite Graph

Let us discuss each one them.

Advertisements

Complete Graph

A complete graph on n vertices, denoted by K_n is a simple graph that contains exactly one edge between each pair of distinct vertices. It any edge from the pair of distinct vertices is not connected then it is called non-complete.

Here are some examples of complete graph.

Complete Graphs
Complete Graphs

Cycles

A cycle is denoted as C_n where n \geq 3 consists of n vertices v1, v2, …, vn and edges { v1, v2 }, { v2, v3 }, …, { vn, v1}.

Here are some examples of cycles.

Cycles, where n >= 3
Cycles, where n >= 3

Wheels

A wheel graph is easy to construct. You get a wheel, W_n when you add an additional vertex to a cycle C_n, for n \geq 3 and place it in center of the cycle. This will connect each of the n vertices of cycle using new edges.

Some examples of wheels.

Wheels
Wheels

n-Cubes

A n-dimensional hyper-cube or n-cube is denoted by Q_n is simple graph that has vertices representing the 2^n bit-strings of length n.

In this scheme, two vertices are adjacent iff the bit strings differ only in one bit position. If this is confusing for you, see the following example.

Suppose Q_1 is given by following diagram.

n-Cube, Q1
n-Cube, Q1

The n-Cube, Q1 graph contains bit string length of 1. To construct Q2 from Q1 write another copy of Q1 and prefix 0 and 1 to each opposite end.

Advertisements
n-Cube, Q1 to Q2
n-Cube, Q1 to Q2

Similarly, to draw Q3 graph from Q2, do same as above, make a copy of Q2 and add 0 and 1 to opposite ends everywhere. Then join them by edges.

n-Cube, Q2 to Q3
n-Cube, Q2 to Q3

Bipartite Graphs

There is a special type of simple graph called bipartite graph. A simple graph G is bipartite if its vertex set V can be partitioned into two disjoint sets – V1 and V2, such that every edge in the graph G connects a vertex in V1 and V2. It means no edge in G connects two distinct vertices in either V1 or V2.

When this condition is holds, then you call the pair (V1, V2) bi-partition of V of graph G.

Consider following graphs.

Bipartite Graph
Bipartite Graph

In the first graph, the vertex set V is divided into

 

V1 = { S, R }

 

V2 = { A, B, C }

 

This graph is a bipartite because there is no edge between nodes of same set. Every edge is connecting two vertices – one from each subset of V.

The second graph, the vertex set is divided into

 

V1 = { A, B }

 

V2 = { C, D }

 

This graph is not a bipartite because A and B has an edge and both A and B belong to subset V1.

Complete Bipartite Graph

If you recall, a complete graph is a graph K_n. However, a complete bipartite graph K_{m,n} has its vertex set V partitioned into 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.

Complete Bipartite Graph
Complete Bipartite Graph

The total number of vertices in the set V = m + n and the total number of edges is E = m * n in a complete bipartite graph.

Advertisements
Advertisements
Advertisements