Wolfram Research

TransversalHypergraph

Contributed by: Daniel McDonald

Source Notebook

Compute the transversal hypergraph of a hypergraph defined by a list of hyperedges and isolated vertices

ResourceFunction["TransversalHypergraph"][list]

computes the transversal hypergraph of list.

Details and Options

The hypergraph represented by {{v11,v12,},{v21,v22,},,u1,u2,} has vertices v11,v12,,v21,v22,,,u1,u2, and hyperedges {v11,v12,},{v21,v22,},.
Given a hypergraph H having sets V and E of vertices and hyperedges, a transversal T of H is a subset U of V that has a non-empty intersection with each hyperedge in E; a minimal transversal is a transversal containing no other transversal as a proper subset. The transversal hypergraph Tr(H) of H is the hypergraph whose hyperedges are the minimal transversals of H.

Examples

Basic Examples

Compute the transversal hypergraph of the hypergraph having vertices a,b,c,d,e,f,g and hyperedges {a,b,c,d},{b,c},{c,d,e}:

In[1]:=
ResourceFunction[
 "TransversalHypergraph"][{{a, b, c, d}, {b, c}, {c, d, e}, f, g}]
Out[1]=

Applications

Define a random hypergraph having n vertices and m hyperedges:

In[2]:=
RandomHypergraph[n_, m_] := With[{edges = Apply[Join, Map[Function[pos, Subsets[Range[n], {1, n}, {pos}]], RandomInteger[{1, 2^n - 1}, m]]]}, Join[edges, Complement[Range[n], Flatten[edges]]]]
rh = RandomHypergraph[15, 3]
Out[3]=

Plot the hypergraph:

In[4]:=
HypergraphPlot[hyp_List] := CommunityGraphPlot[
  Graph[DeleteDuplicates[Flatten[hyp, 1]], {}, VertexLabels -> "Name"], Select[hyp, ListQ], CommunityRegionStyle -> Apply[Function[{r, g, b}, RGBColor[r, g, b, .5]], Most[Tuples[{0, 1}, 3]], {1}]]
HypergraphPlot[rh]
Out[5]=

Find its transversal hypergraph:

In[6]:=
th = ResourceFunction["TransversalHypergraph"][rh]
Out[6]=

Plot the transversal hypergraph:

In[7]:=
HypergraphPlot[th]
Out[7]=

Resource History

Source Metadata

See Also