Задание 2

1. Чему равен диаметр сети, содержащей больше чем один связный компонент? Почему?

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

2. Простая сеть состоит из n узлов и одной компоненты. Какое максимальное количество связей в ней может быть? Какое минимальное количество связей? Объяснить почему.

Максимальное количество связей в простой сети с n узлами может быть достигнуто, когда каждый узел соединен со всеми остальными узлами. Таким образом, для каждого узла есть n-1 связей, и общее количество связей будет равно сумме связей каждого узла:

(n-1) + (n-1) + ... + (n-1) = n(n-1)

Минимальное количество связей в такой сети может быть достигнуто, когда нет связей между узлами, то есть когда сеть состоит из n изолированных узлов. В этом случае количество связей равно 0.

Таким образом, максимальное количество связей в сети из n узлов - n(n-1), а минимальное количество связей - 0.

3. Рассмотрим двудольную сеть с двумя типами узлов и предположим, что в ней n1 узлов первого типа и n2 узлов второго типа. Покажите, что средние степени и для вершин двух типов связаны отношением: < ???? 2 >= ???? 1 /???? 2 < ???? 1 >

Двудольная сеть - это сеть, в которой узлы могут быть разделены на две непересекающиеся группы, и все связи идут только между узлами разных групп. Пусть первая группа содержит n1 узлов, а вторая - n2 узлов. Пусть k1 - средняя степень узлов первой группы, а k2 - средняя степень узлов второй группы.

Общее количество ребер E в двудольной сети между первой и второй группами можно выразить через k1 и k2, используя формулу:

E = k1 * n1 = k2 * n2

Это происходит потому, что каждый узел первой группы имеет k1 связей с узлами второй группы, и общее количество таких связей равно k1 * n1, и это же количество связей у узлов второй группы.

---

Используя этот результат, мы можем выразить среднюю степень каждого типа узлов через n1, n2, k1 и k2:

= 2E/n1 = 2k2*n2/n1

= 2E/n2 = 2k1*n1/n2

Теперь мы можем использовать первое уравнение, чтобы выразить k2 через k1:

k2 = (k1 * n1) / n2

Подставляем это выражение для k2 в уравнение для , получаем:

= 2k1*n1/n2 = 2(n1/n2) * k1

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

= (n1/n2) *

---

Смотрите также файлы

• Всероссийский государственный университет юстиции (рпа минюста России).pptx

• Этические ценности современной казахстанской молодежи.pptx

• Амортизация есть процесс Тип ответа.doc

• 1. в соответствии с Указом Президента рф Об утверждении основ государственной политики по сохранению и укреплению традиционных российских духовнонравственных .docx

• 2 Asaka tumanida abonent kirish tarmoqlari tahlili.docx