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

Содержание

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

Введение

Работа выполнена в соответствии с темой 4. Циклы в графах.
С циклами и цепями связаны наиболее известные задачи из истории графов, одна из них задача о гамильтоновых цепях и циклах. Требуется найти, при каких условиях конечный связный граф содержит цепь или цикл, проходящий через все вершины. Если такая цепь или цикл существует и являются простыми, то они называются соответственно гамильтоновыми цепями или гамильтоновыми циклами.
Если граф обладает гамильтоновым циклом S, то, очевидно, он обладает и гамильтоновой цепью. Обратное, вообще говоря, неверно.
Несмотря, на наличие частных результатов, в общем случае задача определения гамильтоновых циклов и цепей недостаточно изучена. Даже нет хороших методов доказательства существования таких цепей и циклов.
Интересной задачей, связанной с поиском кратчайшего гамильтонова пути, является задача коммивояжера. Коммивояжер должен посетить по одному разу каждый из n городов (каждый город связан с другим дорогой) и вернуться в исходный город. При этом он должен выбрать кратчайший маршрут. Очевидно, что определения кратчайшего маршрута с помощью просмотра всех гамильтоновых циклов приводит к перебору гамильтоновых циклов (n-1)!/2 возможных циклов, а это величина астрономическая при больших n.

 

Предположим, что в графе 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.
При замещении атома водорода ОН, получаем такой же результат для спиртов.