Point-tree hypergraph

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

Point-tree hypergraph --- дерево-точечный гиперграф.

A hypergraph [math]\displaystyle{ H }[/math] is called a point-tree hypergraph if it is obtained from a bipartite graph by replacing, in each edge, the point in one side of the graph (the same side for all edges) by a tree. More formally, [math]\displaystyle{ H }[/math] is point-tree, if for some set [math]\displaystyle{ X }[/math] and a tree, whose vertex set is disjoint with [math]\displaystyle{ X }[/math], each edge [math]\displaystyle{ e \in H }[/math] is of the form [math]\displaystyle{ \{x\} \cup V(t) }[/math], where [math]\displaystyle{ x = x(e) \in X }[/math]and [math]\displaystyle{ t = t(e) }[/math] is a subtree of [math]\displaystyle{ T }[/math]. For such a hypergraph we denote by [math]\displaystyle{ \sigma(H) }[/math] the number [math]\displaystyle{ w(H,F) }[/math], where [math]\displaystyle{ F = F(H) = \{\{x(e)\}: \; e \in H\} \cup \{V(t(e)): \; e \in H\} }[/math].