Кружок 6 класса
Руководитель Елена Анатольевна Чернышева
2005/2006 учебный год
Занятие 13. При чём здесь граф?(18.02.2006)
Граф — набор точек, некоторые из которых соединены отрезками. Точки называются вершинами графа, а отрезки рёбрами. На картинках рёбра могут изображаться не в виде отрезков, а просто линией, соединяющей вершины.
Количество рёбер выходящих из вершины графа называется степенью этой вершины.
- 1.
-
При дворе принца Лимона служили герцоги, графы и бароны. В
начале правления принца придворных было 2006, но каждый день один из
них убивал другого на дуэли, причем графы убивали только герцогов,
герцоги — только баронов, а бароны — только графов. При этом
никто не выиграл дуэль дважды. В конце концов остался в живых лишь
граф Апельсин. Какой титул был у первого погибшего придворного?
- 2.
-
В Таниной квартире есть восемь розеток, 21 тройник и
неограниченное количество утюгов. Какое наибольшее число утюгов Таня
может включить одновременно?
- 3.
-
В графе n вершин, и каждая соединена с каждой. Сколько рёбер в
графе?
- 4.
-
Докажите, что число людей, когда-либо живших на земле и сделавших
нечетное число рукопожатий, четно.
- 5.
-
В графе каждая вершина покрашена в синий или зеленый цвет. При
этом каждая синяя вершина связана с пятью синими и десятью зелеными,
а каждая зеленая с девятью синими и шестью зелеными. Каких вершин
больше — синих или зеленых?
- 6.
-
Докажите, что среди девяти человек найдутся либо трое попарно
знакомых, либо четверо попарно незнакомых.
- 7.
-
В городе проводилось совещание врачей. От каждой поликлиники на
совещание было приглашено по пять врачей. Оказалось, что каждый из
приглашенных работал в двух поликлиниках, поэтому на совещании
представлял обе поликлиники. Кроме того, для любых двух поликлиник
города среди участников совещания найдется врач, который в них
работает. Сколько в городе поликлиник и сколько врачей принимало
участие в совещании?
- 8.
-
На окружности отмечены 7 красных и 5 синих точек. Каких
треугольников с вершинами в этих точках больше: одноцветных или
разноцветных? На сколько?