Задание №1
1. Проверить справедливость тождеств или включений, используя алгебру множеств и диаграммы Эйлера-Венна.
а) X/Y = (
; б) A/(B/C) = 
/B) 
Решение:
a).Покажем, что X/Y = X 
Если X/Y, то элемент а 
X и а 
Y;
Так как а Y, то а 
, т.е., тогда для выполнения обоих условий необходимо:
а (X 
).
X = 
= 
(правило де Моргана)
Множество (X ) является подмножеством (X 
, поэтому: (X 
, тогда
X/Y = (X 
б). Покажем, что A/(B/C) = /B) :
A/(B/C) =A/(B 
) = A 
= A 
B/C = B 
A 
A 
A/(B 
Задание №2
Изобразите граф и матрицу отношения, обладающего свойствами рефлексивности, транзитивности и антисиммеричности. (не менее 5 вершин)
Решение:
Рефлексивность:
Бинарное отношение R на множестве X называется рефлексивным, если всякий элемент этого множества находится в отношении R с самим собой.
Все диагональные элементы матрицы равны 1; граф содержит петли во всех узлах.
Антисимметричность:
Бинарное отношение R на множестве X называется антисимметричным, если для каждой пары элементов множества а, b выполнение отношений aRb и bRa влечет a=b.
В матрице нет симметрично расположенных 1; для графа не существует двух различных узлов, связанных парой разнонаправленных дуг.
Транзитивность:
Бинарное отношение R на множестве X называется транзитивным, если для любых трех элементов множества а, b, с выполнение отношений aRb и bRс влечет выполнение отношения aRc.
В графе для любых двух дуг, таких, что одна направлена от а к b, а другая от b к с, существует дуга, соединяющая а и с
Задание №3
тождество граф ассиметричность неориентированный
Считая данный граф неориентированным, обозначить его вершины и рёбра разными символами и определить.
|
|
. Локальные степени и окружения каждой вершины в виде структуры смежности;
. Построить матрицы инцидентности и смежности;
. Рассмотреть части графа. Привести примеры суграфа, накрывающего суграфа. Показать подграф, состоящий из трёх вершин. Сколько таких подграфов можно найти в данном графе? Показать примеры пересечения и объединения частей графа;
. Привести примеры циклического маршрута, цепи, простой цепи. Попытаться найти Эйлеров цикл;
. Определить центр, диаметр и радиус графа.
Считая граф ориентированным, определить
. Степени вершин
. Матрицы инцидентности и смежности.
. Привести примеры пути, ориентированной цепи, простой цепи, контура, цикла и простого цикла.
Решение:
Степени вершин:
a - 4; NG(a) = 4;
b - 3; NG(b) = 3;
c - 3; NG(c) = 3;
d - 4; NG(d) = 4;
e - 4; NG(e) = 4;
f - 3; NG(f) = 3;
q - 5; NG(q) = 5;
Количество ребер, инцидентных вершине Х называют локальной степенью вершины.
Множество вершин графа, смежных с некоторой вершиной Х, называется окружением вершины Х и обозначается через NG(X).
Построить матрицы инцидентности и смежности
Матрица смежности
| a | b | c | d | e | f | g | |
| a | |||||||
| b | |||||||
| c | |||||||
| d | |||||||
| e | |||||||
| f | |||||||
| g |
Матрица инцидентности:
| a | b | c | d | e | f | g | |
|
|
. Рассмотреть части графа. Привести примеры суграфа, накрывающего суграфа. Показать подграф, состоящий из трёх вершин. Сколько таких подграфов можно найти в данном графе? Показать примеры пересечения и объединения частей графа.
Граф G:
Цифры (1,2,3,4,5,6,7,8,9,10,11,12,13 - название рёбер)
Не считать рёбра нагруженными.
Суграф-часть графа, образованная удалением из исходного графа некоторых рёбер. Количество вершин графа и суграфа одинаково (если в графе G есть изолированная вершина q, не инцидентная ни одному ребру, покрывающие суграфы этого графа не существуют).
Пример суграфа
Пример накрывающего суграфа
Часть графа, сохраняющего все дуги, инцидентные выделенным вершинам графа G (исходного графа), называют подграфом, порождённым графом G.
Подгаф, состоящий из трёх вершин:
(f, e, q); (f, a, e); (e, a, q); (q, c, d); (d, b, c); (q, d, e) - в данном графе G можно найти 7 подграфов состоящих из трёх вершин.
Объединение: (f, a, q) 
(f, e, q)
Пересечение
