Вход

Любая из понравившихся вам тем в прикрепленном файле

Курсовая работа
Дата создания 27.01.2016
Страниц 20
Источников 3
Вы будете перенаправлены на сайт нашего партнёра, где сможете оформить покупку данной работы.
1 287руб.
КУПИТЬ

Содержание

Содержание ВВЕДЕНИЕ 3 1. ОСНОВОПОЛАГАЮЩИЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ 4 2. ЦИКЛОМАТИЧЕСКОГО ЧИСЛА ГРАФА И ЕГО ОСНОВНЫЕ СВОЙСТВА 7 3. ОПРЕДЕЛЕНИЕ ГРУПП ОДНОМЕРНЫХ И НУЛЬМЕРНЫХ ЦЕПЕЙ ГРАФА 10 РЕШЕНИЕ ЗАДАЧ 15 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 18 Содержание

Фрагмент работы для ознакомления

Теорема. Если связный граф G допускает плоскую реализацию, то границы областей, на которые граф G разбивает плоскость, образуют базу независимых циклов.ДоказательствоКак будет доказано ниже, для плоского графа выполняется равенствоSo— Sx + S2 = 2, откуда v (G) = Sx — So + P =S2— 2+ 1 =S,— 1, и достаточно доказать лишь независимость циклов базы. Доказательство проведем индукцией по S2.Базис индукции. Если S2 = 2, то утверждение очевидно, так как база содержит всего один цикл.Индукционный шаг.Пусть теорема справедлива для всех графов СсS2 = п. Пусть G — связный граф с S2 = п + 1. Возьмем одно из ребер, лежащих на границе неограниченной области и не являющееся тупиком или перешейком. После удаления его получаем граф G' с S2 = п. Применяя предположение индукции и замечая, что цикл, содержащий выброшенное ребро, не зависит от остальных, завершаем индукционный шаг.Решение задачЗадача 9bДокажите, что каждое дерево является двудольным графом; какие деревья являются полными двудольными графами?Решение задачиИспользуем следствие из теоремыКенинга:Теорема Кёнига 2 (о необходимых и достаточных условиях разбиения множества вершин графа на два независимых подмножества). Для того, чтобы граф был двудольным, необходимо и достаточно, чтобы он не содержал циклов нечетной длин.Доказательство. Необходимость.Пусть Γ — двудольный граф, C — один из его циклов длины k. Пройдем все ребра этого цикла в той последовательности, в какой они в нем расположены, начиная с некоторой вершины v. Так как концы каждого ребра лежат в разных долях, то k — четное число. Достаточность.Не теряя общности, можно рассматривать только связные графы. Пусть связный граф Γ не имеет циклов нечетной длины. Рассмотрим произвольную вершину v0 и построим разбиение вершин графа Γ на два класса V1 и V2 следующим образом: к классу V1 отнесем вершину v0 и любую такую вершину u, что расстояние между u и v0 четное, к классу V2 отнесем любую такую вершину u, что расстояние между u и v0 нечетное. Остается показать, что любые две вершины из множества V1 или любые две вершины из множества V2 не смежны. Пусть, например, существуют две смежные вершины u и v, входящие в один класс. Тогда ни одна из них не совпадает с вершиной v0, так как вторая в этом случае принадлежала бы другому классу (расстояние между смежными вершинами равно 1). Пусть далее Z1 — кратчайшая цепь, соединяющая v0 и u, а Z2 — кратчайшая цепь соединяющая v0 и v. Обозначим через v1,v2,...,vp общие вершины, считая от вершины v0. Поскольку Z1 и Z2 — кратчайшие цепи, то их части от вершины от вершины v0 до вершины v1 имеют одинаковые длины. То же самое можно сказать и о частях цепей Z1 и Z2 от любой вершины vi до вершины vi+1. Поэтому части цепей от вершины vp до вершин u и v имеют одинаковые четности. Но тогда объединение этих частей и ребра {u,v} является циклом нечетной длины, что запрещено условиями теоремы. Теорема доказана. Следствие из теоремы Кёнига.Любое дерево является связным двудольным графом. Действительно, дерево является связным ацикличным графом и, следовательно, не содержит циклов нечетной длины. Деревья с цепями с длиной равными 2 являются полными двудольными графами.Задача 9сДокажите, что графы, соответствующиенасыщенным углеводородам (СпН2n+2) и спиртам (CnH2n+1OH), являются деревьями.Решение задачиГрафом молекулы называется граф, вершинами которого являются атомы, а ребрами – соответствующие валентные связи между атомами. Докажем, что графом G молекулы насыщенного углеводорода является дерево. Предположим, что в графе G есть цикл C. Поскольку валентности атомов водорода равны 1, то цикл C может состоять только из атомов углерода. Разорвав некоторую связь между атомами углерода в цикле и соединив эти атомы с атомами водорода, мы получим соединение, в котором атомов водорода будет больше, чем в первоначальном соединении (рис.1). Это противоречит тому, что граф G был графом насыщенного углеводорода.Пусть молекула насыщенного углеводорода содержит n атомов углерода и m атомов водорода. Граф молекулы является деревом, поэтому согласно лемме  он имеет n + m вершин и n + m – 1 ребер.Воспользуемся леммой о рукопожатиях:4  n + 1  m = 2 (n + m – 1).Отсюда получаем m = 2 n + 2. Это значит, что формула насыщенного углеводорода, имеющего n атомов углерода, имеет вид CnH2n + 2.При замещении атома водорода ОН, получаем такой же результат для спиртов.Список использованных источников1. Уилсон Р. Введение в теорию графов - М . Мир, I9772. Белов В.В. Воробьев Е. М . Шаталов В. Е. Теория графов — М ВШ. 1976.3. Березина Л. Ю. Графы и их применения. Пособие для учителей. - М.. 1979.

Список литературы

Список использованных источников 1. Уилсон Р. Введение в теорию графов - М . Мир, I977 2. Белов В.В. Воробьев Е. М . Шаталов В. Е. Теория графов — М ВШ. 1976. 3. Березина Л. Ю. Графы и их применения. Пособие для учителей. - М.. 1979. список литературы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
Сколько стоит
заказать работу?
1
Заполните заявку - это бесплатно и ни к чему вас не обязывает. Окончательное решение вы принимаете после ознакомления с условиями выполнения работы.
2
Менеджер оценивает работу и сообщает вам стоимость и сроки.
3
Вы вносите предоплату 25% и мы приступаем к работе.
4
Менеджер найдёт лучшего автора по вашей теме, проконтролирует выполнение работы и сделает всё, чтобы вы остались довольны.
5
Автор примет во внимание все ваши пожелания и требования вуза, оформит работу согласно ГОСТам, произведёт необходимые доработки БЕСПЛАТНО.
6
Контроль качества проверит работу на уникальность.
7
Готово! Осталось внести доплату и работу можно скачать в личном кабинете.
После нажатия кнопки "Узнать стоимость" вы будете перенаправлены на сайт нашего официального партнёра Zaochnik.com
© Рефератбанк, 2002 - 2017