Шпаргалка по "Математике"

Дискретные оптимизационные  задачи можно решать двумя методами: метод дискретного программирования и метод ветвей и границ. Они  будут рассмотрены на примере  задачи коммивояжера.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

32.Теория графов

Теория графов является эффективным  аппаратом формирования задач.

Основным объектом этой теории является графы. Граф определяется заданием 2х множеств Х и U (B{X;U}) множествах наз.

Важно, что они соединяют 2 данные вершины множества х. Если в паре вершин хi и хj указано направление связи. Отрезок соединяющих их наз. Дугой Uk или напраяление не известно то ребром Вершины опред. Дугу(ребро) Uк Если концевые вершины совпадают то дугу или ребро наз. Петлей.

На графе могут существовать дуги или ребра с  одинаковыми  вершинами.

Две стороны, имеющие общую вершину, наз. смежными, а две вершины ломаной - концы одного отрезка ломаной - наз. смежными вершинами.

Определение степенью P(xi) вершины xi наз. Число дуг (ребер) права в дан. Вершине

Вершина степени О наз. Изамированной  В опред. Полустепени захода  P (xi) вершины хi- это количество дуг исходящих из xi

P+(xi)+P-(xi)=P(xi)

Граф назыв. Простым если он не содержит петель и параллельных дуг.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

33/

Пусть имеется граф G, не содержащий петель, имеющий n вершин и m дуг (ребер). Графу G можно сопоставить матрицу инциденций графа G. Строки m этой матрицы соответствуют вершинам, столбцы n – дугам (ребрам) графа. Если граф ориентированный, то элементы aB_ij Bматрицы инциденций равны: (-1), если дуга u исходит из i-й вершины; (+1), если дуга заходит в i-ю вершину. Если граф неориентированный, то элементами матрицы будут 1 и 0. На рис. 1.2 показаны орграф и его матрица инциденций, на рис. 1.3. - неориентированный граф и матрица инциденций.

 

	u1	u2	u3	u4	u5	u6	u7
x1	-1	0	0	0	-1	-1	0
x2	1	-1	0	0	0	0	0
x3	0	0	0	1	1	0	-1
x4	0	1	1	0	0	0	0
x5	0	0	-1	0	0	1	1

Рис.1.2

u1   u2   u3   u4   u5   u6   u7   x1   1   0   0   0   1   1   0   x2   1   1   0   0   0   0   0   x3   0   0   0   1   1   0   1   x4   0   1   1   0   0   0   0   x5   0   0   1   0   0   1   1

 
Рис.1.3 

Для ориентированных и  неориентированных графов можно  сформировать матрицу смежности  вершин. Пусть орграф G содержит n вершин. Его матрица смежности представляет собой квадратную матрицу n-го порядка. Строки и столбцы этой матрицы соответствуют вершинам орграфа G. Элементы uB_ij Bесть число дуг, выходящих из i-й вершины и входящий в j-ю. В орграфе, не содержащем параллельных дуг, элементами матрицы будут 1 и 0. На рис. 1.4. представлен орграф и его матрица смежности вершин. Как видно из рис. 1.5, у неориентированного графа матрица смежности вершин будет симметрической. По матрице смежности вершин определяется степень вершины, т.е. число дуг, пересекающихся в этой вершине. Число входящих в i-ю вершину дуг равно сумме элементов i- го столбца; число дуг, исходящих из данной вершины, равно сумме элементов i-й строки.

	x1	<p class="Normal_0020Table" style=" margin-bottom: