Основные определения.

Графы возникли в результате рассмотрения изображения на плоскости, состоящее из точек на плоскости.

Пусть задано множество V – множество вершин графов .

Множество вершин графов может быть как конечными, так и бесконечными.

Графом G↔ G(V) называется совокупность пар чисел типа E=(a, b), где объекты a и b принадлежат множеству вершин графа, т.е. и .

Пусть граф содержит 4 вершины и они соединены ребрами l₁, l₂, l₃.

V={υ ₁, υ ₂, υ _3, υ ₄}

{ (υ ₁ υ ₂), (υ ₁ υ ₃), (υ ₂ υ ₃)} – множество ребер графа G.

В зависимости от вида ребер графы могут быть неориентированными или ориентированными (орграфы) и смешанные.

Неориентированные графы содержат ребра вида E=(a, b)=(b, a).

Граф называется неориентированным, если выполняется E=(a, b)=(b, a), если это условие не выполняется, то граф называется ориентированным или орграфом и обозначается стрелкой.

неориентированный граф, ориентированный граф

т.к. (a, b)=(b, a) т.к. (a, b)≠ (b, a)

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

Простейшие примеры графов.

1. План города.

Улицы – ребра города.

Перекрестки – вершины города.

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

Если разрешено лишь односторонне движение, то граф ориентированный.

Вся теория графов возникла с решением Эйлером, задачей о Кёнигсбергских мостах.

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

Возможно ли начав путь в части города А и пройдя ровно 1 раз по всем 7 мостам вернуться снова в часть А.

Построим граф плана.

Эйлеровый цикл

2. Электрическая схема.

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

Сложное разветвление ребра называется ребром гиперграфа.

Теория графов имеет большое применение в автоматах из проектирования ЦВМ.

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

Обозначения логических формул по частям:

1.«И» 2.«ИЛИ» 3.«НЕ» «И-ИЛИ-НЕ»

1. конъюнкция

2. дизъюнкция

3. отрицание

Простейшая микросхема (по этому принципу составляют машины 3 поколения).

Электрическая схема вычислительного устройства формализуется в виде графа. Пусть дана схема для того чтобы ее формализовать необходимо создать несколько микросхем. Процесс проектирования рассмотрим по этапам:

1 ЭТАП

Исходная электрическая схема представляется в виде графа в котором вершины соответствует логическим элементам схемы, а ребра электрическим связям (кодовым шинам), соединяет указанные элементы.

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

Серия микросхем, включенная в состав микросхемы типа, который образует полный базис логической функции.

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

2 ЭТАП

Это описание микросхем в виде графа. Включающий в себя автоматически проект ТЭЗов (типовой элемент замены), содержит множество микросхем ТЭЗ – некоторая печатная плата. Из ТЭЗов строится ВМ.

Задача создания ТЭЗ сводится к проблеме разбиения графа G₁ на части соответствующим определенным ТЭЗам.

3 ЭТАП

Необходимо разбить всю схему ВМ на отдельные блоки.

Проектирование 1 ТЭЗа инженером- конструктором занимает 35 – 40 дней. Комплекс программ автоматической конструкции для ЭВМ ЭС-10-22 позволяет выполнять проект ТЭЗа за 1 час машинного времени.

Дальнейшие определения.

1. частью Н графа G называют произвольное подмножество вершин графов и некоторых ребер графа Н. (обозначают )

2. под графом G₁ графа G называется такая его часть которая вместе с вершинами этой части содержит все соединяющие эти вершины ребра.

3. Если имеется ребро L, соединяющие вершины υ ₁ и υ ₂ графа G, то ребро L называют инцедентным вершинам υ ₁ и υ ₂ и обратно вершины υ ₁ и υ ₂ называют инцидентными ребру L.

Описание графов с помощью матриц.

1. M₁(G) – матрица графа G смежности вершин. Она предоставляет собой таблицу строки и столбца который представляет вершины.

На месте υ _i υ _j ставится единица, если эти вершины соединены хотя бы одним ребром если нет, то ставим ноль.

4. локальной степенью вершины υ называется число P(υ), которое равно числу ребер графа инцидентных вершине υ.

5. кратностью (ребра) (υ ₁, υ ₂) называют число ρ (υ ₁, υ ₂); число ребер, которые связывают вершины υ ₁ и υ ₂.

В общем случае на месте υ _i и υ _j в матрице М₁(G) ставится кратность ρ (υ _i, υ _j) = 0

Существует такая формула.

V_l – число ребер графа G

V_l=V_l(G)

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

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

Лемма рукопожатий.
На конечном графе число вершин нечетной степени четно (её вывел Эйлер).

2) М₂(G) – матрица инциденции графа, (где строки есть), это таблица, где строки есть ребра графа.

ε _ij= 1, если υ _j – начальная вершина ребра l_i

ε _ij = -1, если υ _j – конечная вершина ребра l_i,

ε _ij = 0, если υ _j не является инцидентным l_i.

3) M₃(G) матрица смежности ребер

На (i, j) месте этой матрицы находятся число

1, если ребра l_i и l_j

имеют хотя бы одну

общую вершину и

различны.

φ (i, j)

0, если i = j