рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Обоснование алгоритма.

Реферат Курсовая Конспект

Выберите учебное заведение

Обоснование алгоритма.

Обоснование алгоритма. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Пусть Мы Находимся В Некоторой Вершине ...

Пусть мы находимся в некоторой вершине . В исходном графе степень вершины — четное число, поэтому после зачеркивания ребер, по которым мы приходили и уходили из вершины , ее степень — нечетна. Следовательно, существует, по крайней мере, одно незачеркнутое ребро, инцидентное вершине . Если это ребро — единственное, инцидентное вершине , то оно, в силу замечания в 5° алгоритма, не может быть «перешейком», и по нему можно покинуть вершину .

Пусть ребер, инцидентных вершине — нечетное число, большее единицы. Докажем, что среди них хотя бы одно ребро не является перешейком. Допустим противное: все ребра, инцидентные вершине— перешейки. Удалим одно из этих ребер, такое, чтобы вершина и оказались в разных компонентах связности. Такое ребро существует, так как в противном случае вершины и были бы связаны более чем одной простой цепью. Это означало бы, что существует простой цикл, содержащий вершины и . Но ребра, входящие в простой цикл, не могут быть перешейками.

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

Итак, наше допущение ведет к противоречию. Более того, мы убедились, что среди ребер, инцидентных вершине в графе, полученном из графа удалением пройденных ребер, лишь одно может быть перешейком.

Таким образом, доказано, что невозможность выполнить предписания алгоритма может возникнуть только в вершине , если попасть в нее, по крайней мере, во второй раз. В отличие от других вершин степень вершины при -м попадании в нее — четна. Если эта степень равна нулю, алгоритм перестает работать.

Докажем, что в этом случае эйлеров цикл уже построен. В самом деле, в силу правила 3° любое ребро может войти в цикл не более одного раза. В силу правил 4°, 5° — пройдены все ребра. Действительно, непройденные ребра определяют в графе компоненты связности. Если эти компоненты можно связать с вершиной цепью из более чем одного зачеркнутого ребра, то среди этих ребер наверняка одно — перешеек; если одним ребром, то была возможность выбора ребра, не ведущего в вершину .

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ... Барабаш В В...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
(2 семестр) (для студентов специальности «Прикладная математика», «Компьютерные системы и сети») У Т В Е Р Ж Д Е Н О на

Основные комбинаторные формулы.
Существует два общих правила комбинаторики: правило сложения и правило умножения. Правило умножения: Пусть составляются всевозможные строки

Размещения.
1) Размещения без повторений. Определение 2: Пусть имеется различных предметов.

Перестановки.
1) Перестановки без повторений. Определение 3: Пусть - конечное множество из

Сочетания.
1) Сочетания без повторений. Определение 3: Сочетания из элементов по

Свойства сочетаний. Бином Ньютона.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след

Определение 1: Коэффициенты бинома Ньютона называются биномиальными коэффициентами.
Числовые значения биномиальных коэффициентов вычисляются по формуле числа сочетаний: . Готовые значения этих коэффициентов располагаются в с

Рекуррентные соотношения.
При решении многих комбинаторных задач применяют метод сведения данной задачи к задаче касающегося меньшего числа элементов. Например, можно вывести формулу для числа перестановок:

Производящие функции.
Метод рекуррентных соотношений позволяет решать многие комбинаторные задачи. Но в ряде случаев рекуррентные соотношения трудно составить, а иногда ещё трудней решить. Часто эти труд

Алгоритм решения.
1°. Присвоить вершине метку 0. 2°. Если

Обоснование алгоритма.
Докажем, что после конечного числа применений правила 3° для каждой дуги графа станет справедливым неравенство

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

Потоки на транспортных сетях.
1. Основная задача теории транспортных сетей. Определение 1: Транспортная сеть есть совокупность

Алгоритм Форда - Фалкерсона для нахождения потока наибольшей величины.
1°. Перенумеровать произвольным образом вершины сети , отличные от входа

Обоснование алгоритма.
Прежде всего, заметим, что реализация алгоритма состоит из конечного числа шагов. В самом деле, п. 3° может применяться лишь конечное число раз, так как на каждом шаге величина пот

Теорема 1: Для заданной транспортной сети величина наибольшего потока равна наименьшей пропускной способности разрезов, т. е. .
Рис. 11 В качестве примера

Цикломатическое число графа. Деревья.
Во многих прикладных задачах существенны свойства графов, связанные с существованием в графе замкнутых цепей (циклов). К рассмотрению этих вопросов мы и приступим. Все графы данного

Эйлерова характеристика. Плоские графы.
Определение 1: Пусть задан набор отрезков гладких кривых на плоскости, причем выполнны следующие услов

Теорема 2: Графы и , где множество состоит из элементов вида , не допускают плоской реализации.
Доказательство: Отметим, что в графе нет циклов длины 3, так как любое ребро ведет из группы вершин

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

Графы правильных многогранников.
Теория графов позволяет решать задачи из традиционных разделов математики, например, исследовать некоторые свойства правильных многогранников. При этом, используя элементы теории гр

Автомат Мура.
Определение:Конечным автоматом называется набор из 5 объектов , где:

Морфизмы.
Пусть - конечный автомат. Тогда по любой входной строке длины

Эквивалентные состояния автоматов.
В этом параграфе мы решим следующую задачу: по данному описанию автомата построить новый автомат

Теорема 1: Если , то либо , либо для подходящей строки имеем .
Доказательство: Утверждение означает, что для подходя

Машина Тьюринга.
Понятие конечного автомата возникло из близкого понятия, введенного в 1936 г. логиком Тьюрингом. Тьюринг рассмотрел гипотетическую машину, имеющую конечное множество

Не полностью описанные автоматы.
До сих пор мы рассматривали полностью описанные автоматы. Практически функции и

Примитивно рекурсивные функции.
Операции над числовыми функции назовем операторами. В этом параграфе мы определим ряд операторов, обладающих тем свойством, что, применяя их к функциям, вычи

Частично рекурсивные функции.
Оператор минимизации. Рассмотрим некоторую n - местную частичную функцию

Машины Тьюринга.
Важный и широкий класс алгоритмов был описан Тьюрингом и Постом в 1936 - 1937 г. Алгоритмы этого класса осуществляются особыми машинами, называемыми сейчас машинами Тьюри