Types of Graphs

Types of Graphs

Graphs are fundamental structures in computer science and mathematics. They consist of vertices (or nodes) connected by edges. Understanding the different types of graphs is crucial for solving various problems in computer science, such as network design, scheduling, and data organization. This section explores the main types of graphs.

1. Simple Graphs

A simple graph is an undirected graph that does not contain multiple edges between the same pair of vertices or loops (edges that connect a vertex to itself). In a simple graph, each edge connects two distinct vertices.

Example: Consider a graph with vertices A, B, and C connected as follows:

Vertices: A, B, C
Edges: (A, B), (B, C), (A, C)

This graph is a simple graph because it contains no loops or multiple edges. The edges connect distinct pairs of vertices.

2. Directed Graphs

A directed graph, or digraph, consists of vertices connected by directed edges (or arcs). Each directed edge has a direction, indicating a one-way relationship between two vertices. In a directed graph, the edge from vertex A to vertex B is not the same as the edge from vertex B to vertex A.

Example: Consider a directed graph with vertices A, B, and C:

Vertices: A, B, C
Edges: (A → B), (B → C), (C → A)

This graph shows a directed edge from A to B, which means that there is a relationship from A to B but not necessarily from B to A.

3. Weighted Graphs

A weighted graph assigns a weight (or cost) to each edge. The weight can represent various factors, such as distance, time, or cost. Weighted graphs are useful in applications like shortest path algorithms, where the goal is to find the path with the minimal total weight.

Example: Consider a weighted graph with vertices A, B, and C:

Vertices: A, B, C
Edges: (A, B, 5), (B, C, 3), (A, C, 10)

In this graph, the edge between A and B has a weight of 5, the edge between B and C has a weight of 3, and the edge between A and C has a weight of 10. This weight information can be used to determine the shortest path from one vertex to another.

4. Complete Graphs

A complete graph is a simple graph in which every pair of distinct vertices is connected by a unique edge. In a complete graph with n vertices, there are a total of n(n - 1)/2 edges.

Example: A complete graph with three vertices A, B, and C:

Vertices: A, B, C
Edges: (A, B), (A, C), (B, C)

This graph is complete because every vertex is connected to every other vertex.

5. Bipartite Graphs

A bipartite graph consists of two sets of vertices. Edges only connect vertices from one set to vertices in the other set. There are no edges between vertices within the same set. Bipartite graphs are useful in modeling relationships between two different groups.

Example: Consider a bipartite graph with sets U = {A, B} and V = {1, 2}:

Vertices: A, B, 1, 2
Edges: (A, 1), (A, 2), (B, 1)

This graph shows connections from vertices in set U to vertices in set V. Vertex A is connected to both 1 and 2, while vertex B is only connected to vertex 1.

6. Cyclic and Acyclic Graphs

A cyclic graph contains at least one cycle, which is a path that starts and ends at the same vertex. An acyclic graph, on the other hand, does not contain any cycles. Directed acyclic graphs (DAGs) have directed edges and are often used to represent dependencies.

Example: Consider a cyclic graph:

Vertices: A, B, C
Edges: (A, B), (B, C), (C, A)

This graph is cyclic because there is a path from A to B to C and back to A.

Example of an acyclic graph:

Vertices: A, B, C
Edges: (A, B), (B, C)

This graph is acyclic because there is no way to return to the starting vertex.

7. Planar Graphs

A planar graph can be drawn on a plane without any edges crossing each other. Not all graphs are planar. A graph is planar if it can be represented in two dimensions without edge intersections.

Example: A simple triangular graph with vertices A, B, and C is planar:

Vertices: A, B, C
Edges: (A, B), (B, C), (C, A)

This graph can be drawn without edges crossing. However, a graph that forms a complete graph with five vertices (K5) is not planar.

8. Subgraphs

A subgraph is a graph formed from a subset of the vertices and edges of a larger graph. A subgraph can be obtained by removing some vertices and edges while retaining the connections between the remaining vertices.

Example: Consider a graph G with vertices A, B, C, and D:

Vertices: A, B, C, D
Edges: (A, B), (B, C), (C, D), (A, D)

A possible subgraph H could be:

Vertices: A, B
Edges: (A, B)

This subgraph H contains only a subset of the vertices and edges from graph G.

Summary

• Simple graphs do not have loops or multiple edges.
• Directed graphs have edges with direction.
• Weighted graphs have edges with associated weights.
• Complete graphs connect every pair of distinct vertices.
• Bipartite graphs connect vertices from two distinct sets.
• Cyclic graphs contain cycles; acyclic graphs do not.
• Planar graphs can be drawn without crossing edges.
• Subgraphs are formed from subsets of vertices and edges.

Check your understanding

1. What is the difference between a simple graph and a directed graph?
2. How do you determine if a graph is bipartite?
3. What characterizes a weighted graph?
4. Can a graph be both cyclic and acyclic? Why or why not?