Доброго дня.
Для решения одной задачки по программированию, связанной с графами, решил что мне нужна некая формула, позволяющая по изначальным условиям высчитать нужное значение, а так как в сети нигде не нашел ничего похожего, то пришлось вывести её самому. К слову сказать, для решения моей задачи формула всё же не понадобилась, однако сама по себе мне кажется она, формула, может кому-то пригодиться. И так.
На рисунке 1 изображён Граф:
1) количество вершин (N) = 5;
2) 1, 2, 3, 4, 5 - вес вершин, последовательность натуральных чисел от 1 до N;
3) 1-2, 1-3, 1-4, 1-5, 2-3 и т.д. - дуги, т.е. направленные рёбра;
4) Граф полный - т.е. любая пара вершин смежная (соединены ребром);
5) Граф регулярный - т.е. степень всех вершин одинакова, и равна N-1;
6) Граф ориентированный - т.е. ребра имеют направление, являются дугами;
7) вершина 1 - Исток, вершина N, в данном случае вершина 5 - Сток;
8) вес дуги равен наименьшему весу соединяемых вершин;
9) направление дуг - от меньшего веса к большему.
И так формула: (N^3 - N) / 6.
Формула находит сумму всех весов дуг. На рисунке 2 показано наглядно о чём речь. Причём, сумма правого столбца равна удвоенной сумме левого. Но если левый столбец это веса дуг, то чем является правый, затрудняюсь сказать.
Соответственно, для случая N=5 сумма всех весов дуг равна 20. Формула работает для любого N (экстремально большие значения не проверял, но причин не сработать на них, вроде как нет).
Какого либо практического применения для формулы в голову так и не пришло. Возможно она по сути и является просто интересной закономерностью. Возможно даже я плохо искал и она уже была выведена раньше и применяется для чего-то там. Как бы то ни было, если кому-то пригодиться - хорошо.