4. Теоремы о степенях вершин и изоморфизм графов

   1. Сумма степеней вершин в неориентированном графе четна и равна удвоенному числу ребер.

Доказательство: поскольку каждое ребро инцидентно двум вершинам, оно добавляет двойку к сумме степеней вершин графа. Следовательно, все ребра дают вместе сумму вдвое большую их числа.

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

2. Число вершин нечетной степени в любом графе четно.

Доказательство: пусть число вершин в графе равно n. Не нарушая общности, предположим, что степени первых r вершин v₁, v₂,,v_r четны, а степени оставшихся n‑r вершин нечетны. Тогда общая сумма степеней всех вершин равна . По теореме 1 левая часть этого равенства – четное число. Первая сумма в правой части также четна, т.к. каждое слагаемое в этой сумме четно по предположению. Следовательно, и вторая сумма в правой части тоже четна. Но так как каждое слагаемое в этой сумме нечетно по предположению, то число этих слагаемых должно быть четным. Поскольку число этих слагаемых совпадает с числом вершин нечетной степени, то число последних четно.

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

Два графа G₁ и G₂ называются изоморфными, если существует биективное отображение между множествами их вершин и ребер такое, что соответствующие друг другу по этому отображению ребра графов G₁ и G₂ инцидентны соответствующим друг другу по этому же отображению парам вершин этих графов.

Другими словами, если вершины v_i и v_j графа G₁ соответствуют вершинам v_i и v_j графа G₂, то ребро е_k=( v_i, v_j ) в G₁ должно соответствовать ребру е_k=( v_i, v_j ) в графе G₂ и наоборот.

С огласно определению, графы, изображенные на рисунке 13, изоморфны. Соответствие между множествами вершин и ребер таково:

для вершин:

для ребер:

5. Подграфы

Подграфом графа G=(V, E) называется граф G=(V, E), у которого множества вершин и ребер V и E являются такими подмножествами множеств V и E соответственно, что ребро (v_i, v_j)E тогда и только тогда, когда вершины v_i и v_jV. Граф G называется собственным подграфом графа G, если V V и E E. Если все вершины графа G присутствуют в его подграфе G, т.е. V=V, то G называется остовным подграфом G.

Подграф без изолированных вершин называется реберно-порожденным подграфом. Множество вершин реберно-порожденного подграфа полностью определяется множеством его ребер.

Если же множество вершин подграфа полностью определяет множество его ребер, то такой подграф называется вершинно-порожденным. Заметим, что множество ребер вершинно-порожденного подграфа является таким максимальным подмножеством множества ребер графа, что концевые вершины всех этих ребер принадлежат подграфу.

Н а рисунке 14 изображены: (а) исходный граф; (б) собственный подграф; (в) остовный подграф; (г) реберно-порожденный подграф; (д) вершинно-порожденный подграф.