Лекции по дискретке (1021001), страница 7

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например:

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

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

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

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

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

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

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

Пример.

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

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

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

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

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

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

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

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

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

Замечания.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Ø

2. Ø

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

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

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

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

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

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

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

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

Пример: .

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

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

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

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

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

1. Ø

2. Ø

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

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

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

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

Пример: G:

Теорема.

Для любой вершины графа имеет место .

Доказательство.

Справедливость этого утверждения следует из того, что всякий путь является цепью.

Следствие.

Для любого конечного графа имеет место: .

18.Расстояние и протяжённость в графе.

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

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

Положим по определению .

Легко видеть, что эта описывающая расстояние функция удовлетворяет аксиомам метрики:

4. Неравенство треугольника

Теорема.

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

Теорема.

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

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

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

Существуют диаметральные по протяжённости или длиннейшие простые цепи, их длина называется диаметром протяжённости.

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

Для каждой вершины существуют наиболее длинные простые цепи, имеющие своим концом, их длина

называется числом протяжённости для вершины .

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

Центрами протяжённости называются вершины с минимальным числом протяжённости.

.

Соответствующие наиболее длинные простые цепи от этих центров можно назвать радиальными по протяжённости простыми цепями, а их длину — радиусом протяжённости.

Теорема.

Любые две длиннейшие простые цепи имеют общие вершины.

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

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