Учебная работа № 5909. «Контрольная Метрические характеристики графа, вариант 3
Учебная работа № 5909. «Контрольная Метрические характеристики графа, вариант 3
Содержание:
«Задача 1
Задать представленный граф: перечислением, матрицей смежности и инцидентности.
Определить следующие характеристики графа: число ребер (дуг), вершин, коэффициент связности, степени всех вершин, цикломатическое число.
Определить метрические характеристики графа: диаметр, радиус, эксцентриситет каждой вершины, центральные вершины).
Задача 2
Определение кратчайшего пути из одной вершины в другую (алгоритм Дейкстры).
Задача 5
Завод выпускает продукцию в четырех цехах: ЦA (ЦA – Цех А), ЦB, ЦC, ЦD расположенных на разных территориях. Свою продукцию завод поставляет в пять магазинов города. Цех A производит 125 тыс. изделий, цех B -105, цех С- 95 и цех D – соответственно 130 тыс. шт. изделий. Плановая потребность магазинов в продукции завода следующая: М1 – 110 тыс. шт. изделий, М2 – 70 тыс. шт., М3- 85 тыс. шт., М4 – 75 тыс. шт., и М5 – 115 тыс. шт. Составьте такой план перевозки изделий, при котором расходы на перевозку изделий были бы наименьшими. Стоимость перевозки 1 тыс. шт. изделий из цехов в магазины приведена в таблице.
М1 М2 М3 М4 М5
ЦА 2 3 6 8 2
ЦВ 8 1 2 3 9
ЦС 7 6 4 1 5
ЦD 2 10 8 5 3
»
Выдержка из похожей работы
Графом
(Г) называется не пустое множество точек
и множество отрезков, оба конца которых
принадлежат данному множеству,
При изображении
графа расположение точек, длина отрезков
не играют роли, не имеют значения, более
того не важно являются ли выбранные
обрезки прямыми или кривыми,
Точки
называются вершинами, отрезки – ребрами,
Вершина, не
принадлежащая ни одному из ребер
называется изолированной,
n
– количество вершин, p
– количество ребер
n=4, p=6,
n=3,
p=0,
n=5, p=2,
A
Теоремой называется
необходимое и достаточное условие, что
два рисунка изображают один и тот же
граф,
Теорема: Для того,
чтобы два рисунка изобразили один и тот
же граф необходимо и достаточно, чтобы
между вершинами на этих рисунках
существовало такое взаимно-однозначное
соответствие, при котором выполнялись
бы два условия:
Две
вершины графа на первом рисунке соединены
ребром, когда соответствующие им вершина
на втором рисунке соединены ребром,
Две вершины графа
на втором рисунке соединены ребром,
когда соответствующие им вершина на
первом рисунке соединены ребром,
Графом Г называется
не пустое множество М и множество
отношений на нем,
Г=(M,Q)
Лабораторная работа № 1,
Основные
характеристики графа
Цель работы:
Изучить понятия
вершины, ребра и дуги графа, цикл графа,
Рассмотреть
понятие дерево,
Литература:
«Графы и их
применение», Березина Л,Ю,, М:
Просвещение, 1979г,
«Теория графов,
Алгоритмический подход», Кристофидес
Н,
«Применение
теории графов в программировании»,
Евстигнеев В
