2.1.3. Смежность и инцидентность

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

Степенью вершины v графа G(V,E) называется число ребер, инцидентных данной вершине. Обозначение: .

Вершина, имеющая степень 0 называется изолированной, имеющая степень 1 – висячей.

Пример. Для графа, изображенного на рис. 3.5: вершина 3 – изолированная, вершины 1 и 4  - висячие.

Пример. Для графа, изображенного на рис. 3.3.

Ребро e₁ инцидентно вершинам v₁ и v₂. Вершина v₁ инцидентна ребрам e₁ и e₂. Ребра e₁ и e₂ – смежны. Вершины v₁ и v₂ – смежны.

  . p(G)=3, q(G)=5.

Т.о. можно заметить, что .

Теорема Эйлера: .

Доказательство данной теоремы вытекает из того, что каждое ребро дает двойной вклад в сумму степеней вершин.

2.1.4. Изоморфизм графов

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

Графы рассматриваются с точностью до изоморфизма.

Пример

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

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

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

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

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

2.2. Представление графов в эвм

Следует подчеркнуть, что конструирование структур данных для пред­ставления в программе объектов математической модели - это основа искус­ства практического программирования. Мы приводим два различных базовых представления графов.

Выбор наилучшего представления определяется требова­ниями конкретной задачи. Более того, при решении конкретных задач исполь­зуются, как правило, некоторые комбинации или модификации указанных пред­ставлений, общее число которых необозримо. Но все они, так или иначе, основаны на тех базовых идеях, которые описаны в этом разделе.

2.2.1. Требования к представлению графов

Известны различные способы представления графов в памяти компьютера, кото­рые различаются объемом занимаемой памяти и скоростью выполнения опера­ций над графами.

Представление выбирается, исходя из потребностей конкрет­ной задачи. Далее приведены два из наиболее часто используемых представле­ния.

Указанные представления пригодны для графов и орграфов, а после некоторой модифи­кации также и для псевдографов, мультиграфов.

Представления иллюстрируются на конкретных примерах графа G и орграфа D, диаграммы которых представлены на рис. 7.10.

Рис. 3.9. Диаграммы графа (слева) и орграфа (справа), используемых в качестве примеров

2.2.2. Матрица смежности

Представление графа с помощью квадратной булевской матрицы

отражающей смежность вершин, называется матрицей смежности, где

Пример