Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/mccme/2008/6klass/14.doc Дата изменения: Sat Jan 26 22:55:27 2008 Дата индексирования: Sun Apr 13 21:55:07 2008 Кодировка: koi8-r Поисковые слова: п п п п п п п п п п п п

Математический кружок 6 класс
Занятие ?14 Графы 26.01.08


1. На рисунке квадратиками обозначены дома Единицына, Двойкина,
Тройкина, Четвёркина и Пятёркина. Кружочками обозначены их колодцы.
Могут ли эти граждане проложить тропинки к своим колодцам так, чтобы
тропинки не пересекались?

[pic]

2. Между 9 планетами Солнечной системы введено космическое сообщение.
Ракеты летают по следующим маршрутам: Земля-Меркурий, Плутон-Венера,
Земля-Плутон, Плутон-Меркурий, Меркурий-Венера, Уран-Нептун, Нептун-
Сатурн, Сатурн-Юпитер, Юпитер-Марс, Юпитер-Нептун и Марс-Уран.

а) Можно ли добраться с Земли до Марса?

б) Есть ли среди приведенных ниже схем те, которые могут отражать
схему движений между планетами? Если есть, то какие?

в) есть ли хоть одна планета, которую на схеме можно однозначно
определить?

[pic]
3. Придумайте и нарисуйте схему движений между 9 планетами Солнечной
системы, такую, чтобы соблюдались три условия:

1) с Земли можно улететь в трёх направлениях,

2) добраться с Земли до Меркурия можно не менее, чем с тремя
пересадками,

3) а между любыми двумя другими планетами есть маршрут с двумя или
меньшим числом пересадок.

4. Сытый марсианский кот Васька поймал 6 марсианских треххвостых мышек и
связал их хвостами так, что свободных хвостов не осталось. Сколько
узелков ему пришлось завязать? Васька поймал еще одну мышку и решил,
развязав некоторые из узелков, связать эту мышку со всеми остальными.
Сможет ли он это сделать так, чтобы по-прежнему не было свободных
хвостов?

5. В городе Маленьком 15 телефонов. Некоторые телефоны соединены
проводами (каждый провод соединяет ровно два телефона). При этом от 5
телефонов отходит по 6 проводов, а от остальных 10 телефонов - по 3
провода. В город пробрался хулиган и разрезал каждый провод пополам.

а) Сколько всего половинок проводов оказалось у бедных владельцев
телефонов?

б) А сколько новых проводов им придется купить, чтобы заменить
старые?

6. В посёлке Подикаразберись 9 домов. Из каждого дома тянется четыре
шланга к четырем другим домам и каждый из этих шлангов имеет длину
178 метров 25 сантиметров. Найдите общую длину шлангов в посёлке
Подикаразберись.

7. В графе с 8 вершинами степени вершин равны 6, 6, 6, 5, 5, 4, 4, 4.
Сколько в нем ребер?

8. Может ли в государстве, в котором из каждого города выходит 3 дороги,
быть

а) ровно 100 дорог?

б) ровно 105 городов?







__________________________________________________________________________



Граф можно представлять себе как набор точек (вершин), некоторые
из которых соединены линиями (рёбрами).

Количество рёбер, выходящих из данной вершины, называется степенью
этой вершины.

Ниже на рисунке изображен граф с 14-ю вершинами. Из вершины,
обозначенной цифрой 4 выходит пять линий (рёбер), поэтому её
степень равна 5. Из вершин обозначенных цифрами 10 и 13 выходит
по четыре ребра, поэтому их степени равны 4. Степень вершины,
обозначенной цифрой 9, равна двум, а степень вершины 8 - трём. Из
вершины 14 вообще не выходит рёбер, поэтому её степень равна 0. Из
всех остальных вершин выходит по одному ребру, поэтому их степени
равны 1.

[pic]

Дополнительная задача.

9. Можно ли, cделав несколько ходов конями из исходного положения,
изображенного на рис. 1, расположить их так, как показано на рис. 2?

[pic] [pic]









Дополнительная задача.

9. Можно ли, cделав несколько ходов конями из исходного положения,
изображенного на рис. 1, расположить их так, как показано на рис. 2?

[pic] [pic]