Генерация графа

@goldolov_na · Регистрация: 31.03.2019

Студворк — интернет-сервис помощи студентам

Андрей изучает социальные сети и пытается определить скрытые атрибуты пользователей по их друзьям. Поскольку Андрей - профессиональный программист, то он хочет протестировать свою программу прежде чем верить ее результатам. Но для этого требуется много разных графов, похожих на социальные сети. Андрей хочет получать графы с разным количеством пользователей (т. е. вершин графа) и разными отношениями дружбы (т. е. ребрами графа). Отношение дружбы ненаправленное. В графе не должно быть петель и кратных ребер. Андрей будет задавать желаемое количество вершин и желаемое среднее количество ребер, инцидентных вершине. Его устроит даже граф, если эти его характеристики будут отличаться от заданных, но не более чем на 20%.

Ваша программа получает на вход 2 целых положительных числа - N - количество вершин и K - среднее количество ребер у вершины (1≤ N ≤ 200, 0 ≤ K ≤ N - 1)

Программа печатает граф описанного вида. В первой строке печатается количество вершин графа. Начиная со следующей строки, печатается матрица смежности графа по строкам. Вершины нумеруются последовательно, начиная с 0. Элемент матрицы смежности равен 1, если соответствующее ребро входит в граф, и 0, иначе. Элементы разделяются пробельными символами. Элементы главной диагонал матрицы смежности должны равняться 0. Если графа описанного вида не существует, программа ничего не печатает.

Добавлено через 4 часа 24 минуты
я составил алгоритм выполнения,но проблема реализовать это в код
поэтому реализуйте пожалуйста
Максимальное количество ребер у неориентированного графа с N вершинами - N(N-1)/2, минимальное - 0. Для заданного количества ребер K допускается граф с количеством ребер от 0.8K до 1.2K. Поэтому надо проверить, существует ли количество ребер графа (обозначим L), которое удовлетворяет неравенствам 0.8K<=L<=1.2K и 0<=L<= N(N-1)/2. Это можно сделать простым перебором для всех L=0...200, а можно как-то преобразовать эти неравенства.
Если не нашлось такого числа L, то ничего не выводим. Если нашлось такое число L, то строим рандомный граф с числом вершин N и количеством ребер L.
Сначала соединяем вершину 0 с вершинами 1, 2, 3, ..N-1.
Потом соединяем вершину 1 с вершинами 2, 3, 4, ..N-1
Соединяем вершину 2 с вершинами 3, 4, 5, ..N-1.
Ну и так далее пока количество таких соединений (ребер) не станет L. После того, как оно станет L - прекратить соединения и вывести граф.

Добавлено через 45 минут
Немного ошибся , будет такой алгоритм
Рассмотрим неориентированный граф с количеством вершин M и количеством ребер L. Такой граф точно существует, если 0<=L<=M(M-1)/2. Итого для целых чисел M и L должно выполняться
0<=L<=M(M-1)/2
0.8K<=L<=1.2K
0.8N<=M<=1.2N
M и L можно найти простым перебором.
Если найдены целые числа M и L, удовлетворяющие этим условиям, то строим граф с M вершинами и L ребрами.

Добавлено через 23 минуты
Помогите пожалуйста, понимаю алгоритм,но сделать не могу(

@dprotas · 08.11.2020, 16:11

Программа на Python:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import random
 
def graf(N,K):
 
    matrix = []
    
    for i in range(N):
        matrix.append ([0]*N)
    
    print (matrix)
    print('======================================')
    
    edges = 0
    
    for i in range(N):
        
        for j in range(N):
            if i < j and edges <= K*N:                       #N*(N - 1)/2 :
                matrix[i][j] = random.randint(0, 1)
                
                edges += matrix[i][j]
                
                
            elif i > j :
                matrix[i][j] = matrix[j][i]
                
            elif i == j:
                matrix[i][j] = 0
            
    print(matrix)
    print('=======================================')
    print('количество ребер = ', edges)
    print('=======================================')
 
    print (N) # печать количества вершин
    for row in matrix:
        for elem in row:
            print(elem, end = ' ')
        print()
 
#-=-=-=-=-=-==-=-=-=-=-=-=-=-===--==-=-=-=-=-=-=-=-=-=-=-=-=-=-=
 
N = int(input()) # число вершин (1≤ N ≤ 200)
K = int(input()) # среднее количество ребер у вершины  (0 ≤ K ≤ N - 1)
 
 
if N < 200 and K*N < N*(N-1)/2:
   graf(N, K)
 
elif int(1.2*N) < 200 and 0.8*K*N < N*(N-1)/2 :
 
       N = int(1.2*N)
       K = int(0.8*K)
 
       print ('Новое число вершин =', N)
       print('-'*100)
       print ('Новое среднее число ребер =', K)
       print('======================================')    
        
       graf(N, K)

@Тюра · 10.11.2020, 19:09

ну у вас условия надо доработать и избавиться от random(можно заполнять граф построчно начиная с номера строки j = i + 1 заполняя a[i][j] = 1, a[j][i] = 1 , j++ пока не заполните нужное количество)

@smalyarovsky · 11.11.2020, 13:18

Вы неправильно поняли условие. K - СРЕДНЕЕ КОЛИЧЕСТВО ребер у одной вершины. Оно очевидно не превышает N - 1. От-того и решения предложенные вами неверны

@Gger · 11.11.2020, 13:18

можно код решения?а то этот ничего не выводит

@goldolov_na · 11.11.2020, 13:22 **[ТС]**

Gger, 13 числа скину))

@Gger · 11.11.2020, 13:22

goldolov_na, скинь сейчас, пж

@goldolov_na · 11.11.2020, 13:24 **[ТС]**

Gger, неа
как закончится олимпиада скину

@Gger · 11.11.2020, 13:28

goldolov_na, мне очень сильно лень писать решение задачи, скинь, пожалуйста

Добавлено через 1 минуту
goldolov_na, у других просишь помощи, так сам помоги

@goldolov_na · 11.11.2020, 13:29 **[ТС]**

Gger, а ты не ленись)) сядь и напиши

@Gger · 11.11.2020, 13:31

goldolov_na, сначала надо попробовать лениться, скинь все, пж.))

@goldolov_na · 11.11.2020, 13:32 **[ТС]**

Gger, ну так и ленись дальше, но решения тебе не будет

@Gger · 11.11.2020, 13:35

goldolov_na, классный чувак, сам все списал и не помогает, эх

@goldolov_na · 11.11.2020, 13:44 **[ТС]**

Gger, где я списал?) решение увидел что ли? если видишь решение откуда можно списать ,так списывай давай))

Добавлено через 7 минут
Gger, да и тем более смысл тебе решение давать , если ты бездарь
тебе написали выше код, стратегии по выполнению , а ты даже по этим данным решить не можешь

@Gger · 11.11.2020, 13:48

goldolov_na, да задача-то легкая, лень писать просто, говорю ж

@goldolov_na · 11.11.2020, 13:49 **[ТС]**

Gger, ну решение составляет около 20 строк, тут не лень , а просто то что ты

@Gger · 11.11.2020, 13:57

goldolov_na, переходить на личности...даже 20 строчек бывает лень написать

@goldolov_na · 11.11.2020, 13:59 **[ТС]**

Gger, да да да ... рассказывай больше сказок))
зачем тогда записывался на эту олимпиаду , если тебе лень писать

было бы лень, тогда бы и не записывался сюда

@smalyarovsky · 11.11.2020, 18:48

Зачем мне поддерживать тебя решением? Чем меньше людей пройдет на финал тем мне лучше

@goldolov_na · 11.11.2020, 18:53 **[ТС]**

smalyarovsky, по идее без разницы)там ведь призеры и победителей может быть неограниченное кол-во)) там призера дают за опред. кол-во баллов

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@goldolov_na 37 / 26 / 1 Регистрация: 31.03.2019 Сообщений: 585

	Генерация графа 06.11.2020, 18:01. Показов 15942. Ответов 26 Метки python (Все метки) Андрей изучает социальные сети и пытается определить скрытые атрибуты пользователей по их друзьям. Поскольку Андрей - профессиональный программист, то он хочет протестировать свою программу прежде чем верить ее результатам. Но для этого требуется много разных графов, похожих на социальные сети. Андрей хочет получать графы с разным количеством пользователей (т. е. вершин графа) и разными отношениями дружбы (т. е. ребрами графа). Отношение дружбы ненаправленное. В графе не должно быть петель и кратных ребер. Андрей будет задавать желаемое количество вершин и желаемое среднее количество ребер, инцидентных вершине. Его устроит даже граф, если эти его характеристики будут отличаться от заданных, но не более чем на 20%. Ваша программа получает на вход 2 целых положительных числа - N - количество вершин и K - среднее количество ребер у вершины (1≤ N ≤ 200, 0 ≤ K ≤ N - 1) Программа печатает граф описанного вида. В первой строке печатается количество вершин графа. Начиная со следующей строки, печатается матрица смежности графа по строкам. Вершины нумеруются последовательно, начиная с 0. Элемент матрицы смежности равен 1, если соответствующее ребро входит в граф, и 0, иначе. Элементы разделяются пробельными символами. Элементы главной диагонал матрицы смежности должны равняться 0. Если графа описанного вида не существует, программа ничего не печатает. Добавлено через 4 часа 24 минуты я составил алгоритм выполнения,но проблема реализовать это в код поэтому реализуйте пожалуйста Максимальное количество ребер у неориентированного графа с N вершинами - N(N-1)/2, минимальное - 0. Для заданного количества ребер K допускается граф с количеством ребер от 0.8K до 1.2K. Поэтому надо проверить, существует ли количество ребер графа (обозначим L), которое удовлетворяет неравенствам 0.8K<=L<=1.2K и 0<=L<= N(N-1)/2. Это можно сделать простым перебором для всех L=0...200, а можно как-то преобразовать эти неравенства. Если не нашлось такого числа L, то ничего не выводим. Если нашлось такое число L, то строим рандомный граф с числом вершин N и количеством ребер L. Сначала соединяем вершину 0 с вершинами 1, 2, 3, ..N-1. Потом соединяем вершину 1 с вершинами 2, 3, 4, ..N-1 Соединяем вершину 2 с вершинами 3, 4, 5, ..N-1. Ну и так далее пока количество таких соединений (ребер) не станет L. После того, как оно станет L - прекратить соединения и вывести граф. Добавлено через 45 минут Немного ошибся , будет такой алгоритм Рассмотрим неориентированный граф с количеством вершин M и количеством ребер L. Такой граф точно существует, если 0<=L<=M(M-1)/2. Итого для целых чисел M и L должно выполняться 0<=L<=M(M-1)/2 0.8K<=L<=1.2K 0.8N<=M<=1.2N M и L можно найти простым перебором. Если найдены целые числа M и L, удовлетворяющие этим условиям, то строим граф с M вершинами и L ребрами. Добавлено через 23 минуты Помогите пожалуйста, понимаю алгоритм,но сделать не могу( 0

@Тюра 8 / 8 / 0 Регистрация: 26.05.2019 Сообщений: 7
	10.11.2020, 19:09
	ну у вас условия надо доработать и избавиться от random(можно заполнять граф построчно начиная с номера строки j = i + 1 заполняя a[i][j] = 1, a[j][i] = 1 , j++ пока не заполните нужное количество) 1

@smalyarovsky 0 / 0 / 0 Регистрация: 12.03.2019 Сообщений: 36
	11.11.2020, 13:18
	Вы неправильно поняли условие. K - СРЕДНЕЕ КОЛИЧЕСТВО ребер у одной вершины. Оно очевидно не превышает N - 1. От-того и решения предложенные вами неверны 0

@Gger 0 / 0 / 0 Регистрация: 09.11.2020 Сообщений: 22
	11.11.2020, 13:18
	можно код решения?а то этот ничего не выводит 0

@goldolov_na 37 / 26 / 1 Регистрация: 31.03.2019 Сообщений: 585
	11.11.2020, 13:22 [ТС]
	Gger, 13 числа скину)) 1

@Gger 0 / 0 / 0 Регистрация: 09.11.2020 Сообщений: 22
	11.11.2020, 13:22
	goldolov_na, скинь сейчас, пж 0

@goldolov_na 37 / 26 / 1 Регистрация: 31.03.2019 Сообщений: 585
	11.11.2020, 13:24 [ТС]
	Gger, неа как закончится олимпиада скину 1

@Gger 0 / 0 / 0 Регистрация: 09.11.2020 Сообщений: 22
	11.11.2020, 13:28
	goldolov_na, мне очень сильно лень писать решение задачи, скинь, пожалуйста Добавлено через 1 минуту goldolov_na, у других просишь помощи, так сам помоги 0

@goldolov_na 37 / 26 / 1 Регистрация: 31.03.2019 Сообщений: 585
	11.11.2020, 13:29 [ТС]
	Gger, а ты не ленись)) сядь и напиши 0

@Gger 0 / 0 / 0 Регистрация: 09.11.2020 Сообщений: 22
	11.11.2020, 13:31
	goldolov_na, сначала надо попробовать лениться, скинь все, пж.)) 0

@goldolov_na 37 / 26 / 1 Регистрация: 31.03.2019 Сообщений: 585
	11.11.2020, 13:32 [ТС]
	Gger, ну так и ленись дальше, но решения тебе не будет 0

@Gger 0 / 0 / 0 Регистрация: 09.11.2020 Сообщений: 22
	11.11.2020, 13:35
	goldolov_na, классный чувак, сам все списал и не помогает, эх 0

@goldolov_na 37 / 26 / 1 Регистрация: 31.03.2019 Сообщений: 585
	11.11.2020, 13:44 [ТС]
	Gger, где я списал?) решение увидел что ли? если видишь решение откуда можно списать ,так списывай давай)) Добавлено через 7 минут Gger, да и тем более смысл тебе решение давать , если ты бездарь тебе написали выше код, стратегии по выполнению , а ты даже по этим данным решить не можешь 0

@Gger 0 / 0 / 0 Регистрация: 09.11.2020 Сообщений: 22
	11.11.2020, 13:48
	goldolov_na, да задача-то легкая, лень писать просто, говорю ж 0

@goldolov_na 37 / 26 / 1 Регистрация: 31.03.2019 Сообщений: 585
	11.11.2020, 13:49 [ТС]
	Gger, ну решение составляет около 20 строк, тут не лень , а просто то что ты 0

@Gger 0 / 0 / 0 Регистрация: 09.11.2020 Сообщений: 22
	11.11.2020, 13:57
	goldolov_na, переходить на личности...даже 20 строчек бывает лень написать 0

@goldolov_na 37 / 26 / 1 Регистрация: 31.03.2019 Сообщений: 585
	11.11.2020, 13:59 [ТС]
	Gger, да да да ... рассказывай больше сказок)) зачем тогда записывался на эту олимпиаду , если тебе лень писать было бы лень, тогда бы и не записывался сюда 0

@smalyarovsky 0 / 0 / 0 Регистрация: 12.03.2019 Сообщений: 36
	11.11.2020, 18:48
	Зачем мне поддерживать тебя решением? Чем меньше людей пройдет на финал тем мне лучше 0

@goldolov_na 37 / 26 / 1 Регистрация: 31.03.2019 Сообщений: 585
	11.11.2020, 18:53 [ТС]
	smalyarovsky, по идее без разницы)там ведь призеры и победителей может быть неограниченное кол-во)) там призера дают за опред. кол-во баллов 0

Генерация графа

Решение