53. Основные понятия теории графов. Степень вершины графа. Ориентированные графы, связные графы и компоненты связности. Понятие взвешенного графа. Способы задания графа.

Теория Г. – удобн. язык в описании программ-х моделей. Граф – это сов-сть точек и линий в к-рой каждая линия соедин. 2 точки. Точки – вершина Г. Линии – ребра Г. Г. G=G(V,E) это пара двух множеств V-кон-ое множество вершин, Е- двухэлементные подмнож-ва из множ-ва V. G=({V₁, : ,V_n},{(V₁,V₂), (V₂,V₃), : , (V₁,Vn)}).Если ребро е=(V₁,V₂) Г G, тогда V₁-смежна с вершиной V₂ и наоборот. Ребро е инцидентно вершине V₁ и V_2. Любые две вершины инцидентны одному ребру – смежные. Два ребра инцидентны одной вершине – смежные. Если 2 ребра инцидентны 1 и той же паре вершин – кратные рёбра. Если Е=0, то граф пустой. Если каждому ребру приписано направление – граф направленный.

Т.1.Пусть Т дерево с мн-ом вершин V и мн-вом рёбер Е, тогда: 1.Для кажд. пары различных вершин сущест. единст-ый путь в Т связ-щий их; 2. Удаления любого ребра из Т прив-ит к обр-ию Г. с 2мя компон-ми, каждое из кот. яв-ся деревом;

3. Кол-во рёбер |Е|=|V|-1.

Связ-ый Г. удовл-ий люб. из этих условий явл. деревом

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

Т.1.Пусть Г произ-ый плоский граф с числом вершин |V|,с числом рёбер|E|, кот-ый разбивает пл-ть на |F|граней, тогда |F|=|E|-|V|+2.

Элементы теории графов. Фигура, состоящая из точек (вершин) и соединяющих их линий (ребер), называется графом. Граф называется связанным, если любая пара его вершин связанна.

Ориентированные графы. Для указания направления связи между вершинами графа соответствующее ребро отмечается стрелкой. Ориентированное таким образом ребро называют дугой, а граф с ориентированными ребрами – ориентированным графом:

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

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

Способы задания графа:

Явное задание графа как алгебраической системы

<{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>.

Геометрический – рисуются вершины и грани на плоскости.

Степенью вершины назовём удвоенное количество петель, инцидентных этой вершине плюс количество остальных инцидентных ей рёбер.

Подграфом графа называется граф, являющийся подмоделью исходного графа. Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого – U, содержащий те и только те рёбра, оба конца которых входят в U.

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежны.

Графы часто используют для изображения различных отношений (например, иерархических отношений, т.е., на языке математики – отношений частичного порядка).

55. Булевы функции. Полные системы Булевых функций. Применение Булевых функций к релейно-контактным схемам. Булевой ф-ей от n перем. наз-ся отобр-е f:Аn А. С-ма Булевых ф-ий наз-ся полной с-мой, если всякая др. ф-я м.б. получена с пом. суперпозиции исходных ф-ий. (н-р, ( , , ‘), где ‘:(x,y)=x’). Релейно-контактная схема – устр-во из проводников и 2-х контактов. Кажд. контакт подключ. к реле или переключателю. Каждому реле ставится в соотв-е Булева ф-я от перем. x₁ …x_n. Если при данном наборе состояний РК схема проводит ток, то Булева ф-я =1, в прот. сл-е =0. Матем. аппарат алг. логики очень удобен для описания функц-я аппаратных средств к-ра, т.к. осн. с-мой счисления в к-ре я-я двоичная, в которой исп-ся цифры 1 и 0, а зн-ий логич. перем. тоже два: “1” и “0”. В электр. устр-вах к-ра двоичные 1 кодируются более высоким уровнем напряжения, чем 0. Логич. эл-т к-ра — это часть электронной логич. схемы, кот. реализует логич. ф-ю (электронные схемы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ и др. (вентили), а также триггер). Работу логич. эл-тов опис. с пом. таблиц истинности – это таблич. предст-е логич. схемы (операции), в к-ом перечислены все возм. сочетания зн-ий ист-ти входных сигналов (операндов) вместе со знач-ем ист-ти выходного сигнала (результата операции) для кажд. из этих сочетаний.

Схема И:	Схема ИЛИ
Схема И-НЕ	Схема ИЛИ-НЕ
Схема НЕ:

Триггер (защелка) – это электронная схема, широко исп. в регистрах к-ра для надёжного запоминания одного разряда двоичного кода. Триггер имеет два устойч. сост-я, одно из к-ых соотв. 1, а другое – 0. RS-триггер (S и R, соответственно, от английских set – установка, и reset – сброс).

Он имеет два симметричных входа S и R и два симм. выхода Q и ,причем выходной сигнал Q я-я логич. отрицанием сигнала . На каждый из 2х входов S и R могут подаваться входные сигналы в виде кратковременных импульсов ( ). Сумматор — это электронная логич. схема, выполн. суммир-е двоич. чисел. Сумматор служит центр. узлом арифм.-логич. устр-ва к-ра, однако он находит прим-е и в других устр-вах к-ра. Многоразрядный двоичный сумматор, предназн. для сложения многоразрядных двоич. чисел, предст. собой комбинацию одноразрядных сумматоров. Условное обозначение При сложении чисел A и B в одном i-ом разряде приходится иметь дело с тремя цифрами: 1. цифра ai первого слагаемого; 2. цифра bi второго слагаемого; 3. перенос pi–1 из младшего разряда. В результате сложения получаются две цифры: 1. цифра ci для суммы; 2. перенос pi из данного разряда в старший. Применение Булевых функций к релейно-контактным схемам (Переключательная схема) В компьютерах и других автоматических устройствах широко применяются электрические схемы, содержащие множество переключательных элементов: реле, выключателей и т.п. Разработка таких схем весьма трудоёмкое дело. Оказалось, что здесь с успехом может быть использован аппарат алгебры логики. Переключательная схема — это схематическое изображение некоторого устройства, состоящего из переключателей и соединяющих их проводников, а также из входов и выходов, на которые подаётся и с которых снимается электрический сигнал. Каждый переключатель имеет только два состояния: замкнутое и разомкнутое. Переключателю Х поставим в соответствие логическую переменную х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то х равен нулю. Будем считать, что два переключателя Х и связаны таким образом, что когда Х замкнут, то разомкнут, и наоборот. Следовательно, если переключателю Х поставлена в соответствие логическая переменная х, то переключателю должна соответствовать переменная . Всей переключательной схеме также можно поставить в соответствие логическую переменную, равную единице, если схема проводит ток, и равную нулю — если не проводит. Эта переменная является функцией от переменных, соответствующих всем переключателям схемы, и называется функцией проводимости. Найдем функции проводимости F некоторых переключательных схем:

a) Схема не содержит переключателей и проводит ток всегда, следовательно F=1;

б) Схема содержит один постоянно разомкнутый контакт, следовательно F=0;

в) Схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, F(x) = x;

г) Проводит ток, когда переключатель х разомкнут, и не проводит, когда х замкнут, F(x) = .;

д) Схема проводит ток, когда оба переключателя замкнуты, следовательно, F(x) = x . y;