Краткие ответы на экзаменационные вопросы по дисциплине "Дискретная математика" (Предмет дискретной математики. Метод Блейка-Порецкого), страница 6

Дистрибутивность К отн-но Д

x₁  (x₂x₃)=(x₁x₂) (x₁x₃) 4.17

Идемпотентность

x*x=x 4.18

Закон 2-го отрицания

=х 4.19

Св-ва констант 0 и 1 4.20

х1=х; х0=0; х1=1; х0=х; =1; =0

Правило Де Моргана

=; = 4.21

Закон противоречия х=0 4.22

Закон исключенного третьего х=1 4.23

Поглощение хху=х; х(ху)=х 4.24

Склеивание хух=х 4.25

Обощенное склеивание

xzyxy=xzy 4.26

xy=xy 4.27

35.Основные понятия теории графов

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

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

В ДМ методы теории графов применяются при анализе и синтезе различных дискретных преобразований (функцион-е блоки ПК, комплекс программ)

Термин «граф» впервые появился в книге выдающегося венгерского математика Д. Кёнига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (XVIII в.).

36. Ориентированные графы (ОГ).

Графы, в к-х связи направлены, называются ориентированными.

ОГ G задается 2 мн-ми V и Е, где V – конечное мн-во, эл-ты к-го наз-т вершинами или узлами, Е – мн-во упорядоченных пар, эл-ты которого наз-т дугами.

UV

Если вершины U и V соединены дугой, где U – начало, V – конец, то они наз-ся смежными. Если дуга имеет начало и конец в одной и той же вершине, то эту дугу наз-т петлей. Вершины, связанные дугами, наз-т связанными отношением непосредственной достижимости.

Дугу (U,V) наз-т заходящей в V и исходящей из U. Дугу наз-т инцидентной вершине, если она исходит заходит в нее.

Полустепенью захода вершины наз-т число всех заходящих в нее дуг и обозн-т dg ^– V

Полустепенью исхода вершины наз-т число исходящих из нее дуг и обозн-т dg ⁺ V

Степенью вершины наз-т сумму полустепеней захода и исхода.

Путь в ОГ G – послед-сть вершин V₀,V₁,…,V_n такая, что V_i  V_i+1, если V_i+1 сущ-т

Если путь конечен и представим в виде последовательности V₀,V₁,…,V_n, то число их – длина пути.

Вершина V достижима из вершины U, если сущ-т путь V₀,V₁,…,V_n, где V₀=U, V_n=V. U – начало пути, V – конец пути.

U*V

Простой путь – путь, все вершины к-го, кроме, возможно, 1-й и последней, попарно различны.

Контур – простой путь ненулевой длины с совпадающим началом и концом.

ОГ, не содержащий контуров наз-ся безконтурным графом.

37.Неориентированные графы (НГ).

Графы, в к-х связи не направлены, называются неориентированными.

НГ G задается 2 мн-ми V и Е, где V – конечное мн-во, эл-ты к-го наз-т вершинами или узлами, Е – мн-во неупорядоченных пар, эл-ты которого наз-т ребрами.

(U;V)

Если вершины U и V соединены ребром, где U – начало, V – конец, то они наз-ся смежными. Эти вершины наз-т связанными отношением непосредственной достижимости.

Ребро наз-т инцидентной вершине, если она явл-ся одним из его концов.

Степенью вершины наз-т число всех инцидентных ей ребер и обозн-т dg V

Цепь в НГ G – послед-сть вершин V₀,V₁,…,V_n такая, что V_i  V_i+1, если V_i+1 сущ-т

Если цепь конечна и представима в виде последовательности V₀,V₁,…,V_n, то число их – длина цепи.

Вершина V достижима из вершины U, если сущ-т цепь V₀,V₁,…,V_n, где V₀=U, V_n=V. U, V – концы цепи.

U□*V

Простая цепь – цепь, все вершины к-го, кроме, возможно, 1-й и последней, попарно различны.

Цикл – простая цепь ненулевой длины с совпадающими концами.

НГ, не содержащий циклов наз-ся ацикличным графом.

38.Способа задания графов.

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

Матрица инцидентности и матрица смежности явл-ся важными характеристиками графов.

МИ ||_ij|| размера m*n по верт и гориз, указ-ся вершины и ребра соот-но, на пересении i-й вершины и j ребра в случае неотриц-го графа представ-ся 1, если они инциденты и, и 0 если наоборот.