Правило прямоугольника для преобразования Симплексной таблицы

Рассчитываем новую таблицу:

Разрешающая строка делится на ведущий коэффициент, а разрешающий столбец заменяется единичным (с 1 вместо ведущего коэффициента и нулями вместо остальных). Все другие коэффициенты пересчитываются по формулам Жордана-Гаусса (или по правилу прямоугольника). Сформулируем его в общем виде.

Пусть a_pq –– ведущий коэффициент и пересчитывается коэффициент a_ij. Тогда

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

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

Теория графов - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Графом G называют пару множеств (V, E), где V - множество вершин графа (точек); E - семейство ребер графа (отрезков или дуг, соединяющих вершины в пары): V={v-i,v2,v3,...,v_n};

E={ei, e2 , ез,...,е_т }; Пример графа: v = {1,2,3,4,5}, e = {(1,2), (2,3), (3,4), (1,5), (1,4), (3,1)}.

То есть, элементы множества V называются вершинами графа. Элементы множества E - ребрами графа. Ребра вида (v,v), в которых первый элемент равен второму элементу, называются петлями. Или, если концевые вершины ребра совпадают, то ребро образует петлю (дугу, начало и конец которой совпадают).

Если пара (vi,v₂) е E - ребро, то vi и v₂ называются концами этого ребра. В этом случае вершины v₁ и v₂ называются смежными в графе, а само ребро (vi, v₂) называется инцидентным вершинам v₁ и v₂.

Пусть в графе есть ребро (v₁,v₂), тогда можно считать, что в нем есть ребро (v₂,v₁). Если при этом указанные ребра не различать (т. е. (v₁,v₂)= (v₂,v₁), пары считаются неупорядоченными), то граф называется неориентированным графом.

Если в графе есть несколько одинаковых ребер вида (v₁,v₂) , то такое ребро называют кратным. Графы можно изображать графически. Вершины изображаются точками, ребра изображаются линиями соединяющие соответствующие вершины.

Число вершин графа называют порядком графа и обозначают I V| = n. Граф будем обозначать парой G = (V, E).

Граф G называется помеченным, если его вершинам приписаны числа 1, 2, ..., п, где п - порядок графа. Граф можно задать с помощью матрицы размера n x n: A(G)=[ajj], где 1 ^ i, j ^ n

эта матрица симметрична с нулями по главной диагонали. Она

1, pe6po(v_i, Vj)

е E 0, pe6po(v, v •) £ E

называется матрицей смежностей графа G = (V, E).

Ребра графа могут быть ориентированными или неориентированными. При изучении бинарных отношений были использованы графы, все ребра которых ориентированы. Такие графы называют ориентированными графами или орграфами.

Если вершины v_i и Vj (ij соединены ребром e_k= (v^vj), то их называют смежными вершинами. Если ребра e_k, e_l имеют общую вершину, то их называют смежными ребрами. Если вершина v_i является концом ребра ej, то v_i называют вершиной, инцидентной ребру ej, а ej - ребром, инцидентным вершине v_i.

Степенью вершины графа называется число инцидентных ей ребер, (число вершин смежных этой вершине, число ребер выходящих из этой вершины, число ребер входящих в нее). Обозначают степень вершины v через deg (v).

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

19. Способы задания графа. Матрицы смежностей и инциденций. Обходы графов

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

как v₁₅ v₂,...,v_n . Затем для каждой пары точек v_i,V- таких, что (v_i,v■)е E, проведем отрезок

прямой, соединяющий точки v_i, Vj . В результате таких действий возникнет некоторый рисунок,

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

1 5 Рис.1 1 Рис.2

Число вершин графа называют порядком графа и обозначают |v|= n. Граф будем обозначать парой G = (V, E). Граф G называется помеченным, если его вершинам приписаны числа 1, 2, ..., n, где n - порядок графа.

Граф можно задать с помощью матрицы размера n x n: A(G)=[a_ij], где 1 ^ i, j ^ n

1, pedpo(v_i, v-) е E

О ребро(у м}£Е^эта матрица симметрична с нулями по главной диагонали. Она

a.. — s

Uj ^

называется матрицей смежностей графа G = (V, E).

	' 0	1	1	1	1^>
	1	0	1	0	0
В приведенном выше примере графа матрица смежностей такова: ^A⁽^G⁾	1	1	0	1	0
	1	0	1	0	0
	,¹	0	0	0	⁰ >
Сопоставим графу G = (V, E) еще одну матрицу. Будем считать, что	V —	= {v	1,^v	V"	, vn)

прежнему множество вершин и пусть

v ^е^e!,

размера n x p: B(G)=[b_ij], i — 1,..., П j — 1,..., p следующим образом: ^bij ^ g £,

Введенная так матрица B(G) называется матрицей инциденций данного графа. Очевидно, вид матрицы смежностей и вид матрицы инциденций существенно зависят от того, как именно занумерованы вершины и ребра. Если в приведенном выше примере графа считать, что

e — (1,2), e2 — (1,3), £3 — (1,4), e₄ — (1,5), e₅ — (2,3), e₆ — (3,4),

(11110 0 ^ 1 0 0 0 1 0 0 10 0 11 0 0 1 0 0 1 _ч0 0 0 1 0 0_J

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

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

Прежде всего, уточним термины "маршрут", "цепь", "цикл" и "путь". Эти четыре понятия находятся в следующем соотношении: пути и циклы - это особые виды цепей, цепь - особый вид маршрута.

Маршрут - это последовательность вершин и ребер графа, следуя по которым, можно попасть

из одной его вершины в другую.

Цепь - это маршрут без повторяющихся ребер.

Путь - это цепь, все вершины которой (за исключением, быть может, начальной и конечной) различны.

Цикл - это цепь, у которой совпадают начальная и конечная вершины, а все остальные различны.

Пример.

Можно составить следующие маршруты из А в С в графе G:

М1: А - е1 - В - е3 - С (путь);

М2: А - е2 - Е - е6 - Д - е7 - Д - е6 - Е - е5 - С (не цепь);

М3: А - е1 - B - е3 - C - е5 - Е - е4 - С (цепь, но не путь). Циклы.

А - е1 - В - е3 - С - е4 - Е - е2 - А; Е - е4 - С - е5 - Е; Д - е7 - Д.

Граф называют связным, если из каждой его вершины существует путь в любую другую его вершину. Граф, рассмотренный в примере, является, связным. Если удалить из него ребро , то он потеряет связность и распадется на компоненты: одна из компонент будет содержать вершину Д и петлю , вторая компонента - вершины А,В,С,Е, связанные между собой всеми оставшимися ребрами.

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

Вершины 5,6,3,7,8,9 называют листьями дерева. Несвязный неорграф, компонентами которого являются деревья, называют лесом.

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

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

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

21. Графы типа дерево. Остовное дерево. Минимальное остовное дерево

G называется деревом, если он является связным и не имеет циклов. Граф G, все

компоненты связности которого являются деревьями,

называется лесом. Граф G1 является деревом (рис.38). Граф G2 является лесом (рис. 38), он содержит три связные компоненты, каждая из которых является деревом.

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

Если у дерева G есть, по крайней мере, одно ребро, то у него обязательно найдется висячая вершина. Пусть G - дерево. Тогда любая цепь в G будет простой.

Опр. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пусть G связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G) - 1 ребер. Таким образом, любое остовное дерево графа G есть результат удаления из G ровно m(G)-(n(G)-1)=m(G)-n(G)+1 ребер.

Опр. Число m(G)-n(G)+1 называется цикломатическим числом связного графа G и обозначается через v(G).

ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ - Задача о нахождении на ориентированном графе пути наименьшей длины между двумя заданными его вершинами. Длиной пути такого графа называется сумма длин дуг, составляющих этот путь. Задача о кратчайшем пути возникает чаще всего при решении транспортных задач, дискретных задач динамического программирования и др. Остовное дерево связного неориентированного графа — ациклический связный подграф данного графа, в который входят все его вершины. Иначе говоря, остовное дерево состоит из некоторого подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрами, и в нём нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды.

Понятие остовный лес неоднозначно, под ним могут понимать один из следующих подграфов: любой ациклический подграф, в который входят все вершины графа, но не обязательно связный; в несвязном графе — подграф, состоящий из объединения остовных деревьев для каждой его компоненты связности.

Остовное дерево также иногда называют покрывающим деревом, остовом или скелетом графа.

Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

( <- Пример минимального остовного дерева в графе. Числа на ребрах обозначают вес ребер.)

Задача о нахождении минимального остовного дерева встречается в постановке: допустим, есть n городов, которые надо соединить дорогами, так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Разрешается строить дороги между заданными парами городов и известна стоимость строительства каждой дороги. Требуется решить, какие дороги нужно строить, чтобы минимизировать общую стоимость строительства.

Граф

Дата добавления: 2018-04-15; просмотров: 964; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 23

Мы поможем в написании ваших работ!