Name some common types and categories of Graphs

Technology CommunityCategory: Data StructuresName some common types and categories of Graphs
VietMX Staff asked 5 months ago
  • In an undirected graph, nodes are connected by edges that are all bidirectional. For example if an edge connects node 1 and 2, we can traverse from node 1 to node 2, and from node 2 to 1.
  • In a directed graph, nodes are connected by directed edges – they only go in one direction. For example, if an edge connects node 1 and 2, but the arrow head points towards 2, we can only traverse from node 1 to node 2 – not in the opposite direction.
  • weight is a numerical value attached to each individual edge. If edges in our graph have weights then your graph is said to be a weighted graph
  • if the edges do not have weights, the graph is said to be unweighted
  • cyclic graph is a directed graph which contains a path from at least one node back to itself. In simple terms cyclic graphs contain a cycle.
  • An acyclic graph is a directed graph which contains absolutely no cycle, that is no node can be traversed back to itself.
  • Dense graph is a graph in which the number of edges is close to the maximal (max) number of edges.
  • Sparse graph is a graph in which the number of edges is close to the minimal (min) number of edges. Sparse graph can be a disconnected graph.

graphs-categories-1

  • A graph is connected if any two vertices of the graph are connected by a path.
  • A graph is disconnected if at least two vertices of the graph are not connected by a path.

graphs-categories-2

 

  • In a multigraph, there can be more than one edge from vertex 1 to vertex 2.
  • In a simple graph there is at most one.

 

graphs-categories-3