Un simple gráfico de $G(V, E)$ es un conjunto de vértices y aristas, donde cada arista $e \in E$ se define como $e \subset V$$|e| = 2$.
Un multigraph generaliza un simple gráfico, permitiendo a los bucles for y varias aristas. Un bucle es un borde que es un elemento del subconjunto de $V$. Como varias aristas son permitidos, $E$ es un conjunto múltiple de uno y de dos elementos y subconjuntos de a $V$.
El hypergraph más generaliza la multigraph, permitiendo hyperedges $h$ a $h \subset V$$h \neq \emptyset$.
Hypergraphs son increíblemente útiles en biología computacional para el modelado de sistemas complejos. También hay problemas en hypergraphs que son computacionalmente intratable, mientras que en gráficas sencillas que el problema es bastante simple. Un buen ejemplo es $2$-colorabilidad. En gráficas sencillas, es fácil comprobar si un grafo es $2$-engañosa, o bipartitas. En un hypergrpah, primero tenemos que definir nuestro colorear problema, que no hyperedge contiene sólo los vértices de un color. Con esta definición, la comprobación de si un hypergraph es $2$-engañosa es $NP$-Completa. La prueba de ofertas con un probabilístico seleccionable prueba. De hecho, me escribió un artículo para una clase sobre esto hace un tiempo, pero estoy un poco oxidado en los detalles.
Todavía hay más estructuras generales que generalizar el concepto de los gráficos, en cierto sentido, como matroids, por ejemplo.
Matroids generalizar el concepto de independencia lineal de álgebra lineal. Gráfico acyclicity comparte esta propiedad, como la propiedad de tres o más puntos colineales en el Plano de Fano. Yo no diría que un Matroid generaliza el concepto de un gráfico, específicamente, aunque.
