Термин для подграфа со всеми инцидентными ребрами.

[pcyanide]

Извините за глупый вопрос. Просмотрел весь Глоссарий теории графов, но не смог найти подходящего термина.

Есть термин «Остовный подграф» для подграфа, содержащего все вершины. Я ищу в некотором смысле противоположный термин, для подграфа, содержащего все ребра, которые можно включить для заданного подмножества вершин. Другими словами, речь идет о подграфе (не обязательно полном), содержащем все инцидентные ребра выбранного подмножества вершин. Надеюсь, такой термин существует.

[arseniiv]

Не в курсе веяний конкретно в теории графов, но было бы вполне логично, если бы такое называлось ограничением графа (на данное множество вершин). Так что если ничего другого не найдётся…

[pcyanide]

Будет очень жаль, если такого термина не окажется. Иначе, можно было бы сформулировать ряд интересных свойств. Назовем, к примеру такой граф долей. Тогда:

1) Всякий неполный граф имеет вполне несвязную долю.
2) Всякая доля полного графа является полным графом.
3) Если А - максимальная вполне несвязная доля, каждая из вершин дополнительного графа смежна
некоторой вершине из А.

Мне кажется вполне естественным, что выбрав подмножество вершин, надо взять из исходного графа все возможные ребра, иначе невыбранные ребра окажутся навсегда утерянными.

Кстати, есть термин для количества вершин графа (напр., размер графа или мощность графа)? Его тоже хотелось бы иметь.

[arseniiv]

«Число вершин графа», и обычно контекст содержит обозначение для множества вершин графа, и тогда короче написать формулой: $|V|$.

Вообще обычные орграфы (с возможными петлями) — это другой взгляд на бинарные отношения, и иногда, возможно, лучше переходить на их язык. Тогда множество вершин зовётся носителем отношения, и «мощность носителя <отношения>» выглядит лично для меня сильно яснее, чем «мощность <графа>».

[eugensk]

Такой термин есть, это порожденный подграф (induced subgraph).
И термин для числа вершин графа, это порядок графа (order of a graph).

[eugensk]

Поправка, на случай если я не понял вопрос. Как назвать подграф который содержит все рёбра исходного графа, и какие-то из вершин, "остовный наоборот", правильно?
Это исходный граф, минус, возможно, какие-то изолированные вершины - не очень интересно, и поэтому без собственного названия.

[pcyanide]

Порожденный подграф — это именно то, что я искал. Спасибо.