Об одном семействе оптимальных графов с заданными мерами связности

Теребин, Богдан Андреевич; Абросимов, Михаил Борисович

Об одном семействе оптимальных графов с заданными мерами связности

Теребин, Богдан Андреевич, Абросимов, Михаил Борисович

Дата публикации: 2022

Дата публикации в реестре: 2022-10-06T22:42:30Z

Аннотация:

Вершинной связностью k называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Рёберной связностью А нетривиального графа называется наименьшее число рёбер, удаление которых приводит к несвязному графу. Исследуются минимальные по числу рёбер n-вершинные графы, которые имеют заданные значения вершинной и рёберной связности. Помимо теоретического интереса, графы с заданными значениями вершинной или рёберной связности представляют и прикладной интерес как модели отказоустойчивых сетей. Основной результат состоит в том, что для определённой области значений k и А удалось описать графы, которые при заданном n имеют минимальное число рёбер.

Ключевые слова:
графы, вершинная связность, реберная связность, отказоустойчивость

Тип: статьи в журналах

Источник: Прикладная дискретная математика. Приложение. 2022. № 15. С. 116-119