Кружок 6 класса

Руководитель Елена Анатольевна Чернышева
2005/2006 учебный год

Занятие 13. При чём здесь граф?(18.02.2006)

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