Понятия диаметра, радиуса и центра графа представляют не только теоретический интерес, но и возникают естественным образом в приложениях. Отсутствие общих методов оценки метрических характеристик графа вынуждает разрабатывать для каждого отдельного класса графов свой особый метод, применимый, как правило, только к этому классу. Ранее авторами было введено метрическое свойство графа, называемое α_i-метрикой. Было показано, что многие метрические характеристики и свойства графа описываются в терминах α_i-метрики. Это позволяет свести задачу их определения к задаче нахождения минимального i, для которого граф обладает α_i-метрикой. Целью данного статьи является демонстрация эффективности такого подхода. В работе приведены основные определения и даны характеристики графов с α₀ и α_i-метриками. В частности, показано, что птолемеевы графы обладают α₀ -метрикой, а хордовые графы — α_i-метрикой. Доказано, что для конечных графов с α_i-метрикой справедлива оценка d(G)≥2r(G)-i-1, а для наследственных по расстоянию графов и некоторых важных подклассов класса хордовых графов справедлива даже оценка d(G)≥2r(G)-i. Также исследованы некоторые свойства центров графов с α_i-метрикой, где i≤2.

теория графов, метрические характеристики графа, эксцентриситет, α_i-метрика

Математические вопросы и теория численных методов