Ламерский вопрос =).

Стоит задача перебрать все возможные графы с количеством вершин N и кол-вом ребер не больше (N^3)/2.Во как. Нужен алгоритм..=)

Здравствуйте, Neuroshifter, Вы писали:

N>Ламерский вопрос =).

N>Стоит задача перебрать все возможные графы с количеством вершин N и кол-вом ребер не больше (N^3)/2.Во как. Нужен алгоритм..=)

Можно переформулировать — всевозможные матрицы N*N с суммой эл-тов (N^3)/2..

Здравствуйте, Neuroshifter, Вы писали:

N>Ламерский вопрос =).

N>Стоит задача перебрать все возможные графы с количеством вершин N и кол-вом ребер не больше (N^3)/2.Во как. Нужен алгоритм..=)

А изоморфные графы считать разными?

Здравствуйте, Mystic, Вы писали:

M>Здравствуйте, Neuroshifter, Вы писали:

N>>Ламерский вопрос =).

N>>Стоит задача перебрать все возможные графы с количеством вершин N и кол-вом ребер не больше (N^3)/2.Во как. Нужен алгоритм..=)

M>А изоморфные графы считать разными?

Да.

Здравствуйте, Neuroshifter, Вы писали:

N>Можно переформулировать — всевозможные матрицы N*N с суммой эл-тов (N^3)/2..

Задача о насыпании K шариков в M урн (где K=(N^3)/2, M=N^2)

class Perebor
{
  // абстрактный API предметной области
  virtual int at(int m) const;
  virtual int put(int m, int k);
  void print(); // выдать на-гора текущее состояние

  // параметры
  virtual int K() const;
  virtual int M() const;

  // итерационный процесс
  void start()
  {
    // насыпем все в первую урну
    put(0, K()); for(int m=1; m<M(); ++m) put(m, 0);
    print();
  }
  bool stopped() const { return at(M()-1) == K; }
  void next()
  {
    int m;
    for(m=M()-2; m>=0 && at(m)==0; --m) {} // ищем (с конца), откуда взять шарик
    assert(m >= 0);
    // перекладываем шарик в следующую урну
    put(m,   at(m)-1);
    put(m+1, at(m+1)+1);
  }

  void play()
  {
     start();
     while(!stopped()) next();
  }
};

Как сделать сопоставление между линейным массивом at|put(m) и двумерной матрицей инцидентности — надеюсь, объяснять не надо.

N>>Можно переформулировать — всевозможные матрицы N*N с суммой эл-тов (N^3)/2.

Уточнение: поскольку изначально стояла задача "с числом ребер НЕ БОЛЕЕ..."

К>Задача о насыпании K шариков в M урн (где K=(N^3)/2, M=N^2)

то будем считать, что урна номер M-1 (или номер 0) — фиктивная, шарики в которой "не считаются".
Соответственно, M=(N^2 + 1).

При этом, если фиктивная урна имеет номер 0, то будем постепенно вводить шарики в игру; если номер M-1 -- то постепенно выводить.

---

Еще одно примечание. Если граф неориентированный, то число урн (не считая фиктивной) будет равно числу "рукопожатий"
= N*(N+1)/2

Если не допускаются петли (ребро, соединяющее вершину с самой собой), то
— для орграфа — N*(N-1)
— для графа — N*(N-1)/2

Здравствуйте, Neuroshifter, Вы писали:

N>>>Стоит задача перебрать все возможные графы с количеством вершин N и кол-вом ребер не больше (N^3)/2.Во как. Нужен алгоритм..=)

M>>А изоморфные графы считать разными?

N>Да.

Кстати, количество ребер в полном графе из N вершин равно N*(N-1)/2, что всегда меньше чем N^3/2. Может быть имеется в виду мультиграф? Или ориентированный мультиграф?

Спасибо за столь развернутый ответ =).

ЗЫ: Надо было всего-лишь подумать...=)

Еще уточнение.
Конечно же, я имел в виду мультиграфы.

Для просто-графов (орграфов) есть ограничение: в урне (кроме фиктивной) может быть не более одного шарика.
Меняем алгоритм.

class Perebor
{
  ...

  virtual int L(int m) const; // лимит количества шаров в урне #m ( = 1 )

  void start()
  {
    put(0, K()); // фиктивная урна - номер 0

    // или, если фиктивная урна - номер M() или ее вообще нет
    for(int m=0; m<M() && k > 0; ++m) // раскидать по первым урнам
    { int kk = (k >= L(m)) ? L(m) : k;
      put(m, kk);
      k -= k;
    }
  }
  bool next()
  {
    int m;
    for(m=M()-2; m>=0 && !(at(m)>0 && at(m+1)<L(m+1)); --m) // ищем пару из заполненной и (полу)пустой
    if(m < 0) return false; // конец
    put(m,   at(m)  -1);
    put(m+1, at(m+1)+1);
    print();
    return true;
  }
}

M>Кстати, количество ребер в полном графе из N вершин равно N*(N-1)/2, что всегда меньше чем N^3/2. Может быть имеется в виду мультиграф? Или ориентированный мультиграф?
Да, и мультиграф тоже.