Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 14
|
ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ 1.Операции и отношения над множествами. Отношения на множествах Множества А и В называются равными или тождественно равными, тогда и только тогда, когда они состоят из одних и тех же элементов(обозначается А = В или А ≡ В). Множества А и В называются равными илитождественно равными, тогда и только тогда, когда каждый элемент множества А есть элемент множества В и наоборот, иначе множества не равны (А ≠ В). Если каждый элемент множества А является также элементом множества В, то говорят, что А содержится или включается в В. В этом случае пишут А В. Множество A – подмножество множества B, если A B. В тех случаях, когда одновременно имеют место соотношения A B и A B(причем последнее особенно хотят подчеркнуть в явном виде), говорят, что A строго включается в B, и используют запись A B. Строгое включение означает, что A B и во множестве В существует хотя бы один элемент, который не принадлежит А. Множества А и В называются равными, т. и т.т., когда A B и В А. Свойства подмножеств: 1)Пустое множество является подмножеством любого множества: Ø А. 2)Само множество является своим подмножеством: А А. 3)Любое множество является подмножеством соответствующего универсального множества: A U. 4)Для любого множества А его подмножествами являются пустое множество и само множество А. Эти подмножества принято называть несобственными, а все отличные от них подмножества — собственными. Булеан Рассмотрим конечное множество , |А|=n. Множество всех, всевозможных подмножеств конечного множества А называют множеством-степенью или булеаном и обозначают Ρ(А). Теорема: для любого множества А, состоящего из n элементов существует различных подмножеств, т.е. . Графическое представление множествДля наглядного изображения соотношений между подмножествами некоторого универсума используют круги Эйлера (диаграмм Венна). Универсум изображается множеством точек плоскости, ограниченных прямоугольником, а его подмножества - в виде кругов (любых простых областей, ограниченных замкнутой линией) внутри этого прямоугольника. Множество-результат выделяют штриховкой. Операции над множествами Объединение множеств A и B (обозначается A B) – множество, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств, т.е. A B = а а A или а B. Объединение множеств A и B (обозначается A B) – множество, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств, т.е. A B= а а A или а B. Пересечение множеств A и B (обозначается А ∩ B) – множество, состоящее из всех элементов, принадлежащих каждому из этих множеств, т.е. А ∩ B = а а А и а B. Разность множеств А и B (обозначается А \ B) – множество, состоящее из всех элементов множества A, не принадлежащих множеству B, т.е. А \ B =а а А и а B. Дополнение множества А в универсальном множестве U(обозначается , А)– множество, состоящее из всех элементов универсального множества U, не принадлежащих множеству А, т.е. А = U \ A. Симметрическая разность множеств A и B (обозначается A B или A B) – множество, состоящее из всех элементов, принадлежащих в точности одному из этих множеств, т.е. AB а либо а A и а B, либо а A и а B A B = (A \ B) (B \ A) = (A B) \ (A B) |
ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ 2.Бинарные отношения. Особенности бинарных отношений. Свойства бинарных отношений Пусть задано на множестве X, Х2. 1. Рефлексивность: х Х х х. Отношение на множестве X называется рефлексивным, если для любого хХ имеет место х х, то есть каждый элемент находится в отношении к самому себе. Матрица рефлексивного отношения имеет единичную главную диагональ, а граф – петлю возле каждого своего элемента. 2. Антирефлексивность: х Х х х. Отношение на множестве X называется антирефлексивным, если не существует хХ такого, что имеет место х х, то есть ни один элемент не находится в отношении к самому себе. Матрица антирефлексивного отношения имеет нулевую главную диагональ,а граф – не имеет ни одной петли. 3. Нерефлексивность: х Х (x, x) . 4. Симметричность: х, y Х х y => y х. Отношение на множестве X называется cимметричным, если для всех х и y из Х, из принадлежности (x,y) отношению следует, что и (y,x) принадлежит отношению . Матрица симметричного отношения симметрична относительно главной диагонали, а граф – для каждой дуги (x,y) существует обратная дуга (y,x). 5. Антисимметричность: х, y Х х y, y х x = y. Отношение на множестве X называется антиcимметричным, если для всех х и y из Х, из принадлежности (x,y) и (y,x) отношению следует, что x=y. Матрица антисимметричного отношения не имеет ни одной симметричной единицы относительно главной диагонали, а граф – для каждой дуги (x,y) не существует обратная дуга (y,x) и наоборот. Свойства симметричности и антисимметричности не являются взаимоисключающими, примером может служить отношения равенства на множестве натуральных чисел. 6. Транзитивность: х, y, z Х х y, y z => x z. Отношение на множестве X называется транзитивным, если для всех х,y,z из Х, из принадлежности (x,y) и (y,z) отношению следует, что (x,z) также принадлежит . Отношение на множестве X называется антитранзитивным, если для всех х,y,z из Х, из принадлежности (x,y) и (y,z) отношению не следует, что (x,z) также принадлежит . Отношение порядка – антисимметрично, транзитивно. Отношение нестрого порядка () - рефлексивно, антисимметрично, транзитивно. = { (x, y) | xy, x,y N}, = { (x, y) | xy, x,y N}. На множестве множеств: “A B”, “A=B”. Отношение строгого порядка () - антирефлексивно, антисимметрично, транзитивно. = { (x, y) | x>y, x,y N}, = { (x, y) | x<y, x,y N}. На множестве множеств: “A B”. В отношениях полного порядка все элементы сравнимы между собой, а в отношениях частичного порядка не все элементы сравнимы между собой. Отношения полного порядка: = { (x, y) | xy, x,y N }, = { (x, y) | xy, x,y N }. Отношения частичного порядка: = { (x, y) | x>y, x,y N }, = { (x, y) | x<y, x,y N }, на множестве множеств: “A B”, “A B”. |
3.4. Алгебра логики
Булевы функции. Законы алгебры логики. Аналитические способы описания.Полные системы функций.
Определение функции алгебры логики
Пусть множество Х состоит из двух элементов 0 и 1, Х={0,1} Xn = {(x1, …, xn) | i = , xi X}, тогда совокупностью координат некоторого фиксированного вектора (х1, …, хn) Х называется двоичным набором.
Каждому двоичному набору можно поставить в соответствие некоторый номер, равный двоичному числу соответствующему данному набору.
Пусть (х1, х2, …, хn) – логический набор, тогда х12n-1+х22n-2+…+xn20 – номер набора.
Например:
(0,1,1) = 022 + 121+120 = 3
(0,0,1,1) = 023+022 +121+120 = 3
Замечание. Чтобы восстановить набор по номеру – нужно знать количество аргументов.
Логическая переменная – это переменная, которая может принимать только два значения: истина или ложь (TRUE/FALSE, 1/0).
Функция алгебры логики (булева функция, ФАЛ) – f(x1,x2, …,xn) – это функция, у которой все аргументы есть логические переменные, и сама функция принимает только логические значения.
Например:
Построим всевозможные двоичные наборы длиной n = 3.
По теореме, приведенной выше, их количество равно 2n = 23 = 8.
|
Номер двоичного набора |
Набор |
||
|
х1 |
х2 |
х3 |
|
|
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
|
2 |
0 |
1 |
0 |
|
3 |
0 |
1 |
1 |
|
4 |
1 |
0 |
0 |
|
5 |
1 |
0 |
1 |
|
6 |
1 |
1 |
0 |
|
7 |
1 |
1 |
1 |
Существуют следующие способы описания ФАЛ
Табличный способ представления ФАЛ
Любую булеву функцию можно представить таблицей, имеющей 2n строк. Такая таблица называется таблицей истинности.
В левой части таблицы перечисляются всевозможные двоичные наборы значений аргументов, а в правой части – значения некоторой булевой функции.
|
№ |
X1 |
х2 |
… |
хn |
f (х1, х2,…,хn) |
|
0 |
0 |
0 |
… |
0 |
1 |
|
1 |
0 |
0 |
… |
1 |
2 |
|
… |
… |
… |
… |
… |
… |
|
2n-1 |
1 |
1 |
… |
1 |
2n |
ФАЛ можно представить в виде n-мерного единичного куба: если наборам значений аргументов сопоставить точки n-мерного пространства, то множество 2n наборов определяет множество вершин n-мерного куба.
Одномерный куб (n = 1)
Функция принимает значения либо 0, либо 1.
F=0 – пустой кружочек,
F=1 – закрашенный кружочек.
Двумерный куб (n = 2)
Трехмерный куб (n = 3)
Таким же способом можно задать функцию от четырех переменных, в виде четырехмерного куба.
Четырехмерный куб (n = 4)
Количество функций от одного аргумента равно = 4.
Таблица . Функции алгебры логики одного аргумента
|
х |
f0(x) |
f1(x) |
f2(x) |
f3(x) |
|
0 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
1 |
0 |
f0(х) 0 – константа 0 («ложь»)
f1(х) 1 – константа 1 («истина»)
f2(х) = х – переменная х
f3(х) = - отрицание х (инверсия х)
Количество различных ФАЛ от двух аргументов равно = 16.
Таблица 2. Элементарные функции алгебры логики
|
х1х2 |
00 |
01 |
10 |
11 |
|
|
f0 |
0 |
0 |
0 |
0 |
тождественный 0, const 0. |
|
f1 |
0 |
0 |
0 |
1 |
х1 и х2, х1х2, х1&х2, х1х2 – конъюнкция, логическое «и» |
|
f2 |
0 |
0 |
1 |
0 |
- запрет х2, ; х1, но не х2 |
|
f3 |
0 |
0 |
1 |
1 |
х1 повторение первого аргумента |
|
f4 |
0 |
1 |
0 |
0 |
- запрет х1; не х1, но х2 |
|
f5 |
0 |
1 |
0 |
1 |
х2 повторение второго аргумента |
|
f6 |
0 |
1 |
1 |
0 |
, - сложение по модулю 2, неравнозначность |
|
f7 |
0 |
1 |
1 |
1 |
х1х2 – дизъюнкция, сумма, логическое «или» |
|
f8 |
1 |
0 |
0 |
0 |
х1х2 – стрелка Пирса, функция Вебба, ; логическое “или-не” |
|
f9 |
1 |
0 |
0 |
1 |
х1х2 – эквивалентность, равнозначность, тождество |
|
f10 |
1 |
0 |
1 |
0 |
- отрицание, инверсия второго аргумента |
|
f11 |
1 |
0 |
1 |
1 |
х2х1 – обратная импликация |
|
f12 |
1 |
1 |
0 |
0 |
- отрицание первого аргумента |
|
f13 |
1 |
1 |
0 |
1 |
х1х2 – импликация |
|
f14 |
1 |
1 |
1 |
0 |
х1 | х2 – штрих Шеффера, логическое «и-не », |
|
f15 |
1 |
1 |
1 |
1 |
f 1 – тождественная 1, константа 1 |
Условные приоритеты булевых функций
Каждая булева функция имеет свой приоритет при выполнении элементарных функций.
Таблица 3. Условные приоритеты булевых функций
|
1. ( ) |
|
2. отрицание () |
|
3. & |
|
4. ≡ |
Замечание. В пределах одного приоритета операции в выражении выполняются слева направо.
Например:
Дана функция .
Составить таблицу истинности функции 3-х переменных: F (x, y, z).
Изобразить функцию графически.
Решение
Расставим порядок выполнения действий, соблюдая приоритеты.
2
5 3 6 4 1
Выполним операции согласно порядку от 1 до 6.
Таблица 4. Таблица истинности функции F(x, y, z)
|
x |
y |
z |
1 |
2 |
3 |
4 |
5 |
F(x,y,z) |
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
Изобразим функцию на кубе:
Фиктивные аргументы ФАЛ
Две ФАЛ f1(x1, x2, … , xn) и f2(x1, x2, … , xn) называются равными, если они принимают одинаковые значения на всех возможных наборах аргументов.
ФАЛ называется существенно зависящей от аргумента xi, если имеет место неравенство:
f1(x1, x2, … , xi-1, 0, xi+1, … , xn)
f2(x1, x2, … , xi-1, 1, xi+1, …, xn).
В противном случае говорят, что функция несущественно зависит от xi, и xi является ее фиктивным аргументом.
ФАЛ не изменится, если к ее аргументам приписать или вычеркнуть любое количество фиктивных аргументов.
Для нахождения фиктивных аргументов необходимо задать ФАЛ таблично:
Например: Имеет ли функция фиктивные аргументы?
Решение
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
Множество Т0:
|
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
Множество Т1:
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
|
1 |
0 |
0 |
1 |
Если вычеркнуть x во множестве Т0 и Т1, то появятся одинаковые наборы. Следовательно, х не является фиктивным аргументом функции F(x,y,z). Аналогично для аргументов y и z.В результате, функция F(x,y,z) не имеет фиктивных аргументов.
|
Законы булевой алгебры |
|
|
Коммутативность Ассоциативность Дистрибутивность Идемпотентность Закон отрицания отрицания
Закон исключающего третьего Закон противоречия |
Свойства констант Законы де Моргана Законы поглощения Правила склеивания Обобщенное склеивание Правило вычеркивания |
|
Свойства ,, |
|
|
Свойства импликации
Свойства |
Свойства функций Шеффера и стрелки Пирса
Функции и связаны соотношениями аналогичными формулам де Моргана |
Выражение одних элементарных функций через другие
Аналитическая запись ФАЛ
Рассмотрим методы перехода от табличного способа задания функций к аналитическому методу (в виде формул).
Дизъюнктивная нормальная форма (ДНФ)
Конъюнкция называется элементарной, если в ней каждая переменная встречается не более одного раза.
Дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).
Например:
Используя законы алгебры логики преобразовать пошагово функцию F(x,y,z) в ДНФ.Для полученного результата составить таблицу истинности.
Решение
Выполним преобразования по действиям:
.
Составим таблицу истинности для полученного результата:
Таблица 5. Таблица истинности для полученного результата
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Сравнив столбцы, соответствующие функциям в таблицах №4 и №5, необходимо получить одинаковые значения функции.
И так как в построенных таблицах соответствующие столбцы равны, можно сделать вывод, что перевод в ДНФ верен.
Дизъюнктивная совершенная нормальная форма (ДСНФ)
Любая таблично заданная ФАЛ f(x1, x2, …, xn) (кроме тождественного нуля) может быть представлена в следующем аналитическом виде:
Представление ФАЛ в таком виде называется дизъюнктивной совершенной нормальной формой этой функции (ДСНФ).
Алгоритм перехода от табличного задания функции к ДСНФ
Конъюнктивная совершенная нормальная форма
Любая таблично заданная ФАЛ f(x1, x2, …, xn) (кроме тождественной единицы) может быть представлена в следующем аналитическом виде:
Представление ФАЛ в таком виде называется конъюнктивной совершенной нормальной формой этой функции (КСНФ).
Алгоритм построения конъюнктивной совершенной нормальной формы
Например:
Построить ДСНФ и КСНФ для функции F(x,y,z).
Решение
Для нахождения ДСНФ выбираем из таблицы №4 только те строки, в которых стоят наборы значений аргументов, обращающие функцию в единицу. Это вторая, третья и пятая строки. Выпишем конъюнкции, соответствующие выбранным строкам:
.
Соединяя эти конъюнкции знаками дизъюнкции, получаем:
.
Для нахождения КСНФ выбираем из таблицы №4 только те строки, в которых стоят наборы значений аргументов, обращающие функцию в ноль. Выпишем соответствующие дизъюнкции и соединим их знаками конъюнкции.
Получим:
.
Полные системы ФАЛ
Система ФАЛ {f1, f2,…, fn} называется полной в некотором классе функций, если любая функция из этого класса может быть представлена суперпозицией этих функций.
Система ФАЛ, являющаяся полной в некотором классе функций, называется базисом.
Минимальным базисом называется такой базис, для которого удаление хотя бы одной из функций fi, которые его образуют, превращает эту систему функций в неполную.
Любая функция может быть представлена с помощью элементарных функций {¬, &, }. Эта система ФАЛ образует универсальный базис.
Наиболее популярными в алгебре логики являются базисы{,¬},{&,¬}, {},{|}, которые являются минимальными.
Например:
Представить функцию в базисах
{, }, {|}. Для проверки результата составить таблицу истинности.
Решение
Для перевода в базис {, } применим закон де Моргана к ДСНФ функции.
Для перевода функции в базис {|} применим следующие соотношения к ДСНФ функции:
Обозначим
Выполним перевод в базис {|} по действиям.
Проверим преобразования с использованием таблицы истинности:
2 1 3 5 4 6
Таблица 6. Таблица истинности для выражения :
|
№ |
x |
y |
z |
y | y |
x | (y | y) |
3 |
z | z |
5 |
6 |
|
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
2 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
3 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
4 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
5 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
6 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
|
7 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
Аналогично, проверяем и .
Для проверки, построим таблицу истинности для полученной формы функции F(x, y, z).
Таблица 7. Таблица истинности для F(x, y, z)
|
№ |
x |
y |
z |
A |
B |
C |
A | B |
|||||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
2 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
|
3 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
4 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
|
5 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
6 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
7 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
Cтолбцы, соответствующие функции F(x, y, z) в таблицах №7 и №4 равны, следовательно, преобразования выполнены правильно.
5.Неориентированный граф. Виды подграфов. Изоморфизм.
Виды маршрутов неорграфов
Обозначение: Cn – простой цикл, n 3, n – количество вершин.
Pn – простая цепь, n – количество вершин.
Дан граф G. Привести примеры маршрута, цепи, простой цепи, замкнутого маршрута, цикла и простого цикла.
Маршрут M1 – открытый, не цепь и не простая цепь (ребро (3,4) повторяется).
Маршрут M2 – замкнутый, не цикл и не простой цикл (ребро (3,4) повторяется).
Маршрут M3 – не простая цепь (вершина 1 повторяется ).
Маршрут M4 – не простой цикл (вершина 7 повторяется).
Маршрут M5 – простая цепь.
Маршрут M6 – простой цикл.
Связность
.
Число вершинной связности χ(G) – наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу.
Число реберной связности (G) – наименьшее число рёбер, удаление которых приводит к несвязному или одновершинному графу.
Точка сочленения (разделяющая вершина) – вершина v графа G, удаление которой увеличивает количество компонент связности графа G.
Мост – ребро, удаление которого приводит к увеличению числа компонент связности.
Неразделимый граф – граф без точек сочленения.
Блок – максимальный неразделимый подграф графа G.
Граф G: Граф R:
Граф G – связен.
Граф R – несвязен, в графе R три компоненты связности, R1 = {1,2,3}, R2 ={4}, R3={5,6,7}.
Граф G1:
Граф G1 : точки сочленения – вершины a, b, c ;
мост – ребро ab.
Граф G1 не является неразделимым;
блоки графа G1: {c,d,e},{c,b,f},{a,g,h,i},{a,b}.
Граф G2:
Вершинная связность графа G2 равна χ(G2)=1 (удаление вершины 5 приводит к нарушению связности графа G2).
Реберная связность графа G2 равна (G2)=2 (удаление рёбер (5,7), (5,8) приводит к нарушению связности графа G2).
Метрика в неорграфах
Пусть в графе G маршрут М=(1,3,4,5,3,1,7), тогда его длина равна шести.
Обхват графа G –длина минимального простого цикла графа G (если он существует).
Окружение графа G – длина наибольшего простого цикла графа G (если он существует).
Геодезическая (u,v) – кратчайшая простая цепь между вершинами u и v,
доставляющая расстояние между этими вершинами.
Подграфы и изоморфизм.
Пусть V – некоторое непустое множество (V ).
V(2) – множество всех его двуэлементных подмножеств (V(2)={(u,v)|u,vV,неупорядоченная пара}).
Неориентированный граф G – пара множеств (V,E), E V(2) ,
где V – множество вершин графа G,
E – множество рёбер графа G.
Смежные вершины графа G – вершины, соединенные ребром.
Смежные ребра графа G – ребра, имеющие общую вершину.
Инцидентные ребро и вершина – вершина является одним из концов ребра.
Конечный граф – множество вершин графа конечно.
Способы задания графов
A=||aij||, i,j=1.. p, |V|=p, |E|=q.
1, если существует ребро (i,j) ;
aij =
0, иначе .
B=||bij||, i=1.. p, j=1.. q, |E|=q, |V|=p.
1, вершина i инцидентна ребру j;
bij =
0, иначе.
Например:
Задан граф G=(V, E), где
V={a, b, c, d},
E={ab, bc, ac, ad, dc}.
Матрица смежности
|
a |
b |
c |
d |
|
|
a |
0 |
1 |
1 |
1 |
|
b |
1 |
0 |
1 |
0 |
|
c |
1 |
1 |
0 |
1 |
|
d |
1 |
0 |
1 |
0 |
Матрица инцидентности
|
ab |
bc |
ac |
ad |
dc |
|
|
a |
1 |
0 |
1 |
1 |
0 |
|
b |
1 |
1 |
0 |
0 |
0 |
|
c |
0 |
1 |
1 |
0 |
1 |
|
d |
0 |
0 |
0 |
1 |
1 |
Степени вершин графа
Степень вершины deg(v) графа G – число инцидентных ей ребер.
Максимальная степень всех вершин графа G – (G):
(G)=MAX deg(v) .
vV
Минимальная степень всех вершин графа G – (G):
(G) = MIN deg(v) .
vV
Лемма о рукопожатиях.
Изолированная вершина графа G – вершина, степень которой равна 0.
Висячая вершина графа G – вершина, степень которой равна 1.
Доминирующая вершина графа G – вершина, степень которой равна p-1, где p – количество вершин графа G.
Например:
Экстремальные графы
Полный граф – любые две вершины смежны. Обозначается, Kn.
Например:
Пустой граф – не имеет ребер. Обозначается через On .
Мультиграф – граф, не содержащий петель, но с кратными ребрами.
Псевдограф – граф, содержащий петли и кратные ребра.
Например:
Нуль-граф – граф без вершин и без ребер.
Тривиальный граф – граф с одной вершиной (1,0 -граф).
Однородный или регулярный граф – все вершины имеют равную степень.
Например:
Двудольный граф – множество вершин графа можно разбить на два непересекающиеся подмножества V1 и V2 таких, что каждое ребро имеет одну концевую вершину в V1, а вторую – в V2, причем V1V2=, а V1V2=V.
Полный двудольный граф – двудольный, у которого любые две вершины, входящие в разные доли, смежны. Обозначается Kp, q.
Звезда – полный двудольный граф, у которого p=1. Обозначается K1,q.
Биграф - двудольный граф.
Например:
Граф G(V,E) называют k-дольным, если множество его вершин V можно разбить на такие подмножества Vi , i= 1..n , что любое ребро графа имеет одну концевую вершину в Vi , а другую Vj , причём Vi Vj = , i j, i,j=1..n, а Vi=V.
Например:
Изоморфизм графов.
Изоморфные графы – существует взаимноодназначное соответствие, т. е. биекция, между множествами их вершин, сохраняющая отношение смежности.
Изоморфизм графов G и H : G H.
Например:
Заданы два графа G1, G2. Определить изоморфизм G1, G2, построив биекцию их вершин.
Решение:
Граф G1 изоморфен графу G2, потому что существует биекция : V1 V2, сохраняющая отношение смежности.
|
u V1 |
a |
b |
c |
d |
|
(u) V2 |
c |
d |
b |
a |
Например:
Изоморфизм есть отношение эквивалентности, т. к. он:
Подграфы
Помеченный граф – граф, у которого каждой вершине поставлена в соответствие некоторая уникальная отметка (символ, цифра), иначе – абстрактный .
Дополнение графа G - граф G' = (V', E'), такой, что V=V', а E'= V(2) \ E (вершины смежные в G' не смежны в G и наоборот).
Подграф G1 = (V1, E1) графа G = (V, E) – граф, у которого все вершины и ребра удовлетворяют следующим соотношениям V1 V, E1 E.
Остовный подграф графа G - подграф, содержащий все вершины графа G, множество ребер есть подмножество ребер графа G.
Порожденный подграф ( порожденный подмножеством вершин V1) – подграф, множество вершин которого V1 V, а множество ребер Е1 содержит все ребра графа G, инцидентные выбранным вершинам V1.
Например:
Независимое множество вершин – множество вершин графа G: SV такое, что любые две вершины в нем несмежны, то есть никакая пара вершин не соединена ребром.
подграф, порожденный независимым множеством – пустой граф.
Максимальное независимое множество – не является собственным подмножеством другого независимого множества.
Наибольшее независимое множество – наибольшее по мощности среди всех независимых множеств.
Число независимости (G) графа G – мощность наибольшего независимого множества.
Например:
Максимальные независимые множества:
S1={X1, X3};
S2={X2, X7, X8};
S3={X2, X5, X7, X8};
S4={X4, X6};
S5={X1, X3, X7};
S6={X2, X4, X8};
S7={X3, X6};
S8={X1, X4}.
Наибольшее независимое множество: S3={X2, X5, X7, X8}.
Число независимости графа G : (G)=4.
Клика
Клика – антипод независимого множества. Подмножество вершин графа G такое, что любая пара из этого множества является смежной.
подграф, порожденный кликой – полный граф.
Максимальная клика – не является собственным подмножеством никакой другой клики графа G.
Наибольшая клика – наибольшая по мощности среди всех остальных клик графа G.
Кликовое число или плотность (G) графа G – мощность наибольшей клики.
Например:
клики графа G:
S1={a,b,с};
S2={b,d,e};
S3={b,c,e};
S4={b,d,c};
S5={c,d,e};
S6={b,c,d,e}.
Максимальные клики: S1={a,b,с}, S6={b,c,d,e}.
Наибольшая клика: S6={b,c,d,e}.
Кликовое число: (G)=4
Доминирующие множества .Доминирующее (внешне устойчивое) множество – подмножество V’V вершин графа такое, что каждая вершина из V\V’ смежна с некоторой вершиной из V’. Иначе, каждая вершина графа находится на расстоянии не более одного ребра от данного множества.
Минимальное доминирующее множество – нет другого доминирующего множества, содержащегося в данном.
Наименьшее доминирующее множество – доминирующее множество с наименьшей мощностью.
Число доминирования (G) – мощность наименьшего доминирующего множества.
Например:
Минимальные доминирующие множества:
S1={X1, X4}
S2={X3, X5, X6}
наименьшее доминирующее множество: S1={X1, X4}.
Число доминирования: (G)=2.