Число Турана

Материал из WikiGrapp

Число Турана (Turan number) — (обозначение [math]\displaystyle{ T(n,k,t) }[/math]) наименьшее число [math]\displaystyle{ t }[/math]-подмножеств [math]\displaystyle{ n }[/math]-элементного множества [math]\displaystyle{ X }[/math] таких, что любое [math]\displaystyle{ k }[/math]-подмножество из [math]\displaystyle{ X }[/math] содержит по крайней мере одно из [math]\displaystyle{ t }[/math]-подмножеств.

Литература

  • Оре О. Теория графов. — М.: Наука, 1968.
  • Toft B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994.