Yurii Nosov » Публикация

Поделиться публикацией:

Опубликовано 2014-09-15 Опубликовано на SciPeople2020-05-03 20:05:39 ЖурналПрикладная дискретная математика

Индекс Винера максимальных внешнеплоских графов

Носов Ю.Л. / Yurii Nosov

ПДМ, 2015, 3(29), С.95–109. УДК 519.17;

Аннотация Рассматривается инвариант W(G) связных неориентированных графов G, равный сумме расстояний между всеми парами вершин графа G. Предлагается эффективный алгоритм расчёта матрицы расстояний и индекса Винера максимальных внешнеплоских графов с большим количеством вершин. Временная сложность алгоритма O(n2). Алгоритм удобен как для ручного расчёта индекса Винера небольших графов, так и для расчёта индекса Винера графов, сгенерированных компьютерной программой.