Просмотр кода страницы Transversal (of a family S)

'''Transversal (of a family <math>S</math>)''' --- трансверсаль (семейства <math>S</math>).

The set  <math>T</math> is called a ''' transversal''' of a family of sets <math>S = \{A_{i}\}</math>,
if

1. <math>T \cap A_{i} \neq \emptyset</math>, for any <math>i</math>;

2. for any <math>a_{j} \in T</math> there exists <math>A_{i_{j}}</math> such that <math>A_{i_{j}}
\cap T = a_{j}</math>.

The maximum  number  of  pairwise  disjoint sets from the class <math>S</math> is
called the ''' independence  number'''  of  <math>S</math>  and  denoted  as <math>\alpha(G)</math>.
<math>\tau(G)</math> denotes the ''' transversal number''' of <math>S</math>, that is the
size of the minimum transversal of <math>S</math>.
==See also==
*'' System of distinct representatives''.

For a '' hypergraph'' <math>{\mathcal H} = (V,{\mathcal E})</math>, a ''' transversal''' is a
transversal of <math>{\mathcal E}</math>.