Cтраница 1
Реберная связность - наименьшее число ребер, которое приводит к несвязному графу. [1]
Наибольшая реберная связность ( р, q) - графа равна его наибольшей связности. [2]
Аналогично реберная связность KK ( G) графа G определяется как наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу. [3]
Связностью и ( реберной связностью К) графа G называется наименьшее число вершин ( ребер), после удаления которых получаем несвязный или тривиальный граф. Таким образом, число графов со связностью п равно разности между числом тг-связных графов и числом ( тг 1) - связных графов. [4]
В каждом кубическом графе связность и реберная связность равны. [5]
Анализ приведенных рассуждений показывает, что подобным образом можно установить реберную связность множества слабо эффективных вершин. [6]
Числом вершинной связности % ( G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному графу. Числом реберной связности ЦС) графа G называется наименьшее число ребер, удаление которых приводит к несвязному графу. [7]
Граф G является fe - связным тогда и только тогда, когда любая пара его вершин соединена по крайней мере fe вершинно непересекающимися цепями. Аналогичные теоремы справедливы и для реберной связности. Граф fe - реберно связен тогда и только тогда, когда любая пара его вершин соединена по крайней мере fe реберно непересекающимися цепями. Множество ребер, удаление к-рых приводит к несвязному графу, наз. [8]
Поэтому 6 ( G) [ 2q / p ], так что x ( G) l2q / p ] в силу теоремы 5.1. Для того чтобы показать, что средняя величина может действительно достигаться, достаточно построить соответствующее семейство графов. То же самое построение дает также ( р, - графы с наибольшей реберной связностью. [9]
Связность графов - понятие в теории графов довольно интуитивное, обобщающее такие ранее введенные понятия, как точка сочленения, мост и блок. При исследовании вопроса о том, какой из двух графов более связен, полезны два инварианта, называемые связностью и реберной связностью. [10]
Минимальное число вершин ( и соединяющих их ребер) графа G, удаление которых из О приводит либо к несвязному графу, либо к тривиальному графу с одной вершиной; в случае k - связных графов должно быть удалено, по меньшей мере, k вершин. Описанное выше свойство иногда называют вершинной связностью, чтобы отличать его от реберной связности, которая по аналогии представляет собой - мичк-мальное число ребер, удаление которых из G приводит к несвязному или три виальному графу. [11]
Кирхгофа A W) графа а & ( Вц) - Г х) - шури-ца ( О, I, - 1) - инцвдвнций произвольной ориентации G заданного помеченного графа G, такая, что ее элемент: , если дута Ui внхсщйт из вершины гт /, В if - I, если И захсдат э, и Л / 0 во всех остальных случаях. Матрицу К мовго представить в виде К 5 3, следовательно, ее собствен ные значения неотрицательны и наименьшее из них всегда равно нулю. Замечательным свойством спектра матрицы К является то, что второе минимальное собственное значение хС ( G) во многом определяет свойства вершинной и реберной связности графа. [12]
Только совсем недавно стала изучаться задача о разделении графа с помощью удаления смешанного множества вершин и ребер. Парой связностей графа G называется упорядоченная пара ( а, Ь) таких целых неотрицательных чисел, что найдется множество, содержащее а вершин и b ребер, удаление которых делает граф несвязным, и не найдется множества с а - 1 вершинами и b ребрами или а вершинами и b - 1 ребрами, обладающего тем же свойством. В частности, упорядоченные пары ( х, 0) и ( О, Я) являются парами связностей графа G, так что понятие пары связностей обобщает оба понятия вершинной связности и реберной связности графа. Легко видеть, что для каждого значения а, О а х, существует единственная пара связностей ( а, Ьа); таким образом, граф G имеет в точности x - j - 1 пар связностей. [13]
Обобщив одну раннюю работу Вайнстейна ( 1963, 1974), Боллобаш и Элдридж ( 1976) получили более благозвучные результаты, но формулировать их еще труднее, чем результаты Хватала и Хансона. Поэтому мы милостиво отказываемся от их полного изложения. Достаточно сказать, что эти два автора определили и вычислили функции тп ( р, 8, Д), т ( р, 8, Д х) и т ( р, 8, Д А), где х и А - вершинная и реберная связности и где, например, т ( р, 8, Д, А) есть минимальный размер наибольшего паросочетания в произвольном графе с р вершинами, с минимальной и максимальной степенями 6 и Д соответственно и с реберной связностью А. [14]
Теперь зададимся вопросом о том, насколько велико может быть паросочетание вообще. Это, конечно, слишком общая постановка вопроса. В каких терминах оценивают размер паросочетания. Среди наиболее приемлемых параметров графа, которые сразу же приходят на ум, - число вершин, число ребер, минимальная степень, максимальная степень, вершинная связность, реберная связность. [15]