G-Отображающая функция

Материал из WikiGrapp
Версия от 17:59, 8 декабря 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''<math>G</math>-Отображающая функция''' (''<math>G</math>-Matching function'') - для фиксированного...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

[math]\displaystyle{ G }[/math]-Отображающая функция ([math]\displaystyle{ G }[/math]-Matching function) - для фиксированного графа [math]\displaystyle{ G }[/math] и любого графа [math]\displaystyle{ H }[/math] функция [math]\displaystyle{ \gamma_{G}(H) }[/math], определяемая как наибольшее целое [math]\displaystyle{ k }[/math] такое, что [math]\displaystyle{ kG }[/math] изоморфен подграфу графа [math]\displaystyle{ H }[/math]. Заметим, что [math]\displaystyle{ \gamma_{K_{2}}(H) }[/math] есть реберное число независимости.

Литература

[J. Graph Theory]