Подграф

Определение 5.1. Граф G ¢= (S ¢, U ¢) называется подграфом графа G = (S, U), если S ¢Í S, а U ¢ – множество всех ребер G, оба конца которых принадлежат S ¢.

Определение 5.2. Подграф называется собственным, если он отличен от самого графа.

Определение 5.3. Граф G ¢= (S ¢, U ¢) называется частью графа G = (S, U), если S ¢Í S, а U ¢ – подмножество множества всех ребер G, оба конца которых принадлежат S ¢.

Любой подграф графа является его частью, но не любая часть графа есть его подграф.

Так как подграф G ¢ полностью определяется множеством S ¢ своих вершин, то его можно обозначать кратко через G ¢(S ¢). Поэтому подграф G ¢= (S ¢, U ¢) называют также графом, порождëнным множеством S ¢ (или вершинно-порождëнным графом).

Пример 5.1. На рис. 10 изображены граф G, его подграф, порождëнный множеством вершин x₁, x₂, x₄, и его часть, содержащая все вершины G, но не все его рëбра. 

Все приведëнные определения распространяются на орграфы.

Определим на множестве подграфов графа G отношение включения. Пусть G ¢(S ¢) и G ²(S ²) – подграфы графа G. Говорят, что G ¢(S ¢) содержится в G ²(S ²) (пишут G ¢Í G ²), если S ¢Í S ². Легко видеть, что отношение включения подграфов графа G является отношением частичного порядка. При этом граф G является единственным максимальным элементом. Справедливо следующее утверждение.

Утверждение 5.1. Пусть G = (S, U) – произвольный псевдограф (ориентированный или неориентированный), S ¢Í S, S ¢ ¹ Æ и G ¢(S ¢) – подграф графа G. Тогда матрица смежности вершин P (G ¢) подграфа G ¢ является подматрицей матрицы смежности вершин P (G) графа G, находящейся на пересечении строк и столбцов, соответствующих вершинам из S ¢. 

Определение 5.4. Кликой называется полный подграф G ¢(S ¢) графа G.

Определение 5.5. Звездой вершины x называется часть графа G, содержащая вершину x, все инцидентные ей ребра и все смежные с x вершины.

Пример 5.2. На рис. 11изображены граф G, клика графа G и звезда вершины x₅ графа G. 

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

Понятие звезды вершины для орграфа, как и степень вершины, расщепляется на две части.

Определение 5.6. Полузвездой исхода (захода) вершины x орграфа называется подграф, порождëнный вершиной x и всеми вершинами, в которые из x

(из которых в x) ведут рëбра.