4.Задача о Кенигсбергских мостах.

Философ Иммануил Кант, гуляя по городу Кенигсбергу, поставил задачу: можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз. В письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно). Тогда исходная задача эквивалентна следующей: можно ли начертить данный граф, не отрывая карандаша от бумаги, то есть таким образом, чтобы каждое его ребро пройти ровно один раз. Такие графы, которые можно начертить, не отрывая карандаша от бумаги, называются эйлеровыми.

В ходе рассуждений Эйлер пришёл к следующим выводам:

• Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

• Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.

• Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком

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

Тема №2. Операции над графами. Матричные представления графов.

1. Объединение, пересечение графов.

Объединение графов G₁ и G₂ , обозначаемое как , представляет такой граф , что множество его вершин является объединением Х₁ и Х₂ , а множество ребер – объединением A₁ и A₂ . Граф G₃ , полученный операцией объединения графов G₁ и G₂ , показан на рис. 2.1,д, а его матрица смежности – на рис. 2.1,е. Матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов G₁ и G₂ .

Рис. 2.1. 

Пересечение графов G₁ и G₂ , обозначаемое как , представляет собой граф . Таким образом, множество вершин графа G₄ состоит из вершин, присутствующих одновременно в G₁ и G₂ . Операция пересечения графов показана на рис. 2.2,в, а результирующая матрица смежности получается операцией поэлементного логического умножения матриц смежности исходных графов G1 и G2 . показана на рис. 2.2.г.

Рис. 2.2. 

2.Топология графа с помощью матриц.

Топологические матрицы

1. Узловая матрица (матрица соединений) – это таблица коэффициентов уравнений, составленных по первому закону Кирхгофа. Строки этой матрицы соответствуют узлам, а столбцы – ветвям схемы.

Более наглядно: схема и матрица. Наглядно видно, что, исходя из направления, ставим -1 или же 1. 3.Построение матриц смежности.

Определение Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ij равно числу рёбер из i-й вершины графа в j-ю вершину.

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

Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.

Примеры

• Ниже приведён пример неориентированного графа и соответствующей ему матрицы смежности A. Этот граф содержит петлю вокруг вершины 1, при этом в зависимости от конкретных приложений элемент может считаться равным либо одному (как показано ниже), либо двум.

Граф	Матрица смежности

• a_ij — число рёбер, связывающих вершины и , причем в некоторых приложениях при каждая петля (ребро при некотором ) учитывается дважды.

• Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.

Е щё примеры.

1)

2)

Граф	Матрица смежности

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

Тема №3. Сетевое планирование. Алгоритм нумерации событий. Метод критического пути.

1.Определение сетевой модели.

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

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

Сетевая модель данных обладает некоторыми особенностями. Все типы используемых связей в обязательном порядке должны быть функциональными, то есть "многие к одному", "один к множеству" или "один к одному". В модели такое внутреннее ограничение выражено тем утверждением, что для этого типа связи с определенным типом записи предка и типом записи потомка обязательно выполняются определенные условия. Для того чтобы определить связь "многие ко многим", был введен особый тип записей, а также пара функциональных связей вида "один к множеству" и "множество к одному". Если есть необходимость, то в запись, исполняющую роль связки, может быть добавлена дополнительная информация.

В сетевой модели групповые отношения обычно описывают связь вида "один к множеству", то есть владелец один, а у него много подчиненных. Можно привести в пример такое отношение, как «работать». Тут подразумевается, что каждый сотрудник работает в каком-то определенном отделе, но в каждом отделе вполне может работать несколько сотрудников. В сетевой модели вида "один к множеству" связь между разными сущностями реализована при помощи групповых отношений.

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

1. событие,

2. работа,

3. путь.

2.Основные элементы сетевого графика.

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

Событие выражает факт окончания одной или нескольких непосредственно предшествующих (входящих в событие) работ, необходимых для начала непосредственно следующих (выходящих из события) работ. Событие, стоящее в начале работы, называется начальным, а в конце -конечным. Начальное событие сетевого графика называется исходным, а конечное — завершающим. Событие, не являющееся ни исходным, ни завершающим, называется промежуточным. В исходное событие сетевого графика не входит, а из завершающего не выходит ни одна работа. В отличие от работ, события совершаются мгновенно без потребления ресурсов.

Обозначение непосредственно предшествующих и непосредственно следующих работ. Любая последовательность работ в сетевом графике, при котором конечное событие каждой работы совпадает с начальным событием последующей, называется путем. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь наибольшей длины между исходными и завершающими событиями называется критическим (Lm).

Если критическое время не соответствует заданному или нормативному, сокращение сроков производственного процесса необходимо начинать с сокращения продолжительности критических работ.