Читайте также:
|
1)Вершине А присвоим индекс 0, а всем остальным +°°
2)Будем последовательно перебирать все пары смежным вершин «х» и «у». Каждый раз проверяем неравенство 
Если оно выполняется, то уменьшаем индекс индекс 
, заменив его на 
3)Процесс останавливается, когда ни один из индексов нельзя уменьшить. Построим путь с этой суммой, возвращаясь из В в А. Среди всех смежных с В вершин, есть С, где 
4)Возвращаемся в С, повторяем процесс, а через некоторое время придем в вершину с индексом 0 (вершина А).
15.
Эйлерова цепь графа - цепь, которая содержитвсе ребра по одному разу.
Эйлеров цикл графа — цикл графа, проходящий через каждое ребро графа ровно по одному разу.
Связный граф обладает незамкнутой эйлеровой цепью <=> две его вершины имеют нечетную степень.
Связный граф обладает незамкнутым эйлеровым циклом О все его вершины имеют четную степень.
16.
Формула Эйлера
В+Г-Р=2 Выполняется для плоского связного графа, где В - вершина, Г - грань, Р - ребро. Также подходит для многогранников в пространстве (при отображении теряется растянутая грань и получается бесконечная грань)
В+Г-Р=К+1<- Если граф плоский, но не связный. Где К - число связных компонентов, К+1 — Эйлерова характеристика графов.
Дата добавления: 2015-02-16; просмотров: 78 | Поможем написать вашу работу | Нарушение авторских прав |