Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/mccme/2012/6klass/14.doc Дата изменения: Thu Jan 26 16:18:42 2012 Дата индексирования: Mon Feb 4 21:14:53 2013 Кодировка: koi8-r Поисковые слова: spring

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


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

[pic]

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

а) Нарисуйте схему движений между планетами.

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

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

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

[pic]

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


Два графа называются равными, если их вершины можно пронумеровать так,
что одинаково обозначенные вершины будут либо в обоих графах соединены,
либо в обоих графах не соединены.

3. Ниже приведены четыре разных изображения одно и того же графа.
Вершины одного из них пронумерованы. Пронумеруйте соответствующие
вершины оставшихся графов так чтобы одинаково пронумерованные вершины
были одинаково соединены.

[pic]
4. Перерисуйте следующий граф так, чтобы его ребра не пересекались:


5. Есть ли среди следующих графов равные? Если да, то какие?
[pic]

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

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

7. В некотором государстве 40 городов и из каждого выходит по 3 дороги.
Сколько всего в государстве дорог? (Каждая дорога соединяет какие-то
два города.)

8. Сева нарисовал 10 точек, некоторые из которых соединил отрезками.
После этого он спрятал рисунок в чемодан, чемодан закрыл на ключ, а
ключ проглотил. В ответ на это Наташа заслала в его чемодан
разведывательного таракана, который сообщил, что из точек выходит
соответственно 5, 5, 4, 4, 3, 3, 2, 2, 1, 1 отрезка. Сколько отрезков
нарисовал Сева?


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

9. В деревне Пятнашкино 15 домов. Электрик решил соединить проводами каждый
дом ровно с девятью другими. Сможет ли он это сделать?

10. Архипелаг ГудЛак, расположенный вблизи континента Австрика, состоит из
7 островов. С каждого из островов ведет 1, 3 или 5 мостов. Верно ли, что
хотя бы один из островов соединён мостом с Австрикой?

-----------------------
[pic]

[pic]