Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №3, Москва, 1991
Авторы: Юшманов С.В., Чепой В.Д.
Один общий метод изучения метрических характеристик графа, связанных с эксцентриситетом
Аннотация:
Понятия диаметра, радиуса и центра графа представляют не только теоретический интерес, но и возникают естественным образом в приложениях. Отсутствие общих методов оценки метрических характеристик графа вынуждает разрабатывать для каждого отдельного класса графов свой особый метод, применимый, как правило, только к этому классу. Ранее авторами было введено метрическое свойство графа, называемое αi-метрикой. Было показано, что многие метрические характеристики и свойства графа описываются в терминах αi-метрики. Это позволяет свести задачу их определения к задаче нахождения минимального i, для которого граф обладает αi-метрикой. Целью данного статьи является демонстрация эффективности такого подхода. В работе приведены основные определения и даны характеристики графов с α0 и αi-метриками. В частности, показано, что птолемеевы графы обладают α0 -метрикой, а хордовые графы — αi-метрикой. Доказано, что для конечных графов с αi-метрикой справедлива оценка d(G)≥2r(G)-i-1, а для наследственных по расстоянию графов и некоторых важных подклассов класса хордовых графов справедлива даже оценка d(G)≥2r(G)-i. Также исследованы некоторые свойства центров графов с αi-метрикой, где i≤2.
Ключевые слова:
теория графов, метрические характеристики графа, эксцентриситет, αi-метрика
Язык публикации: русский,  страниц: 16 (с. 217-232)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке: Сведения об авторах:
  • Юшманов Сергей Владимирович
  • Чепой Виктор Дмитриевич