1 Тема от Jumbo

  • Jumbo
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-04-28
  • Сообщений: 37

Тема: Расставить числа в графе

Дан неориентированный граф без кратных ребер и петель. Нужно расставить в вершинах числа так, чтобы если они соединены ребром то их НОД больше 1, а если не соединены то он=1 (взаимно простые). Подскажите алгоритм!

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Расставить числа в графе

Ну если ограничений на числа нет, то можно вообще просто. Изначально в каждую вершину поставим единицу. Пронумеруем все ребра. Теперь если вершины A и B соединены ребром с номером K, то умножим числа в обеих вершинах на K-е простое число. Очевидно, что если вершины не соединены ребром, то НОД их чисел равен 1.