Изменения
Нет описания правки
'''Диаметр дерева''' - максимальная длина кратчашего кратчайшего пути между любыми двумя вершинами.
Алгоритм в этой статье находил диаметр в дереве,при чём очень простым алгоритмом.
void diameter(graph g)
{
v = u = w = 0;
bfs(v);// заполняет массив d[n] расстояниями до всех вершин.
for(i = 0; i < n; i++)
if (d[i] > d[u])
Доказательство: пусть нет, пусть искомое расстояние - есть расстояние между вершина a, b, где b - не является листом.Т.к. b не является листом, то значит её степень > 1 => из неё существует ребро в непосещенную вершину (дважды посетить вершину b мы не можем). Лемма доказана.
Запустив BFS от случайной произвольной вершины. Мы получим дерево BFS.
Теорема. В дереве BFS не существует ребер между вершинами из разных поддеревьев некоторого из общего предка.
Доказательство как про дерево DFS.
