Сумматор 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-03-27; просмотров: 903;