Algorithms

Classified in Language

Written at on English with a size of 41.41 KB.

 

Connected and Disconnected Graph: A graph is connected if any two vertices of the graph are connected by a path and a graph is disconnected if at least two vertices of the graph are not connected by a path. If a graph G is unconnected, then every maximal connected subgraph of G is called a connected component of the graph G.

Dense graph is a graph in which the number of edges is close to the maximal number of edges. Description: Connected graphDescription:  Unconnected graph

Sparse graph is a graph in which the number of edges is close to the minimal number of edges. Sparse graph can be a disconnected graph.

  • Informally, a graph with relatively few edges is sparse, and a graph with many edges is dense.
  • Sparse graphs are sparsely connected (eg: Trees). Usually the number of edges is in O(n) where n is the number of vertices. Therefore adjacency lists are preferred since they require constant space for every edge.
  • Dense graphs are densely connected. Here number of edges is usually O(n^2). Therefore adjacency matrix is preferred.
  • To give a comparison, let us assume graph has 1000 vertices. Irrespective of whether the graph is dense or sparse, adjacency matrix requires 1000^2 = 1,000,000 values to be stored.
  • If the graph is minimally connected (i.E. It is a tree), the adjacency list requires storing 2,997 values. If the graph is fully connected it requires storing 3,000,000 values.1

2

                     Storage     Add Vertex Add Edge   Remove Vertex Remove Edge Query
Adjacency list O(|V|+|E|)     O(1)            O(1)         O(|V| + |E|)         O(|E|)         O(|V|)
Adjacency matrix O(|V|^2)  O(|V|^2)      O(1)        O(|V|^2)              O(1)           O(1)

Tree: A connected acyclic graph is called a tree. In other words, a connected graph with no cycles is called a tree. Image

  • The edges of a tree are known as branches. Elements of trees are called their nodes. The nodes without child nodes are called leaf nodes.

  • A tree with ‘n’ vertices has ‘n-1’ edges. If it has one more edge extra than ‘n-1’, then the extra edge should obviously has to pair up with two vertices which leads to form a cycle. Then, it becomes a cyclic graph which is a violation for the tree graph.

Entradas relacionadas: