Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Задачи оптимизации на графахСодержание книги
Поиск на нашем сайте
Если дуге ориентированного графа G1 (V, E) поставлено в соответствие некоторое вещественное число a (u, v), называемое весом, то последовательность вершин v 0, v 1,..., vp определяет путь в G1 а его длина определяется как сумма весов: Задача о кратчайшем пути возникает чаще всего при решении транспортных и дискретных задач динамического программирования и др. Длину кратчайшего пути обозначают r (vi, vj) и называют расстоянием от vi до vj (расстояние может быть отрицательным). Для любого орграфа можно построить матрицу расстояний R=r (i, j). Заполняется матрица построчно, выбирая вершину слева (справа). Значением является наименьшее число дуг, связывающее вершину слева с одной из вершин строки. Если не существует ни одного пути из vi в vj, то полагаем r (vi, vj) = ¥. Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v 1,..., vp не будет повторов. Среднее отклонение вершины vi от центра графа D(vi) равно:
где m - число дуг в графе, v - пробегает вершины графа, n – количество вершин графа, i = 1..n. Вершина, для которой D(vi) окажется минимальным, называется центром графа (возможно несколько вершин – центр графа). Путем или маршрутом на графе G1(V,E) называется последовательность его вершин и ребер v1e1v2e2v3…vnen vn+1, в которой любые два соседних элемента инцидентны. Путь называется простым, если все ребра и все вершины на нем, кроме первой и последней, различны. Маршрут называется цепью, если все его ребра различные. Маршрут называется простой цепью, если все его вершины, а значит и ребра, различные. Циклом в графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро. Цикл Если в графенет циклов, то он называется ациклическим. Теперь можно иначе определить понятие дерева. Связный граф без циклов называется деревом. Примеры выполнения заданий
Постройте матрицу расстояний. Вычислите центр орграфа. Решение: построим матрицу расстояний: R= r (i, j):
| ||||||||||||||||||||||||||||||||||||||||||||||
| Общее число дуг m = 8. Рассчитываем отклонения от центра графа: D(1)=7/8; D(2)=D(3)=6/8=3/4; D(4)=10/8=5/4; D(5)=8/8=1. |
. Если в произвольном графе вес каждой дуги равен единице, то длина пути равна числу дуг.
,
называется простым, если в нем нет одинаковых вершин, кроме первой и последней, т.е. если все вершины 
различны.
Итак, центром графа являются вершины 2 и 3.
2. Посёлок построен в виде квадрата 3 квартала на 3 квартала (кварталы - квадраты со стороной b, всего 9 кварталов).Какой наименьший путь должен пройти асфальтоукладчик, чтобы заасфальтировать все улицы, если он начинает и кончает свой путь в угловой точке A? (Стороны квадрата - тоже улицы).
| Решение: Понятно, что длина маршрута асфальтоукладчика не меньше 24, так как он должен проехать по каждой улице хотя бы один раз. Докажем, что по крайней мере по четырём улицам ему придётся проехать по два раза. Ровно на восьми перекрёстках пересекается нечётное число улиц. | 
Рис. 6. Кратчайший путь
|
Следовательно, любой кольцевой маршрут асфальтоукладчика должен проходить по два раза по крайней мере по 8/2 = 4 улицам.Минимальная длина маршрута асфальтоукладчика равна 28; один из возможных маршрутов приведён на рисунке 6.
3. Задайте граф геометрически и решите задачу:
Выбежав после уроков на двор, каждый школьник кинул снежком ровно в одного другого школьника. Докажите, что всех учащихся можно разбить на три команды так, что члены одной команды друг в друга снежками не кидали.
Решение:
Отметим школьников на плоскости точками и соединим стрелочкой, если один кидал во второго. Получившаяся картинка будет выглядеть как несколько циклов с "рожками" (путями, ведущими от точки в цикл). Каждую такую фигуру легко разбить на три группы: разрывая цикл, одного школьника относим в первую группу, а получившиеся деревья разбиваем на четные и нечетные вершины.
Задания для самостоятельного выполнения
Запишите: 1) любой путь, не являющийся цепью; 2) цепь и простую цепь; 3) цикл, простой цикл, если таковые имеются.
|
| Поделиться: |
