0 Replies - 53731 Views - Last Post: 22 May 2011 - 06:14 PM Rate Topic: -----

#1 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon

Reputation: 12742
  • View blog
  • Posts: 45,926
  • Joined: 27-December 08

Data Structures- Introduction to Graph Theory (Types of Graphs)

Posted 22 May 2011 - 06:14 PM


Introduction to Graph Theory- Types of Graphs

The purpose of this tutorial is to introduce basic graph theory terminology and concepts.

To begin, a graph is a collection of vertices that are connected by edges. Graphs can be weighted so that there is a cost to go from one vertex to another across an edge, or unweighted so that there is no cost. They can also be directed so that travel is only possible from one vertex to another, but not necessarily bidirectional; or they can be undirected so travel is bidirectional across all edges.

Simple Graphs, Multigraphs, and Hypergraphs
There are three major types of graphs to be familiar with: simple graphs, multigraphs, hypergraphs. When referring to graphs in general, simple graphs are generally being referenced. Simple graphs are unweighted, undirected, and have no loops (vertices with edges pointing to the same vertex on both ends) or multiple edges which point to the same pair of vertices. A simple graph is displayed below:

Attached Image

Multigraphs are graphs which have one or more pairs of vertices with multiple edges connecting the same two vertices. Various academics are conflicted as to whether or not multigraphs can contain loops. This ambiguity leaves a lot of discretion up to the individual. Below is an example of a multigraph:

Attached Image

Hypergraphs have edges, called hyperedges, which can connect more than two vertices together. When displaying them visually, they can quickly get messy. A good, clean example of a hypergraph, however, is a circuit diagram, as shown below. Any resistors, batteries, capacitors, etc., are all considered vertices; and the wires connecting are the edges.

Attached Image

Basic Classes of Graphs

In addition to simple graphs, multigraphs, and hypergraphs, there are a number of other types of graphs, described based on the relations of the vertices to each other. In this tutorial, the following types of graphs will be introduced: cyclic grahps, wheels, complete graphs, bipartite graphs, and cubes.

Cyclic graphs are, as the name suggests, simply circuits. They are denoted by a Cn, with n being the number of vertices. In Cyclic graphs, n is also the number of edges. The cyclic graph C6 is displayed below.

Attached Image

Wheels are similar to cyclic graphs, and actually contain a cyclic graph. The main difference is that wheels have a central vertex that connects to the rest of the vertices in the graph. A wheel is denoted by Wn, where n is the number of vertices in the graph, and Wn contains Cn-1. There are 2(n-1) edges contained in any wheel. Some examples of wheels are displayed below.

Attached Image

Complete graphs are a type of graph where all the vertices are connected to each other. They are denoted by Kn, where n is the number of vertices. Complete graphs have n(n-1)/2 edges. The K5 graph is displayed below as an example of complete grahps.

Attached Image

Bipartite graphs are best defined using set theory. They are graphs such that there are two sets of vertices, where the vertices in the first set only have edges to vertices in the second set, and vertices in the second set only have edges connecting to vertices in the first set. In other words, vertices in the same set are not connected. It could also be described as a disjoint set data structure. Both the cyclic and complete graphs can be bipartite. In order for a cyclic graph to be considered bipartite, it must have an even number of vertices. Otherwise, there will be a vertex that is connected to vertices in both of the sets, violating the bipartite property.

Complete bipartite graphs are slightly different than normal complete graphs. In a complete bipartite graph, the vertices are still in disjoint sets, but all the vertices in the first set connect to all the vertices in the second set, and vice versa. Complete bipartite graphs are noted by Ka,b, where a is the number of vertices in the first set, and b is the number of vertices in the second set.

Below is an example of a bipartite graph, specifically K3,3.

Attached Image

The last type of graph covered in this tutorial is a cube. These graphs are also bipartite, and are denoted with the notation Qn, where n is the number of vertices. Cubes have 2n vertices and n * 2n-1 edges. Looking back at Calculus, this looks exactly like a derivative for xn. In order to determine which vertices are connected, each vertex is given a binary number n digits long ranging from n 0's to n 1's. Only vertices whose binary indices differ by a single digit are connected. So for example, in Q3, there are 8 vertices labeled: 000, 001, 010, 011, 100, 101, 110, 111. Vertex 000 is connected to vertices 001, 010, and 100 exclusively.

Below is the Q3 graph as an example of the cube graph.

Attached Image

Is This A Good Question/Topic? 8
  • +

Page 1 of 1