Sum hypergraph

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

Sum hypergraph --- суммарный гиперграф.

A hypergraph [math]\displaystyle{ {\mathcal H} }[/math] is a sum hypergraph iff there are a finite [math]\displaystyle{ S \subseteq N^{+} }[/math] and [math]\displaystyle{ \underline{d}, \bar{d} \in N^{+} }[/math] such that [math]\displaystyle{ {mathcal H} }[/math] is isomorphic to the hypergraph [math]\displaystyle{ {\mathcal H}_{\underline{d}, \bar{d}}(S) = (V,{\mathcal E}) }[/math], where [math]\displaystyle{ V = S }[/math] and [math]\displaystyle{ {\mathcal E} = \{e \subseteq S: \; \underline{d} \ leq |e| \leq \bar{d} \wedge \sum_{v \in e} v \in S\} }[/math]. For an arbitrary hypergraph [math]\displaystyle{ {\mathcal H} }[/math], the sum number [math]\displaystyle{ \sigma = \sigma({\mathcal H}) }[/math] is defined as the minimum number of isolated vertices [math]\displaystyle{ w_{1}, \ldots, w_{\sigma} \not \in V }[/math] such that [math]\displaystyle{ {\mathcal H} \cup \{w_{1}, \ldots, w_{\sigma}\} }[/math] is a sum hypergraph.