Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Функциональные элементы. СхемыСодержание книги Похожие статьи вашей тематики
Поиск на нашем сайте
.
При подаче на выходы любой комбинации двоичных сигналов, на выходе также возникает сигнал. Каждый вход – аргумент функции. Выход – булева функция от аргументов.
Из функциональных элементов можно строить по правилам их соединения схемы (логические сети).
Два и более входов можно отождествлять.
Возможные соединения функциональных элементов соответствуют булевым функциям и их суперпозициям.
Полный набор булевых функций, который мы будем использовать для построения логических сетей (схем) в какой-нибудь задаче, мы назовем базисом из функциональных элементов. Число функциональных переменных считаем сколь угодно большим.
Базис называется полным, если с его помощью можно реализовать любую булеву функцию в виде схемы.
Очевидно, чтобы базис был полным, необходимо и достаточно, чтобы система функций, реализуемых элементами базиса, была полной.
Пример полного базиса.
- Дизъюнктор
- И
Чтобы построить минимальную функциональную схему для функции на конъюнкторах, дизъюнкторах и инверторах, которая реализует эту функцию, нужно 1. Найти минимальную ДНФ. 2. Для любой из минимальных ДНФ (их может быть много) попробовать упростить формула с помощью вынесения за скобки общего множителя. Сумматор n-разрядных двоичных чисел Составить элементы с 2n входами и n+1 выходом, реализующих сложение n-разрядных двоичных чисел вида X = XnXn-1…X1 Y = YnYn-1…Y1 Z = x+y = Zn+1Zn…Z1 X+Y – сумма чисел. Для решения такой задачи вводим qi – единица переноса из одного разряда в другой. Формулы сумматора Zi = Xi + Yi + Qi – сумма по модулю 2 Qi+1 = XiYi V XiQi V QiYi Лекция 11 Графы
Графом (G) будем называть тройку объектов (V, X, q)
V – множество n вершин. X – конечное множество ребер. q - функция инцидентности, которая каждому элементу множества X ставит в соответствие пару элементов из множества V.
q задана на множестве X.
Если в значении функции инцидентности допускается перестановка вершин, то граф называется неориентированным. В противном случае граф называется ориентированным (Орграф). Vj – начало ребра Vk – его конец
q(xi) = (Vj, Vk) – ребро инцидентно в вершине Vj и в вершине Vk.
Если одной и той же паре вершин инцидентно несколько ребер, то ребра называются кратными. Если на ребре xi0 q(x0) = (Vj0, Vj0), то ребро называется петлей.
Способы задания графов 1. Аналитический Если вершине не инцидентно никакое ребро, то эта вершина называется изолированной. Выписываются все ребра и пишутся напротив две пары вершин, которым они инцидентны. В конце выписываются все изолированные вершины. 2. Геометрический Каждая вершина графа задается точкой. А ребра, инцидентные паре вершин – кривой. Желательно рисовать кривые без пересечения. Если пересечения существуют, то их надо отличать от вершин.
3. С помощью матрицы инцидентности A(m*n) m = [V] – число вершин n = [X}- число ребер
а) Неориентированные графы Aij = {0, если Vi не инцидентно xj, 1, если Vi инцидентно xj)
б) Орграфы Aij = {0, если Vi не инцидентно xj, -1, если Vi - начало xj, 1, если Vi - конец xj)
Для петель нужны дополнительные предположения.
4. Матрица смежности (задается одинаково для всех графов)
B(m*m) m = [V]
Bij равно числу ребер, инцидентных паре вершин (oi, oj) Если граф не ориентирован, то матрица симметрична.
Граф, в котором нет кратных ребер и петель, называется простым. Простой граф называется полным, если любой паре его вершин инцидентно одно ребро. Дальше все о неориентированных графах.
K1 – полный граф с одной вершиной
K2 – с двумя
K3 – с тремя
K4 – полный граф с четырьмя вершинами
K5 – полный пятивершинник
Граф называется двудольным, если множество вершин разбивается на 2 непересекающихся подмножества, такие, что ребра соединяют вершины из разных подмножеств. Двудольный граф называется полным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.
Полный двудольный граф.
Маршруты, циклы, связности.
Маршрутом в графе называется чередующаяся последовательность вершин и ребер, начинающаяся и заканчивающаяся вершинами, такую, что каждое ребро в нем соединяет только те вершины, между которыми оно стоит. Будем говорить, что этот маршрут соединяет первую и последнюю вершину. Если существует маршрут, то последняя вершина называется достижимой из первой вершины. Маршрут, в котором нет повторяющихся ребер, называется цепью. Маршрут, в котором нет повторяющихся вершин (кроме первой и последней), называется простой цепью. Если в простой цепи первая и последняя вершины совпадают, то она называется циклом. Граф называется связным, если любая вершина достижима из любой другой вершины. В противном случае граф называется несвязным. Несвязный граф распадается на несколько частей, каждая из которых является связным графом. Эти части называются компонентами связности. Ребро называется циклическим, если оно входит хотя бы в один цикл графа. В противном случае ребро называется ациклическим.
Утверждение. Если из связного графа удалить циклическое ребро, то вновь полученный граф останется связным, а если удалить ациклическое ребро, то граф распадется на два компонента связности. Связный граф, у которого все ребра ациклические, называется деревом. Несвязный граф, компонентами связности которого являются деревья, лесом. Свойства деревьев. 1. Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один. 2. Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом. 3. Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла. Лекция 12 Эйлеровы графы
Дан граф. Требуется найти в нем маршрут, проходящий по каждому ребру ровно один раз. Начало и конец – в одной вершине. Такой маршрут называется Эйлеровым циклом, а граф, в котором он существует, называется Эйлеровым графом. Степень вершины в графе – это число ребер, инцидентных этой вершине.
Критерий эйлеровости графа. Для того, чтобы связный граф без петель был Эйлеровым, необходимо и достаточно, чтобы степень его вершины была четным числом.
Планарные графы.
Определение.
Укладкой графа называется такое его геометрическое изображение, при котором ребра пересекаются только в вершинах. Если существует укладка графа на плоскости, то граф называется планарным. Сама же укладка графа без пересечения ребер называется плоским графом.
Любой граф можно изобразить в трехмерном пространстве без пересечения ребер.
Для любого графа xi, соединяющего 2 вершины проводим новую плоскость, содержащую эту прямую, а ребро рисуем на плоскости.
Граф будет планарным, если существует его укладка на сфере.
Доказательство следует из взаимно однозначного соответствия точек на сфере с точками плоскости из стереографических проекций. Следствие. Граф любого выпуклого многогранника планарен.
Ребра плоского графа разбивают плоскость на несколько частей, одна из которых бесконечна. Эти части и являются гранями плоского графа.
Теорема Эйлера о плоских графах. Формула Эйлера.
Для плоского графа справедливо соотношение. M – N + P = 2.
Докажем индукцией по числу граней P = 1 Если P = 1, то граф – дерево. В нем нет ни одного цикла. У дерева число вершин больше числа ребер на 1. M = N + 1 N + 1 – N + 1 = 2 – справедливо.
Пусть p = k, и утверждение верно. Тогда оно верно и при P= k+1 Берем ребро графа, отделяющее бесконечную грань от внутренних и удаляем это ребро из графа. Т.к. оно циклическое, то в новом графе g1 (он также будет связным) число вершин M останется прежним. N1 = N – 1 P1 = P – 1 M = M k + 1-1 = k Для g1 справедливо предположение индукции. M1 + N1 + P1 = 2 M – N – 1 + K = 2 M – N + K – 1 = 2 M – N + P = 2 Что и требовалось доказать.
Следствие 1. Для плоского связного простого графа справедливо соотношение n <= 3*(m-2)
Следствие 2. Для плоского связного простого графа без треугольных граней справедливо соотношение n <= 2*(m-2)
Следствие 3. Граф K5 – непланарен.
m > 2
И если бы он был плоским, то для него было бы справедливо следствие 1.
N <= 3*(m-2) 10 <= 9 – неверно. Противоречие. Значит, он не может быть нарисован плоским.
Следствие 4. Граф K3-3 непланарен.
Нет треугольных граней. Если бы он был плоским, то для него было бы справедливо следствие 2.
9 <= 2*(6-2) 9 <= 8 – неверно.
Противоречие из предположения, что он не может быть плоским.
Операцией разбиения ребра графа называется следующая процедура:
Ребро удаляется из графа, и в граф добавляется новая вершина, соединенная новыми ребрами с концами данного ребра.
Два графа называются гомеоморфными, если каждый из них может быть получен из одного и того же графа путем применения конечного числа раз операции разбиения ребер.
Теорема Понтрягина – Куратовского. Чтобы граф был планарным, необходимо и достаточно, чтобы он не содержал гомеоморфных подграфов. Лекция 13
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-18; просмотров: 446; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 13.58.77.244 (0.007 с.) |