Теорема Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K5 и K3,3. Деревья и лес. Дерево - с–язный граф без циклов. Лес (или ациклический граф) - н–ограф без циклов (может быть и несвязным).
Теорема. Для неографа G с n вершинами без петель следующие условия эквивалентны:
G - д–рево;
G - с–язный граф, содержащий n-1 ребро;
G - а–иклический граф, содержащий n-1 ребро;
Любые две несовпадающие вершины графа G соединяет единственная цепь.
G - а–иклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.
Остов (каркас) связного графа - д–рево, содержащее все вершины графа. Определяется неоднозначно. Редукция графа - о–тов с наибольшим числом ребер. Цикломатическое (или циклический ранг) число графа ν=m-n+c, где n - ч–сло вершин,m - ч–сло ребер, c - ч–сло компонент связности графа. Коциклический ранг (или коранг) ν*=n-c.
Теорема. Число ребер неографа, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно цикломатическому числу графа.
Неограф G является лесом тогда и только тогда, когда ν(G)=0. Неограф G имеет единственный цикл тогда и только тогда, когда ν(G)=1. Остов неографа имеет ν* ребер. Ребра графа, не входящие в остов, называются хордами. Цикл, получающийся при добавлении к остову графа его хорды, называется фундаментальным относительно этой хорды.
Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Очевидно, что для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v)- маршрут.
Теорема. Граф G=(V,E) связен тогда и только тогда, когда множество го вершин нельзя разбить на два непустых подмножества V1 и V2 так, чтобы бе граничные точки каждого ребра находились в одном и том же множестве. Всякий максимальный связный подграф графа G называется связной компонентой (или компонентой) графа G. Слово "ма«симальный" о»начает максимальный относительно включения, т.е. не содержащийся в связном подграфе с большим числом элементов. Множество вершин связной компоненты называется областью связности. Для ориентированного графа вводится понятие ориентированного маршрута – это последовательность вида (1), в которой ei=(vi,vi+1). Аналогом цепи в этой итуации служить путь (ориентированная цепь). Аналогом цикла служит контур ориентированный цикл).
Орграф называется сильносвязным, если любые две его вершины достижимы руг из друга. Орграф называется одностороннесвязным, если для любой пары его вершин по меньшей мере одна достижима из другой. Орграф называется слабосвязным, если любые две вершины его основания соединены маршрутом. Орграф называется несвязным, если его основание несвязный псевдограф.
Теорема. Орграф является сильносвязным тогда и только тогда, когда в нем есть основной циклический маршрут.
Необходимость. Пусть G – сильносвязный орграф и T=(v0, x1, v1, ..., xn, v0) – его циклический маршрут, проходящий через максимально возможное число вершин. Если этот маршрут не является остовным, то возьмем вне его вершину v. Так как G – сильносвязный орграф, то существуют маршруты T1=(v0, y1, ..., v), T2=(v, z1, ..., v0). Но тогда циклический маршрут T’=(v0, x1, v1, ..., xn, v0, y1, ..., v, z1, ..., v0) содержит большее число вершин, чем T, что противоречит выбору маршрута T. Следовательно, T – остовной маршрут.
Достаточность. Пусть u и v – две произвольные вершины орграфа G, а T=(v0, x, ..., v, y, ..., u, z, ..., v0) – циклический маршрут. Тогда u достижима из v с помощью маршрута (v, y, ..., u) – части маршрута T, – а v из u – с помощью маршрута (u, z, ..., v0, x, ..., v).3
Теорема. Орграф является одностороннесвязным тогда и только тогда, когда в нем есть остовной маршрут.
Теорема. Орграф является слабосвязным тогда и только тогда, когда в его основание есть связный псевдограф.
Сильносвязной компонентой орграфа называется его максимальный относительно включения сильносвязный подграф.
Матричное представление графов
Орграфы и матрицы. Матрицей сложностей A (D) орграфа D называется (рхр)-матрица \аи\> У которой ai}=\, если vfl,— дуга орграфа D, и atj~Q в противном случае. Сумма по столбцу легко проверить, что суммы элементов по строкам матрицы A (D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам — полустепеням захода. Как и в случае графов, степени матрицы смежностей. А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую. Есть еще три матрицы, связанные с орграфом D — матрица достижимостей, матрица расстояний и матрица обходов. Матрицу достижимостей орграфа можно использовать для нахождения его сильных компонент. Формула для числа остовных входящих деревьев данного орграфа была найдена BOTTOM и Мейберри, а доказана Таттом. Чтобы сформулировать этот результат, известный как матричная теорема о деревьях для орграфов, введем еще матрицы, связанные с D. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента 1-й строки матрицы Mod равно числу остовных входящих деревьев, у которых вершина vt является стоком. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента j-го столбца матрицы Mid равно числу остовных выходящих деревьев, у которых вершина Vj является источником. Эйлеров контур в орграфе D — это замкнутый остовный маршрут, в котором каждая дуга орграфа D встречается по одному разу. Орграф называется эйлеровым, если в нем есть эйлеров контур. Для графов, можно легко показать, что слабый орграф D эйлеров тогда и только тогда, когда у каждой его вершины полустепень захода равна полустепени исхода. Сформулируем теперь теорему, в которой дается формула для числа эйлеровых контуров в эйлеровых орграфах. Эту теорему можно доказать очень изящно с помощью матричной теоремы о деревьях для орграфов; В эйлеровом орграфе число эйлеровых контуров равно с \ (d,-—1)! Заметим, что для эйлерова орграфа МоА=М\А и все суммы и по строкам, и по столбцам равны нулю, так что все алгебраические дополнения равны между собой. Первый орграф с тремя вершинами называется транзитивной тройкой, второй — циклической тройкой.
Орграф называется строго слабым, если он слабый и не односторонний; строго односторонним, если он односторонний и не сильный. Пусть С0— класс всех несвязных орграфов, GI— класс всех строго слабых орграфов, С2— класс всех строго односторонних орграфов и Ся— класс всех сильных орграфов. Тогда максимум и минимум числа q дуг среди всех орграфов с р вершинами, относящихся по соединимости к категории С;, i=0, 1, 2, 3,. Орграф, являющийся декартовым произведением DjXZ^ двух орграфов, имеет VjX У2 в качестве множества вершин, и вершина («j, и2) смежна к вершине (уь у2) тогда и только тогда, когда или [ui=0i и u, adj гл2], или \u. Если орграф D относительно соединимости находится в категории С„, то будем писать c(D)=n. Ни один строго слабый орграф не содержит вершину, удаление которой приводит к сильному орграфу.
Реберный орграф L(D) имеет множество всех дуг данного орграфа D в качестве множества вершин, и две его вершины х и у смежны тогда и только тогда, когда дуги х к у порождают маршрут в орграфе D. Выразить число вершин и число дуг орграфа L(D) через соответствующие величины орграфа D. Реберный орграф L (D) слабого орграфа D изоморфен самому орграфу D тогда и только тогда, когда D или D' — функциональный орграф. Если D — несвязный орграф, то утверждение, содержащееся в предыдущем упражнении, не верно. Пусть S и Т — непересекающиеся множества вершин орграфа D, а X (S, Т) — множество всех дуг, идущих из S в Т. Орграф D реберный тогда и только тогда, когда не существует множеств 5 и Т, имеющих по две вершины и таких, что \Х (S,T)|=3. Число эйлеровых путей орграфа D равно числу гамильтоновых контуров реберного орграфа L(D]. Пусть орграф 7\ состоит из одной вершины с двумя ориентированными петлями. Пусть T2=L(T1) — реберный орграф (здесь, если быть более точным, нужно использовать термин «псевдоорграф») орграфа Тг, определенный естественным образом; рекурсивно определяется Tn=L(Tn,l). (Такие орграфы Т„ известны под названием «телетайпных диаграмм».) Тогда число эйлеровых путей в орграфе Т„ равно 22""1-1. Каждый орграф, у которого id (v)^p/2, od (v)^p/2 для любой вершины v, гамильтонов.
Рассмотрим орграфы, у которых для любой вершины и сумма ^d(u, v) расстояний от этой вершины до всех остальных постоянна. Найти среди этих орграфов орграф, не являющийся вершинно-симметрическим. Орграф D, его дополнение D и обратный к нему D' имеют одну и ту же группу (автоморфизмов). Пусть А—матрица смежностей реберного орграфа полного симметрического орграфа.
Два орграфа называются коспектральными, если их матрицы смежностей имеют один и тот же характеристический многочлен. Существуют в точности три различных коспектральных сильных орграфа с четырьмя вершинами.
Орграф, называемый конъюнкцией D=Dl/\D2 двух орграфов Z)j и D2, имеет в качестве множества вершин K=V1XV2, и вершина u=(u1, ы2) смежна к вершине v=(v-L,v2) тогда и только тогда, когда %adj г,^ в орграфе Dl и ы2 adj v.
Матрица смежностей А конъюнкции D=Dl/\D2 есть тензорное произведение матриц смежностей орграфов D1 и D2. Пусть Dl и D2— два орграфа, a d,-— наибольший общий делитель длин всех простых контуров орграфа D,-, t=l,2. Конъюнкция Dlf\D^ является сильным орграфом тогда и только тогда, когда Ог и D2 — сильные орграфы, a d1 и d2 взаимно просты.
Орграф называется примитивным, если какая-нибудь степень его матрицы смежностей целиком состоит из положительных чисел. Орграф примитивен тогда и только тогда, когда длины его простых контуров имеют наибольший общий делитель, равный 1. Пусть D — примитивный орграф. Аналогично для вершин и и v орграфа из и в v. Исключение составляют (3,3)-орграф и (4,6)-орграф. П2, составленной Обершельпом , приведены числа орграфов с р вершинами, Эти числа вычислены с помощью соотношения (15. L(D) реберный орграф орграфа D.