Связность графов. Теорема Менгера.

Граф G называется связным, если любые две его вершины соединены цепью или путем (в случае, если граф - ориентированный). Максимальный по включению вершин связный подграф называется компонентой связности k(G). Вершина графа - точка сочленения, если её удаление увеличивает число компонент связности графа. Вершина x связного графа тогда и только тогда является точкой связности, если найдутся 2 вершины x_i и х_j такие, что каждая цепь, соединяющая эти вершины, проходит через точку х. Мостом называется ребро, удаление которого увеличивает число компонент связности: n-k≤m≤(n-k)(n-k+1)/2.

Вершинной связностью графа называется наименьшее число вершин, удаление которых приводит к несвязному или нетривиальному графу. Если это число ᴂ(G) = 0 - граф несвязный, если 1 - одна точка сочленения. ᴂ(k_n)=n-1.

Реберная связность λ(G) - наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу. Если оно равно 1 - есть мост.

Для любого графа вершинная и реберная связности связаны соотношением: ᴂ(G) ≤ λ(G) ≤δ(G).

Если в графе две вершины соединены множеством цепей, то эти цепи наз. вершинно непересекающимися, если у них нет общих вершин кроме данных двух. Если две цепи, соединенные в x_i и х_j не имеют общих ребер - то они наз. реберно непересекающимися.

Теорема Менгера гласит: Пусть G — конечный неориентированный граф и x _i x_j— две несмежные вершины. Наименьшее число вершин, разделяющих x _i и x_j равно наибольшему числу вершинно непересекающихся цепей.

Раскраска вершин и ребер графа

Раскраской вершин графа в k цветов называется разбиение x на k непересекающихся подмножеств так, что в каждом подмножестве нет смежных вершин. Каждому подмножеству сопоставляется цвет. Все вершины соцветные в одном подмножестве. Раскраской ребер графа называется разбиение сигнатуры графа U на k непересекающихся подмножеств , таким образом при котором каждое подмножество не имеет ни одной пары сложных ребер. Граф G называется реберно k - раскрашиваемым, если его ребра можно раскрасить k красками таким образом, что никакие два смежных ребра не окажутся одного цвета. Хроматическим числом графа (G) называется минимальное число цветов, в которые можно раскрасить вершины графа так, чтобы концы любого ребра имели разные цвета. Граф G называется двудольным, если (G) ≤ 2.

Теорема о пяти красках.

Каждый планарный граф можно раскрасить с помощью пяти цветов так, что любые две смежные вершины будут окрашены в разные цвета.

Гипотеза о четырех красках

Каждый планарный граф можно раскрасить с помощью четырех цветов так, что любые две смежные вершины будут окрашены в разные цвета.

 

Гиперкубы

Гиперкубом (n-мерный куб) Hn называется граф, каждая вершина которого взаимнооднозначно соответствуют области пространства и 2 вершины соединены ребром, если они соответствуют соседним областям.

Свойства:

1) h(Hn) = 2 (2 цвета вершин)

2) Гиперкуб используется для вложения в производные графов с целью определения характеристик последних.

H(Hn) = n (цвет ребер)

Максимальная длина цепи: lmax = 2^n-1; d(Hn) = n;

Запрещенными фигурами для вписания графа в гиперкуб являются графы с циклами нечетной длины и К₂₃.

Граф называется вложенным в булевое пространство или кубируемым, если существует взаимнооднознозначное соответствие между вершинами графа и гиперкубом. Граф, который не вписывается в гиперкуб – некубируемый.

Число цепей, которое соединяет 2 произвольные вершины гиперкуба равняется n!