Составители:
Рубрика:
73
86.
Имеются три пробирки. Вместимость каждой из них 100 миллилитров. Две пробирки из трех
одинаково размечены. Деления нанесены произвольно и соответствуют целым количествам
миллилитров. Изначально одна из пробирок с делениями наполнена 100 миллилитрами кваса, а
остальные пустые. Описать алгоритм, который выясняет, можно ли поместить в пробирку без
делений один миллилитр кваса и, если да
, то находит минимальное число необходимых для этого
переливаний. Каждое переливание из одной пробирки в другую можно проводить до тех пор,
пока либо первая из них не станет пустой, либо одна из пробирок не окажется заполненной до
какого-либо деления.
87.
Имеется расписание беспосадочных авиарейсов. Составить оптимальный алгоритм
определяющий, можно ли из пункта А попасть в пункт В.
88.
Имеется атлас автомобильных дорог с указанием расстояний между городами. Составить
оптимальный алгоритм нахождения минимального пути между двумя городами.
Деревья.
89. Докажите, что граф, в котором любые две вершины соединены ровно одной цепью, является
деревом.
90.
Докажите, что в дереве любые две вершины соединены ровно одной цепью.
91. Докажите, что в дереве с р вершинами р–1 ребро.
92. Докажите, что связный граф, у которого число ребер на единицу меньше числа вершин, является
деревом.
93.
Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина
называется висячей).
94.
Докажите, что в любом нетривиальном дереве имеются, по крайней мере, две висячие вершины.
95.
Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.
96.
Какое максимальное число висячих вершин может иметь дерево, обладающее 9 вершинами?
97. В графе все вершины имеют степень 3. Докажите, что в нем есть цикл.
98.
В парке «Лотос» невозможно найти такой маршрут для прогулок по его дорожкам, который
начинается и оканчивается в одной и той же точке и каждую дорожку содержит не более одного
раза. Докажите, что некоторые дорожки парка приводят в тупик.
99.
В стране 101 город, и некоторые из них соединены дорогами. При этом любые два города
соединяет ровно один путь. Сколько в этой стране дорог?
100.
Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими
из нее ребрами так, чтобы он остался связным.
101.
Сколько ребер нужно удалить из связного графа, имеющего q ребер и p вершин, чтобы
получить дерево, содержащее все вершины этого графа.
102.
Докажите, что полный двудольный граф с n вершинами в одной доле и m вершинами в
другой имеет не менее mn-m-n+1 различных циклов?
Страницы
- « первая
- ‹ предыдущая
- …
- 71
- 72
- 73
- 74
- 75
- …
- следующая ›
- последняя »
