Доказательство утверждения «б»

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

Поскольку в замкнутом маршруте для каждой вершины число исходов равно числу заходов, то в силу того, что согласно утверждению «а» и правилу 2 все ребра, инцидентные вершине , были пройдены по разу в направлении из (т.е. раз исходили из ), получаем, что ровно раз мы заходили в , причем по правилу 2 каждый раз по новому ребру. Т.е. все ребра были пройдены во всех направлениях.

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

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

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

Задача 1

Задача 2

Результаты экспертной оценки представим таблицей рангов целей:

Эксперты

A

B

+

-

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

Метод ранговой корреляции позволяет ответить на вопрос — насколько коррелированны, неслучайны ранжировки каждого из двух экспертов, а значит — насколько можно доверять результирующим рангам? Как обычно, выдвигается основная гипотеза — об отсутствии связи между ранжировками и устанавливается вероятность справедливости этой гипотезы. Для этого можно использовать два подхода: определение коэффициентов ранговой корреляции Спирмэна или Кендэлла.

Более простым в реализации является первый — вычисляется значение коэффициента Спирмэна

Rs = 1 -

где d_i определяются разностями рангов первой и второй ранжировок по n объектов в каждой.

Сумма квадратов разностей рангов составляет 40, а коэффициент корреляции Спирмэна около 0.86, что означает уровень связи «сильная» по шкале Чеддока.

Коэффициент корреляции рангов Кенделла используется для оценки связи двух признаков и определяется по формуле:

Этапы расчета коэффициента:

1). Значение «х» и «у» ранжируются в порядке возрастания или убывания

Эксперты

A

B

+

-

2). Значение «х» устанавливается в порядке соответствующем пункту 1

3). Значения рангов «у» располагаются в порядке соответствующего значения рангов «х»

4). Определяются для каждого значения ранга «у» число следующих за ним рангов, больших его. Суммарное значение этих превышений обозначается P=5+4+8+8+3+6+0+0+3+0+0+0=37

5). Для каждого значения ранга «у» определяется число следующих за ним рангов меньших значений данного ранга. Суммируя эти значения получаются величины Q=4+3+0+1+6+0+5+4+0+2+0+0=25

6). Величина S определяется по формуле: S = P + (-Q) = 37 – 25 = 12

Связь между факторами слабая