Разделы
Главная Сапромат Моделирование Взаимодействие Методы Инновации Индукция Исследования Факторизация Частоты
Популярное
Как составляется проект слаботочных сетей? Как защитить объект? Слаботочные системы в проекте «Умный дом» Какой дом надежнее: каркасный или брусовой? Как правильно создавать слаботочные системы? Что такое энергоэффективные дома?
Главная »  Математика 

1 ... 22 23 24 25 26 27 28

163. Найти хроматическое число л-вершинного дерева, л > 1.

164. Доказать, что в компании из 6 человек всегда найдутся либо трое знакомых друг с другом, либо трое друг с другом не знакомых.

165. Доказать, что при любой раскраске ребер полного 6-графа в два цвета найдется монохроматический 3-граф.

166. Рассмотрим граф Мп Муна-Мозерас Зл вершинами {1,2, Зл}, в котором вершины разбиты на триады {1, 2, 3}, {4, 5, 6}, ...,{3л - 2, Зл - 1, Зл}; М„не имеет ребер внутри любой триады, но вне их каждая вершина связана с каждой из остальных. Докажите (по индукции), что Мп имеет 3 клик.

167. Показать, что в графе с л вершинами ж с к компонентами связности число ребер не более ((л - к){п - к+ 1))/2.

168. Докажите, что если в графе все вершины имеют четные степени, то в этом графе нет мостов. Указание: допустить, что существует мост; удалить это ребро-мост и показать, что полученный граф будет противоречить условию задачи.

169. Разобьем плоскость на конечное число частей прямыми линиями. Докажите, что полученная карта имеет хроматическое число равное двум. Указание: для доказательства воспользуйтесь индукцией по числу прямых.

170. Для каждого графа а) и б) найти остовное дерево, используя программную реализацию жадного алгоритма (алгоритм 6.7) п алгоритма ближайшего соседа (алгоритм 6.9). На каждом шаге алгоритмов отобразить состояние используемых структур данных.

20 х2 х] 7


171. Найти кратчайшие пути от вершины х0 до всех остальных вершин ориентированного графа (см. рис. на следующей странице).




172. Пусть /Г И'/!/]. ,7 = 1,л обозначает А-ю степень матрицы

смежности орграфа. Доказать, что элемент данной матрицы

равен количеству маршрутов длины к из вершины хг Указание: при доказательстве воспользоваться индукцией по числу к.

173. Выполнить хроматическое разложение графа. Найти все клики, фундаментальное множество циклов, листы, блоки и мосты. Определить центры, радиус и диаметр графа.


174. Сколь много ребер может иметь -вершинный граф, у которого степень всякой вершины не превосходит о?

175. Показать, что в дереве с нечетным диаметром любые две простые цепи наибольшей длины имеют хотя бы одно общее ребро.

176. Пусть корневое дерево с п (п 2) висячими вершинами не имеет вершин степени 2, отличных от корня. Показать, что общее число вершин дерева не превосходит 2л - 1.

177. Доказать, что дерево обладает единственным центром в случае, когда его диаметр есть число четное, и обладает двумя центрами, когда диаметр есть нечетное число.

178. Доказать, что в любом дереве с п 2 вершинами имеется не менее двух висячих вершин.

179. Вершины графа Г пронумерованы в порядке возрастания их степеней. Доказать, что если к - наибольшее число, такое, что k < d(xk\ + 1, то х(Г) к, где d(xk. - степень вершины

180. Доказать, что если для любыгх двух вершин х и у связного л-вершинного графа выполняется d(x) + d(y) > п, то граф имеет



181. Используя алгоритм чередующихся цепей (см. п.6.14.3), расширить заданное начальное паросочетание в двудольном графе Г- (Vi и V2, U, Ф)до максимального паросочетания, где Vx = {sy, s2, St s4, s5, s6}h V2 = {1,2, 3, 4, 5, 6}, смежные вершины в графе: 5j - {1,2, 3}, s2 - {1, 2}, s3 - {1,2}, s4 - [1,2, 3, 4}, s5 - {1,2, 4, 5}, s6 - {1, 2, 3, 5, 6} и начальное паросочетание n = {(sl51), (s2, 2), (j4, 3), (j5> 4), (s6, 5)}.

182. Используя алгоритм чередующихся цепей (см. п.6.14.3), расширить заданное начальное паросочетание в двудольном графе Г= (Fj u F2, С/, до максимального паросочетания, где = {j, s2, 54) %, s6, s-j} и = U>2, 3,4,5,6, 7};смежные вершины в графе:- {1,2}, sj- {2,5, 6},53- {5},j4- {1,2, 5}, s5- {3,4, 5,6}, s6 - {4, 5, 7}, 57- {5, 6}, и начальное паросочетание я= {(jj, 1), (s2,2), (j3, 5), (ss, 3), (д6, 7), (j7, 6)}.

183. Перераспределить заданный начальный поток по транспортной сети а), б) и в) так, чтобы он стал максимальным, а сеть - насыщенной. п.6.10). Найти все разрезы транспортной сети и их мощности, сравнить мощность минимального разреза с найденным максимальным потоком.





184. Решить задачи о назначениях максимального выбора

185. Решить задачи о назначениях минимального выбора

9-2697



186. Фирма по перевозке грузов должна забрать пять контейнеров в пунктах района края А, В, С, D, Еп доставить их в пункты а, Ь, с, d, e. Расстояния в километрах между пунктами загрузки и пунктами назначения контейнеров приведены ниже:

А-а

В-Ь

С-с

Е-е

Фирма располагает пятью грузовиками двух типов Ли Уна стоянках Т, U,V, W. Три грузовика типа ЛГнаходятся на автостоянках U, Кидва грузовика типа Унаходятся на автостоянках Т, W. Стоимость пробега одного километра для грузовиков типа Y, включая горючее, страховку и т.д., приведена ниже:

Гружёный

Расстояния от стоянки грузовиков до места назначения приведены ниже:

Стоянки

Расстояние

А

В

С

Е

Т

и

Определить распределение контейнеров по грузовикам, минимизирующее общую стоимость перевозок. 187. Ежедневно авиалиния, которая принадлежит некоторой компании, осуществляет следующие перелеты между городами и В:

Отправление

Прибытие

Отправление

Прибытие

из города А

в город В

из города В

в город А

9.00

11.00

8.00

10.00

10.00

12.00

9.00

11.00

15.00

17. 00

14.00

16.00

19.00

21.00

20.00

22.00

20.00

22.00

21.00

23.00



Вылет

Прибытие

Город

Город

А

8.00

В

12.00

А

9.00

с

12.00

А

10.00

в

14.00

А

14.00

в

18.00

А

18.00

в

22.00

А

20.00

с

23.00

В

7.00

А

11.00

В

9.00

А

13.00

В

13.00

А

17.00

В

18.00

А

22.00

С

9.00

А

12.00

С

15.00

А

18.00

Как следует распределить самолеты по линиям для минимизации стоимости простоя в каждом из городов? Следует учесть, что самолет не может подняться менее чем через 1 час после приземления, так как требуется время на технический контроль и заправку.

Теория групп и приложения

189. Показать, что Gx = {л \ л е Z) - группа с операцией сложения чисел, где Z- множество целых чисел; G2 = {2л л е Z) - группа с операцией сложения чисел; G3 = {2 \ п е Z) - группа с операцией умножения чисел; С4 - множество квадратных матриц порядка л, определитель которых не равен нулю, является группой с операцией умножения матриц; - множество ортогональных матриц порядка п является группой с операцией умножения матриц; = - группа с операцией умножения чисел; - множество рациональных чисел является группой относительно операций сложения и умножения (без нуля); - множество вещественных чисел является группой относительно операций сложения и умножения (без нуля). Установить, какие из групп являются подгруппами других групп.

Компания хочет организовать полеты туда и обратно так, чтобы минимизировать время простоя при условии, что каждому самолету требуется 1 час для дозаправки.

188. Авиалиния связывает три города А, В, С. Полеты происходят семь дней в неделю согласно расписанию:



190. Пусть М - подмножество группы Gu Уа,Ъ еМвыполняется abA е М. Показать, что М- подгруппа.

191. Пусть G2 - группы и отображение/: Gy -> G2 - гомоморфизм. Показать, что ядро и образ гомоморфизма являются подгруппами.

192. Пусть = {х е iiT} и G2 = {х е R), где R - положительные вещественные числа, R - вещественные числа. Показать, что Gx - группа с операцией умножения, G2 - группа с операцией сложения. Рассмотрим отображение ф :(?,-> G2 такое, что Ух е Gi ф) = ln(x) е G2. Показать, что ф - изоморфизм групп.

193. Пусть G- группа и г е G- фиксированный элемент. Определим отображение ф : G- Gформулой Vg е Gq>(g)= r~lgr. Докажите, что ф - изоморфизм группы на себя.

194. Докажите, что если порядок группы: G равен 2л и Н - подгруппа порядка группы: G, то Н - ее нормальный делитель.

195. Доказать, что если в квадратной матрице порядка л содержится нулевая подматрица размера г х s иг + s > л, то определитель матрицы: равен нулю.

196. Найти порядок группы, порожденной подстановкой ( 1 2 3 4 5)

(2 3 4 5 1/

197. Разложить подстановки 2 4 7 5 6 {1) и (i 6 2 4 3 5) в произведение независимых циклов и в произведение транспозиций, определить их четность.

198. Пусть Не $4, где 54 - симметрическая группа. Будет ли Н

подгруппой в следующих случаях:

я н Ш 3 4\ (12 3 4\ (12 3 4\ (12 3 4 М. d}n~\{i2 3 4){21 4 3>34 1 2>U3 2 1 J}

VJ1-\{U3 4){2 3 1 4>U 1 2 4j(24 1 Щ

199. Пусть G- циклическая группа, \G\=m. Показать, что число образующих группы равно ф(/и) - функция Эйлера.

200. Пусть G - циклическая группа. Показать, что элементы группы одинакового порядка являются образующими одной и той же подгруппы G.

Пусть G - группа порядка - простое число. Пока-

зать, что G - циклическая группа.

202. Показать, что циклическая группа - коммутативна.



203. Пусть G - группа. Показать, что для всякого g е G найдется такое целое k, что g = e.

204. Показать, что число образующих циклической группы G= {g,

равно значению функции Эйлера ср(л) - количество чисел из множества {1, 2,..., п - 1} взаимно простьк с и.

205. Пусть G - конечная абелева группа порядка \G\ =/> р\г...

р^к, тдерьр2,..-,Рк- простые различные числа; множествоА(р) =

= {л е G \ \ x =р11}, где принимает произвольнге цел^1е значения. Показать, что А{р) - подгруппа.

206. Пусть Grj, G2, - коммутативные группы порядков \GX \ = 56, \G2 \ = 64. Найти количество возможныхпрямькразложений каждой из групп на циклические подгруппы.

207. Определить множество левых и правых смежных классов симметрической группы S3 по подгруппе Н, где Н- циклическая подгруппа с образующим элементом [\ \ 3]. Доказать что Н-

нормальный делитель.

208. Найти цикловой индекс группы самосовмещений (автоморфизмов), действующей на множестве а), б), в), г). Отдельно рассмотреть случаи действия группы на плоскости и в пространстве.

209. Применить теорему Пойа для определения количества возможных раскрасок двумя и тремя красками вершин графов а), б), в), г) предыдущей задачи.

210. Используя теорему Пойа, найти количество различных ожерелий, которые можно составить из четырех бусинок пяти цветов. Рассмотреть отдельно варианты, когда группа самосовмещений

(автоморфизмов) действует на плоскости и в пространстве.

211. Задача о стоянке. На некоторой улице с односторонним дви жением имеется п мест для стоянки автомобилей, расположенных в ряд и перенумерованных от 1 до т. Муж везет в автомобиле


Алгоритмы и графы



жену. Внезапно жена просыпается и требует остановиться. Он послушно останавливается на первом свободном месте. Если нет свободных мест, к которым можно подъехать, не поворачивая обратно (т.е. если жена проснулась, когда машина достигла места для стоянки, но все позиции k, к+ 1,.... т заняты), то муж приносит свои извинения и едет дальше.

Предположим, что это происходит с я различными машинами, жена просыпается в момент, когда машина находится перед местом ау Сколько имеется таких последовательностей аь аъ...,ат при которых все машины удачно припаркуются, предполагается, что первоначально улица пуста и никто со стоянки не уезжает? Составить алгоритм-программу вычисления всех воз-

расположения автомобилей. Исходные данные - т, п. Например, если и = й = 9и (а а2,..., ап) = (3, 1, 4, 1, 5, 9, 2, б, 5), то автомобили расположатся следующим образом: 2, 4, 1, 3, 5, 7, 8, 9, 6. 212. Фальшивая монета. Банк Золотой Ящик получил информацию, что в последней партии из п монет ровно одна монета фальшивая и отличается от других монет по весу. Для определения фальшивой монеты кассиру выдали только аптечные весы без гирь. Первым шагом кассир перенумеровал все монеты от 1 до п. Таким образом, каждая монета получила уникальный номер - целое число. После этого он начал взвешивать различные группы монет по составу, отмечая, какие из них больше, меньше или равны.

Ваша задача - написать которая по ре-

зультатам взвешиваний, выполненных кассиром, определит фальшивую монету или определит, что этого нельзя сделать.

Текстовый файл входных данных содержит следующую информацию.

Первая строка файла содержит два целых числа п и k, разделенных пробелами, где я - число монет в партии (п > 2) и к - число взвешиваний, выполненных кассиром. Следующие 2к строк файла описывают результаты взвешивания. Каждое взвешивание представляется двумя строками файла.

Первая из них начинается числом/>, (1 < < я/2), которое обозначает число монет, участвовавших при взвешивании на каждой чашке весов. Следующие чисел на этой же строке файла являются номерами монет, которые располагались на левой чашке весов, и чисел на же строке файла являются номерами монет, которые располагались на правой чашке весов.



Вторая строка содержит один из знаков: <, > или =.

Знак < означает, что вес левой чашки меньше веса правой чашки весов.

Знак > означает, что вес левой чашки больше веса правой чашки весов.

Знак = означает, что вес левой чашки равен весу правой чашки весов.

Ниже приведен пример файла входных данных.

Результаты определения номера фальшивой монеты сохранить в текстовом файле. Если по выполненным взвешиваниям нельзя выявить фальшивую монету, то в качестве результата сохранить 0. Ниже приведен пример файла результатов.

ИСХОДНЫХ ДАННЫХ

ИСХОДНЫХ ДАННЫХ

5 3

б

2 1

2 3 4

4 5 6

<

<

1 1

1 2

<

РЕЗУЛЬТАТОВ

>

РЕЗУЛЬТАТОВ

О

213. Грядки. Садовый участок, имеющий прямоугольную форму и разбитый на квадратные клетки со стороной 1 метр, имеет ширину п и длину т метров. На этом участке вскопаны грядки. Грядкой называется совокупность клеток, удовлетворяющих условиям:

из любой клетки этой грядки можно попасть в любую другую клетку же грядки, последовательно переходя по грядке из клетки в клетку через их общую сторону;

никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам клеток (касание грядок по углам клеток

Составьте расчета количества грядок на

садовом

Исходные данные задаются в текстовом файле. В первой строке располагаются два числа: п и т, разделенные одним или несколькими пробелами. Далее следуют п строк по т символов. Символ





1 ... 22 23 24 25 26 27 28