On the optimality of graph implementations with prescribed connectivities.pdf 1. Условие Уитни Связные графы имеют важнейшее значение с точки зрения прикладной теории графов. Две основные меры связности графа - вершинная k и рёберная Л. Вершинной связностью k графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Рёберная связность Л графа G определяется как наименьшее количество рёбер, удаление которых приводит к несвязному или тривиальному графу. Основные определения используются по работе [1]. Вершинная связность графа k, его рёберная связность Л и минимальная степень вершины 8 связаны неравенством Уитни [2]: Теорема 1 [2]. Для любого графа G справедливо неравенство k ^ Л ^ 8. Результат теоремы является неулучшаемым: Теорема 2 (Чартрэнд, Харари [3]). Для любых натуральных чисел a, b, c, таких, что a ^ b ^ c, существует граф G, у которого k = a, Л = b, c = 8. Из доказательства теоремы 2 следует, что для любых a, b, c можно построить граф с числом вершин 2(c + 1) и числом рёбер c(c + 1) + b. Предлагается схема построения соответствующего графа: необходимо взять два полных графа Kc+1, в одном выбрать a вершин, в другом - b вершин и соединить выбранные вершины b рёбрами. Возникает вопрос: можно ли для заданных k = а, Л = b, c = 6 построить граф с меньшим числом вершин и рёбер? Оказывается, что в некоторых случаях это действительно возможно, что и является предметом исследования данной работы. 2. Основные результаты Результат теоремы 2 можно улучшить не всегда, поэтому общий случай а ^ b ^ c разделим на следующие неравенства: 1) а ^ b < c; 2) а = b = c; 3) а < b = c. Для первого случая оказалось, что результат теоремы 2 является оптимальным по числу вершин: Теорема 3. Граф с наименьшим количеством вершин, удовлетворяющий условию Уитни при а ^ b < c, является графом с числом вершин 2(c + 1). Однако число рёбер может быть меньше. Следующий пример иллюстрирует данный случай. Пример 1. Пусть а = b = 4, c = 5, т. е. k = Л = 4, 6 = 5. Количество вершин равно 2(c + 1) = 2(5 + 1) = 12. Количество рёбер в реализации из теоремы 2 должно быть c(c + 1) + b = 34. На рис. 1 изображён граф, построенный по теореме 3, с числом рёбер 30. Рис. 1 В двух остальных случаях результат теоремы 2 может быть улучшен и по числу вершин. Второй случай является достаточно тривиальным: Теорема 4. Граф с наименьшим количеством вершин, удовлетворяющий условию Уитни при а = b = c, является полным графом с числом вершин c + 1 . Наиболее интересным оказался третий случай, для которого удалось получить следующий результат: Теорема 5. Граф с наименьшим количеством вершин, удовлетворяющий условию Уитни при а < b = c, является графом с числом вершин 2(c +1) - а. Доказательство теоремы также является конструктивным и предлагает схему построения соответствующего графа. Следует отметить, что в общем случае можно построить несколько реализаций с числом вершин, как в теореме 5, но с разным числом рёбер. Схема из теоремы 5 позволяет строить граф не только с минимальным числом вершин, но и с минимально возможным числом рёбер. Теорема 6. Граф с наименьшим количеством рёбер, удовлетворяющий условию Уитни при а < b = c, является графом с числом рёбер c2 - а2 + а + c + а, где _ 0, если [(2а2 - аc - 2а)/2] ^ 0, [(2а2 - ac - 2а)/2] иначе. Следующий пример иллюстрирует этот случай. Пример 2. Пусть a = 4, b = c = 5, т. е. k = 4, Л = 5 = 5. Данный случай удовлетворяет условию теорем 5 и 6. Согласно теореме 5, количество вершин равно 2(c +1) - a = 2(5 + 1) - 4 = 8. Найдем значение а: а = |(2a2 - ac - 2a)/2] = [(36 - 20 - 8)/2] = 2. Тогда число рёбер равно c2 - a2 + a + c+а = 25 -16 + 4 + 5 + 2 = 20. На рис. 2 изображён соответствующий граф. Рис. 2

Скачать электронную версию публикации