Смежность вершин и ребер

Пусть v₁, v₂ — вершины, e = (v ₁, v ₂ ) – соединяющее их ребро. Тогда вершина v ₁ и ребро е инцидентны, вершина v ₂ и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Множество вершин, смежных с вершиной v, называется множеством смежности вершины v и обозначается

, ,

(Если не оговорено противное, то подразумевается и обозначается просто ).

При этом .

Если — множество вершин, то Г(А) — множество всех вершин, смежных с вершинами из А:

.

1.4 Изоморфизм графов

Говорят, что два графа G ₁(V ₁, E ₁) и G ₂(V ₂, E ₂ ) изоморфны (обозначается G ₁~ G ₂), если существует биекция h: , сохраняющая смежность:

Изоморфизм графов есть отношение эквивалентности. Действительно, изомор­физм обладает всеми необходимыми свойствами:

1) рефлексивность: G~G, где требуемая биекция суть тождественная функция;

2) симметричность: если G ₁ ~G ₂ с биекцией h, то G ₂~ G ₁ с биекцией h ^-1;

3) транзитивность: если G ₁~ G ₂ с биекцией h и G ₂~ G ₃ с биекцией g, то G ₁~ G ₃ с биекцией .

Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются классы эквивалентности по отношению изоморфизма.

Пример. Три внешне различные диаграммы, приведенные на рис. 3, являются диаграм­мами одного и того же графа K _3,3.

Рис. 3. Диаграммы изоморфных графов

Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа. Так, p(G) и q(G) — инварианты графа G.

Не известно никакого набора инвариантов, определяющих граф с точностью до изоморфизма.

Пример. Количество вершин, ребер и количество смежных вершин для каждой вершины не определяют граф. На рис. 4 представлены диаграммы графов, у которых указанные инварианты совпадают, но графы при этом не изоморфны.

Рис. 4. Диаграммы неизоморфных графов с совпадающими инвариантами