5.3 Формула Кэли для подсчета всех помеченных деревьев
Основы перечислительной комбиаторики
5.3 Формула Кэли для подсчета всех помеченных деревьев
модуль 5.3 шаг 4
Построить последовательность Прюфера для дерева, показанного на предыдущем шаге. В качестве ответа введите числа через пробел.
Пример ввода: 3 3 1 1 1 1 1
Решение
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from matplotlib import pyplot as plt
import networkx as nx
G = nx.Graph([(1, 2),
(4, 3),
(3, 2),
(2, 5),
(6, 5),
(8, 7),
(9, 7),
(7, 5),
(5, 10),
(10, 11),
(11, 12),
(11, 13)])
while len(G.edges()) > 1:
leaves = [node for node in G.nodes() if len(list(G.neighbors(node))) == 1]
node_to_del = min(leaves)
print(list(G.neighbors(node_to_del))[0], end=' ')
G.remove_node(node_to_del)
nx.draw(G, with_labels=True)
plt.show()
Ответ
2 3 2 5 5 7 7 5 10 11 11
модуль 5.3 шаг 6
Какова степень вершины 2 в дереве, последовательность Прюфера которой имеет вид (1,7,2,2,2,2)?
Ответ 5
модуль 5.3 шаг 13
Построить деревья, отвечающие последовательностям Прюфера (1,2,3,4) и (3,3,3,3).
Ответ и решение
