Граф сидел у камина, лениво покуривая дорогую кубинскую сигару…
Между планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля-Меркурий, Плутон-Венера, Земля-Плутон, Плутон-Меркурий, Меркурий-Венера, Уран-Нептун, Нептун-Сатурн, Сатурн-Юпитер, Юпитер-Марс и Марс-Уран. Можно ли добраться с Земли до Марса?
Картинки, представляющие собой набор точек, некоторые из которых соединены линиями, называются графами. При этом, точки называются вершинами графа, а отрезке - его ребрами.
Можно ли, сделав несколько ходов конями, из положения 1 получить положение 2?
В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли из города 1 добраться в город 9?
В графах важно лишь то, что некоторые вершины соединены ребрами, а некоторые - нет, при этом совершенно не важно, как эти вершины расположены на рисунке. Одинаковые, но по-разному нарисованные графы, называются изоморфными.
Какие из графов на рисунке изоморфны? (см. рис.)
В кружочках написали числа 1, 2, 3, 4, 6 и 12, и от каждого числа к каждому его делителю направили стрелку. Хулиган Вася стер все числа и часть стрелок. Восстановите исходное положение, рассмотрев все возможные варианты.
В стране 100 городов. Некоторые города соединены дорогами, причем из каждого города выходит не менее 50 дорог. Доказать, что из любого города этой страны можно доехать до любого другого города этой страны.
*В стране любые два города соединены или железной дорогой, или авиалинией. Доказать, что чтобы добраться от одного города до другого в этой стране можно пользоваться только одним видом транспорта.
*В кружке у любого члена имеется один друг и один враг. Доказать, что а) число членов кружка четно. б) кружок можно разделить на 2 нейтральных кружка (т.е. таких кружка, где ни у кого нет ни друзей, ни врагов).
Связным графом называется такой граф, что по его ребрам можно из любой вершины "дойти" до любой другой. Какие графы (из графов 1-8) связные?
Граф распадается на компоненты связности. Это такие части графа, которые сами являются связными графами и при этом не связаны между собой.
а) В государстве 1000 городов, из каждого города выходит 4 дороги. Посчитать количество дорог в государстве. б) В государстве 1001 город и из каждого города выходит по 5 дорог. Сколько дорог в государстве?
Количество ребер, выходящих из вершины называется степенью этой вершины. Если степень вершины - четное число, вершина называется четной, наоборот - нечетной
.
(Лемма о рукопожатиях.) Докажите, что людей, которые пожимали нечетное число рук, четное число (или, говоря на языке графов, доказать, что нечетных вершин в графе четное число).
Можно ли нарисовать 9 отрезков так, чтобы каждый пересекался с тремя другими?
Могут ли степени вершин в графе быть равны: а) 8,6,5,4,4,3,2,2. б) 7,7,6,5,4,2,2,1.
в) 6, 6, 6, 5, 5, 5, 3, 2, 2 ?
*Доказать, что из связного графа можно выкинуть вершину, оставив его связным.
Устные задачи.
В двух бидонах содержится молоко: в первом в два раза больше, чем во втором. Когда из первого отлили 30 литров, а из второго 20 литров, то в первом осталось молока в 3 раза больше, чем во втором. Сколько молока было в каждом бидоне до отливания?
Али-Баба, Синдбад и Магрибинец нашли клад. Не разделив его, легли спать. Али-Баба проснулся первым, взял треть всех монет, пожадничал и взял еще одну. Затем проснулся Синдбад. Думая, что он первый, взял треть оставшихся монет и еще одну. Наконец, Магрибинец взял треть остатка и еще одну монету. Осталось 5 монет. Сколько монет было вначале?
Говорит дед внукам:" Вот вам 130 орехов. Разделите их на две части так, чтобы меньшая часть, увеличенная в 4 раза, равнялась бы большей части, уменьшенной в 3 раза". Как разделить орехи?
Лошадь съедает воз сена за месяц, коза - за два месяца, овца - за три месяца. За какое время лошадь, коза и овца вместе съедят такой же воз сена?
Задачи на движение.
Автомобиль половину пути проехал со скоростью 60 км/час. С какой скоростью он должен ехать вторую половину пути, чтобы средняя скорость на маршруте составила 48 км/час?
Если Аня идет в школу пешком, а домой едет на автобусе, то всего на дорогу она тратит полтора часа. Если же весь путь проделан на автобусе, то он занимает полчаса. Сколько времени потратит Аня на дорогу, если весь путь пройдет пешком?
Из пункта А в пункт Б вышел Андрей, а из пункта Б в пункт А вышел Боря. Когда Андрей дошел до середины пути, Боре оставалось идти до А ровно половину того расстояния, которое нужно было пройти Андрею в тот момент, когда Боря оказался на половине пути от А до Б. Сколько осталось идти Боре, когда Андрей добрался до Б?
Из А в В вышел пешеход. Одновременно из В в А выехал автомобиль. Встретив пешехода, автомобиль доставил его в В и тут же снова поехал в А. Пешеход добрался до В в 4 раза быстрее, чем если бы он всю дорогу шел пешком. Во сколько раз быстрее попал бы автомобиль в А, если бы ему не пришлось возвращаться?
Улитка ползет по вертикальной трубе снизу вверх. Длина трубы 9 метров. Улитка может ползти с постоянной скоростью вверх ровно 1 час и поднимается за это время на 4 метра, а затем 1 час отдыхает, либо за 1 час поднимается на 5 метров, а потом 2 часа отдыхает.
За каждый час отдыха она опускается вниз на 2 метра. За какое наименьшее время улитка может подняться до верха трубы?
Поезд "Стрела" выходит из Антоновки в Андреевку и по пути встречает 5 таких же составав "Стрела". Придя в Андреевку, он тут же возвращается в Антоновку, и т.д. Сколько составов "Стрела" обслуживают маршрут?
Путник вышел из Антоновки в 12:00 и пришел в Андреевку в 18:00. По пути, проходя мимо дома часовщика, он заметил время. На другой день путник выехал на велосипеде из Андреевки в 12:00, а приехал в Антоновку в 13:12. Проездая мимо дома часовщика, он удивился: часы показывали то же время, что и накануке, но они шли! Какое время показывали часы?
Письменная домашняя работа.
От жары площадь озера сократилась на 20%, но потом в сезон дождей площадь озера выросла на 25%. Выросла или уменьшилась площадь озера по сравнению с первоначальной и на сколько процентов?
У крестьянина были коза, корова и кобыла, а еще стог сена и сын. Сын подсчитал, что этого сена козе и кобыле хватит на 1 месяц, козе и корове на 3/4 месяца, а корове и кобыле на 1/3 месяца. Отец сказал, что сын плохо учился в школе. Кто прав?
Незнайка хочет расставить в кружках натуральные числа так, чтобы в кружках, соединенных отрезками, стояли числа, у которых есть общий делитель, больший единицы, а числа, не соединенные отрезками, имели наибольший общий делитель 1. Удастся ли ему это сделать?
Лена, Наташа и Саша ели конфеты. Лена и Саша съели на 11 конфет больше Наташи, а Наташа и Лена - на 7 больше Саши. Сколько конфет съела Лена?
В деревне у прямой дороги стоят четыре избы А, В, С,
D на расстоянии 50 метров друг от друга. В какой точке дороги следует построить колодец, чтобы сумма расстояний от колодца до всех четырех изб была наименьшей?
В деревне А живет 50 школьников, в деревне В живет 100 школьников. Расстояние между деревнями 3 км. В какой точке дороги из А в В надо построить школу, чтобы суммарное расстояние, проходимое всеми школьниками, было наименьшим?
