02. Определение графа. Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Локальная степень. Подграф. Полный граф. Матрицы смежностей и инциденций. Изоморфизм графов

Пусть A - любое множество. Обозначим через множество всех Неупорядоченных пар его различных элементов. Например, если A={1,2,3}, то ={(1,2), (1,3), (2,3)}; если A={1,2}, то ={(1,2)}. Если A={1}, то , так как различных элементов в A нет. Когда в записи ={(1,2), (1,3), (2,3)} указывается пара (1,2), подразумевается, что выраже-ния (1,2) и (2,1) означают одно и то же: это и означает, что пара Неупорядоченна, т. е. не имеет значения, в каком порядке записаны эелементы пары.

Графом называется пара множеств , где A - любое непустое множество, а B. Элементы из A называются Вершинами Графа, а элементы из B - его Ребрами. Вот пример графа:

Опишем традиционную Геометрическую интерпретацию графа. Пусть - некоторый граф и . Фиксируем на плоскости произ-вольным образом P точек и произвольным образом дадим им в качестве имен имена вершин данного графа; в итоге на плоскости возникнут точки, обозначенные как . Затем для каждой пары точек таких, что , проведем отрезок прямой, соединяющий точки . В результате таких действий возникнет некоторый рисунок, который и называется

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

Если в некотором графе , где

пара вершин такова, что , то вершины называются Смежными; в этой ситуации каждая из них называется Инцидентной ребру , а ребро называется Инцидентным каждой из вершин . Если вершина и ребро инцидентны, то пишут .

Количество ребер, инцидентных данной вершине A называется ее Степенью или Локал-ной степенью графа в вершине A; степень вершины A обозначается через . В приведенном выше примере степень вершины «1» равна 4, степень вершины «2» равна 2, степень вершины «3» равна 3, степень вершины «4» равна 2, степень

Вершины «5» равна 1. А вот пример графа с локальной степенью 0: ; здесь вершина «3» имеет степень 0. Вершины со степенью 0 называются Изолированными.

Можно проверить, что В любом графе количество вершин нечетной степени обязатель-но четно.

Пусть теперь - два графа таких, что и ; тогда говорят, что является Подграфом графа . Если в некотром графе множество ребер B таково, что , то граф называется Полным. Заметим, что если в полном графе число вершин равно P, то число ребер равно .

Пусть по-прежнему - граф и - его вершины. Построим квадратную матрицу , положив

Очевидно, эта матрца симметрична. Она называется Матрицей смежностей графа . В приведенном выше примере графа матрица смежностей такова:

.

Сопоставим графу еще одну матрицу. Будем считать, что - по-прежнему множество вершин и пусть - множество ребер. Определим матрицу следующим образом:

Введенная так матрица N называется Матрицей инциденций данного графа.

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

,

То матрица инциденций будет такой:

.

В каждом столбце матрицы инциденций всегда ровно две единицы, остальные элементы равны нулю. Если в графе все вершины имеют степень ноль, то матрицы инциденций не существует.

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

1) если , то ;

2) для всякого существует такой, что ;

3) если , то ;

4) для всякого существует такое , что

И .

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

< Предыдущая		Следующая >