Релейно-контактные схемы в ЭВМ. Двоичный полусумматор. Одноразрядный двоичный сумматор.

Графы. Основные понятия и определения (вершины, ребра, петли, кратность ребра, псевдограф, мультиграф, граф, орграф, неориентированный граф). Привести примеры.

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах граф

Совокупность множества вершин и множества ребер, причем каждое ребро связано отношением инцидентности с двумя вершинами; другими словами, каждое ребро является связью двух вершин

Графом G(X, U) называют совокупность множества вершин X = (x1, x2, …, xn) и ребер U = (u1, u2, …, um), если каждое ребро

инцидентно двум вершинам, другими словами, является связью двух вершин. В частном случае в качестве этих двух вершин может дважды выступать одна и та же вершина, тогда ребро называется петлей. Инцидентность - отношение типа "лежит на" или "проходит через". Если связываемые вершины xi и xj в (1) упорядочены, то ребро становится направленным и называется дугой. Граф с направленными связями называют направленным графом (ориентированным графом или орграфом), в противном случае — ненаправленным (неориентированным). Граф называют смешанным, если в нем имеются как ребра, так и дуги. Ребра, соединяющие одинаковые вершины, — кратные или параллельные. Граф без петель, но с кратными ребрами — мультиграф. графа как совокупности двух множеств V (точек) и Е (линий), между элементами которых определено отношение инцидентности, причем каждый элемент е  Е инцидентен ровно двум элементам v', v"  V. Элементы множества V называются вершинами графа G, элементы множества Е – егоребрами. Направленные ребра часто называют дугами. Различные ребра могут быть инцидентны одной и той же паре вершин (рис. 3.1, е), в этом случае они называются кратными; граф, содержащий кратные ребра, часто называют мультиграфом. Ребро может соединять некоторую вершину саму с собой (рис. 3.1,ж), такое ребро называется петлей. Песевдограф допускает и кратные ребра, и петли.

Рис. 3.1. Примеры изображения неориентированных графов

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

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга ведёт от вершины v к вершине w. Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Инцидентность Отношение типа "лежит на..." или "проходит через..." между двумя объектами

Число инцидентных вершине ребер называется степенью вершины и обозначается P(X i).
Вершина, степень которой равно 0, называется изолированной.висячей (или листом), если она является концом ровно одного ребра.

Графы. Матричное задание графов. Матрица смежности, матрица инцидентности. Привести примеры.

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

Пусть D = (V, Х) – орграф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}.

Определение. Матрицей смежности орграфа D называется квадратная матрица A(D)=[aij] порядка n, у которой

Определение. Матрицей инцидентности орграфа D называется (nґm) –матрица B(D)=[bij], у которой

Введем также матрицы смежности и инцидентности для неориентированных графов. Пусть G = (V, X) – граф, где V={v1,v2, …,vn}, X={x1, x2, …, xm}.

Определение. Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, у которой

Определение. Матрицей инцидентности графа G называется (nґm) –матрица B(G)=[bij], у которой

С помощью введенных матриц удобно задавать графы для обработки на ЭВМ. Используя матрицу смежности легко определить локальные степени вершин графа: сумма элементов матрицы по строке равна локальной степени соответствующей вершины. Для орграфов по строке определяются полустепени исхода, по столбцам – полустепени захода.

Пример 72.

Построить матрицы смежности и инцидентности для графа G = (V, X) (рис. 25).

Решение.

Матрица смежности имеет вид

.

Поскольку граф не имеет петель, то на главной диагонали стоят все нули. Для любого графа матрица смежности симметрична относительно главной диагонали.

Для того, чтобы построить матрицу инцидентности необходимо пронумеровать ребра графа (рис. 26). Матрица инцидентности имеет вид:

Напомним, что в строках указываются вершины, в столбцах – ребра. Матрица инцидентности может быть как квадратной, так и прямоугольной.

Пример 73.

Построить матрицы смежности и инцидентности для орграфа D= (V, X) (рис. 27).

Решение.

Матрица смежности имеет вид:

Матрица инцидентности имеет вид

Графы. Маршруты, пути (определение маршрута; начальная, конечная, внутренняя вершины; подмаршрут, выделенный маршрут, выделенный подпуть, длина маршрута, замкнутый маршрут, цепь, простая цепь, цикл (контур), простой цикл (контур)). Привести примеры. Утверждение о выделении просто цикла (простого контура) и простой цепи.

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

Путь - это маршрут, в котором все ребра различны. Путь называется простым, если и все вершины в нем различны.

Цикл - это замкнутый путь. Цикл называется простым, если все вершины попарно различны.

В графе на рисунке 2.1 последовательность вершин

· - не маршрут;

· - маршрут, но не путь;

· - путь, но не простой;

· - замкнутый маршрут, но не цикл;

· - цикл, но не простой;

· - простой цикл.

Рис. 2.1.

Последовательность ребер графа, в которой любая пара соседних ребер имеет одну и ту же инцидентную вершину, называют маршрутом. В орграфах аналогом маршрута является путь, т.е. такая последовательность дуг, в которой конец одной дуги является началом другой дуги. Маршрут, все ребра которого различны, является цепью, а если различны все вершины, то маршрут — простая цепь. Замкнутая цепь является циклом, замкнутая простая цепь — простым циклом. Цикл, содержащий все ребра графа, называютэйлеровым циклом, а граф, имеющий эйлеров цикл, — графом Эйлера. Простой цикл, который включает все вершины графа, называют гамильтоновым циклом. Для орграфов понятиям цепь и цикл соответствуют понятия путь и контур. Простой путь - путь, в котором ни одна дуга не встречается дважды. Элементарный путь - путь, в котором ни одна вершина не встречается дважды. Контур - путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если послед­ ние заданы).

Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.

Цикл − замкнутая цепь (в неориентированном графе).

Контур − замкнутый путь (в ориентированном графе).

Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.

Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.

Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.

Эйлерова цепь (путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.

Длина маршрута (пути) − число ребер в маршруте (дуг в пути).

Утверждение 1. Для того чтобы связный псевдограф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.

Утверждение 2.Для того чтобы связный псевдограф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.

30. Графы. Свойства матрицы смежности и инцидентности. Утверждение о числе всех путей (маршрутов) длины k из одной вершины в другую. Утверждение о наличие хотя бы одного контура.

Свойства матриц смежности и инцидентности.

Для ориентированного мультиграфа D=(V,X), V={v₁,...,v_n}, X={x₁,...,x_m}

- сумма строк матрицы B(D) является нулевой строкой (дуга один раз входит и один раз выходит);

- любая строка матрицы B(D) является линейной комбинацией остальных строк (вследствие предыдущего);

- ранг матрицы B(D) не превосходит n(D)-1 (также вследствие предыдущего);

- для любого контура в D сумма столбцов матрицы B(D), соответствующих дугам, входящим в этот контур, равна нулевому столбцу.

Для неориентированного мультиграфа G=(V,X), V={v₁,...,v_n}, X={x₁,...,x_m}

- сумма строк матрицы B(G) по модулю 2 является нулевой строкой (дуга один раз входит и один раз выходит, а вместе четно);

- любая строка матрицы B(G) является суммой по модулю 2 остальных строк (вследствие предыдущего);

- для любого цикла в G сумма по модулю 2 столбцов матрицы B(G), соответствующих ребрам, входящим в этот цикл, равна нулевому столбцу.

Графы. Связность. Компоненты связности. (Достижимость вершины, связный (сильно связный орграф) граф, слабо связанный, несвязанный, компонента связности (сильной связности)). Привести примеры.

Определение. Вершина w орграфа D (графа G) достижима из вершины v, если либо v=w, либо существует путь изv в w(маршрут, соединяющий v, w).

Дадим более удобное определение связных графов.

Определение. Граф называется связным, если для любых двух его вершин v, w существует простая цепь из v в w.

Определение. Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v, w (из v и w).

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

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

Определение. Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа.

В дальнейшем количество компонент связности графа будем обозначать k.

Пример 79.

Данный граф не является связным: k = 3.

Данный граф является связным: k = 0.

Теорема. Пусть G – простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам

Следствие. Любой простой граф с n вершинами и более чем (т-1)(т-2)/2 ребрами связен.

При исследовании графов возникает вопрос: насколько сильно связен связный граф? Этот вопрос можно сформулировать и так: сколько ребер нужно удалить из графа, чтобы он перестал быть связным? Под операцией удаления вершин из графа будем понимать операцию, заключающуюся в удалении некоторой вершины вместе с инцидентными ей ребрами.

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

Определение. Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу.

Определение. Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.

Определение. Разрез, состоящий из одного ребра, называется мостом (перешейком).

Пример 80.

Для графа, изображенного на рис.33, каждое из множеств {e1, e2, e5}и {e3, e6, e7, e8} является разделяющим.

Разрезом является множество ребер {e1, e2}.

В графе возможно выделить несколько разделяющих множеств и разрезов.