Обоснование алгоритма. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Докажем, Что После Конечного Числа Применений Правила 3° Для...
Докажем, что после конечного числа применений правила 3° для каждой дуги графа станет справедливым неравенство .
Для этого заметим, что на любом этапе метки при , а метка , что можно доказать по индукции. В самом деле, при первом применении правила 3° будет изменена метка у одной из вершин , смежных с вершиной . Эта вершина получит новую метку .
Предположим, что после того, как применено правило 3°раз , станет справедливым утверждение, что для . На шаге какая-то вершина получит новую метку . Но в силу предположения индукции , кроме того, ; поэтому .
Ясно, что при каждом изменении метка вершины графа уменьшается на положительную величину, не меньшую, чем минимальная разность длин путей графа.
Из этих двух утверждений вытекает, что метка-любой вершины графа может изменяться лишь конечное число раз. Так как вершин конечное множество, то правило 3° может применяться лишь конечное число раз.
Докажем теперь утверждения, содержащиеся в пункте 5°. Вершина такая, что обязательно найдется в случае, если существует хотя бы один путь, соединяющий с вершиной . Ибо тогда, как нетрудно сообразить, метка . Поэтому — это, например, та вершина, которая послужила для изменения метки в последний раз. Аналогично доказывается существование вершин .
По условию дуги графа имеют положительную длину, поэтому метки образуют строго убывающую последовательность неотрицательных чисел, отличающихся друг от друга на величину, большую или равную длине кратчайшей дуги графа. Следовательно, какое-то . (Вершина выделена тем, что ей в силу правила 2° с самого начала присвоена метка и в формировании этой метки не участвуют дуги графа.)
Докажем, что путь — кратчайший. Для этого рассмотрим произвольный путь: , соединяющий решину с . Имеем неравенства:
Складывая эти неравенства, получаем соотношение:
,
так как . В то же время, по построению пути имеем:
, откуда .
Пример. В графе (рис. 9) легко установить, что кратчайший путь, соединяющий вершины и , имеет длину .
ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ... Барабаш В В...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Обоснование алгоритма.
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
(2 семестр)
(для студентов специальности «Прикладная математика», «Компьютерные системы и сети»)
У Т В Е Р Ж Д Е Н О
на
Основные комбинаторные формулы.
Существует два общих правила комбинаторики: правило сложения и правило умножения.
Правило умножения:
Пусть составляются всевозможные строки
Размещения.
1) Размещения без повторений.
Определение 2: Пусть имеется различных предметов.
Перестановки.
1) Перестановки без повторений.
Определение 3: Пусть - конечное множество из
Сочетания.
1) Сочетания без повторений.
Определение 3: Сочетания из элементов по
Свойства сочетаний. Бином Ньютона.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след
Рекуррентные соотношения.
При решении многих комбинаторных задач применяют метод сведения данной задачи к задаче касающегося меньшего числа элементов. Например, можно вывести формулу для числа перестановок:
Производящие функции.
Метод рекуррентных соотношений позволяет решать многие комбинаторные задачи. Но в ряде случаев рекуррентные соотношения трудно составить, а иногда ещё трудней решить. Часто эти труд
Алгоритм построения Эйлерова цикла.
Обратимся к задаче об эйлеровом цикле, уже рассмотренной нами в предыдущем параграфе. Пусть — связный граф, степени всех вершин которого — ч
Обоснование алгоритма.
Пусть мы находимся в некоторой вершине . В исходном графе степень вершины
Потоки на транспортных сетях.
1. Основная задача теории транспортных сетей.
Определение 1: Транспортная сеть есть совокупность
Обоснование алгоритма.
Прежде всего, заметим, что реализация алгоритма состоит из конечного числа шагов. В самом деле, п. 3° может применяться лишь конечное число раз, так как на каждом шаге величина пот
Цикломатическое число графа. Деревья.
Во многих прикладных задачах существенны свойства графов, связанные с существованием в графе замкнутых цепей (циклов). К рассмотрению этих вопросов мы и приступим. Все графы данного
Оценка хроматического числа плоского графа.
1. Теорема о пяти красках. Теорема утверждает, что любой граф, обладающий плоской реализацией, может быть правильно раскрашен пятью красками. Вспоминая задачу, сформулированную в нача
Графы правильных многогранников.
Теория графов позволяет решать задачи из традиционных разделов математики, например, исследовать некоторые свойства правильных многогранников. При этом, используя элементы теории гр
Автомат Мура.
Определение:Конечным автоматом называется набор из 5 объектов , где:
Морфизмы.
Пусть - конечный автомат. Тогда по любой входной строке длины
Машина Тьюринга.
Понятие конечного автомата возникло из близкого понятия, введенного в 1936 г. логиком Тьюрингом. Тьюринг рассмотрел гипотетическую машину, имеющую конечное множество
Примитивно рекурсивные функции.
Операции над числовыми функции назовем операторами. В этом параграфе мы определим ряд операторов, обладающих тем свойством, что, применяя их к функциям, вычи
Машины Тьюринга.
Важный и широкий класс алгоритмов был описан Тьюрингом и Постом в 1936 - 1937 г. Алгоритмы этого класса осуществляются особыми машинами, называемыми сейчас машинами Тьюри
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
.
при 
, а метка 
, что можно доказать по индукции. В самом деле, при первом применении правила 3° будет изменена метка 
у одной из вершин 
, смежных с вершиной 
. Эта вершина 
.
раз 
, станет справедливым утверждение, что 
для 
. На 
шаге какая-то вершина 
получит новую метку 
. Но в силу предположения индукции 
, кроме того, 
; поэтому 
такая, что 
обязательно найдется в случае, если существует хотя бы один путь, соединяющий 
с вершиной 
. Ибо тогда, как нетрудно сообразить, метка 
. Поэтому 
— это, например, та вершина, которая послужила для изменения метки 
в последний раз. Аналогично доказывается существование вершин 
.
образуют строго убывающую последовательность неотрицательных чисел, отличающихся друг от друга на величину, большую или равную длине кратчайшей дуги графа. Следовательно, какое-то 
. (Вершина 
— кратчайший. Для этого рассмотрим произвольный путь: 
, соединяющий решину 
,
имеем:
, откуда 
.
(рис. 9) легко установить, что кратчайший путь, соединяющий вершины 
, имеет длину 
.
Новости и инфо для студентов