ответы. Задание 2. Чему равен диаметр сети, содержащей больше чем один связный компонент Почему
 Скачать 15.6 Kb.
|
|
Задание 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: Теперь мы можем использовать первое уравнение, чтобы выразить k2 через k1: k2 = (k1 * n1) / n2 Подставляем это выражение для k2 в уравнение для Таким образом, мы получаем, что средняя степень узлов второго типа связана с средней степенью узлов первого типа соотношением: |