Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/vmsh/vmsh_7_0708/text04.ps Дата изменения: Mon Sep 1 19:56:22 2008 Дата индексирования: Sat Sep 6 23:50:47 2008 Кодировка: koi8-r Поисковые слова: sts-64

Гимназия 1543, Вечерняя математическая школа, 7 класс, 8 ноября 2007, занятие 4.
Графы.
Какая общность в этом есть?
Какие зыбкие нас связывают нити?
Александр Городницкий
Мы начинаем знакомиться с графами | замечательным способом наглядно-
го представления связей между объектами. Если есть некоторое конечное число
объектов, некоторые из которых определённым образом связаны между собой, то
удобно изобразить на листе бумаги объекты точками, а связи | линиями (мож-
но кривыми). Такая картина называется графом. Выучим простейшие термины
теории графов:
Вершина | точка, одна из тех, которые мы соединяем линиями.
Ребро | линия, соединяющая две вершины.
Степень вершины | количество рёбер, исходящих из неё.
Если специально не оговаривается, будем считать, что две вершины соединя-
ются не более чем одним ребром, вершина сама с собой не соединяется.
1) Графом можно изобразить самые разные жизненные ситуации. Можно за вершины принять
марсиан, стоящих на космодроме, а соединять рёбрами тех, кто пожимает друг другу руки. Можно
вершинами считать города, а рёбрами | связывающие их дороги. Можно вершинами графа считать
людей, а ребром соединить тех, кто дружит между собой... Придумайте какой-нибудь свой пример
ситуации, которую можно изобразить графом.
У нас в прошлом занятии была задача: Докажите, что среди штатов США
количество таких, которые граничат с нечётным числом штатов, чётно. Решим
её. Пусть штаты | вершины графа, а рёбрами связываем те и только те пары
штатов, у которых есть общая граница. Тогда штаты, которые граничат с не-
чётным числом других штатов | вершины нечётной степени. Подсчитаем число
рёбер графа: сложим степени всех вершин. При этом каждое ребро посчиталось
дважды, "с одного конца и с другого". Значит, сумму надо поделить пополам. Но
если в ней будет нечётное число нечётных слагаемых, это сделать не удастся!
Наша задача решена. Обратим внимание, что нам не понадобилось знать коли-
чество штатов США, не понадобились никакие сведения об их географии. Мы
решили задачу для графа. Запомним полученную теорему:
"В любом графе количество вершин нечётной степени чётно"
2) Рассмотрим задачу: "В любой компании из шести человек найдутся либо трое, которые дружат
между собой, либо трое, никакие двое из которых не дружат". Не решая эту задачу, сформулируйте
её на языке графов.
3) А теперь наоборот: дана задача про граф: "В графе 102 вершины, степень каждой не менее, чем
68. Докажите, что найдутся четыре вершины одинаковой степени". Не решая её, переформулируйте
её в задачу о дружбах между людьми или на ещё какой-нибудь "жизненный" сюжет.

4) Нарисуйте граф с восемью вершинами степени которых равны 0, 1, 1, 1, 2, 2, 3, 4. Можно ли
нарисовать граф с девятью вершинами, добавив к списку ещё вершину степени 5?
Вершина степени 0 называется изолированной, вершина степени 1 | вися-
чей.
5) В стране некоторые города соединены дорогами. Из столицы выходит 1543 дороги, из города
Дальний | только одна дорога, а из всех прочих городов по 100 дорог. Докажите, что из столицы
можно добраться до Дальнего (проезжая, если нужно, через другие города).
Если из одной вершины, переходя несколько раз по рёбрам, можно попасть в
другую, то говорят, что они связаны, а цепочка рёбер, по которым мы перешли
из одной в другую | связывающий их путь.
6) В стране некоторые города связаны беспосадочными авиарейсами. Известно, что из столицы
можно долететь в любой город, возможно пересаживаясь с самолёта на самолёт. Докажите, что из
любого города можно добраться до любого другого, также, возможно, с пересадками.
Если в графе любые две вершины связаны, он называется связным.
7) В стране 9 городов, некоторые из них связаны авиалиниями. Известно, что из каждого города
выходит по крайней мере по 4 авиалинии. Докажите, что из любого города можно долететь в любой
другой, возможно, пересаживаясь в других городах.
8) Докажите, что граф с семью вершинами, степени которых 1, 2, 2, 2, 2, 3, 4, связен.
9) В стране любые два города соединены или железной дорогой, или авиалинией. Доказать, что
один из видов транспорта позволяет добраться из любого города в любой.
Домашнее задание на 15 ноября.
4.1) Могут ли степени вершин в графе быть равны:
а) 8, 6, 5, 4, 4, 3, 2, 2;
б) 7, 7, 6, 5, 4, 2, 2, 1;
в) 6, 6, 6, 5, 5, 3, 2, 2?
4.2) Можно ли расположить на столе 7 монет так, чтобы каждая касалась ровно трех других?
4.3) Государство расположено на пяти островах, между любыми двумя из которых проложен
кабель связи. Какое минимальное количество кабелей должен повредить враг, чтобы связь между
какими-то островами (даже при посредстве связистов на других островах) стала невозможной?
Специальная задача ‚4.
В 7 "Г" с начала учебного года завелась хорошая традиция: когда у какого-
то ученика бывает день рождения, он зовёт на празднование всех своих друзей из
класса. День рождения при этом бывает всегда таким шумным и весёлым, что все
гости с того дня начинают дружить между собой. Когда 7"Г" в новом учебном
году превратился в 8"Г", обнаружилось, что Вася и Петя не дружат. Докажите,
что они так и не подружатся, сколько бы ещё ни продолжалась традиция весёлых
дней рождения. (Считаем, что дружбы завязываются только на днях рождения.)