algorithm - Significance of various graph types -

there lot of named graph types. wondering criteria behind categorization. different types applicable in different context? moreover, can business application (from design , programming perspective) benefit out of these categorizations? analogous design patterns?

we've given names common families of graphs several reasons:

• certain families of graphs have nice, simple properties. example, trees have numerous useful properties (there's 1 path between pair of nodes, they're maximally acyclic, they're minimally connected, etc.) don't hold of arbitrary graphs. directed acyclic graphs can topologically sorted, normal graphs cannot. if can model problem in terms of 1 of these types of graphs, can use specialized algorithms on them extract properties can't obtained arbitrary graph.

• certain algorithms run faster on types of graphs. many np-hard problems on graphs, of don't have polynomial-time algorithms, can solved on types of graphs. example, maximum independent set problem (choose largest collection of nodes no 2 nodes connected edge) np-hard, can solved in polynomial time trees , bipartite graphs. 4-coloring problem (determine whether nodes of graph can colored 1 of 4 different colors without assigning same color adjacent nodes) np-hard in general, true planar graphs (this famous four-color theorem).

• certain algorithms easier on types of graphs. matching in graph collection of edges in graph no 2 edges share endpoint. maximum matchings can used represent ways of pairing people groups. in bipartite graph, maximum matching can used represent way of assigning people tasks such no person assigned 2 tasks , no task assigned 2 people. there many fast algorithms finding maximum matchings in bipartite graphs work , easy understand. corresponding algorithms general graphs more complicated , less efficient.

• certain graphs historically significant. many named graphs named after used graph disprove conjecture properties of arbitrary graphs. petersen graph, example, counterexample many theorems seem true graphs not.

• certain graphs useful in theoretical computer science. expander graph graph where, intuitively, collection of nodes must connected proportionally larger collection of nodes in graph. not graphs expander graphs. expander graphs used in many results in theoretical computer science, such 1 proof of pcp theorem , in proof sl = l.

this not exhaustive list of why care different graph families, helps motivate usage , study.

hope helps!