Теория графов транспортная задача

Теория графов транспортная задача

На этой странице вы найдете готовые примеры по теории графов (разделу дискретной математики). Теория графов берет свое начало еще в 18 веке, когда Эйлер написал свою знаменитую статью о Кёнигсберских мостах (см. решения на алгоритм Эйлера). Сейчас достижения теории графов применяются в строительстве, программировании, электротехнике, социологии, экономике, биохимии, телекоммуникациях и планировании транспортных коммуникаций, психологии и т.д.

Какие виды заданий решаются студентами?

Задачи, решаемые в рамках теории графов, можно условно поделить на несколько групп:

  • Определение графа и его свойства. Задачи на построение графа по заданному числу вершин и ребер, построение матрицы смежности и инцидентности, вычисление основных характеристик графа (связность, простота, эйлеровость, полнота, двудольность, регулярность графа и т.п.). Проверка планарности и изоморфности графов.
  • Действия с графами. Добавление и удаление вершин и ребер, компонент связности, слияние вершин, объединение, пересечение, соединение и декартово произведение графов. Построение дополнение графа.
  • Маршруты, цепи и циклы, контуры. Эйлерова цепь и гамильтонов цикл и проверка графа на выполнение этих свойств.
  • Вычисление характеристик графа. Расстояния: диаметр графа, центр графа, радиус графа. Вычисление цикломатического и хроматического числа.
  • Задачи на графах. Задача о кратчайшем пути (алгоритм Дейкстры, Беллмана, построение дерева путей). Задача на построение минимального остовного дерева (алгоритм Краскала). Задача о максимальном потоке в сети (алгоритм Форда-Фолкерсона). Задача о раскраске графа.
  • Изучение деревьев (специальных видов графов без циклов). Деревья применяются в шифровании, программировании и многих других прикладных областях.

Задачи по графам с решением онлайн

Задача 1. Постройте граф отношения "x+y ≤7" на множестве М=<1,2,3,4,5,6>. Определите его свойства.

Задача 2. Найти кратчайшие пути в орграфе от первой вершины ко всем остальным, используя алгоритм Дейкстры. Постройте дерево кратчайших путей.

Задача 3. Найти максимальный поток и минимальный разрез в транспортной сети, используя алгоритм Форда–Фалкерсона (алгоритм расстановки пометок) Построить граф приращений. Проверить выполнение условия максимальности построенного полного потока. Источник – вершина 1, сток – вершина 8.

Задача 4. Постройте остовное дерево минимального веса, используя алгоритмы Прима и Краскала. С помощью матрицы Кирхгоффа найдите количество (неизоморфных) остовных деревьев, используя пакеты компьютерной математики (например, MathCAD, Mathematica, MatLab).

Задача 5. Требуется составить структурную матрицу для данного орграфа (или графа) и, методами булевой алгебры, найти все пути $P_$ из вершины $i$ в вершину $j$, затем найти все сечения $S_$ между этими вершинами. В данном задании (чтобы исключить возможные неясности графического рисунка) указываются все ориентированные ребра, причем запись (2–4) означает, что 2 вершина связана с 4-й, а обратной связи нет. Напомним, что для нахождения путей из вершины $i$ в вершину $j$ нужно раскрывать минор структурной матрицы$М_$ (вычеркивать из структурной матрицы строчку с номером $j$ и столбец с номером $i$). Сечения же находятся отрицанием путей (конъюнкция меняется на дизъюнкцию и наоборот).

Задача 6. Для графа $G=(X,U)$ выполнить следующее:
1.1. Построить:
— матрицу смежности,
— матрицу инцидентности.
1.2. Определить степени для всех вершин $$ данного графа.

Задача 7. Найти все кратчайшие пути в орграфе, используя алгоритм Флойда.

Задача 8. Задан $G (X,ГX)$
$X=$,
ГХ:
Гx1=, Гx2=, Гx3=, Гx4=, Гx5=.
Определить хроматическое и цикломатическое число данного графа.

Задача 9. Считая данный граф неориентированным, обозначить его вершины и рёбра разными символами и определить.
3.1. Локальные степени и окружения каждой вершины в виде структуры смежности;
3.2. Построить матрицы инцидентности и смежности;
3.3. Рассмотреть части графа. Привести примеры суграфа, накрывающего суграфа. Показать подграф, состоящий из трёх вершин. Сколько таких подграфов можно найти в данном графе? Показать примеры пересечения и объединения частей графа;
3.4. Привести примеры циклического маршрута, цепи, простой цепи. Попытаться найти Эйлеров цикл;
3.5. Определить центр, диаметр и радиус графа.
Считая граф ориентированным, определить
3.6. Степени вершин
3.7. Матрицы инцидентности и смежности.
3.8. Привести примеры пути, ориентированной цепи, простой цепи, контура, цикла и простого цикла.

Решение теории графов на заказ

Выполняем решение задач, контрольных и практических работ по любым разделам теории графов. Подробное оформление, таблицы, чертежи, пояснение, возможно написание программ на языках программирования (для алгоритмов на графах) или использование специальных программ. Решение экономических задач, связанных с теорией графов.

Стоимость примера от 100 рублей , оформление производится в Word, срок от 2 дней. Также оказываем помощь в сдаче тестов по графам.

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

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

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

Пример 3.5 – Решить транспортную задачу, заданную на рисунке 3.7.

Рисунок 3.7 – Постановка транспортной задачи в виде графа

Здесь имеется шесть пунктов. Они обозначены вершинами графа (их номера – от 1 до 6). Для каждого пункта указаны запасы груза (положительные числа) или потребности в нем (отрицательные). Видно, что пункты 1, 2 и 3 — поставщики; в пункте 1 имеется 60 единиц груза, в пункте 2 – 20, в пункте 3 – 50 (всего имеется 60+20+50 = 130 единиц груза). Пункты 4, 5 и 6 – потребители; пункту 4 требуется 60 единиц груза, пункту 5 – 30, пункту 6 – 40 единиц груза (всего требуется 60+30+40 = 130 единиц груза). Ребрами графа обозначены дороги, соединяющие пункты. Для каждой дороги указана цена перевозки единицы груза; например, чтобы перевезти одну единицу груза из пункта 1 в пункт 2 (или, наоборот, из пункта 2 в пункт 1), требуется израсходовать две денежные единицы. Перевозка одной единицы груза из пункта 1 в пункт 6 (или наоборот) требует затрат в размере трех денежных единиц, и т.д.

Примечание – Незаполненные места в обозначениях вершин и ребер будут заполняться вспомогательными величинами по ходу решения задачи.

Решение задачи включает два основных этапа. Сначала необходимо составить исходный (опорный) план перевозок. Он составляется произвольным образом без учета цен. Единственное требование к нему – обеспечение всех необходимых перевозок (т.е. все потребители должны получить необходимое количество груза). Такой план называется допустимым. Затем на его основе определяется оптимальный план, при котором перевозки выполняются с минимальными затратами.

Читайте также:  Программа для работы с html кодом

Пример допустимого плана приведен на рисунке 3.8.

Рисунок 3.8 – Допустимый план перевозок

Предложенный план перевозок означает, что следует перевезти 60 единиц груза из пункта 1 в пункт 6, 20 единиц – из пункта 2 в пункт 6, 40 единиц – из пункта 6 в пункт 5, 10 единиц – из пункта 5 в пункт 4, 50 единиц – из пункта 3 в пункт 4. Видно, что все потребители при этом получат необходимое количество груза: пункт 4 – 60 единиц (10+50), пункт 5 – 30 единиц (ввезено 40 единиц, вывезено 10), пункт 6 – 40 единиц (ввезено 60+20 = 80 единиц, вывезено 40). При этом от поставщиков вывозится весь груз (так как количество груза, необходимого для потребителей, равно его запасам).

Затраты на перевозки составят E = 360 + 420 + 240 + 610 + 350 = = 550 ден.ед.

Следует еще раз обратить внимание, что этот план перевозок составлен произвольным образом. Можно было составить и много других вариантов допустимого плана.

Примечание – Количество ребер графа со стрелками, т.е. ребер, где указаны перевозки (такие ребра называют нагруженными), должно быть ровно на единицу меньше количества вершин. В данном случае это требование выполняется (количество вершин – 6, запланировано 5 перевозок). В некоторых случаях количество нагруженных ребер оказывается меньше необходимого; в этом случае на граф произвольным образом добавляется необходимое количество стрелок, а соответствующие перевозки считаются равными нулю. При этом стрелки на графе нигде не должны образовывать замкнутый контур.

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

1 Для каждой вершины вычисляется вспомогательная величина, называемая потенциалом. Для этого одной из вершин (обычно – вершине 1) присваивается потенциал, равный нулю: U1 = 0. Потенциалы остальных вершин определяют, перемещаясь по нагруженным ребрам графа от вершин, для которых потенциалы уже найдены, к вершинам, для которых потенциалы требуется найти. Пусть для некоторой (i-й) вершины потенциал уже известен и равен Ui, а для некоторой другой (j-й) вершины потенциал требуется найти. При этом i-я и j-я вершины соединены нагруженным ребром (т.е. запланирована перевозка из i-го пункта в j-й или наоборот), и цена перевозки между этими пунктами равна Cij. Тогда потенциал j-й вершины (Uj) вычисляются по формуле: Uj = Ui + Cij, если переход из i-й вершины в j-ю выполняется в направлении стрелки, или по формуле Uj = UiCij, если переход из i-й вершины в j-ю выполняется в направлении, противоположном стрелке.

Рассмотрим определение потенциалов для данного примера. Присвоим вершине с номером 1 потенциал, равный нулю: U1 = 0. Теперь можно найти потенциал вершины 6, перемещаясь в нее по стрелке из вершины 1: U6 = U1 + C16 = 0 + 3 = 3. Зная потенциал вершины 6, можно найти потенциалы вершин 2 и 5: U2 = U6C62 = 3 – 4 = -1 (здесь выполняется вычитание, а не сложение, так как переход из вершины 6 в вершину 2 выполняется против стрелки; U5 = U6 + C65 = 3 + 2 = 5. Зная потенциал вершины 5, можно найти потенциал вершины 4: U4 = U5 + C54 = 5 + 6 = 11. Наконец, зная потенциал вершины 4, можно найти потенциал вершины 3: U3 = U4C43 = 11 – 3 = 8. Таким образом, все потенциалы найдены. Их удобно записать в вершинах графа (см. рисунок 3.9).

2 Для каждого ненагруженного ребра вычисляется вспомогательная величина, называемая оценкой, по следующей формуле: dij = Cij – UiUj. Здесь i и j – номера вершин, соединяемых ребром; Ui и Uj – их потенциалы; Cij – цена перевозки между i-м и j-м пунктами.

Найдем оценки ребер для рассматриваемого примера:

Оценки ребер удобно записать на ребрах графа (см. рисунок 3.9).

Если все оценки ребер оказываются положительными, значит, текущий план перевозок – оптимальный. В данном случае есть отрицательные оценки, значит, оптимальное решение еще не найдено.

3 Выбирается ребро с максимальной по модулю отрицательной оценкой. Это ребро соответствует новой перевозке, включаемой в план. В данном примере это ребро (1, 3). На этом ребре указывается стрелка от вершины с меньшим потенциалом к вершине с большим потенциалом. В данном примере U1 = 0, U3 = 8, поэтому стрелка направлена от вершины 1 к вершине 3. На рисунке 3.9 эта стрелка показана пунктиром. Таким образом, будет выполняться перевозка из пункта 1 в пункт 3.

Рисунок 3.9 – Поиск оптимального плана перевозок: промежуточные расчеты и определение новой перевозки

4 Определяется величина изменения перевозок (обозначим ее как X). Для этого в графе перевозок (с новой перевозкой) находится замкнутый контур из стрелок, причем стрелки в контуре могут иметь разное направление. Такой контур всегда образуется при указании новой стрелки (на шаге 3), причем только один. Из рисунка 3.9 видно, что в данном примере это контур 1-3-4-5-6-1. В этом контуре находится минимальная перевозка в направлении, противоположном новой стрелке. Из рисунка 3.9 видно, что в данном примере новой стреле противоположны перевозки 1-6 (эта перевозка составляет 30 единиц груза), 6-5 (40 единиц) и 5-4 (10 единиц). Выбирается минимальная из них: X=10.

5 Составляется новый план перевозок. Все перевозки в контуре по направлению новой стрелки увеличиваются на величину X (в данном примере это означает, что перевозки 1-3 и 3-4 увеличиваются на 10). Все перевозки в направлении, противоположном новой стрелке, уменьшаются на X (в данном примере перевозки 1-6, 6-5 и 5-4 уменьшаются на 10). При этом найденная на шаге 4 минимальная перевозка (в данном примере – перевозка 5-4) становится равной нулю. Стрелка с нее снимается. Это означает, что данная перевозка выполняться не будет. Новый план перевозок для рассматриваемого примера приведен на рисунке 3.10. Затраты на новый план перевозок составят E = 350 + 420 + 230 + 360 + 110 = 480 ден.ед.

Примечание – При выполнении шага 5 может оказаться, что несколько перевозок станут равными нулю. Это происходит, если на шаге 4 минимальное значение (обозначенное как X) имели несколько перевозок. В этом случае стрелка снимается только из перевозок, ставших равными нулю (с любой). Остальные стрелки на графе сохраняются, но перевозки для них становятся равными нулю.

Рисунок 3.10 – Новый план перевозок

Для нового плана перевозок повторяются те же действия, что и для исходного, начиная с шага 1.

Читайте также:  Чем открыть файл mif

1 Для всех вершин вычисляются потенциалы. Принимаем U1 = 0. Зная U1, можно вычислить потенциалы вершин 6 и 3 (т.е. тех вершин, с которыми вершина 1 соединена нагруженными стрелками): U6 = U1 + C16 = 0 + 3 = 3, U3 = U1 + C13 = 0 + 1 = 1. Зная потенциал вершины 6, можно найти потенциалы вершин 2 и 5: U2 = U6C62 = 3 – 4 = -1, U5 = U6 + C65 = 3 + 2 = 5. Зная потенциал вершины 3, можно найти потенциал вершины 4: U4 = U3 + C34 = 1 + 3 = 4. Потенциалы показаны на рисунке 3.11 в вершинах графа.

2 Для всех ненагруженных ребер вычисляются оценки:

Оценки ребер показаны на рисунке 3.11.

Рисунок 3.11 – Проверка плана перевозок на оптимальность

Так как все оценки ребер неотрицательны, найденный план – оптимальный. Этот план состоит в следующем: следует перевезти 50 единиц груза из пункта 1 в пункт 6, 10 единиц – из пункта 1 в пункт 3, 20 единиц – из пункта 2 в пункт 6, 30 единиц – из пункта 6 в пункт 5, 60 единиц – из пункта 3 в пункт 4. Затраты на перевозки, как рассчитано выше, составят E = 480 ден.ед.

Презентация к уроку

Внимание! Предварительный просмотр слайдов используется исключительно в ознакомительных целях и может не давать представления о всех возможностях презентации. Если вас заинтересовала данная работа, пожалуйста, загрузите полную версию.

Цель работы:

Общая: воспитание у обучающихся устойчивых стремлений к знаниям при изучении общеобразовательных дисциплин и математики в частности.

Прикладная:

  • показать курсантам НКРУ им. С.И. Дежнева значение прикладной математики для их будущей профессиональной деятельности;
  • продемонстрировать курсантам высокую экономическую эффективность речных перевозок, и тем самым закрепить у них уважение к своим будущим специальностям.

Указанная цель достигается:

1. Кратким описанием теории графов и истории её возникновения.
2. Перечислением различных областей эффективного применения теории графов в прикладных задачах.
3. Описанием линейной транспортной задачи.
3. Представлением примеров применения теории графов в логистике. В частности при выборе наиболее оптимальной схемы и способов перевозки грузов.
4. Представлением реального примера расчета стоимости различных типов перевозок грузов, в котором показана высокая экономическая эффективность речных перевозок.

Состав работы:

I. Лекция (продолжительность: 1 академический час)
II. Презентация.
III. Комплект контрольно-проверочных средств.

Содержание:

1. Введение: Логистика
2. История возникновения теории графов.
3. Области эффективного применения теории графов.
4. Основные понятия и теоремы теории графов.
5. Наиболее известные и яркие задачи теории графов.
6. Применение теории графов в логистике. Типовая задача речного флота.
7. Контрольные вопросы для проверки усвоения материала.
8. Литература

1. Введение

Если рассматривать логистику как задачу нахождения оптимального перемещения, то с этой точки зрения – каждый человек в течении дня на уровне подсознания неоднократно решает такую задачу, перемещаясь:
– из дома на работу и обратно;
– с работы в театр, в кино, в кафе и т.п.;
– в столовую во время обеда, по помещениям и учреждениям во время работы, и т.д.
– даже первобытный человек во время охоты, решал данную задачу в процессе погони за добычей!
В своей общественно-практической деятельности человек также каждодневно решает задачи логистики оптимального перемещения:
– грузов;
– войск;
– готовой продукции и комплектующих в процессе её производства;
– пассажиров и многого другого.

Логистика – как наука известна со времен Римской империи, где: “Логист” – снабженец в армии.

В настоящее время – основная задача логистики, это:

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

К началу 20-го века Логистика, как наука, получила в арсенал своих научных средств новый математический аппарат – теорию графов

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

2. История возникновения теории графов

Датой рождения теории графов принято считать 1736 год, когда Леонард Эйлер сформулировал первые теоремы новой теории, решая задачу "О кенигсбергских мостах", и написал об этом в письме итальянскому математику и инженеру Мариони 13 марта 1736 г., чем и закрепил за собой приоритет автора новой теории.
Однако: Термин «граф» впервые ввел в математику венгерский математик Денеш Кениг в 1936 году.

В настоящее время:

– в некоторых отраслях прикладной деятельности вместо понятия "граф" используется термин "сеть": сетевой график; сеть железных дорог и т.п.;
– вместо термина "вершина графа" при использовании "сетевой" терминологии используется термин "сетевой узел" или просто – "узел".

"Задача о кенигсбергских мостах".

В 1736 г. город Калининград назывался Кёнигсбергом. Он был расположен на берегах р. Прегель, и на двух островах между ними. Четыре образовавшихся участка суши (правый и левый берег, и два острова) соединяло семь мостов так (рис.1). В задаче предлагалось составить маршрут для почтальона, полицейского или туриста, чтобы они побывали во всех районах города, и при этом прошли по каждому мосту только один раз – в настоящее время такой путь называется "Эйлеровым путём".

В числе сформулированных Эйлером теорем была теорема о том, что: Граф с более чем двумя нечётными степенями вершин невозможно начертить или обойти все его вершины так, чтобы пройти по каждому ребру графа только один раз.

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

На рис. 2 показано изображение графа, для "Задачи о кенигсбергских мостах".

Вершины графа соответствуют определённому району города, а ребра – мостам через реку.
Из рисунка видно, что все четыре вершины графа – имеют нечетные степени: вершины А, В, Г – имеют степень 3, вершина Б – степень 5, т.е. "Эйлерового пути" у данного графа не существует!

На рис. 3 приведены примеры изображений графов, для которых существуют "Эйлеровы пути".

Рис. 1.

Рис. 2.

Эйлеровы Графы:

Рис. 3.

Далее, вплоть до начала 20-го века теория графов развивалась в основном в виде формулирования новых теорем, сформированных по результатам решения различных "головоломных задач".
Серьезное развитие теория графов получила в связи с возникновением массового крупносерийного производства, общим всплеском науки и технологий в первой половине 20-го века.

Читайте также:  Установить приложение транспорт в москве

3. Области применения графов.

В настоящее время теория графов нашла очень широкое применение в:

1. В микроэлектронике – при разработке топологии микросхем.
2. При разработке сложных электрических схем и схем их монтажа в электротехнических шкафах, в электрощитах.
3. В химии – при разработке новых сложных молекулярных соединений и т.п.
4. Физике – при описании и анализе схем развития квантовых процессов.
5. При разработке коммуникационных систем различного назначения.
6. В транспортных системах – как для изучения самих систем, так и при составлении оптимальных маршрутов доставки грузов – логистика.
7. В информатике и программирование – при разработке алгоритмов расчетов, программ.
8. В экономике и планировании – в виде сетевых графиков.
и т.д.

4. Основные понятия теории графов.

Графом, или точнее: "Изображением графа" – называется конечное множество точек, соединенных, как правило, друг с другом любыми линиями. Данные точки называются вершинами графа или узлами сети, а соединяющие их линии – рёбрами.
Если, точка не соединена ни с одной другой точкой – она называется "висячей".
Степень вершины графа равна количеству линий или ребер, связанных с данной точкой, вершиной, узлом. p(N)
С точки зрения решения задачи, связанной с конкретным изображением графа:
Граф непосредственнл – это решение поставленной задачи в виде конкретной схемы пути по вершинам и ребрам изображения графа. Каждая задача может иметь одно и более решений, либо не иметь решения.
Эйлеров граф – это такой граф, в котором существует путь по всем его ребрам такой, чтобы каждое ребро было пройдено только один раз.
Гамильтонов путь – путь через все вершины графа наиболее коротким путем.
Пути могут быть замкнутыми, т.е. начинаться и заканчиваться в одной точке, либо разомкнутыми.
Ориентированные графы – граф, имеющий ребра по которым можно перемещаться только в одном направлении.
Неориентированные графы – в котором по всем ребрам можно перемещаться в любую сторону.

Элементарные теоремы:

Теорема 1.

Сумма степеней вершин графа – четное и равна удвоенному числу ребер графа.
Доказательство: Каждое ребро соединяет две вершины (например A и B), и будет дважды учтено при определении степеней узлов, поскольку: p(А) = p(B) =1 и p(А) + p(B) = 2.

Теорема 2.

Число узлов с нечетной степенью любого графа – четное.

Доказательство: Из Теоремы 1 мы знаем, что сумма четных и нечетных степеней вершин – четная: ∑ pч + ∑ pн = 2R, а сумма четных чисел ∑ pч – всегда четная. Значит и ∑ pн – четная.

Теорема 3.

У Графа с количеством вершин нечетной степени больше 2-х Эйлерова пути нет.

Доказательство: выполнено Эйлером в 1736 г.

5. Наиболее известные и "яркие" задачи теории графов:

1. Теорема о четырёх красках утверждает, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. Теорема была сформулирована в 1852 году, однако доказать ее долгое время не удавалось. В течение этого времени было предпринято множество попыток как доказательства, так и опровержения, и эта задача носила название проблемы четырёх красок. Для простых карт достаточно и трёх цветов, а четвёртый цвет начинает требоваться, например, тогда, когда имеется одна область, окруженная нечетным числом других, которые соприкасаются друг с другом, образуя цикл. Теорема о пяти красках, утверждающая, что достаточно пяти цветов, имела короткое несложное доказательство и была доказана в конце XIX века, но доказательство теоремы для случая четырёх цветов столкнулось со значительными трудностями и была доказана лишь в 1976 году. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Доказательство этого факта заняло сотни страниц и не все математики признали его. В 1997 году, и в 2005 году были найдены более простые доказательства, также проделанные с помощью компьютера.

2. Задача коммивояжера – в которой необходимо посетить каждый город в пределах определенной территории и возвратиться в пункт отправления, причем так, чтобы путь был как можно короче. С современной точки зрения – это типичная задача логистики, была придумана исключительно для развлечения.

3. Задача о ходе коня – задача о нахождении маршрута шахматного коня, проходящего через все поля стандартной шахматной доски по одному разу. Как оказалось: Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно:
13 267 364 410 532.Количество всех незамкнутых маршрутов (с учётом направления обхода) равно: 19 591 828 170 979 904.
Наиболее красивое решение (рис. 4) получено при помощи "Шахматного компьютера". Однако с точки зрения логистики наиболее интересным кажется маршрут, найденный К. Я. Янишем, в котором конь сначала обходит одну половину доски, а затем вторую.

6. Применение Теории Графов в логистике.

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

Типичная задача речного флота (рис. 5): У Базы в точке Б имеется в распоряжении транспортные средства грузоподъемностью:1000, 600, 200,10 тонн.
В точки А, С, Д требуется доставить 1200, 85 и 20 тонн груза соответственно.
Стоимость перевозок сухогрузами:
1000 тонн – 60 000 рублей/сутки; 600 тонн – 35 000 рублей/сутки и 200 тонн – 24 000 рублей/сутки.

Задание.

Необходимо составить графы возможный решений и найти наиболее выгодные варианты с экономической точки зрения для Изображения Графа на Рис. 5.

Данная задача предлагается курсантам для самостоятельного практического задания на 2-ой час занятий по теме: "Графы".

7. Контрольные вопросы для проверки усвоения материала.

1. Что называется степенью вершины Графа?
2. Альтернативное название Графа?
3. Что такое "полный" Граф?
4. Что такое "неполный" Граф?
5. Какие пути существуют в Графе?
6. Чему равна сумма степеней Графа?
7. Какую ещё теорему о Графах знают учащиеся?
8. Нарисовать изображение графа для простой перевозки одним из транспортных средств (рис. 5).
9. Составить Граф решений для одного из транспортных средств по Рис. 5.

8. Литература.

[1]. Интернет ресурсы по темам Теория Графов, Логистика.

Ссылка на основную публикацию
Телефонный шлюз что это
VoIP-шлюз — это межсетевой шлюз, предназначенный для перевода трафика между сетями различных типов. VoIP-шлюзы можно разделить на многоканальные и одноканальные:...
Сравнить технические характеристики rx330 и rx350
Линейка популярных люксовых SUV Lexus RX пополнилась новой модификацией – RX 350. Теперь покупателем RX быть еще приятнее – ведь...
Сравнить процессоры кирин и снапдрагон
Snapdragon 636 vs. Kirin 960: кто лучше? Результаты тестов и сравнительных таблиц, описанных в этой статье, помогут определить, какой из...
Телефонная клавиатура на компьютере
Виртуальная клавиатура выручит Вас, когда выйдет из строя основное физическое устройство ввода, полностью или частично ( поломается несколько клавиш )....
Adblock detector