Ещё одни лекции (1021740), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Моментом рождения теории графов как математической дисциплины считают появление в 1736 году статьи Эйлера, в которой рассматривалась задача о Кёнигсбергских мостах (см. раздел дополнительные сведения). Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.

Определение.

Граф называется не ориентированным, если каждое его ребро не ориентировано, и ориентированным, если ориентированы все его рёбра.

Определение.

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

Определение.

Вершина, не инцидентная никакому ребру, называется изолированной.

Определение.

Граф, состоящий только из изолированных вершин, называется нуль-графом.

Определение.

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

Рис. 2.1. Полные графы.

Определение.

Рёбра у которых обе концевые точки совпадают называются петлёй. Петля обычно считается не ориентированной.

Определение.

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

Определение.

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

Рис. 2.2 Плоский и не плоский граф.

10.Планарные графы.

Определение.

Планарный граф — это граф, который может быть изображён на плоскости без пересечения рёбер.

Теорема Понтрягина-Куратовского.

Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных (топологически эквивалентных) и .

, полный граф с 5 вершинами граф иллюстрирующий задачу о трёх колодцах

Критерий непланарности:

Достаточное условие — если граф содержит двудольный подграф или полный подграф ,то он является не планарным.

Необходимое условие — если граф не планарный, то он должен содержать больше четырёх (4) вершин, степень которых больше трёх (3) или больше пяти (5) вершин степени больше двух (2).

11.Локальные степени графа. Части и подграфы.

Определение.

Пусть G — неориентированный граф. Число рёбер, инцидентных одной вершине а, будем обозначать . Это число называется локальной степенью или просто степенью графа в вершине а.

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

Теорема: В конечном графе число вершин нечётной степени чётно.

Определение.

Граф Н называется частью графа G, H G, если его множество вершин содержится в множестве вершин графа b, и все рёбра Н являются рёбрами G.

Нуль-граф считается частью каждого графа.

Определение.

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

Определение.

Для любой части Н графа G существует единственная дополнительная часть (дополнение) , состоящая из всех рёбер графа G, которые не принадлежат Н, то есть .

12.Бинарные отношения в теории графов.

Определение.

Бинарное отношение определяется как соотношение , которое выполняется для некоторых пар элементов заданного множества V.

Между бинарными отношениями и графами с однократными рёбрами существует взаимно однозначное соответствие.

Так, например. Нуль — граф отвечает нулевому отношению . Полный граф отвечает универсальному отношению .

Каждое отношение имеет дополнительное отношение, или отрицание , такое что тогда и только тогда, когда не выполняется.

Определение.

Граф является дополнением к Графу , то есть по отношению к полному графу , определённому на V.

Определение.

Для любого отношения существует обратное отношение , такое что тогда и только тогда, когда выполняется .

Определение.

Отношение называется частичным упорядочением, если оно обладает следующими свойствами:

1. Рефлексивность .

2. Транзитивность. Из и , следует .

3. Антисимметричность. Из и следует .

Соответствующий граф транзитивен, имеет петли, и любые две вершины в нём соединены не более чем одним ребром.

Например:

13.Матрицы смежности и инцидентности.

Во многих задачах теории графов (особенно решаемых на ЭВМ) графы удобно описывать матрицами.

Определение.

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

Определение.

Матрицей инцидентности графа называется матрица размера , определённая следующим образом:

В случае неориентированного графа матрица определяется следующим:

Пример.

Неориентированные и ориентированные графы и можно представить в аналитической форме, либо матрицей смежности , либо матрицей инцидентности .

Матрица смежности ( ) для неориентированного графа ( ) всегда симметрична.

Фигурирующая в ней двойка(2) в некоторых случаях может быть заменена на единицу(1).

В матрице инцидентности сумма единиц по столбцам указывает степень вершины .

В общем случае матрица смежности для ориентированного графа уже не будет симметричной.

В матрице инцидентности ставится 1, если дуга исходит из вершины и , если дуга заходит в неё.

14.Маршруты, цепи и простые цепи.

Определение.

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

Замечания.

1. Одно и тоже ребро может встречаться в маршруте несколько раз.

2. Если нет рёбер, предшествующих , то называется начальной вершиной , а если нет рёбер, следующих за , то называется конечной вершиной .

3. Любая вершина , принадлежащая двум соседним рёбрам и , называется внутренней или промежуточной вершиной. Так как рёбра и вершины в маршруте могут повторяться, внутренняя вершина может также оказаться начальной или конечной вершиной.

Определение.

Если маршрут имеет начальную вершину, но не имеет конечной вершины или если он имеет конечную вершину, но не имеет начальной, то он называется односторонне бесконечным.

Определение.

Если маршрут не имеет ни начальной, ни конечной вершины, то он называется двусторонне-бесконечным.

Определение.

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

Любой участок цепи есть цепь.

Определение.

Нециклическая цепь называется простой цепью, если в ней нет повторяющихся вершин.

Определение.

Цикл с концом называется простым циклом, если не является в нём промежуточной вершиной и никакие другие вершины не повторяются.

Участок простой цепи или простого цикла есть простая цепь.

15.Связность, сильная связность и компоненты.

Определение.

Пусть — вершина графа . Свяжем с ней множество , определённое следующим: (существует цепь ведущая из в ).

Свойства множества :

1. Ø

2. Ø

Нетрудно проверить, что отношение заданное в следующем виде:

(существует цепь, ведущая из в ), является отношением эквивалентности на множестве — вершин графа.

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

Определение.

Компонентой связности вершины графа называется подграф порождённый .

Определение.

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

Число связности обозначается .

Пример: .

Определение.

Граф называется связным, если , и не связным, если .

Определение.

Пусть — вершина графа . Свяжем с ней множество , определённое следующим ((существует путь, ведущий из в )&(существует путь, ведущий из в )).

Свойства множеств :

1. Ø

2. Ø

Определение.

Компонентой сильной связности вершины графа называется подграф, порожденный множеством , то есть .

Определение.

Характеристики

Список файлов лекций