LineGraph - Maple Help

Hypergraphs

 LineGraph
 Return the linegraph of an hypergraph

 Calling Sequence LineGraph(H)

Parameters

 H -

Description

 • The command LineGraph(H) returns line graph of the hypergraph H.

Terminology

 • Line graph : If H :=(X, Y) is a hypergraph, then the line graph of H is the graph G on Y such that any two hyperedges y1, y2 of H form an edge of G if and only if y1 and y2 have a non-empty intersection.

Examples

 > $\mathrm{with}\left(\mathrm{Hypergraphs}\right):$$\mathrm{with}\left(\mathrm{GraphTheory}\right):$$\mathrm{with}\left(\mathrm{ExampleHypergraphs}\right):$

Create a hypergraph from its vertices and edges.

 > $H≔\mathrm{Hypergraph}\left(\left[1,2,3,4,5,6,7\right],\left[\left\{1,2,3\right\},\left\{2,3\right\},\left\{4\right\},\left\{3,5,6\right\}\right]\right)$
 ${H}{≔}{\mathrm{< a hypergraph on 7 vertices with 4 hyperedges >}}$ (1)

Print its vertices and edges.

 > $\mathrm{Hypergraphs}:-\mathrm{Vertices}\left(H\right);$$\mathrm{Hyperedges}\left(H\right)$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}{,}{7}\right]$
 $\left[\left\{{4}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{1}{,}{2}{,}{3}\right\}{,}\left\{{3}{,}{5}{,}{6}\right\}\right]$ (2)

Draw a graphical representation of this hypergraph.

 > $\mathrm{Draw}\left(H\right)$

Check whether H is connected.

 > $\mathrm{Hypergraphs}:-\mathrm{IsConnected}\left(H\right)$
 ${\mathrm{false}}$ (3)

Check whether H is linear.

 > $\mathrm{IsLinear}\left(H\right)$
 ${\mathrm{false}}$ (4)

Construct the line graph L of H.

 > $L≔\mathrm{Hypergraphs}:-\mathrm{LineGraph}\left(H\right)$
 ${L}{≔}{\mathrm{Graph 1: an undirected graph with 4 vertices, 3 edge\left(s\right), and 4 self-loop\left(s\right)}}$ (5)

Draw a graphical representation of L.

 > $\mathrm{DrawGraph}\left(L\right)$

Construct the vertex-edge-incidence graph M of H.

 > $M≔\mathrm{VertexEdgeIncidenceGraph}\left(H\right)$
 ${M}{≔}{\mathrm{Graph 2: an undirected graph with 11 vertices and 9 edge\left(s\right)}}$ (6)

Draw a graphical representation of L.

 > $\mathrm{DrawGraph}\left(M\right)$

Create another hypergraph.

 > $H≔\mathrm{Lovasz}\left(3\right)$
 ${H}{≔}{\mathrm{< a hypergraph on 6 vertices with 10 hyperedges >}}$ (7)

Print its vertices and edges.

 > $\mathrm{Hypergraphs}:-\mathrm{Vertices}\left(H\right);$$\mathrm{Hyperedges}\left(H\right)$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}\right]$
 $\left[\left\{{1}{,}{2}{,}{4}\right\}{,}\left\{{1}{,}{3}{,}{4}\right\}{,}\left\{{2}{,}{3}{,}{4}\right\}{,}\left\{{1}{,}{2}{,}{5}\right\}{,}\left\{{1}{,}{3}{,}{5}\right\}{,}\left\{{2}{,}{3}{,}{5}\right\}{,}\left\{{1}{,}{2}{,}{6}\right\}{,}\left\{{1}{,}{3}{,}{6}\right\}{,}\left\{{2}{,}{3}{,}{6}\right\}{,}\left\{{4}{,}{5}{,}{6}\right\}\right]$ (8)

Draw a graphical representation of this hypergraph.

 > $\mathrm{Draw}\left(H\right)$

Check whether H is connected.

 > $\mathrm{Hypergraphs}:-\mathrm{IsConnected}\left(H\right)$
 ${\mathrm{true}}$ (9)

Check whether H is linear.

 > $\mathrm{IsLinear}\left(H\right)$
 ${\mathrm{false}}$ (10)

Construct the line graph L of H.

 > $L≔\mathrm{Hypergraphs}:-\mathrm{LineGraph}\left(H\right)$
 ${L}{≔}{\mathrm{Graph 3: an undirected graph with 10 vertices, 45 edge\left(s\right), and 10 self-loop\left(s\right)}}$ (11)

Draw a graphical representation of L.

 > $\mathrm{DrawGraph}\left(L\right)$

Construct the vertex-edge-incidence graph M of H.

 > $M≔\mathrm{VertexEdgeIncidenceGraph}\left(H\right)$
 ${M}{≔}{\mathrm{Graph 4: an undirected graph with 16 vertices and 30 edge\left(s\right)}}$ (12)

Draw a graphical representation of L.

 > $\mathrm{DrawGraph}\left(M\right)$

References

 Claude Berge. Hypergraphes. Combinatoires des ensembles finis. 1987,  Paris, Gauthier-Villars, translated to English.
 Claude Berge. Hypergraphs. Combinatorics of Finite Sets.  1989, Amsterdam, North-Holland Mathematical Library, Elsevier, translated from French.
 Charles Leiserson, Liyun Li, Marc Moreno Maza and Yuzhen Xie " Parallel computation of the minimal elements of a poset." Proceedings of the 4th International Workshop on Parallel Symbolic Computation (PASCO) 2010: 53-62, ACM.

Compatibility

 • The Hypergraphs[LineGraph] command was introduced in Maple 2024.