По графам

[Герыч]

Пишу сюда, потому что по общим вопросам программирования ветки нет:mad:
Итак, есть n вершин, у каждой может быть максимум k рёбер. Как посчитать, сколько у всего графа будет максимально рёбер?
Это мне нужно, чтобы оптимально просчитать размер пула для динамического создания связей в желе.

Добавлено через 5 минут
Пока получается наверно такая формула: round(n*k/2)

[r_r_f_r]

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

[Герыч]

=) я сразу так сделал. Вопрос не в этом, вопрос в оптимальном размере для пула. Для каждой частицы я разрешаю максимум k связей, поэтому узнав эту формулу я узнаю оптимальный размер для пула. Вот как)
P.S. пул - это у меня связный список

[r_r_f_r]

что-то не понимаю зачем нужен размер пула?// извиняюсь если что:)

Element:


public static var pool:Element;
public var next:Element;
public var prev:Element;

Container:

public function addElement(value:Element):Element
{
Element.pool.prev = value;
value.next = Element.pool;
value.prev = null;
Element.pool = value;
return element;
}

public function removeElement(value:Element):void
{
if (value == Element.pool)
{
Element.pool = Element.pool.next;
}
else
{
value.prev.next = value.next;
value.next.prev = value.prev;
}
value.next = null;
value.prev = null;
}

public function doSmt():void
{
var element:Element = Element.pool;
while (element)
{
// element.doSmt();
element = element.next;
}
}


Всё же нужно вчитываться лучше, ступил, сорри.
Но всё таки я не понимаю, зачем в списке нужен размер?
Ты же не выделяешь пямять под него.

[Герыч]

Ты путаешь пул (http://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D0%BD%D1%8B%D0%B9_%D0%BF%D1%83%D0%BB) со связным списком (http://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA).
Сам пул я организовал как связный список(это не так важно, это чисто реализация), но его сначала надо инициализировать некоторым числом элементов. Поскольку у меня почти гарантированно происходит ситуация, когда у каждой частицы желе будет достигнуто максимальное число связей, то пул мне лучше сразу инициализировать нужным числом объектов - связей.

[r_r_f_r]

Ну хозяин как говорится - барин.
Но формула у вас неверна, при к=5 и n=3, а на другую мозгов не хватает.

Я бы сделал инициализацию по требованию.

curentEelement = Element.pool ? Element.pool : Element.pool = new Element();

[Герыч]

Сейчас именно такая инициализация)
Просто ...у меня почти гарантированно происходит ситуация, когда у каждой частицы желе будет достигнуто максимальное число связей, то пул мне лучше сразу инициализировать нужным числом объектов - связей.

а, я забыл про k и n сказать) k<<n, т.е. к примеру n=200, k=20

[r_r_f_r]

Тут тем более, я не знаю математического способа как можно описать "много меньше":)

[Герыч]

Так, зря я всех тут тревожил. Я просто немного ошибся. Формула отлично работает)
P.S. На будущее: перепроверять код, написанный в час ночи=)

[udaaff]

Количество ребер, по идее, будет зависеть от того, как мы соединим вершины. Поэтому точную формулу, скорее всего, вывести нельзя. Есть формула для полного графа, где все вершины соединены: n * (n - 1) / 2. Т.е. как твоя формула, только без округления, так как оно тут не нужно. В правильной формуле округление бы не понадобилось.
К примеру: У графа с четырьмя вершинами и максимальным количеством ребер 2, может быть 4 ребра, а может быть и три.

[$mival]

Количество ребер, по идее, будет зависеть от того, как мы соединим вершины. Поэтому точную формулу, скорее всего, вывести нельзя. Есть формула для полного графа, где все вершины соединены: n * (n - 1) / 2. Т.е. как твоя формула, только без округления, так как оно тут не нужно. В правильной формуле округление бы не понадобилось.
К примеру: У графа с четырьмя вершинами и максимальным количеством ребер 2, может быть 4 ребра, а может быть и три.

вообще то там считаются максимумы, об это мнаписано: максимум k рёбер ... сколько у всего графа будет максимально рёбер?

[Герыч]

Да, максимумы. Я просто объясняю форумулу:
каждой вершине присвоим число k, а потом будет брать любые 2 вершины и уменьшать число, приписанное вершине на 1, а число рёбер увеличивать на 1. Как не думай, больше чем k*n/2 раз не получится.