Основные понятия теории графов. Изолированная и висячая вершина. Основные задачи теории графов. Проблемы надежности, страница 2

Два графа называются гомеоморфными , если после их сжатия/расширения они становятся изоморфными.

Граф, гомеоморфный плоскому также называют плоским.

Теорема Понтрягина-Куратовского:

Граф планарен тогда и только тогда, когда он не содержит подграфов гомеоморфных полному графу К5 и полному графу К3,3.

3.  Минимальное количество ребер, которое необходимо удалить из графа, чтобы он стал планарным – число планарность: θ(G)

Для полного графа θ(Kn)= [(n-3)(n-4)]/2

Гипотеза теории графов: Любой граф можно раскрасить ≤ 4-мя красками.

Граф представляется:

a)  перечисление ребер.

b)  отображением Гxi – это множество вершин смежных xi.

c)  отображением Гxs (расширеним Гxi) – множество вершин, смежных вершинам из xs.

d)  Внутренне устойчивым множеством графа называют такое множество, что любые 2 вершины в нем несмежные

4.  Число внутренней устойчивости ά(G) – максимальное количество несмежных вершин.
Внешне устойчивый граф – множество вершин xs, выбранное таким образом, что для каждой вершины xj не принадлежащей xs существует xi принадлежащая xs связанное с xj (xsUГxs = x)

5.  Число внешней устойчивости β(G) минимальная мощность xs (β(G)=min|xs|)

Матричное представление графа.

1.  Матрица инцидентности (комплексов) B=||bij||_n*m n=|x|,  m=|V|, bij= 1, xi инцидентно uj, bij=0, если иначе.

2.  Матрица смежности (соединения) K=||aij|| _n*m , aij=1, xi смежна xj, aij=0 если иначе.

Основные задачи теории графов.

1.  Задачи на независимые и доминирующие множества (внутренне и внешне устойчивые множества)

a)  выбор проекта из n предложений

b)  размещение центров, покрывающих заданную область

c)  задача о наименьшем покрытии

2.  Задачи центровки. Необходимо разместить объекты так, чтобы расстояние lij или время tij, за которое можно добраться от центра до любого объекта было минимальным.

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

4.  Задачи уентровки. Необходимо разместить объекты так, чтобы расстояние lij или время tij за которое можно добраться от центра до любого объекта было минимальным. (боьница, пожарная охрана) – минимаксная задача.
Размещение может быть медианным. Медианой в графе называют место, расстояние от которого до всех вершин минимально – минисуммная задача (расположение пункта сортировки почны)

5.  Задачи на деревья. Построение всех основных деревьев графа. Построение минимального связывающего дерева. Задача Штейнера – построение дерева Штейнера. Оно отличается введением дополнительных вершин:

6.  Кратчайшие пути

7.  Нахождение Эйлерового цикла (задача китайского почтальона) минимальное время прохождения по всем ветвям.

8.  Задача коммивояжера минимальное расстояние(время, скорость) при прохождении всех пунктов.

9.  Задача потоки в сетях – определение максимального потока между двумя вершинами.

10.  Транспортная задача. Есть n производителей изделия с производительностями ai. Есть m потребителей этого изделия с потребностями bj. Скорость перевозки одного изделия от I производителя к j потребителю – cij. Необходимо составить план перевозок x со следующими ограничениями ∑(i=1 до n)=bj; ∑(i=1 до m)=ai.
∑(i=1 до n) ∑(i=1 до m) xijCij→min/

Проблемы надежности.

1.  Большое количество элементов

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

3.  Повышение требований к точности работы и непрерывности функционирования.

4.  Повышение ответственности функция ЭВМ и высокая цена отказа.

5.  Полное или частичное исключение человека из контура управления.

Эти проблемы решаются на стадиях разработки, изготовления, производства и эксплуатации ЭВМ.