Лекции_по_ДМ

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

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

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

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

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

Доказательство: пусть число вершин в графе равно 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, изоморфны. Соответствие между множествами вершин и ребер таково:

для вершин:

для ребер:

Содержание