Теория графов и комбинаторика

ТЕОРИЯ ГРАФОВ И КОМБИНАТОРИКА

специальность ПО

2-й семестр 

Лекция 2

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

      Пусть 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 точек и произвольным образом дадим им в качестве имен имена вершин данного графа; в итоге на плоскости возникнут точки, обозначенные как . Затем для каждой пары точек таких, что , проведем отрезок прямой, соединяющий точки . В результате таких действий возникнет некоторый рисунок, который и называется

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

                 3             3 

                   2                      4      2            5        4 

                        1          5                                  1

                         Рис.1      Рис.2

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

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

      Количество ребер, инцидентных данной вершине 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, а в другом такой степени вообще нет). Однако, проверка двух графов на изоморфизм представляет собой намного более трудную задачу, чем простое сравнение степеней.