Основные понятия теории графов.

Граф есть конечное множество V, элементы которого называются вершинами, и множество Е его двухэлементных подмножеств, называемых ребрами. Если и , то вершины называются смежными. Поэтому граф можно определить также как симметричное иррефлексивное бинарное отношение смежности на множестве V. Вершины, составляющие ребро, называются инцидентными этому ребру.

Графы с небольшим числом вершин удобно представлять рисунками, на которых вершинам соответствуют точки, а ребрам – соединяющие их линии. Например:

Здесь

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

Граф на n вершинах называется полным, если у него присутствуют все возможных ребер, и пустым, если он не имеет ни одного ребра. Графы и называются дополнительными друг к другу, если их множества вершин совпадают, а ребро присутствует в одном графе в том и только в том случае, если оно отсутствует в другом графе. Таким образом, пустой и полный графы на одном и том же множестве вершин – это два взаимно дополительных графа.

Граф называется подграфом графа , если и . При этом, если , то граф называется остовным подграфом.

Если вершина инцидентна k ребрам, то говорят, что она имеет степень k. Граф называется регулярным степени k, если все его вершины имеют степень k.

На множестве из n вершин существует различных графов. Если два графа имеют одинаковое число вершин и между их вершинами может быть установлено взаимно однозначное соответствие, сохраняющее смежность, то графы называются изоморфными. Два графа, изображенных на рисунке, изоморфны

Изоморфизм устанавливается с помощью биекции: , , , , , .

Путем длины k называется последовательность вершин в которой каждые две рядом стоящие вершины смежны, т.е. , ,…, .

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

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

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

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

Связный граф без циклов называется деревом. Дерево на n вершинах имеет ребер. Необязательно связный граф без циклов называется лесом.

Граф называется двудольным, если множество его вершин можно разбить на 2 непересекающихся подмножества так, что каждое ребро имеет одну вершину из одного подмножества, а другую – из другого: и для любого ребра имеем . Если при этом любая вершина из соединена ребром с любой вершиной из , то граф называется полным двудольным. Для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечетной длины.

В реальных задачах вершинам графа могут соответствовать, например, населенные пункты, а ребрам – связывающие их дороги. Тогда каждому ребру естественно поставить в соответствие длину соответствующей дороги. Вообще, если ребрам графа поставить в соответствие некоторые числа (обычно неотрицательные), то граф называется взвешенным.

Помимо обычных графов часто рассматриваются так называемые ориентированные графы или орграфы.

Орграф – это пара , где V, как обычно, множество вершин, а – множество упорядоченных пар вершин, т.е. ориентированных ребер, которые называются дугами.

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

Число дуг, входящих в вершину, называется полустепенью захода вершины, а число дуг, выходящих из вершины, - полустепенью исхода вершины. Пусть . Через Гбудем обозначать множество таких вершин , что . Через Г^-1обозначим множество вершин таких, что . Таким образом, полустепени захода и исхода вершины равны, соответственно и .

Тест.

1. Степенью однородного графа называется а) число его вершин; б) число его ребер; в) степень любой его вершины.

2. Дерево с n вершинами имеет а) n ребер; б) (n+1) ребер; в) (n-1) ребер.

3. Лес с n вершинами и k компонентами связности имеет а) (n-1) ребер; б) (n-k) ребер; в) k ребер.