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


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.034 сек.