Элементы теории графов. Центры и периферийные вершины графов, их радиусы и диаметры. Максимальный поток транспортировки груза и поток минимальной стоимости. Пропускная способность пути. Анализ сетей Петри, их описание аналитическим и матричным способами.
Аннотация к работе
Если значения индексов a, b, g… переменной x не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Гхі. Выполнить следующие действия: а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами; X = {x1, x2, x3, x4, x5, x6 }, n = 6 k = 2, l = 1 Гхі={x|I±k|, x|I±l|}. а) определим исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами: Определим граф аналитическим способом: Гх1 = {x1, x3, x2 }; AD - матрица инцидентности v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 x1 1* 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 x2 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 x3 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 x4 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 x5 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 x6 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов: - матрица отклонений имеет вид: x1 x2 x3 x4 x5 x6 x1 1 1 1 2 2 3 x2 1 0 1 1 2 2 x3 1 1 0 1 1 2 x4 2 1 1 0 1 1 x5 2 2 1 1 0 1 x6 3 2 2 1 1 0 Определяем пропускную способность найденного пути, которая равна наименьшей из пропускных способностей дуг: Определяем остаточные пропускные способности дуг найденного пути и симметричных ему дуг.