G-Отображающая функция: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 2: | Строка 2: | ||
для фиксированного [[граф|графа]] <math>G</math> и любого графа <math>H</math> функция | для фиксированного [[граф|графа]] <math>G</math> и любого графа <math>H</math> функция | ||
<math>\gamma_{G}(H)</math>, определяемая как наибольшее целое <math>k</math> такое, что <math>kG</math> | <math>\gamma_{G}(H)</math>, определяемая как наибольшее целое <math>k</math> такое, что <math>kG</math> | ||
[[изоморфизм|изоморфен]] [[подграф|подграфу]] графа <math>H</math>. Заметим, что <math>\gamma_{K_{2}}(H)</math> есть | [[изоморфизм графов|изоморфен]] [[подграф|подграфу]] графа <math>H</math>. Заметим, что <math>\gamma_{K_{2}}(H)</math> есть | ||
''[[реберное число независимости]]''. | ''[[реберное число независимости]]''. | ||
==Литература== | ==Литература== | ||
[J. Graph Theory] | [J. Graph Theory] | ||
Версия от 01:07, 10 декабря 2009
[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]