Работа выполнена на отлично,автор выполнил в срок.Заказываю у этого автора не в первый раз,все быстро и качественно.Рекомендую
Информация о работе
Подробнее о работе
Любая из понравившихся вам тем в прикрепленном файле
- 20 страниц
- 2015 год
- 82 просмотра
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Введение
Работа выполнена в соответствии с темой 4. Циклы в графах.
С циклами и цепями связаны наиболее известные задачи из истории графов, одна из них задача о гамильтоновых цепях и циклах. Требуется найти, при каких условиях конечный связный граф содержит цепь или цикл, проходящий через все вершины. Если такая цепь или цикл существует и являются простыми, то они называются соответственно гамильтоновыми цепями или гамильтоновыми циклами.
Если граф обладает гамильтоновым циклом S, то, очевидно, он обладает и гамильтоновой цепью. Обратное, вообще говоря, неверно.
Несмотря, на наличие частных результатов, в общем случае задача определения гамильтоновых циклов и цепей недостаточно изучена. Даже нет хороших методов доказательства существования таких цепей и циклов.
Интересной задачей, связанной с поиском кратчайшего гамильтонова пути, является задача коммивояжера. Коммивояжер должен посетить по одному разу каждый из n городов (каждый город связан с другим дорогой) и вернуться в исходный город. При этом он должен выбрать кратчайший маршрут. Очевидно, что определения кратчайшего маршрута с помощью просмотра всех гамильтоновых циклов приводит к перебору гамильтоновых циклов (n-1)!/2 возможных циклов, а это величина астрономическая при больших n.
Содержание
ВВЕДЕНИЕ 3
1. ОСНОВОПОЛАГАЮЩИЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ 4
2. ЦИКЛОМАТИЧЕСКОГО ЧИСЛА ГРАФА И ЕГО ОСНОВНЫЕ СВОЙСТВА 7
3. ОПРЕДЕЛЕНИЕ ГРУПП ОДНОМЕРНЫХ И НУЛЬМЕРНЫХ ЦЕПЕЙ ГРАФА 10
РЕШЕНИЕ ЗАДАЧ 15
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 18
Предположим, что в графе 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. Уилсон Р. Введение в теорию графов - М . Мир, I977
2. Белов В.В. Воробьев Е. М . Шаталов В. Е. Теория графов — М ВШ. 1976.
3. Березина Л. Ю. Графы и их применения. Пособие для учителей. - М.. 1979.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
