Дискретная математика – Шамшев А.Б.

1. Теория множеств. Основные понятия и определения. Способы задания множеств. Основные операции над множествами

Множество - совокупность определенных, вполне различаемых объектов, рассматриваемых как целое.

Элемент множества - отдельный объект множества.

Пустое множество Æ - множество не содержащее элементов.

Универсальное множество (универсум) U – множество, содержащее все возможные элементы в рамках заданного рассмотрения.

Мощность множества |M| - количество элементов множества.

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

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

Способы задания множеств:

Перечисление элементов

М = {a1, a2, a3, …, ak}

M9 = {1, 2, 3, 4, 5, 6, 7, 8, 9}

Выделение определяющего свойства

M = { x | P (x)}

M9 = { n | n NÎ & n < 10}

Определение порождающей процедуры

M = { x | x = f}

M9 = { n | for n from 1 to 9 write n }

Операции над множествами

- Объединение AÈB = {x |xÎ A Ú xÎ B}

Объединением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств А или В.

- Пересечение AÇB = {x |xÎ A & xÎ B}

Пересечением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству А, так и множеству В.

- Разность A\B = {x |xÎ A & xÏ B}

Разностью множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат множеству А и не принадлежат множеству В.

- Симметрическая разность A/B = (AÈB)\(AÇB) = {x | (xÎ A & xÏ B) Ú (xÏ A & xÎ B)}

Симметрической разностью множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат объединению множеств А и В, и не принадлежат их пересечению.

- Дополнение = {x | x Ï A} = U\A, где U - некоторый универсум.

Дополнением множества А до универсального множества называется множество, состоящее из всех тех и только тех элементов, которые принадлежат универсальному множеству, и не принадлежат множеству А.

- Прямое произведение множеств

Прямым (декартовым) произведением множеств А и В, называется множество А´В, состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству А, вторая - В.

А´В = {(a,b) | aÎ A & bÎ B}.

А1´А2´...´Аn = {(a1,a2,…,an) | aiÎ Ai, i=1, 2, …, n}.

Степенью множества А называется его прямое произведение самого на себя: Аn=A´A´... ´A.

Соответственно,

А0 = {L}; А1 = A; А2 = A´A; Аn = A´An-1.

2. Отношения. Виды и свойства отношений, Отношение порядка, Отношение эквивалентности

Термин «отношение» обозначает некоторые виды соответствий, заданные на одном множестве.

Если задано соответствие (Х,R), то о элементе у ÎR(х) говорят, что он находится в отношении R к элементу х: у R х. Отношением называется пара множеств (Х,R), где RÍХⁿ.

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

Если RÍA² - отношение, заданное на множестве А, то

Обратное отношение R^-1={(a,b) | (b,a)ÎR}

Дополнение отношения `R ={(a,b) | (a,b)ÏR}

Тождественное отношение I = {(a,a) | aÎA}

Универсальное отношение U = {(a,b) | aÎA&bÎA} [ U = A²]

Ядро отношения O = R° R-1

Свойства отношений

- Рефлексивность х R х -истинно;

- Антирефлексивность х R х-ложно;

- Симметричность х R у ®уR х;

- Антисимметричность (х R у)&(у R х)®x=y;

- Несимметричность (полнота, или линейность) Если (х R у) – истинно, то (у R х) – ложно;

- Транзитивность (х R у)&(у Rz)®xRz.

Отношение эквивалентности

Отношение является отношениемэквивалентности, если оно рефлексивно, симметрично и транзитивно.

Рефлексивность: Отношение R, определенное на некотором множестве (классе), называется рефлексивным, если для любого элемента x этого множества имеет местоxRx (т.е. x находится в отношении R к самому себе). Примером рефлексивного отношения служит любое отношение типа равенства (тождества, эквивалентности).

Симметричность: В математике бинарное отношение на множестве X называется симметричным, если для каждой пары элементов множества выполнение отношения влечёт выполнение отношения . Формально, отношение симметрично, если .

Транзитивность: В математике бинарное отношение на множестве называется транзитивным, если для любых трёх элементов множества выполнение отношений и влечёт выполнение отношения . Формально, отношение транзитивно, если .

Элементы множества рассматриваются как эквивалентные тогда, когда любой из этих элементов при некотором рассмотрении может быть заменен другим.

Например,

на множестве студентов – отношение «быть в одной группе» или «быть на одном курсе»;

на множестве целых чисел – «иметь одинаковый остаток при делении на число n».

Отношения порядка

Отношения порядка определяют порядок расположения элементов множества.

Отношение является отношением нестрого порядка, если оно рефлексивно, антисимметрично и транзитивно (£, Ê, ³, Í).

Отношение является отношением строго порядка, если оно антирефлексивно, несимметрично и транзитивно (<,Ì, >,É,®).

Множество Х называется упорядоченным, если сравнимы между собой любые 2 его элемента, то есть для них имеет место

x<yилиx = yилиx>y

3. Высказывания. Логические переменные и функции. Способы представления булевых функций. Базис представления булевых функций.

МножествоM путем описания свойств его элементов может быть выделено из универсального множестваU.

Высказывание – это утверждение, которое может быть истинным или ложным.

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

Если множество истинности высказывания – пустое множество, то такое высказывание называют тождественно ложным.

Если множество истинности высказывания совпадает с универсальным множеством, то такое высказывание называют тождественно истинным.

Высказывания, которым соответствуют простые (атомарные, выделяемые одним свойством) множества истинности, называются простыми.

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

Для получения составных высказываний используют различные логические связки: и (Ù, &, *, Ç), или (Ú, |, +, È), не (Ø,`), если … то (®).

Логические переменные

Для обозначения высказываний вводят логические переменные.

Логической переменной называется такая величина х, которая может принимать только 2 значения: 1 – истина или 0 – ложь.

где Х Í U – множество истинности высказывания х в некотором универсуме U.

Связки в составных высказываниях являются логическими операциями, определенными на множестве логических переменных.

Элементарные логические операции.

Логическое отрицание «не» (Ø`).

Логическое сложение «или» (Ú, |, +, È).

Логическое умножение «и» (Ù, &, *, Ç).

Логическим отрицанием (инверсией) высказывания х является высказывание ` х (не х) со множеством истинности `Х, являющимся дополнением множества истинности Х высказывания х до универсального множества U.

х	` х	х ` х инвертор

Логическим сложением (дизъюнкцией) высказываний х и у является высказывание х Ú у (х или у) со множеством истинности Z=Х È Y, являющимся объединением множества истинности Х высказывания х и множества истинности Y высказывания y.

х	y	х Ú у	х y х Ú у дизъюнктор

Логическим умножением (конъюнкцией) высказываний х и у является высказывание х Ù у (х и у) со множеством истинности Z=Х Ç Y, являющимся пересечением множества истинности Х высказывания х и множества истинности Y высказывания y.

х	y	х Ù у	&     х y х Ù у конъюнктор

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

Логическая функция – это функция вида f (x1,x2,…,xn), принимающая значение 0 или 1 на наборе логических переменных x1,x2,…,xn.

- Выражение алгебры логики f (x1, x2, x3) = x1 + x2 *` x3

- Таблица истинности

4. Представление функций алгебры логики в аналитическом виде. ДНФ. СДНФ

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

Результатом вычисления логической функции является логическое значение.

Каждый упорядоченный набор логических переменных функции может быть представлен в виде двоичного числа: i = х ₁·2^n-1 + х ₂·2^n-2 + … + х _n-1·2¹ + х _n·2⁰

Для обозначения переменных в логических функциях используются литералы. Литерал – это булева переменная х или ее дополнение ` х.

Литералы записывают как х ¹ для переменной х, и х ⁰ для ее дополнения.

Терм – это выражение, составленное из литералов различных переменных (по одному литералу на каждую переменную), соединенных либо операцией умножения (конъюнктивный терм), либо операцией сложения (дизъюнктивный терм).

Например,

Ранг терма определяется количеством переменных, входящих в данный терм.

Минтерм (полное произведение или конъюнктивный терм) n переменных – это булево выражение, которое имеет форму произведения всех булевых переменных или их дополнений, то есть минтерм состоит из n литералов по 1-му литералу на каждую переменную.

Дизъюнктивные формы представления логических функций

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

, где i – номера наборов, на которых функция равна 1.

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

Если на каком-либо наборе функция f(х’ ₁, х’ ₂… х’ _n)=1, то вследствие того, что х Ú1=1 в представлении функции всегда найдется минтерм m_i=1.

Если же на наборе х” ₁, х” ₂… х” _n f(х” ₁, х” ₂… х” _n)=0, то в данном представлении не найдется ни одного элемента, равного 1, так как 0 Ú 0 Ú … Ú 0 = 0.

Получается, что каждому набору i, для которого f_i =1, соответствует минтерм m_i, а для наборов j, на которых f_j =0, нет ни одного минтерма m_i=1. Поэтому таблица истинности однозначно отображается аналитической записью вида:

Следствие. Любая таблично заданная логическая функция может быть представлена в виде:

где

Объединение конъюнктивных термов переменного ранга называют нормальной дизъюнктивной формой (НДФ) представления логической функции.

Например,

f (x₁, x₂, x₃) = x₁ + x₂ ·` x₃

f (x₁, x₂, x₃, x₄, x₅) = x₁ + x₂ ·` x<sub>3</sub> · x<sub>4</sub> ·` x₅ +`x<sub>2</sub> ·` x₃

Объединение конъюнктивных термов максимального ранга называют совершенной нормальной дизъюнктивной формой (СНДФ) представления логической функции.

СНДФ является единственной.

Свойства СНДФ:

- СНДФ не имеет двух одинаковых минтермов

- Ни один минтерм СНДФ не содержит двух одинаковых множителей

- Ни один минтерм СНДФ не содержит вместе с переменной ее отрицание

5. Геометрическое представление логических функций. Минимизация булевых функций. Карты Карно

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

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

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

Примеры полных базисов: {и, или, не}; {и, не}; {или, не}; {функция Шеффера}; {функция Пирса}.

Геометрическое представление логических функций

Каждый набор х 1, х 2… х n может рассматриваться как n-мерный вектор, определяющий точку n-мерного пространства.

Все множество наборов, на которых определена функция n-переменных f(х 1, х 2,.., х n), представляется в виде вершин n-мерного куба.

Отмечая точками вершины, где функция равна 1, получаем ее геометрическое представление.

Функцию 2-х переменных можно представить на плоскости в декартовой системе координат.

Две вершины, принадлежащие одному и тому же ребру, называются соседними и «склеиваются» по переменной, меняющейся вдоль этого ребра. («склеивание» по х ).

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

Термы максимального ранга называют 0-кубами (точки) и обозначают К0.

Если 2 0-куба из комплекта К0 отличаются только по 1-й координате, то они образуют путем «склеивания» 1-куб К1 (отрезок).

Если 2 1-куба из комплекта К1 отличаются только по 1-й координате, то они образуют путем «склеивания» 2-куб К2 (плоскость).

И т.д.

Карты Карно – развертки кубов на плоскости, где вершины куба – клетки карты, координаты которых совпадают с координатами соответствующих вершин куба.

Карта заполняется также как таблица истинности: в клетке ставится 1, если эта клетка соответствует набору, на котором функция равна 1.

х1	х2	х3	f (x1, x2, x3)	x1	K0 {010; 100; 101; 110; 111}
				K1 { *10; 10*; 1*0; 1*1; 11*}
				K2 { 1** }
				K0 {000; 001; 011}
				K1 {00*; 0*1}

6. Теория графов. Основные определения. Инварианты графа. Изоморфизм графов. Способы представления графов.

ГрафомG(V, E) называется совокупность множеств V (точек) и Е (линий), между которыми определено отношение инцидентности, причем каждый элемент е ÎЕинцедентен ровно двум вершинам u’, u’’ ÎV.

Степень вершины равна числу ребер, инцидентных ей.

Ребро S и вершина V (U) называются инцидентными, если ребро S = <U, V>соединяет вершины U и V.

Sи U – инциденты

S и V – инциденты

Вершины U и Vназываются смежными, если ребро S = <U, V>соединяет вершины Uи V.

Ребра, инцидентные одной и той же вершине, называются смежными.

Множество вершин, смежных с вершиной V,называется множеством смежности вершины V.

G(V, E) = <V; E>, V ¹ Æ, E = { e= { a,b } | a,b Î V&a ¹ b&e ƹ &"e Î E|e|=2 }

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

Ребро можно обозначить

не только как множество { v1, v2 },

но и какпару (v1, v2).

Граф изображают диаграммой: вершины - точками (или кружками),ребра - линиями.

На рис.4 диаграмма графа, имеющего 4 вершины и 5 ребер.

Множества смежности вершины v1:

Г+(v1) = {v2, v4} Г*(v1) = {v1, v2, v4}

Множество смежности множества вершин А={ v1, v2 }:

Г (А) = {v1, v2, v3, v4}

Виды графов:

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

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

- Граф, в котором каждая пара вершин соединена ребром, называется полным (Kp).

Полный граф с p вершинами имеет максимально возможное число ребер: q(Kp) = p (p - 1) / 2

- Ориентированный граф содержит направленные ребра (направления ребер отмечаются стрелками).

- Пустой граф – если множество вершин V пусто, то пусто и E.

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

- Псевдограф – граф с петлями. Ребро может соединять некоторую вершину саму с собой, такое ребро называется петлей.

-

Выражение "граф G (V, E)" означает неориентированный непомеченный граф без петель и кратных ребер с множеством вершин V и множеством ребер Е.

Инварианты графа

Инвариант графа в теории графов — некоторое обычно числовое значение или упорядоченный набор значений (хэш-функция), характеризующее структуру графа и не зависящее от способа обозначения вершин или графического изображения графа.

Количество ребер, инцидентных вершине v, называется степенью (валентностью) вершины V.

(Если не оговаривается особо, то петля учитывается дважды при подсчете d(v))

Степень изолированной вершины равна нулю (то есть d(v) = 0).

Если степень вершины равна единице (то есть d(v) = 1), то вершина называется концевой или висячей.

Обозначим минимальную степень вершины графа G – d(G), а максимальную –через D(G):

d(G(V, E)) =min d(v),D(G(V, E)) = max d(v).

Если степени всех вершин графаравны k, то граф называется регулярным графом степени k:

d(G) = D(G) = k.

Степень регулярности является инвариантом графа и обозначается r(G). Для нерегулярных графов r(G) не определено.

Пример:

На рис.6. приведены диаграммы двух регулярных, но неизоморфных графов степени 3.

На рис.7. приведена диаграмма регулярного графа степени 3.

Изоморфизм графов

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

Способы представления графов

1) Перечень ребер (1,3) (3,3) (2,3)

2) Матрица инцидентности. В матрице столбцы соответствуют вершинам графа, строки – ребрам. Если ребро инцидентно вершине, то в клетку (i,j) матрицы инцидентности надо занести 1, и 0 – в противоположном случае. Для ориентированного графа «1» означает, что начало дуги в j-ой вершине, а «-1», что в j-ой вершине – конец дуги, «2» (или любое другое число, отличное от 0,1,-1) – если в j-ой вершине петля.

3) Матрица смежности. Строки и столбцы матрицы помечены номерами вершин. Для неориентированного графа в «1» (i,j) клетке матрицы соответствует наличие ребра, инцидентного j вершине. Для орграфа – наличие ребра с началом в i-той вершине и концом в j-той. Матрица смежности неориентированного графа симметрична, а орграфа необязательно.

4) Массив векторов смежности. Позволяет сжать разреженные матрицы смежности и инцидентности. Строки помечены номерами вершин и содержат номера смежных вершин.

7. Маршруты, цепи, циклы в графе. Связность графа. Деревья.

Маршрутом M(v0,vk) в графе называется чередующаяся последовательность вершин и ребер v0, e1, v1, e2, v2,..., ek, vk, в которой любые два соседних элемента инцидентны.

- Если v0 = vk, то маршрут замкнут, иначе открыт.

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

- Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью.

- В цепи v0, e1,..., ek, vk вершины v0 и vk называют концами цепи. Говорят, что цепь с концами u, v соединяет вершины v и u. Цепь, соединяющая вершины u и v, обозначается < u, v>.

Очевидно, что если есть цепь, соединяющая вершины u и v, то есть и простая цепь, соединяющая эти вершины.

Замкнутая цепь называется циклом.

Число циклов в графе G обозначается z(G).

Замкнутая простая цепь называется простым циклом.

Граф без циклов называется ациклическим.

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

Граф, состоящий из простого цикла с k вершинами, обозначается Сk.

Пример:

v1, v3, v1, v4 - маршрут, но не цепь;

v1, v3, v5, v2, v3, v4 - цепь, но не простая цепь;

v1, v4, v3, v2, v5 - простая цепь;

v1, v3, v5, v2, v3, v4 - цикл, но не простой цикл;

v1, v3, v4, v1 - простой цикл.

Связность

Две вершины в графе связаны, если существует соединяющая их (простая) цепь.

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

Отношение связанности вершин является эквивалентностью.

Классы эквивалентности по отношению связанности называются компонентами связности графа.

Число компонент связности графа G обозначается k (G).

Граф G является связным тогда и только тогда, когда k (G) = 1.

Если k (G) > 1, то G - несвязный граф.

Граф, состоящий только из изолированных вершин (в котором k (G)= p (G) и r (G) = 0), называется вполне несвязным.

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

ТЕОРЕМА. Если граф G имеет р-вершин и k-компонент связности, то максимально возможное количество ребер в нем N(p, k) = ½(p - k + 1)(p - k)

Связность характеризуется:

- Числом вершинной связности (числом связности) c(G) - наименьшим количеством вершин, удаление которых приводит к несвязному или тривиальному графу.
Так, c(K1) = 0; c(Kp) = p - 1; c (Cp) = 2.

- Числом реберной связности λ(G) - минимальным количеством ребер, удаление которых приведет к несвязному графу.

В общем случае c(G) £ λ(G) £ degmin(G), где degmin(G) - минимальная степень вершин в графе.

- Рассмотрим случай λ(G) £ degmin(G):

o Если граф тривиален, следовательно, в нем нет ребер, а значит: λ(G) = deg(G) = 0.

o Если G - связный граф, то превратить его в несвязный граф можно следующим образом: найти вершины с минимальной степенью и удалить инцидентные им ребра.

- Рассмотрим случай c (G) £ λ(G):

o Для несвязных графов c = λ = 0;

o Для графа с мостом c = λ = 1.

o В общем случае c £ λ, так как удаление вершины ведет за собой удаление всех инцидентных ребер.

Расстояния между вершинами, ярусы и диаметр графа

- Длиной маршрута называется количество ребер в нем (с повторениями). Если маршрут М = v0, e1,..., ek, vk, то длина М равна k (обозначается | M | = k).

- Расстоянием между вершинами u и v (обозначается d(u, v)) называется длина кратчайшей цепи < u, v>, а сама кратчайшая цепь называется геодезической.

- Множество вершин, находящихся на одинаковом расстоянии n от вершины v (обозначение D(v, n)), называется ярусом: D(v, n) = { u Î V | d(v, u) = n }

Ясно, что всякий граф однозначно разбивается на ярусы относительно данной вершины.

- Диаметром графа G (обозначается D(G)) называется длина длиннейшей геодезической цепи.

- Обхват графа - это длина кратчайшего простого цикла.

- Окружение графа - длина максимального простого цикла.

Эксцентриситет и центр

- Эксцентриситетом e(v) вершины v в связном графе G(V, E) называется максимальное расстояние от вершины v до других вершин графа G: e(v) = max d(v, u).

Наиболее эксцентричные вершины - это концы диаметра.

- Радиусом R(G) графа G называется наименьший из эксцентриситетов вершин: R(G) = min e(v).

- Вершина v называется центральной, если ее эксцентриситет совпадает с радиусом графа, e(v) = R(G).

- Множество центральных вершин называется центром и обозначается С(G): С(G) = { v Î V | e(v) = R(G) }.

Пример:

На рис.9. указаны эксцентриситеты вершин и центры двух графов. Вершины, составляющие центр, выделены.

Деревья

- Граф без циклов называется ациклическим (или лесом).

- Дерево - это связный ациклический граф. (обозначается Tn, где n - количество вершин)

Дерево можно построить путем добавления ребер в его вершинах.

- Простейшее дерево состоит из 2 вершин, соединенных ребром.

- При добавлении очередного ребра, добавляется еще одна вершина.

o Граф G - дерево, если это связанный граф и p=q+1, где р, q - количество вершин и ребер соответственно.

o Граф G - дерево, если это ациклический граф такой, что если между двумя его вершинами провести ребро, в нем получится ровно 1 простой цикл.

o Граф G - дерево, если любые 2 его вершины соединены простой цепью.

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

- Если имеем граф с характеристиками (p, q)-граф, то для получения дерева надо удалить q – p + 1 ребро. Данное число называется циклическим рангом графа или цикломатическим числом ν(G) = q – p + 1.

- Число ν*(G)= p – 1 ребер любого остова графа G называется коциклическим рангом графа G.

ν(Tn) = 0, ν(Cn) = 1 - простой цикл,

ν(Gk) = q - p + k, ν*(Gk) = p - k,

где Gk - несвязный граф состоящий из k -компонент связности.

ТЕОРЕМА. Центр свободного дерева состоит из одной вершины или из двух смежных вершин:

z(G) = 0 & k(G) = 1 Þ C(G) = K1 Ú C(G) = K2.

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

Для деревьев K1 и К2 утверждение теоремы очевидно.

Пусть теперь G(V, E) - некоторое свободное дерево, отличное от К1 и К2. Рассмотрим граф G'(V', E'), полученный из G удалением всех висячих вершин. Заметим, что G' - дерево, поскольку ацикличность и связность при удалении висячих вершин сохраняется.

Далее, если эксцентриситет eG(v) = d(v, u), то u - висячая вершина в дереве G. Поэтому " v Î V' eG(v) = eG' (v) + 1 и при удалении висячих вершин эксцентриситеты оставшихся уменьшаются на 1. Следовательно, при удалении висячих вершин центр не меняется, C(G) = C(G').

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

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

Основной вопрос теории перечисления деревьев - сколько существует деревьев Тn неизоморфных друг другу.

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

 

8. Расстояние между вершинами графа. Алгоритм поиска кратчайшего пути.

 

Пусть G = (М,R) – связный неорграф, а, b — две его несовпадающие вершины. Длина кратчайшего (а,b)-маршрута называется расстоянием между вершинами а и b и обозначается через р (а,b). Положим р (а,а) = 0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:

— р (а,b) > 0;

— р (а,b) = 0 Û а = b;

— р (b,а) = р (а,b)(симметричность);

— р (a,b) £ р (а,с) + р (с,b)(неравенство треугольника).

Если М = { a_i,a₂,…,a_n }, то матрица Р = (p_ij),в которой р_ij = p (

⇐ Предыдущая3456789101112Следующая ⇒

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

---

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: