Задачи по дискретной математике

mchernega

Вот тут сестре задачки дали, а я чегой-то всё забыла уже...помогите,а? мож кто-нить помнит побольше чем я?
1. Эйлеров замкнутый путь(цикл) (выполняется на бумаге размером А4)
а)Построить конечный связный граф без петель с числом вершин не менее 12, все вершины графа - чётные степени не ниже 4.
б)Построить пошагово эйлеров цикл.
2. Эйлеров путь (выполняется на бумаге размером А4)
а)Построить конечный связный граф без петель с числом вершин не менее 11, все вершины кроме 2 нечётных вершин А и В - чётные степени не ниже 4.
б)Построить пошагово эйлеров путь.
3. Минимальное порождающее дерево
а)В печатном издании (книге/художественной, по истории, по менеджменту и т.д./, журнале или газете) или в интернете отыскивается задача, приводящая к сети, число узлов которой не меньше 10, а каждое ребро сети нагружается определённым числом (от 5 до 15непременно указываются выходные данные источника - автор, название, место и время издания или адрес сайта).
б)Составляется таблица, описывающая выбранные данные.
в)Пошагово строится минимальное порождающее дерево.
г)В ответе приводятся построенный граф (дерево) и указывается сумма длин его рёбер; делаются необходимые выводы.
4. Максимальный поток
а)В печатном издании (книге/художественной, по истории, по менеджменту и т.д./, атласе, журнале или газете) или в интернете отыскивается задача, приводящая к сети, число узлов которой не меньше 10, а каждое ребро сети нагружается определённым числом (от 5 до 15непременно указываются выходные данные источника - автор, название, место и время издания или адрес сайта).
б)Составляется таблица, описывающая выбранные данные, указываются начальный и конечный узлы (источник и сток).
в)Методом разделяющих сечений находится величина максимального потока из начального узла у конечный.
г)Пошагово ищется поток максимальной величины (максимальный поток).
д)В ответе указываются минимальное разделяющее сечение, указываются пропускная способность сети, а также то, каким образом можно пропустить этот максимальный поток через заданную сеть; делаются необходимые выводы.
Я в первой и второй задачке от руки нарисовала картинку,но это максимум моих возможностей,а вот сечения...
Вобщем, буду оч признательна=)

griz_a

) Берем такой граф
Выбираем вершину 1.
Идем как попало, выкидывая ребра по которым проходим, так чтобы при этом граф не распадался на две части, например,
1-3-5-7-9-11-1-2-3-4-5-6-7-8-9-10-11-12. Здесь нельзя идти 12-1, т.к. граф распадется.
Т.ч. 12-2-4-6-8-10-12-1.
Вроде все, цикл построен.

griz_a

)
Чтобы сильно не менять картинку, сделаем так
Две нечетных вершины 12 и 2.
Начинаем из одной из них - например из 2.
Теперь делаем так 2-13-3-11-13-12. Теперь задача сведена к предыдущей - строим на оставшемся графе (таком же, что и раньше) эйлеров цикл. Он заканчивается в 12.
(в том графе он был циклом, а тут уже нет )
В итоге имеем граф:
2-13-3-11-13-12-2-4-6-8-10-12-1-2-3-4-5-6-7-8-9-10-11-1-3-5-7-9-11-12. Вроде так

griz_a

В 3 и 4 найдите задачу, пожалуйста, сами
А решение я, вероятно, расскажу.

mchernega

за первые 2 огромное спасибо!а всё просто
я просто не понимаю какого типа даж задачки искать...как можно в книге по истории найти задачку,приводящую к сети?

griz_a

В любой можно. Вот, например, находишь генеалогическое древо какое-нибудь, или кто кого убил, получаешь граф.

mchernega

ладно,сейчас поищу!
но ты - Гений!

griz_a

Тупанул. Генеалогическое древо - прежде всего дерево %)
Я вот подумал, наверное, схема браков и детей в д-гр мифологии - граф с циклами. Прометей точно имел детей от собственной внучки. Сейчас я еще посмотрю лит-ру по этой теме дискры. У нас ее не было, т.ч. надо поднабраться базовых материалов

griz_a

Подожди пока. Нам же сеть надо, а не просто граф. Тогда это дороги какие-нибудь....

griz_a

http://www.sell-buy.ru/useful/map.htm
Всю карту мне много, т.ч. возьму кусочек. Сейчас разберусь с остовным деревом и запощу

mchernega

класс!да...всего дерева,пожалуй многовато

griz_a


Карта дорог азиатской части россии.

mchernega

Супер=)

griz_a

Теперь делаем веса от 5 - до 15.
Будем считать, что в каждом городе мы стоим в течение 5 часов.
Далее мы едем со скоростью 80 км в час.
Весом ребра будем называть время стояния в вершине+время, затраченное на дорогу, округленное до целого числа единиц.
Имеем граф

griz_a

Покатились
Нам надо поставить дерево с вершинами в наших 16 точках.
Берем наикратчайшее ребра и добавляем их к дереву, если не получится цикла:
14-15
3-4
1-3
1-2
2-5
14-17
15-16
7-8
7-13
7-10
8-9
11-12
10-12
5-6
6-7
5-14
Готово

Пропустил тут одно ребро, но у него длина большая - 10

griz_a

Плохо только, что это не совсем нагрузка. То есть под эту-то задачу это подходит, а вот под вторую
Пусть нам надо проехать из 1 в 12. (Челябинск - Красноярск)
При этом мы не нагружаем дорогу свыше чем машина в час. Сколько машин максимум способна вместить наша сеть.
Не вполне, конечно, но как никак.
алгоритм - берем произвольный путь из 1 в 12 (простой путь). Например,
1-3-5-6-7-10-12
Грузим эту дорогу, пока не достигнем предела на одном из участков.
Т.е. пускаем по ней 7 машин.
Подписываем нагрузку на сеть от синего маршрута синими цифрами

Теперь первое звено (1-3) нагружено до предела. (синяя цифра совпадает с красной)
Значит надо нагружать через другие звенья
Например, берем маршрут 1-2-5-6-7-9-10-11-12.
Нагружаем его до предела
Этот предел 6 - до насыщения звена 5-6.

Теперь на каждом из ребер сумма голубого и синего чисел не больше красного числа.
При этом ребро 5-6 нагружено полностью (т.е. сумма голубого и синего чисел равна красному) и других маршрутов, не проходящих через полностью нагруженные ребра не имеется.
Получаем, что максимальная загрузка равна 13=7+6.

griz_a

Черт, это алгоритм Форда-Фалкерсона, а не разделяющих сечений
не, видимо, искать его максимальный поток так и надо. Но можно найти величину потока с помощью минимального сечения

griz_a

есть теорема, что величина мощности потока совпадает с пропускной способностью минимального сечения.
Что такое сечение - разбиение всех вершин на две группы, непересекающихся, в объединении дающих все и таких, что источник в первой группе, сток во второй.
Пропускная способность сечения - сумма значений на ребрах графа, соединяющих вершины из разных групп.
Минимальное - с минимальной пропускной способностью.
Покажем, что минимальное сечение имеет пропуск. сп-ть 13.
Во-первых, можно поделить вершины на группы 1-5 + 14-17 и все остальное.
Тогда есть всего одно ребро, соединяющее вершины разных групп и у него способность 13.
С другой стороны, пусть есть сечение с пропускной способностью меньше 13.
Но, если в нем хотя бы 2 ребра, то т.к. все наши ребра не меньше 6, то это 6 и 6 (иначе не менее 13). Но с 6 всего одно ребро.
Следовательно есть лишь одно ребро с концами из разных групп.
Т.е. после его удаления граф распадается на две части (несвязных одна из которых содержит 1, другая 12.
Тогда путь 1-2-5-6-7-10-12 и путь
1-3-5-6-7-13-10-11-12 распадутся на две части при удалении этого ребра, т.е это ребро принадлежит обоим графам.
Значит эти либо 5-6, либо 6-7. У обоих пропускная способность не менее 13.
Т.е. минимальное сечением имеет пропускную способность 13, т.е. такова же и величина максимального потока.

mchernega

и ведь как прекрасно, что после мехмата хоть кто-то что-то помнит! и не только помнит,а дпже применять может!
вобщем огроменный тебе RESPECT!

griz_a

Не за что. Я еще не после мехмата

mchernega

Слушай,и всё-таки я поняла совсем не всё...
Берем наикратчайшее ребра и добавляем их к дереву,если не получится цикла

как это понимать?
При этом мы не нагружаем дорогу свыше чем мащина в час

почему?при чём тут машины-то? я запуталась чё-то
и почему если звено 1-3 нагружено до предела,мы должны нагружать через другие звенья?
Почему мы берём маршрут 1-2-5-6-7-9-10-11-12,а не какой-нибудь другой?

mchernega

тем более

griz_a

У нас на каждом ребре есть число. В третьей задаче оно интерпретируется просто как число километров. Тогда мы каждый раз берем одно из ребер графа с самым маленьким числом на нем. (т.е. самый короткий участок дороги) и добавляем его к уже имеющемуся графу, если не получается цикла при добавлении нашего ребра и не добавляем, если получается
В четвертой задаче число - это насыщенность участка дороги. Для нахождения потока нам нужна задача, где вес у ребра - максимальное количество раз, которое оно может участвовать в наших маршрутах. Поэтому я использую модель - по каждому участку дороги выпускаются машины так, чтобы их число не превышало вес ребра. Соответственно, если мы нагрузим ребро до веса (т.е. через него будут идти столько путей, сколько его вес то нам его больше нельзя использовать. И мы берем любой маршрут, у которого есть не полностью нагруженное ребро из начала в конец (из 1 в 12). Я взял тот, который ты написала. Можно было и другой. Ответ получился тот же самый, а вот маршрут загрузки - другой. Но надо найти любой

mchernega

я поняла уже,что я не понимаю пока что первую фразу:
Нам надо поставить дерево с вершинами в наших 16 точках.

Как мы из графа делаем дерево?
P.S.да, туплю,знаю....

griz_a

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

mchernega

Потом,вот когда мы рёбра к дереву добавляем, так не одного ребра в списке не хватает,а трёх(2-7(кстати,это важно в каком порядке вершины идут? 2-5 и 7-9(как раз у которого длина = 10...почему?

griz_a

Я же исправил вроде в дальнейшем. На итог это не повлияло. Два я не переписал в первый раз, а третье прошляпили на карте, но я нашел в другом месте.

mchernega

ещё я вот сижу и думаю,как бы это теперь разбить на 2 задачи=)
а так я вроде всё поняла наконец-то

griz_a

почему на две задачи?

mchernega

разобралась
слушай, а когда мы вот строим это минимальное порождающее дерево, его нарисовать реально или это тока в виде списка рёбер может быть?

mchernega

потому что были - задача 3 и задача 4=)
первые я дааавно поняла

griz_a

А у меня оно на картинке выделено синими черточками...

griz_a

Так там же две задачи отдельно написаны?

mchernega

я просто копировала всё в файл, поэтому у меня всё было слитным текстом
значит,всё что синими чёрточками выделено-это и есть вот енто минимальное порождающее дерево?

griz_a

В первой из задач да. Во второй - первый путь для максимального потока.

mchernega

3. г)В ответе приводятся построенный граф (дерево) и указывается сумма длин его рёбер; делаются необходимые выводы.

вот ещё для меня загадка - зачем указывать сумму длин рёбер, по рисунку же можно сосчитать...?
и что за загадочная фраза "делаются необходимые выводы"?...
д)В ответе указываются минимальное разделяющее сечение, указываются пропускная способность сети, а также то, каким образом можно пропустить этот максимальный поток через заданную сеть; делаются необходимые выводы.

а как тут ответ записать?у меня ваще мозги не варят сегодня
и опять эти "необходимые выводы"...

mchernega

Во второй - первый путь для максимального потока.

Это я поняла=)не настока уж одурела
просто я думала,что в первой задаче ты просто отметил рёбра,которые создают это чудо-деревоа то,что они все вместе-это минимальное дерево,до меня не дошло

griz_a

в г. Видимо, надо посчитать сумму и сделать вывод - минимальная подсеть имеющихся дорог, по которой можно проехать из каждого города в каждый составляет ---- единиц.
в д. Минимальное сечение я указал в одном из постов. Пропускная способность = величине макс. потока, а то, каким образом можно пропустить - это сине-зеленая картинка
Ну а выводы таковы - наша сеть автодорог при указанных правилах позволяет одновременно везти 13 машин.

mchernega

Минимальное сечение я указал в одном из постов
То есть оно состоит из 2 путей?
1-3-5-6-7-10-12 и 1-2-5-6-7-9-10-11-12 ?так?

griz_a

Не,не - это схема, реализующая поток - 7 раз взятый путь 1 и 6 раз взятый путь 2.

griz_a

Во-первых, можно поделить вершины на группы 1-5 + 14-17 и все остальное.

Вот минимальное сечение и есть разбиение множества вершин на группы 1,2,3,4,5,14,15,16,17 - первая, все остальное - вторая.

mchernega

ну наконец-то)
осталось теперь это донести до сестры
СПАСИБО!
Оставить комментарий
Имя или ник:
Комментарий: