Самостоятельная работа №1 План: Аксиоматические теории множеств. Нечеткие множества

Рисунок 3
а) б)

Задача, которая привела к появлению понятия Эйлерова цикла, широко известна в истории математики. Это так называемая задача о кенигсбергских мостах. Расположение семи мостов в городе Кенигсберге в начале XVIII века приведено на рисунке 3а. Требуется обойти город, пройдя через каждый мост ровно один раз, и вернуться в исходную точку.
Можно представить описанную задачу следующим образом. Имеется связный неориентированный граф с четырьмя вершинами и семью рёбрами. Требуется выяснить, существует ли простой цикл, позволяющий обойти данный граф по маршруту, включающему в себя по одному разу каждое ребро графа.
Именно решение данной задачи привело Л. Эйлера к доказательству приведённой выше теоремы. Кстати, согласно ей, данная задача неразрешима, поскольку степени всех вершин графа нечётны.
Теорема 15.2.Для того, чтобы связный граф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечетной степени.
По сути дела, теоремы 15.1 и 15.2 описывают условия, при которых можно построить геометрическую фигуру “не отрывая карандаша от бумаги”, одной сплошной линией. Только в первом случае начало и конец этой линии будут совпадать, а во втором случае они будут различны.
Определение.Цикл (цепь) в графеGназываетсяГамильтоновым, если он проходит через каждую вершину графаG ровно один раз.
Пример 1.
а )
- в графе есть и Эйлеров и Гамильтонов циклы
б )
- в графе есть Эйлеров цикл, но нет Гамильтонова
в)
- в графе есть гамильтонов, но нет Эйлерова цикла
г)
- в графе нет ни Эйлерова, ни Гамильтонова цикла
Граф Gназываетсяполным, если каждая его вершина является смежной со всеми остальными вершинами. В полном графе всегда существуют гамильтоновы циклы.
Также необходимым условием существования гамильтонова цикла является связность графа.

Планарные графы

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

• 
  граф планарен?
  
• 
  Как получить планарное изображение графа?
  

Если граф не планарен, то приходится удалять (переносить на другой слой, на другую плоскость) отдельные ребра.
Минимальное число ребер, которое надо удалить для получения плоского изображения, называется числом планарности графа и обозначается  (G). Для полных графов с 
(K_n) = (n–3)(n–4)/2.
Из формулы следует, что при n = 4  (K₄) = 0. Для K₅  (K₅) = 1, следовательно, чтобы граф K₅ стал плоским, из него надо удалить одно ребро.
При перенесении на вторую плоскость, перенесенная часть может опять оказаться не плоской. Тогда отдельные ребра переносят на новую плоскость и т.д.
Минимальное число плоскостей, при котором граф разбивается на плоские части, называется толщиной графа и обозначается t(G).
Толщина произвольного графа удовлетворяет неравенству
t(G) .
Здесь [x] – целая часть x.
Толщина полных графов удовлетворяет неравенству
t(K_n) .
Например, для K₅ t(K₅) = 2.

23.2.2 Условия планарности