Graphes

 

A graph is a collection of nodes and edges. These nodes are connected by links(edges).
These edges may be directed or undirected. Moreover these edges can have weights associated with them

So edges can be categorized as :
  1. Directed, weighted edges
  2. Directed, unweighted edges
  3. Undirected, weighted edges
  4. Undirected, unweighted edges


Uses of graphs

Graphs are extremely useful. Look everywhere and one can easily find use of graphs. Listed below are a few of the vast set of practical uses of graphs.

Delhi Metro Rail Map
 Each station is a vertex, the distance in between is a weighted edge.

A Maze
 Each corner is a vertex, Line between two corners is and edge.

A tournament fixture
Courtesy: http://www.squadtd.com/
Each team is a vertex, match between the teams is an edge.


Kind of graphs

There are numerous classifications and types of graphs available. I have collected a few of those types from various sources and organized a list of types of graphs:

  • Undirected Graphs

Undirected Graph
     Characteristics:
  1. Order of vertices doesn't matter
  2. 1-2 is same as 2-1

  • Directed Graphs

Directed Graph
     Characteristics:
  1. Order of vertices does matter
  2. 1-2 is not same as 2-1

  • Vertex labeled Graphs.

Vertex Labeled Graph
     Characteristics:
  1. Each vertex contains additional information. e.g {2,orange}, {4,green}

  • Cyclic Graphs.

Cyclic Graph
     Characteristics:
  1. Graph contains at least one cycle.

  • Edge labeled Graphs.

Edge Labeled Graph
     Characteristics:
  1. Edge has labels e.g an edge in the above graph will be represented as {orange,green,{blue,cyan}}

  • Weighted Graphs.

Weighted Graph
     Characteristics:
  1. Each edge has some weight associated with it.

  • Directed Acyclic Graphs.

Direct Acyclic Graph(DAG)
     Characteristics:
  1. Graph has no cycles.

  • Disconnected Graphs

Disconnected Graph
     Characteristics:
  1. Vertices are disconnected 

  • Mixed graph

Mixed Graph
     Characteristics:
  1. Some edges may be directed and some may be undirected 

  • Multigraph

Multigraph
     Characteristics:
  1. Multiple edges (and sometimes loops) are allowed

  • Quiver

          

     Characteristics:
  1. Directed graph which may have more than one arrow from a given source to a given target. A quiver may also have directed loops in it.

Representation of graphs:

Fig. 1: An undirected graph
Fig 2: A directed graph
In order to use Graphs programatically , they need to be somehow represented in code. Following are the most widely used methods of representing a graph.

Adjacency Matrix : 

For N vertices an adjacency matrix is an NxN array A such that
                       A[i][j] = 1 if there is an edge E(i,j)
                                  = 0 otherwise

For an undirected graph, A[i][j] = A[j][i]

For weighted graphs,
                       A[i][j] = weight of the edge, if there is an edge E(i,j)
                                 = a constant representing no edge (e.g a very large or very small value)

For Fig 1, the adjacency matrix would be 

The adjacency matrix for directed graph in Fig 2 would be:


Adjacency List : 

Adjacency matrix representation consume a lot of memory (O[N2]). If the graph is complete or almost complete(i.e. contains most of the edges between the vertices), then this representation is good to use. But if there are very few edges as compared to number of vertices, it will unnecessarily consume extra space. Adjacency list can handle this situation very optimally.

Every vertex has a linked list of the vertices it is connected with.

Adjacency list for Fig 1 would be:


Adjacency list for Fig 2 would be:


No comments

JavaFX Scene Builder

  This is an article about the JavaFX Scene Builder. You will get a short introduction about the installation and usage of the software. The...