The meaning of various types of graphs

There are many named types of graphs . I wonder what the criteria for this categorization are. Are different types applicable in different contexts? Moreover, can a business application (in terms of design and programming) benefit from this categorization? Are these similar to design patterns?

+4
source share
1 answer

We gave names to common graph families for several reasons:

  • Some chart families have nice simple properties . For example, trees have many useful properties (there is exactly one path between any pair of nodes, they are maximally acyclic, they are minimally connected, etc.) that do not have arbitrary graphs. Directional acyclic graphs can be sorted topologically , which normal graphs cannot. If you can model the problem in terms of one of these types of graphs, you can use specialized algorithms to extract properties that may not necessarily be obtained from an arbitrary graph.

  • Some algorithms work faster on some types of charts . Many NP-hard problems on graphs that currently do not have polynomial time algorithms can be easily solved on some types of graphs. For example, the maximum independent installation problem (select the largest collection of nodes where neither of the two nodes is connected by edges) is NP-hard, but can be solved in polynomial time for trees and two-sided graphs . The 4-coloring problem (determining whether graph nodes can be colored in one of four different colors without assigning the same color to adjacent nodes) is NP-hard in general, but right away for flat graphics (this is the famous four-color theorem) .

  • Some algorithms are simpler on some types of graphs . A matching in a graph is a set of edges in a graph where two edges do not share an endpoint. Maximum correspondences can be used to represent how people are grouped together. In a bipartite graph, maximum coincidence can be used to represent the way people are assigned to tasks in such a way that no tasks are assigned to two people and no tasks are assigned to two tasks. There are many quick algorithms for finding maximum matches in bipartite graphs that are fast and easy to understand. The corresponding algorithms for general graphs are much more complicated and slightly less efficient.

  • Some graphs are historically significant . Many of these graphs are named after those who used the graph to refute the hypothesis about the properties of arbitrary graphs. For example, the Petersen graph is a counterexample for many theorems that seem correct with respect to graphs but are not really.

  • Some graphs are useful in theoretical computer science . An extension graph is a graph where, intuitively, any collection of nodes must be connected to a proportionally larger set of nodes in the graph. Not all graphs are extension graphs. Expander graphs are used in many theoretical computer science results, such as a single proof of the PCP theorem and a proof that SL = L.

This is not an exhaustive list of why we care about different families of charts, but I hope this helps to motivate their use and study.

Hope this helps!

+2
source

All Articles