Автор работы: Пользователь скрыл имя, 22 Марта 2012 в 12:50, курсовая работа
Графы стали изучаться ещё математиками 18 веке но как предмет математической теории только в 20 веке. В настоящее время теория графов находит всё более и более широкое применение применяются в естественных науках (физика, химия, биология, социология, лингвистика). Простейшему с топологической точки зрения объекту – графам (1 – мерным комплексам) посвящена моя работы. Сначала обсуждается общие понятия, затем его топологическое и метрическое свойство: планарность.
Введение____________________________________________________2
0. Необходимые вспомогательные утверждения__________________3
1. Плоские и планарные графы_______________________________4
2. Формула Эйлера для планарных графов_________________________7
3. Критерии планарности____________________________________10
4. Двойственность и планарность_____________________________18
5. Алгоритм укладки графа на плоскости_______________________21
6. Характеристики планарных графов___________________________25
7. Упражнения______________________________________________________27
8. Список литературы_______________________________________________29
Решение. Предположим, что граф Г плоский, т. е. существует его плоское представление. Граф Г — связный, он не имеет перегородок, так как не имеет ни одного моста. Для плоского представления графа Г верна формула Эйлера, Подсчитаем число вершин и ребер: в = 5, р = 10, тогда г =2 — 5 + 10 = 7. Оценим удвоенное число ребер 2р. Каждая грань ограничена не более чем тремя ребрами (граф полный), причем каждое ребро принадлежит границам двух граней, поэтому число Зг не может быть больше числа 2р, то есть Зг ≤ 2р. Но 2р = 20, а Зг = 21, то есть 20 ≥ 21. Противоречие доказывает, что предположение было неверным, то есть граф Г не плоский.
Список литературы
1. Емеличев Р.И., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов.
2. Ф. Харари. Теория графов. М.: «Мир». 1973
3. Зыков А.А. Основы теории графов
4. Березина Л.Ю. Графы и их применение
5. Берж К. теория графов и их применение
1