We are glad you are taking a moment to explore the Wolfram Language’s hypergraph capabilities. In this notebook, we’ll start by showing how you can represent and plot hypergraphs, then walk you through two simple algorithms for computing transversal hypergraphs. Get an overview of all the functionalities available in the Wolfram Language in the Wolfram Language & System Documentation Center.

Recall that a hypergraph consists of the set of vertices and the set of hyperedges, each of which is a non-empty subset of those vertices. When it is understood that every vertex lies in at least one hyperedge, then we can let also refer to its set of hyperedges.

H=(V,E)

V

E

H

Clickinthecode,thenholdandpresstorunit.

Represent a hyperedge as a list of vertices, and a hypergraph as a list of edges and isolated vertices:

hypergraph={{a,b,c,d},{b,c},{c,d,e},f,g};

In[1]:=

Plot hypergraphs using the built-in function CommunityGraphPlot, which creates a colored region for each hyperedge:

hypergraphPlot[hyp_]:=CommunityGraphPlot[Graph[DeleteDuplicates[Flatten[hyp,

1]],{},VertexLabels"Name"],Select[hyp,ListQ],

CommunityRegionStyleRandomColor[RGBColor[_,_,_,.5],5]]

hypergraphPlot[hypergraph]

In[2]:=

Out[3]=

A transversal of a hypergraph is a subset of that has a non-empty intersection with each hyperedge in . A minimal transversal is a transversal containing no other transversal as a proper subset. The transversal hypergraph of H is the hypergraph , where is the subset of consisting of all vertices appearing in an edge of , and is the collection of all minimal transversals of . For instance, the hypergraph below is the transversal hypergraph of the hypergraph above:

T

H=(V,E)

U

V

E

Tr(H)

(U,F)

U

V

H

F

H

hypergraphPlot[{{c},{b,d},{b,e}}]

In[4]:=