Неориентированные графы. Степени вершин. Сумма степеней вершин графа. Изоморфизм графов. Пример неизоморфных графов с одинаковыми степенями

Определение. Неориентированный граф состоит из множества вершин V и множества ребер E, причем каждому ребру e ∈ E сопоставлена неупорядоченная пара вершин a, b.

Определение. Ребро, сопоставленное паре {a, a} называется петлей. Если несколько ребер сопоставлены одной и той же паре вершин {a, b}, то такие ребра называют кратными.

Определение. Неориентированный граф (V, E) называется простым, если среди элементов V нет петель и кратных ребер. Для случая простых графов мы будем отождествлять ребра e ∈ E с соответствующей парой вершин {a, b} ∈ V^2.

Определение. Если ребру e ∈ E сопоставлена пара вершин {a, b} ∈ V^2, то будем говорить, что ребро e инцидентно каждой из вершин a и b.

Определение. Если имеется ребро e ∈ E, сопоставленное паре вершин {a, b} ∈ V^2, то будем говорить, что вершины a и b являются смежными.

Определение. Степенью вершины deg(j) неориентированного графа называют количество инцидентных вершине j ребер, при этом каждая инцидентная ей петля считается два раза. Другими словами, deg(j) =

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

Доказательство.

Определение. Неориентированные графы G = (V, E) и G’ = (V’, E’) изоморфны, если существуют биективные отображения f: V → V’ и g: E → E’ такие, что e ∈ E инцидентна a ∈ V ⇐⇒ g(e) ∈ E’ инцидентна f(a) ∈ V’.

Для случая простых графов для изоморфизма достаточно существования биективного отображения f: V → V’ такого, что

a, b ∈ V — смежные ⇐⇒ f(a), f(b) ∈ V’ — смежные.

Для изоморфных графов G и G’ имеем deg(a) = deg(f(a)).