Часть 2.

12.Что такое орграф, граф, вершина, дуга, ребро, путь, цепь, контур, цикл?

13.Каков алгоритм решения задачи о кратчайшем пути в невзвешенном графе?

14.Во взвешенном?

15.Что такое «Эйлерова Цепь» (цикл) У каких графов существуют?

16.Формула Эйлера. Для каких объектов она верна?

17.Как выглядят непланарные графы №1 и №2,1 и 2 типа, и в чем состоит теорема Куратовского-Понтрягина?

18.Что такое хроматическое число графов? Что вы знаете о его величине?

19.Что такое хроматическая величина?

Ответы

12.

орграф - мультиграф, ребрам которого присвоено направление '

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

Дуга - ориентированное ребро

Ребро - связующая двух вершин в графе

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

Цепь-это путь в неорграфе

Контур - замкнутый путь в орграфе

Цикл- замкнутая цепь в графе

13.

Алгоритм для не взвешенного графа

1)Вершине А присвоим индекс О

2)Всем вершинам, смежным с А, присвоим индекс 1

3)Всем вершинам, смежным с 1, присвоим индекс 2.

Процесс останавливается, когда вершина В получит некоторый индекс n(n - длина кратчайшего пути)

4)Построим этот путь, возвращаясь из вершины В в вершину А

5)Среди вершин, смежных с В, обязательно найдется вершина С с индексом (n-1)

Возвращаемся в С и продолжаем процесс. Ровно через п шагов мы придем в вершину индекса 0, т.е. в вершину А.

Алгоритм для взвешенного графа

1)Вершине А присвоим индекс 0, а всем остальным +°°

2)Будем последовательно перебирать все пары смежным вершин «х» и «у». Каждый раз проверяем неравенство

Если оно выполняется, то уменьшаем индекс индекс , заменив его на 3)Процесс останавливается, когда ни один из индексов нельзя уменьшить. Построим путь с этой суммой, возвращаясь из В в А. Среди всех смежных с В вершин, есть С, где

4)Возвращаемся в С, повторяем процесс, а через некоторое время придем в вершину с индексом 0 (вершина А).

15.

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

Эйлеров цикл графа — цикл графа, проходящий через каждое ребро графа ровно по одному разу.

Связный граф обладает незамкнутой эйлеровой цепью <=> две его вершины имеют нечетную степень.

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

16.

Формула Эйлера

В+Г-Р=2 Выполняется для плоского связного графа, где В - вершина, Г - грань, Р - ребро. Также подходит для многогранников в пространстве (при отображении теряется растянутая грань и получается бесконечная грань)

В+Г-Р=К+1<- Если граф плоский, но не связный. Где К - число связных компонентов, К+1 — Эйлерова характеристика графов.