Программа 16 Кирсанов М.Н,
Графы в Maple
Центроид дерева
| > | restart; with(networks): |
| > | n:=16: G:=void(n):# Пустой граф |
| > | addedges({{13,14},{11,12},{15,16},{6,7},{7,8},{8,4}},G): |
| > | addedges(Path(1,5,9,10,14,15,11,7,3,2),G): |
| > | nops(edges(G)):# Число ребер |
| > | r:=seq([seq(1+j+4*i,i=0..3)],j=0..3): |
| > | draw(Linear(r),G):# Рисунок |
| > | DL:=maxdegree(G): # Максимальная степень вершин |
| > | V:=Vector(DL): |
| > | for i to n do # Цикл для расчёта весов вершин |
| > | H:=duplicate(G):# Последовательное удаление вершин из копии G |
| > | H:=delete(i,H): |
| > | Di:=vdegree(i,G); |
| > | K:=components(H):# Список вершин каждой ветви: |
| > | for j to nops(K) do |
| > | V[j]:=nops(edges(induce(K[j],G)))+1; # Вес ветви |
| > | od: |
| > | W[i]:=max(seq(V[k],k=1..Di));# Вес вершины |
| > | od: |
| > | W:=convert(W,array);# Массив весов |
W := vector([15, 15, 14, 15, 14, 15, 10, 14, 13, 12, 8, 15, 15, 10, 8, 15])
| > | # Построим центроид: |
| > | minW:=min(seq(W[i],i=1..n));# Наименьший вес вершины |
minW := 8
| > | print("Центроид состоит из следующих вершин:"): |
| > | C:={}: |
| > | for i to n do |
| > | if W[i]=minW then |
| > | C:=C union {i}; |
| > | fi; |
| > | od: |
| > | print(C); |
"Центроид состоит из следующих вершин:"
{11, 15}