Курсовое задание № 3
Матрица |
5-ки |
2 |
3 |
4а |
6 |
9 |
12 |
14 |
|
А3 |
А1 |
+ |
+ |
+ |
+ |
+ |
4 |
+ |
|
|
А2 |
|
|||||||
|
А3 |
|
|||||||
|
А4 |
|
|
|
|
|
|
|
|
|
А7 |
|
|
|
|
|
|
|
Задание 2.
Найти медиану и значение критерия для матриц Ак1,Ак2,Ак3,Ак4,Ак5.
Постановка:
Медиана – это вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимально возможная.
Значение критерия – сумма кратчайших расстояний от медианы до исходных графов.
Обобщённое правило простого большинства – если элемент входит не менее, чем в половину множеств, то он входит и в результирующие множество.
Решение.
Ак1=А1; Ак2=А2; Ак3=А3; Ак4=А4 Ак5= - А2;
Так как у нас взвешенный граф – применяем обобщенное правило простого большинства.
Т.к. дано 5 матриц, N=5=2p+1. отсюда следует, что р=2.
Упорядочиваем элементы матриц по возрастанию:
Таблица упорядочивания весов ребер.
∑ |
|
||||||
1-2 |
-5 |
-1 |
1 |
2 |
9 |
17 |
|
2-3 |
-1 |
-1 |
1 |
1 |
4 |
7 |
|
3-4 |
-2 |
-1 |
1 |
5 |
10 |
18 |
|
4-5 |
-4 |
-1 |
4 |
6 |
10 |
21 |
|
5-6 |
-6 |
-2 |
2 |
5 |
6 |
19 |
|
6-7 |
-7 |
-5 |
-3 |
-1 |
5 |
16 |
|
7-8 |
-4 |
-3 |
2 |
3 |
8 |
18 |
|
8-9 |
-1 |
1 |
1 |
3 |
8 |
11 |
|
9-10 |
-5 |
-1 |
1 |
5 |
10 |
21 |
|
10-11 |
-6 |
-1 |
1 |
1 |
4 |
12 |
|
11-12 |
-7 |
-1 |
1 |
2 |
9 |
19 |
|
12-13 |
-12 |
-1 |
3 |
8 |
12 |
33 |
|
13-14 |
-14 |
-10 |
2 |
8 |
14 |
46 |
|
14-15 |
-7 |
-2 |
-1 |
-1 |
2 |
10 |
|
15-16 |
-7 |
-1 |
2 |
5 |
7 |
20 |
|
4-9 |
-10 |
-5 |
-1 |
0 |
10 |
25 |
|
3-10 |
-12 |
-2 |
-1 |
0 |
1 |
15 |
|
2-11 |
-10 |
-5 |
-5 |
0 |
5 |
20 |
|
1-12 |
-10 |
-2 |
-1 |
0 |
2 |
14 |
|
7-10 |
-3 |
0 |
0 |
3 |
7 |
13 |
|
6-11 |
-5 |
0 |
0 |
5 |
6 |
16 |
|
5-12 |
-7 |
0 |
0 |
5 |
7 |
19 |
|
4-13 |
-9 |
0 |
0 |
4 |
9 |
22 |
|
3-14 |
-11 |
0 |
0 |
3 |
11 |
25 |
|
2-15 |
-13 |
0 |
0 |
2 |
13 |
28 |
|
1-16 |
-15 |
1 |
6 |
10 |
15 |
39 |
|
8-13 |
0 |
0 |
0 |
0 |
10 |
10 |
|
7-14 |
0 |
0 |
0 |
0 |
4 |
4 |
|
6-15 |
0 |
0 |
0 |
0 |
3 |
3 |
|
5-16 |
0 |
0 |
0 |
0 |
1 |
1 |
Остальные ребра имеют вес, равный 0, поэтому они не повлияют на решение.
Ответом является столбец номер р+1=3.