- •Множества. Основные понятия. Способы задания.
- •Счетное множество
- •Несчетное множество
- •Существование множеств сколь угодно большой мощности.
- •Отношение на множествах
- •Свойства бинарных отношений на множестве м.
- •Замыкание отношений.
- •Основные булевы функции.
- •Двойственность. Принцип двойственности.
- •Переход от табличного задания функции к аналитическому.
- •Запись бф через сп.(сднф)
- •Построение бф через сс.(скнф)
- •Замкнутость и полнота.
- •Реализация функций многочленом Жегалкина.
- •Запись аналитического выражения функции, заданной таблично, через функцию Шеффера и Пирса.
- •Основные понятия теории графов.
- •Способы задания графов.
- •Подграфы. Операции над графами.
- •Степени вершин графа.
- •Теорема о выделении из всякого замкнутого маршрута (пути) нечетной длины простого цикла (контура) нечетной длины.
- •Нахождение числа маршрутов (путей) через матрицу смежности.
- •Необходимое и достаточное условие существования контура ор-графа.
- •Связность графа. Отыскание компонент связности при графическом задании графа.
- •Диаметр, радиус, центр графа. Алгоритм их отыскания.
- •Отыскание кратчайших расстояний на графе.
- •Ациклические ориетированные графы. Теорема о существовании его начальной и конечной вершины.
- •Ранги вершин. Правильная нумерация вершин.
- •Определение дерева. Теорема о связи любых его двух вершин.
Отыскание кратчайших расстояний на графе.
Расстояние между двумя вершинами – это минимальное число ребер в маршруте. Каждому ребру припишем число Cij. Если Cij=1, то алгоритм даст способ отыскания кратчайшей цепи между парой любых вершин. Рассматривая конкретные практические задачи, Cij может быть любым числом, например, если Cij рассматривать как стоимость пути между i-м и j-м пунктом, то здача о наикратчайшем расстоянии интерпретируется как нахождение пути минимальной стоимости между i-м и j-м пунктами. Графы, каждому ребру которых приписано число Cij, называются нагруженными.
Алгоритм: 1) берется вершина графа и находится наикратчайший путь от этой вершины до всех остальных. 2) затем фиксируют другую вершину и находят расстояние от этой вершины до всех остальных. 1!) выбираем вершину k и считаем, что d0(k,j)={0, if k=j; w, if k≠j}, w> Cij. d1(k,j)=min{d0(k,i)+ Cij}, где i- множество вершин, непосредственно предшествующих вершине j. d(m)(k,j)=min{dm-1(k,i)+Cij}, iB(j). Алгоритм заканчивает работу, как только d(m)(k,j)= d(m-1)(k,j)= d(k,j). Этот алгоритм дает не только кратчайшее расстояние, но и показывает маршрут, по которому нужно двигаться из k-й вершины в j-ю. Этот алгоритм работает как для ор-графов, так и для не ор-графов, но в случае ор-графа может случиться так, что алгоритм закончил работу, а в некоторых вершинах осталось число w, это говорит о том, что данная вершина недостижима из k-й вершины.
Ациклические ориетированные графы. Теорема о существовании его начальной и конечной вершины.
Ациклическим называется ор-граф, не содержащий контуров. Вершину такого графа назовем начальной (конечной), если в нее не входит (не выходит) ни одна дуга.
Теорема (о существовании …): у каждого конечного ациклического графа имеется по крайней мере одна начальная и одна конечная вершина. Доказательство: возьмем вершину Vj и найдем все пути, заканчивающиеся в этой вершине. Т.к. граф конечный и ациклический, то существует самый длинный путь. Обозначим этот путь (V0,V1,V2,…,Vn), тогда вершина V0 является начальной. Действительно, если бы V0 не была бы начальной, то существовала бы дуга (VaV0), и тогда бы путь (V0…Vn) не был бы максимальным. Если заменить направление дуг на противоположное, то свойство ацикличности не нарушится, откуда вытекает доказательство теоремы и о существовании конечной вершины. Ациклический граф, у которого одна начальная и одна конечная вершина, называется направленным. В направленных графах из начальной достижимы все вершины.
Ранги вершин. Правильная нумерация вершин.
Рангом R(j) называется максимальное число дуг пути, соединяющих начальную вершину с j-й. ранги всегда определены, если граф направленный, в противном случае этого может и не быть.
Алгоритм, позволяющий найти ранги вершин: 1) каждой вершине в порядке введеннной нумерации присваиваем ранг=0: R(0)(j)=0, 2) R(k)(j)=max{R(k-1)(i)+1}, где i непосредственно предшествует k. Алгоритм заканчивает работу, когда R(k)(j)= R(k-1)(j)=R(j). если у графа мало дуг, то ранги можно находить геометрически.
Чтобы правильно проставить нумерацию, нужно каждой вершине присвоить номер в порядке возрастания ранга. Нумерация называется правильной, если для любой дуги графа номер начала меньше номера конца.