Введение в теорию графов. Индивидуальные задания (66
.pdfсоответствующую теорему для графа, состоящего из k планарных компонент связности?
2)В нетривиальном дереве есть хотя бы одна висячая вершина.
2.1Каким методом доказывается теорема?
2.2Что дано, что требуется доказать?
2.3Как составляется противоречие, то есть что допускаем?
2.4Какой вывод относительно степеней вершин отсюда следует?
2.5Какие действия осуществляются для того, чтобы прийти к противоречию?
2.6Почему при первом входе в каждую вершину из нее есть выход? Можно ли слово «первом» опустить?
2.7Почему после конечного числа шагов мы вернемся в какую-нибудь из пройденных вершин? Обязательно ли это начало обхода?
2.8В чем же противоречие, с каким элементом условия?
2.9Где эта теорема используется в дальнейшем?
3)Если в связном графе q p 1, то это дерево.
3.1Метод доказательства.
3.2Что дано, что требуется доказать?
3.3Какие действия осуществляются, чтобы перейти к противоречию?
3.4Почему после конечного числа этих действий остается дерево?
3.5В чем же противоречие и с чем?
3.6Где в доказательстве были использованы связность графа и условие q p 1?
4)Для связного графа G следующие 3 утверждения эквивалентны:
(1)G – эйлеров граф;
(2)каждая вершина графа G имеет четную степень;
(3)множество ребер графа G можно разбить на простые циклы.
5)Теорема о 5 красках. Каждый планарный граф 5 – раскрашиваем.
6)Число правильных многогранников не более 5.
41
7)В любом графе с 6 вершинами всегда найдутся либо 3 попарно смежные, либо 3 попарно несмежные вершины.
8)Графы K5 и K33 не являются планарными.
9)В любом планарном графе q 3 p 6 . Если же в планарном графе нет треугольников, то q 2 p 4.
10)Для того чтобы паросочетание М в двудольном графе было максимальным, необходимо и достаточно, чтобы в нем не было увеличивающей М чередующейся цепи.
Приложение.
Советы и вопросы, помогающие усвоить доказательства теорем
Со времен греков говорить «математика» – значит говорить «доказательство».
Н. Бурбаки
1.Прочитайте формулировку теоремы. Запишите, что дано и что требуется доказать. Попробуйте сами сформулировать теорему, сравните вашу формулировку с записями в лекции. Какие понятия использовались в формулировке? С какими теоремами возможна связь?
2.Проверьте, если возможно, справедливость теоремы на частных случаях; нарушения заключения, если не выполняется какой-либо пункт условия. Приведите, если возможно, графические иллюстрации.
3.Нельзя ли некоторые элементы условия ослабить так, чтобы заключение теоремы осталось верным? Если нельзя, то постройте доказывающий это контрпример.
4.Составьте утверждение, обратное теореме, и постарайтесь установить, будет ли оно иметь место.
42
5.Можно ли сформулировать теорему в форме достаточного, или необходимого, или необходимого и достаточного условия какого-либо факта?
6.Прочитав доказательство, попробуйте сформулировать его основную идею. Какие шаги доказательства являются естественными, а какие «берутся с неба»? Если последние встретились в доказательстве, то нельзя ли установить ход рассуждений, которые помогли бы догадаться до этого шага без подсказки.
7.Составьте план доказательства, постарайтесь оформить его в виде схем, рисунков. Попробуйте представить доказательство как цепочку отдельных элементов, следующих друг за другом. Можно ли изменить их порядок? Определите, какие из элементов цепочки являются основными, а какие играют вспомогательную роль. Не можете ли Вы некоторые элементы доказательства построить самостоятельно или доказать по-другому?
8.Выясните, какие теоремы и определения использовались при доказательстве, где использовался каждый элемент условия, что главное надо запомнить, чтобы восстановить доказательство.
9.Постарайтесь конспективно изложить доказательство, заменяя каждое предложение одним подлежащим или одним сказуемым. Попробуйте записать доказательство с пропущенными ключевыми словами и предложить товарищу вставить эти слова. Придумайте вопросы по этому доказательству, упражнения, помогающие усвоить доказательство.
10.Постарайтесь найти следствия из изучаемой теоремы или ее обобщение, установить аналогии с другими теоремами, как по содержанию, так и по способу доказательства.
11.Изучая доказательство теоремы, которое ведется дедуктивно, рассмотрите его ход в обратном направлении. До каких из полученных шагов Вы могли бы догадаться или, в крайнем случае, объяснить их целесообразность? Постарайтесь на основе проведенного анализа построить индуктивный ход доказательства теоремы.
12.Завершите работу по анализу доказательства теоремы полным рассказом (изложением) этого доказательства.
Е. К. Годунова
Введение в теорию графов
Индивидуальные задания
Издательство «Прометей» 115035, Москва, ул. Садовническая, д.72, стр.1
Тел/факс: 8 (495) 799-54-29 E-mail: info@prometej.su
Подписано в печать 23.07.2012 г. Формат 60х90/16. Объем 2,75 п.л.
Тираж 500 экз. Заказ № 226.