ВУЗ:
Составители:
Рубрика:
28
два куска, то в итоге получим удвоенное число ребер. Так как
все куски, кроме внешнего, – треугольники, а внешний кусок
ограничен 4 ребрами, то получаем
EF 2413 , то есть
2
2
13
F
E . Заметим, что число вершин графа равно 24 и
подставим количества вершин ребер в формулу Эйлера
22
2
13
24
F
F
. Отсюда
43
F
. Итак, число тре-
угольников 42. 3. Для этого графа не выполнено неравенство
63
VE
. 4. а) Можно. Расположим 6 точек (ЭВМ) в верши-
нах правильного шестиугольника. Его стороны закрасим через
одну цветами 1 и 2, а диагонали – цветами 3, 4, 5 (одним цветом
закрасим две параллельные малые диагонали и перпендикуляр-
ную к ним большую). б) Нельзя, так как число проводов каждо-
го цвета должно быть равным
2/15
. 5. Нельзя. Если бы такой
граф был плоским, то, так как каждый кусок должен быть огра-
ничен по меньшей мере 4 ребрами, получим
F
E
2
. В задаче
9
E
, поэтому
4
F
. А из формулы Эйлера имеем
5962
F
. 6. Предположим противное. Тогда
VE 62
,
то есть
VE 3
, что противоречит неравенству. 7. Не выполня-
ется неравенство
EV
63
. 8. Пусть оба эти графа – плоские.
Тогда у них вместе не более чем
5461136113 реб-
ра. Однако в полном графе с 11 вершинами 55 ребер. Противо-
речие.
5. 1. Пусть в столицу входит
a
дорог. Тогда общее число
«входящих» дорог равно
a
10021
, а общее количество «вы-
ходящих» дорог не больше
a 10010020 . Поэтому
aa 1001002010021 , то есть
02
a
. Таким обра-
зом,
0
a
. 2. Рассмотрим сначала вершины, соединенные с лю-
бой фиксированной вершиной
A
, затем – новые вершины, со-
единенные с ними и так далее. При этом ребра, соединяющие
добавляемые вершины с уже рассмотренными, ориентируем в
направлении к новым вершинам. 3. Указание. Занумеруем горо-
