Экстремальные оценки индекса Винера для слабо связных ориентированных графов

Аннотация

В статье рассматривается индекс Винера для слабо связных ориентированных графов. Для таких графов из-за слабой связности не всегда определено расстояние $d(u,v)$ между вершинами $u$ и $v$, что требует уточнения чтобы индекс Винера имел содержательный смысл. Достаточно хорошо изучен случай, когда полагают что $d(u,v)=0$ при отсутствии пути между вершинами. Мы рассматриваем уточнение, когда $d(u,v)$ равно количеству вершин в графе при отсутствии пути между вершинами $u$ и $v$. В статье представлены графы на $n$ вершинах, где индекс Винера с таким уточнением достигает минимального и максимального значения. Мы также представляем результаты экспериментов, которые показывают как изменяется индекс Винера (с учетом обоих способов уточнения расстояния) при добавлении дуг в слабо связный ориентированный граф как фиксированной, так и случайной структуры.