Получение мднф с помощью 1-ого куба:

Функцию 3 переменных записать в виде МДНФ можно с помощью 1-ого куба, для этого достаточно: 1)выделить в кубе вершины соответствующие строкам, на которых функция равна 1; 2) если найдутся 4 выделенных вершины образующие грань куба, нужно записать переменную соответствующую оси, которая эта грань перпендикулярна, если грань пересекает эту ось в нуле, переменную записывают с отрицанием;3) если остались не использованные вершины, найти пары вершин образующие ребро куба, для этого ребра записать конъюнкцию 2-ух переменных соответствующих плоскости которой это ребро перпендикулярна, отрицание у этой пары поставить в соответствии с координатами точки пересечения ребра с плоскостью;4) если остались не использованные вершины, записать соответствующие каждой вершине совершенную элементарную конъюнкцию;5) все записи объединить знаком дизъюнкции.

Получение мднф с помощью карты Карно:

Карта Карно это прямоугольная табл. строки которой соответствуют одной половине аргументов, а столбцы другой. Если число переменных нечетна, тогда для образования столбцов, берут на 1 переменную больше чем для образования строк. В заголовках строк и столбцов записывают все совершенные элементы конъюнкции. Соседние заголовки должны отличаться ровно одним отрицанием.

Совершенная элементарная конъюнкция соответствующая клетке карты составляется из заголовков строки и столбца, где расположена эта клетка. Клетки заполняются 1-ами в том случае если в строке таблицы соответствующей этой клетке стоит 1, если же функция задана в виде СДНФ 1-ами заполняются клетки соответствующие каждой совершенной элементарной конъюнкцией.

В заполненной таблице находят прямоугольные области содержащие клеток, полностью заполненных 1. Для каждой такой области составляют элементарную конъюнкцию из заголовков строк и столбцов. Переменная в нее не включается, если она в заголовках встречается с отрицанием или без него. Из полученных конъюнкций составляется дизъюнкция.

9) Одной из основных булевых операций является сумма Жегалкина или сложение по модулю 2 или двойное сложение.

Она записывается таблицей:

Х	У	Х+У
0	0	0
0	1	1
1	0	1
1	1	0

Не трудно убедиться, что эта операция обладает следующими свойствами:

- коммутативность x+y=y+x

- ассоциативность (x+y)+z=(y+z)+x=x+y+z

- дистрибутивность конъюнкции относительно двоичного умножения x(y+z)=xy+xz

- действие с константами x+0=x; x+1= ; x+x=0; x+ =1

Свойства отрицания двоичной суммы = +у=х+ . В этом легко убедиться из свойства двоичного сложения с константой и свойств коммутативности и ассоциативности. =(x+y)+1=x+y+1=(x+1)+y= +y=x+(y+1)=x+

Многочленом Жегалкина n-переменных называют двоичную сумму всех возможных конъюнкций не более n-переменных.

+ + +…+ + + +…+ +…+

10) Пусть имеется класс булевых функций K={ ( }. Суперпозицией функции этого класса называют любую функцию которая получается из данных переименованием переменных и заменой любой из переменных любой из функцией данного класса. Класс функции называется полным , если с помощью суперпозиции функции этого класса, можно получить любую булеву функцию. Система булевых функций называется независимой, если не одну из ее функций нельзя выразить через другие. Полная независимая система функций называется базисом.

Класс функции K={ ( }, называется замкнутым, если любая суперпозиция ее функции дает функцию этого же класса.

11)Класс булевых f-ий сохран. константу 0, его замкнутость. Число f-ий n переменных, сохран. конст. 0

Класс класс f-ий сохран. конст. 0, так назыв. f-ии у которых . Подсчитаем число f-ий сохран. конст. 0 с n переменнами. Общее число f-ий сохран. конст. 0 –это . Класс f-ии назыв. замкнутым если люб. суперпозиция его f-ий дает f-ию этого же класса.

12) Класс булевых f-ий сохран. константу 1, его замкнутость. Число f-ий n переменных, сохран. конст. 1

Класс класс f-ий сохран. конст. 1, так назыв. f-ии у которых . Общее число f-ий сохран. конст. 0 –это . Класс f-ии назыв. замкнутым если люб. суперпозиция его f-ий дает f-ию этого же класса.

13)Линейная функция.Замкнутость класса линейных f-ий. Число линейных f-ий, с n переменных.

Класс L-линейных f-ий. Булева f-ия яв. линейной если ее можно записать многочленом жегалкина первой степени. Т.к. в записи линейного многочлена Жегалкина с n переменными использ. n+1 коэф. То число, линейных f-ий n-переменных равно .

14)Двойственность булевых f-ий. Самодвойственная f-ия.Замкнутость класса самодвойственных f-ий. Число f-ий самодвойственных, n переменных.

Класс S-самодвойственные f-ии. F-ия –назыв.двойственной f-ей если она получена отрицанием самих переменных = . F-ия назыв. самодвойственной, если она двойственна самой себе, т.е. = . Класс самодвойственной f-ии n-переменных содержит

15)Монотонность булевых f-ий.Замкнутость класса монотонных f-ий.

Класс M-монотонная f-ия. Пусть даны 2 n-ных булевых вектора . F-ия назыв. монотонным если ее значение на предшествующих векторах не превосходят ее значение на последующих . Среди f-ий 2-ух переменных монотонными яв. Только 0,1,xy,xvy.F-ия записанная формулой яв. Монотонной тогда и только тогда, когда она записана с помощью конъюнкцией и дизъюнкцией, но без отрицаний.

16)Полнота множества булевых функций. Базис. Теорема Поста.

Класс f-ии назыв. полным, если с помощью суперпозиции f-ии этого класса можно получить люб.булеву f-ию. К полным относят: - - это след. из того, что для люб. f-ии можно записать СДНФ. -: - - т.к. люб. булеву f-ию можно написать многочленом Жегалкина. Полная независимая система f-ии назыв. базисом. Теорема Поста:Класс булевых f-ий яв.полным тогда и только, когда он содержит:-f-ию не сохр. конст. 0;- f-ию не сохр. конст. 1;- f-ию не яв.самодвойственной;- f-ию не яв.линейной;- f-ию не яв.монотонной.

17)Понятие подмножества. Формула количества подмножеств конечного множества.

Под множеством понимают совокуп. объектов облад. некоторым св-ом.Множества сост. из конечного числа элементов назыв. конечной, из бесконечного числа элементов в конечной.

Формула им. вид

18)Определение операций над множествами: объединение,пересечение,дополнение,разность,симметрическая разность, декартово произведение.

Множества C содерж. элементы вход. в множества A или в мн-во B назыв. объединением мн-в A и B. C=A

Множества C содерж. элементы яв. Одновременно элементами как множества A так и мн-вами B, назыв. пересечением.

Множества C назыв. разностью мн-в A и B,если оно содержит все элементы мн-в A невход в мн-во B.

Множество C назыв. симметрической разностью мн-в A и B, если она содержит элементы A не вход. в B и элементы B не вход. в A.

Множество в которое входят все участвующие в рассмотренное мн-во, назыв. универсальным, обознач. U и изоб. .

Дополнение мн-ва A – назыв. мн-во сост. из всех элементов универсального мн-ва не вход. в мн-во A

19)Формулы количества элементов в объед. двух и трех мн-в,декартовом произведение двух мн-в.

Фоpмула 2-ух мн-в.

Формула 3-х мн-в.

Декартовые произведения 2-ух мн-в назыв. мн-во всех пар, первый элемент которого берется из первого мн-во и второй элемен из второго. Не трудно убедится, число элементов декартово произведение

20)Понятие предиката.Область определения и область истинности предиката.Конъюкция и дизъюнкция предикатов и их области истинности.

Придикатами назыв. выражения с переменными любой природы приращяющиеся в истинное или ложное высказывание при постановке мест переменных к их возможных значений.

Мно-во значений переменных для которых можно сказать истинна предикат или ложно, назыв. его облостью определения и обознач. D(P). Область истиности предиката T(P) назыв. подмножество области опред. На котором этот предикат истинен.

Дизъюнкция предикатов PvQ с общей обл. опред. Назыв. предикат истинна когда истен хотябы один исходный предикат.

Конъюнкция P*Q-это предикат истинна тогда, когда оба предиката истины.

21)Отрицания –предикат истинно когда Р ложно и наоборот, поэтому область истинности T( )=D\T(P)/.

Импликация Р Q это предикат ложное в одном случае когда 1 предикат истинно а 2 ложно т.к если Р Q= v Q, то T(Р Q)=(D\T(P)UT(Q)

Эквивалентность Р Q это предикат истинный когда оба предиката вместе истинны или ложны т.к. Р Q=PQ U то Т(Р Q)= (Т(P) T(Q)) (D\T(P)) (D\T(Q))

22) Квантор общности x-для всех x; Квантор существования х-существует х; переменная находящаяся под знаком квантора называется связанной. Остальные переменные свободные, квантор уменьшает в предикате число переменных на 1. Из определения квантора легко увидеть что получается при его отрицании = , = ;

23)

24) Шифры перестановки. Простейшим способом шифровации являются шифры перестановки. В них буквы криптограммы просто переставляются. Одним из способов такого шифрования являются шифрование таблицы. Ключом служит размер таблицы, сообщение записывает в таблицу по столбцам. Криптограмма считывается по строкам.

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

Шифры сложной замены. Система шифрования Вижинсра

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

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

Примером шифра сложной замены может служить шифр Вижинера. Этот шифр многоалфавитной замены можно описать таблицей (квадратом) Вижинера,. Таблица имеет два входа:

верхнюю строку символов, используемую для считывания очеред­ной буквы исходного открытого текста;

крайний левый столбец ключа.

Последовательность ключей обычно получают из числовых значений букв ключевого слова.

При шифровании исходного сообщения его выписывают в строку, а под ним записывают ключевое слово (или фразу). Если ключ оказался короче сообщения, то его циклически повторяют. В процессе шифрования находят в верхней строке таблицы очередную букву исходного текста и в первом столб­це очередное значение ключа. Очередная буква шифрограммы находится на пересечении столбца, определяемого шифруемой буквой, и строки, опреде­ляемой числовым значением ключа.

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

25)понятие графов. Пусть имеется некоторое множество Х-множество вершин. Пусть имеется множество U некоторых 2 элементов подмножеств из множества вершин. U X X-это множество называют ребра. Не ориентированным графом G(X,U) называют множество вершин и множество ребер. Граф можно задать Перечислением множеств вершин и ребер. Граф удобно изображать диаграммой в которой вершины изображаются толчками а ребра соединяющими их линиями. Ребро соединяющее вершину с собой называются петлей. Граф с петлями называют псевдограф. Если 2 вершины графа соединены более чем одним графом эти ребра называют кратным ребром. Граф с кратными ребрами называют мультиграфом. Вершину называют инициативной ребру если она является началом или концом этого ребра.

Ребра называют инцидентно вершиной если оно начинается и заканчивается этой вершиной. Граф можно задать матрицей инцидентности B=(bij) в которой строки соответствуют вершинам, столбцы ребрам.

2 вершины графа называют смежными если они соединены ребром. Матрица а=(aij) называют матрицу смежности если в ней строки и столбцы соответствуют вершине графа и элементу. Aij=1, ели Xi смежно с Xj.0 в противном случае.

26)Путем графа между вершинами Xi и Xj называют последовательность ребер начинающиеся вершиной xj заканчивающиеся вершиной xi в которой каждая последующее ребро начинается в вершине в которой заканчивается предыдущее ребро. Циклом называется путь начинающийся и заканчивающийся в одной вершине. Путь и цикл называются простыми если они не содержат других циклов. 2 вершины называют связанными если существует путь между ними. Граф называют связным если связна любая пара его вершин. Каждый и связанных подграфов называют компоненты связанности графа.

27)степенью вершины называют число инцидентных ей ребер. Вершина степени 0 называется изолированной. Граф состоящий только из изолированных вершин называют куль-граф. Вершина степени 1 называют висячим.

Теорема 1. Сумма степеней вершин графа всегда четная.

Док во: Сумма степеней кульграфа равнв 0, добавим к кульграфу одно ребро. У 2 вершин степени увеличились на 1 а сумма степеней увеличились на 2. Так происходит с добавлением каждого, сумма степеней вершины ув. На 2 поэтому в результате сумма степеней станет равной удвоенному числу ребер

Теорема 2. Число вершин нечетной степени в графе всегда четная.

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

28)граф называют полным если любая пара его вершин связана ребром. Xn- полный граф с n вершинами. Подсчитаем число ребер в полном графе с n вершинами из каждой вершины такого графа выходит n-1 ребро, поэтому общее число ребер исходящих из каждой вершины равно n(n-1) в нем каждое ребро повторяется ровно 2 раза поэтому число всех ребер равно n(n-1)/2.

Граф называется дополнением графа G если он состоит и всех вершин графа G и только тех ребер которую не хватает граф Gдо полного .

29)РАЧТОЯНИЕ между 2 вершинами A(x,y) называют длину кратчайшего пути между этими вершинами. Эксцентриситет E(x) наибольшее из расстояний от этой вершины до других вершин графа. Диаметром графа D(G) называют наибольшее из расстояний между любой парой вершин. Радиусом графа R(G) называют наименьший из эксцентриситетов его вершины. Центральной вершиной называют такой эксцентриситет который равен радиусу. Центром графа называют множество его центральных вершин.

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

Граф G(X,U) называется двухдольным если его множество вершин можно разбить на подмножества x1 и x2 причем (x1Ux2=x, x1 x2=0)

Двухдольный граф с n вершинами в одной доле и с m вершинами в другой доле наз. Полным и обозначают k c индексом nm если каждая вершина одной ее дроби связана с ребром с каждой вершиной другой доли.

31) Эйлеров цикл ,эйлеров граф. Необходимое и достаточное условие существования эйлерова цикла

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

Теорема:Граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда, когда он связный и каждая его вершина имеет четную степень.

Необходимость: пусть у графа есть эйлеров цикл, значит он проходит через все вершины т.е. граф связан. Будем подсчитывать степени вершин, проходя через эти вершины по эйлеровому циклу. Так как проходя через вершину и покидая ее к степени добавляеться 2 то в итоге каждая вершина имеет четную степень.

Достаточность: пусть граф связан и все его вершины имеют четную степень. При числе вершин n=1,2,3 этот граф имеет эйлеров цикл. Поэтому доказывать будем n>=3 методом математической индукции по числу вершин, n=3 эйлеров цикл есть (база индукции). Предположим, что любой связный граф с k вершинами и четными степенями всех вершин имеет эйлеров цикл. Рассмотрим граф с n+1 вершиной и всеми четными степенями . Начнем движение из произвольной вершины x1 из нее уйдем в некоторую вершину x2 и будем продолжать движение. (рисунок.1)Число вершин в графе конечно, а движение можно продолжать бесконечно, поэтому рано или поздно попадем в вершину x1. Может случиться. Что построенный цикл прошел по всем ребрам ровно один раз и тогда эйлеров цикл построен, если это не так то вычеркнув все пройденные ребра получим новый граф с меньшим числовым числом ребер. Степень его вершин вновь четная. Может случиться что в новом графе изолированных вершин нет, т.е. он снова связан тогда начнем из той же самой вершины x1 и снова построим цикл. Обозначим построенные циклы c1 и с2 так будем продолжать до тех пор пока в графе не появиться хотя бы одна изолированная вершина. В этом случае останется связный граф с четными степенями вершин и с числом вершин <=k но такой граф по предположению имеет эйлеров цикл. Обозначим его c3. Этот цикл имеет хотя бы одну общую вершину с построенными ранее циклами, обозначим ее a. Тогда начиная с вершины a можно построить эйлеров цикл с k+1 вершиной начнем в вершине а, пройдем по циклу с3 затем по верней части цикла с2 потом по циклу с1 и по нижней части цикла с2. Рассмотрим задачу о кенексберских мостах. Превратим этот мультиграф (р.2) в граф,расположив еще по одной вершине в центре каждого моста. Мультиграф стал графом полученный граф имеет вершины нечетной степени поэтому эйлерова цикла в нем нет.

32)Эйлеров цикл. Необходимое и достаточное условие существования эйлерова пути. Неразрешимость задачи о кенегсберских мостах. Эйлеровым путем вне цикла называют называют путь проходящий по каждому ребру графа ровно один раз. Граф с эйлеровым путем называют полу-эйлеровым. Теорема: связный граф является полу-эйлеровым тогда и только тогда когда ровно две его вершины имеют нечетную степень. Связный граф называют гамильтоновым если он содержит гамильтонов цикл, т.е. цикл проходящий через каждую вершину ровно один раз. Граф на рисунке 3 эйлеровым не является , так как имеет вершины нечетной степени. Но таких вершин две х1 и х4. Нетрудно убедиться что он имеет эйлеров путь. Начинающийся в одной из них и заканчивающийся в другой.

33)Планарный граф. Плоский граф. Формула эйлера для плоского графаГраф укладывается на некоторой поверхности, если его можно его можно нарисовать на этой поверхности так, чтобы ребра графа при этом не пересекались. .(р1) Граф называется планарным если его можно уложить на плоскости . Граф который уложен на плоскости называетс плоским. (плоский рис3, планарный рис2)Часть плоскости ограниченная ребрами плоского графа называется гранью. Теорема(формула эйлера)Связный плоский граф с n вершинами ,m ребрами разбивает плоскость на r граней так что n-m+r=2 Доказательство: по индукции по числу ребер. Пусть m=0 тогда n=0, r=1, т.е. формула эйлера выполняется. N-m+r=1-0+1=2(база). Пусть для графа с m ребрами справедлива добавим еще одно ребро. Это ребро может связывать существующую вершину графа с новой вершиной, тогда в этом графе число вершин n’=n+1 m’=m+1 r’=r тогда n’-m’+r’=(n+1)-(m+1)+r=n-m+r=2 новое ребро может соединить две существующие вершины ,тогда n’=n m’=m+1 r’=r+1 тогда n’-m’+r’=n-(m+1)+(r+1)= n-m+r=2

34) соотношение между числом вершин плоского графа. Невозможность представить плоским графом графов К5 и К3,3 Следствие 1: В любом плоском графе число вершин число вершин n и число ребер m удовлетворяет соотношению 3n-m>=6 при n>=3 Докозательство: Пусть число вершин в графе n>=3(1) и граф не имеет циклов. У каждого графа число вершин больше числа ребер n>m или n-m>0 (2) умножим неравенство (1) на неравенство (2) и сложим с неравенством (2) (рис1)

Пусть произвольный плоский связный граф имеет циклы. Обозначим число его граней r подсчитаем сумму s числа его ребер ограничивающих грани. Так как минимальное число ребер ограничивающих грань равно 3 то s>=3r. Так как каждое ребро может ограничивать только две соседние грани; то s<=2m Сравнивая эти два неравенства получаем 2m>=3r выразим число r из формулы эйлера (рис2)

Следствие 2:Графы К5 и К3,3 не являются планарными. В графе К5 число вершин n=5 сисло ребер m=10 (рис1) 3n-m=3*5-10>=6 это неверно. Т.е. граф К5 не может быть плоским . Граф К3,3 двудольный (рис 2) значит его чиклы имеют только четную длину поэтому число ребер ограничивающих грани s>=4r поэтому 2m>=4r выразим r из формулы эйлера 2m>=4(2-n+m) 2n>=8-4n+4m 4n-2m>=8 |:2 2n-m>=4 в графе К3,3 n=6 m=9, тогда 2*6-9=3>=4 неверно т.е. граф К3,3 не может быть плоским графом. Можно показать что граф является планарным тогда и только тогда когда он не содержит в кач-ве подграфов графы К5 и К3,3.

35) Понятие дерева. Теоремы о пути между любыми двумя вершинами дерева и о добавлении ребра между двумя несмежными вершинами. Деревом называется связный граф без циклов. Теорема 1: Любые две вершины дерева соединены ед-ным простым путем. Доказательство: Так как дерево это связный граф, то существует путь между любой парой его вершин xy между которыми существует 2 разных пути . Начинаются они где-то в вершине x потом должны разойтись. Может быть в самом начале, Закончиться они должны в одной и той же вершине y, поэтому в каком то месте они должны сойтись , может быть и в самом конце. В результате получился цикл которого в дереве не существует, значит 2-го пути между двумя вершинами быть не может.

Теорема 2: добавление ребра между несмежными вершинами приводит к появлению в дереве ед. простого цикла. Доказательство: Соединим ребром две такие вершины . По теореме 1 между этими вершинами существует единственный простой путь . Дополнительное ребро превратило этот путь в цикл.

36) Понятие дерева. Теоремы о числе ребер дерева и его мостах. Деревом называется связный граф без циклов. Теорема 3: Дерево с n вершинами имеет m=n-1 ребер. Доказательство: (индукция по числу ребер) Для числа ребер m=1 свойство очевидно: дерево с одним ребром имеет две вершины . Добавим дереву еще одно ребро. Оно не может связывать две существующие вершины, так как между ними существует простой путь, который этим ребром замкнется цикл, и граф перестанет быть деревом. Это ребро не может также связывать две новые вершины, так как в этом случае нарушиться связность. Значит новое ребро связывает существующую вершину с новой вершиной . т.е. добавление одного ребра дереву добавляет ему еще одну вершину и соотношение между числами вершин и ребер сохраняется . Теорема 4: любое ребро дерева является мостом. Действительно удаление ребра (x,у) приводит к исчезновению пути между этими двумя вершинами т.е. число компонент связности увеличилось. Так как дерево это граф его можно задать любым способом как и любые графы. Для деревьев с пронумерованными величинами существует еще один способ задания: код прюфера. Алгоритм построения кода прюфера:1) найти висячую вершину с наименьшим номером 2)включить в код смежную вершину. 3)пройденное ребро вычеркнуть4) повторять пункты 1-3 до исчерпания ребер.

37)Понятие ориентированного графа и способы его задания. Достижимость вершин , матрица достижимости. Ориентированнный граф или орграф G(x,y) состоит из множества x вершин или узлов и бинарного отношения U на множестве x называемого множеством ориентированных ребер, или дуг, или просто ребер. Элемент множества U называется ориентированным ребром или дугой. Если (a,b)€ ᴜ(a,b)- ребро, то а- начальная вершина , В-конечная вершина, так как граф ориентирован , то его ребра на диаграмме обозначают стрелками, орграф может содержать ветви. G(X,U): x={x1,x2,x3,x4}, U={(x1,x2), (x3,x4),(x4,x1),(x1,x3),(x3,x1),(x2,x2)}. (рис1).Так же как неориентированные графы орграф может быть задан диаграммой, матрицей ицедентности и матрицей смежности. Если (x,y) ребро орграфа G(X,U) в котором x-начальная вершина и y конечная вершина то ребро (x,y) называют ицедентным вершинам x и у , а эти вершины ицедентны ребру. (х,у) при этом вершину Х называют смежной к вершине У, а вершину У смежной от вершины Х. Вершина Xi называется достижимой из вершины Xj если существует путь от Xi к Xj. Множество вершин достижимых из данной вершины называется множеством достижимости этой вершины. Матрица (Dij) называется матрицей достижимости если в ней строки и столбцы соответствуют вершинам и в строке с номером i единицы располагаются в столбцах, номера которых соответствуют вершинам достижимости из вершины с номером i. Для записи матрицы достижимости формируют мн-во достижимости каждой вершины алгоритмом похожим на алгоритм фронтоволны. Сформировав Мн-во достижимости вершины заполняют соответствующую строку матрицы достижимости. Пример: по матрице смежности ографа записать матрицу достижимости . Если вершина Xi достижима из Xj и Xj достижима из Xi тогда говорят что эти две вершины взаимно достижимы.(рис2).

38) Ориентированное дерево, его св-ва и элементы. Кодирование двоичным вектором. Оргаф называется корневым деревом. Если в нем существует вершина со степенью входа раной нулю. , ее наз. Корнем. Для всех остальных вершин степень входа рана 1. Каждая вершина достижима с корнем. Корневые деревья принято изображать с корнем наверху и направление ребер вниз. Поэтому ребра можно изображать без стрелок. Корневые деревья с 3 и 4 мя вершинами.) Св-ва корневых деревьев: 1) Число ребер в корневом дереве на единицу меньше числа вершин. 2) если забыть направление ребер корневое дерево превращается в простое дерево. 3) для любой вершины существует единственный путь из корня. Если взять любую вершину и все вершины достижимые из нее, получится поддерево с корнем выбранной вершины. Листья- вершины со степенью выхода раной нулю. Остальные вершины называются внутренними. Уровнем вершины называют длину пути от корня до нее. Высотой дерева называют уровень самого удаленного листа. Если в корневом дереве существуют ребра(x;y) то вершину Х называют отцом вершины У. А вершину У называют Х. Если в корневом дереве существует путь от вершины X до вершины У, то вершину Х называют предком У. А вершину У называют потомком вершины x . корневое дерево можно задать при помощи двоичного кода. Для получения этого кода обходят все ребра дерева начиная от корня и возвращаясь к нему. При первом проходе по ребру в код записывается 0, при втором 1.

39)Бинарное дерево. Сбалансированное бинарное дерево. Дисбаланс вершины. Кодирование бинарного дерева списочной структурой. Бинарным называют дерево в котором у каждой вершины степень выхода не превосходит 2. В бинарном дереве различают правого и левого сына. Бинарное дерево называется сбалансированным если уровень каждого из его листьев либо совпадает с высотой дерева либо на единицу меньше. Бинарное дерево называется полным, если все его вершины кроме листьев имеют степень выхода равную двум. Дисбалансом вершины называют разность между высотой правого поддерева и левого поддерева с корнем в этой вершине. Бинарное дерево записать двоичным кодом нельзя. Так как по нему нельзя определить левым или правым сыном является новая вершина. , поэтому бинарные деревья кодируют списочной структурой. Это таблица из из 3 строк в 1 указывается адрес вершины во второй адрес левого сына в 3 адрес правого сына.

40) Бинарное дерево сортировки и работа с ним. Одна из основных функций компьютера- это хранение данных и их обработка. Поэтому хранение информации должно быть как-то организовано. Можно располагать информацию в порядке ее записи, но затем для обработки придется искать необходимый файл просматривая подряд весь список. Это неудобно и поэтому имена файлов располагают в виде бинарного дерева сортировки:1) всегда начинать с корня. 2) если имя записываемой информации предшествует имени достигнутой вершины идти влево иначе вправо. 3)По достижению новой вершины присвоить имя записываемого файла. Поиск информации: 1) всегда начинать с корня. 2) если имя разыскиваемого файла предшествует имени достигнутой вершины идти влево иначе вправо. 3) по достижению разыскиваемой вершины обработать найденный файл и на этом закончить. Если же в процессе поиска достигнута пустая вершина то выдать информацию разыскиваемого файла. Удаление файла:1) при удалении листа просто удалить эту вершину. 2) если нужно удалить вершину с одним сыном ее удаляют расположив на ее месте ее сына. 3) если требуется удалить вершину Х с двумя сыновьями, идут от нее вправо на одно ребро и затем до вершины не имеющей левого сына удаляют вершину Х и ее левым сыном ее родителя делают вершину У.