Каково число всех возможных нециклических простых путей в полностью связном ориентированном графе?

Question

Допустим, у нас есть полностью связанный орграф G с N вершинами и M ребрами.

Сколько ребер у графа?Это M = N^2?

Если мы возьмем одну вершину и начнем посещать ее соседей способом «поиска в глубину» и избегая циклов, сколько нециклических простых путей мы получим?

Например, если мы начнем с вершины 1 в графе из 4 вершин, вот пути:

- 1
- 1,2
- 1,3
- 1,4
- 1,2,3
- 1,2,4
- 1,3,2
- 1,3,4
- 1,4,2
- 1,4,3

Это N! или более для графа с Nвершины?Я не мог найти способ обобщить это и вывести пригодную для использования формулу.

Answer 1

Если ваш граф заполнен, для каждой вершины есть n! простых путей, поэтому всего n*n! простых путей в графе.

пусть начальная вершина будет v_1.
Есть |V| возможностей, что делать дальше: перейти к одному из V\{v_1} или остановиться.
далее у вас есть |V|-1 возможностей: перейти к одному из каждого V\{v_1,v_2} [где v_2 - узел, выбранный в качестве второго] или остановка.
... [сделайте индукцию, чтобы формально доказать это здесь]
после того, как у вас есть путь n узлов, есть только одна возможность: остановка.
общее количество n*(n-1)*...*1 = n! возможных простых путей для каждой вершины и n*n! общее количество возможных простых путей в графе