Все деревья двудольные графы

Двудольный граф

Двудольный граф позволяет, в частности, представлять бинарные отношения .

Резюме

Характеристика

Есть несколько способов охарактеризовать двудольный граф.

По хроматическому номеру Двудольные графы — это графы, хроматическое число которых меньше или равно 2. По длине циклов Граф двудольный тогда и только тогда, когда он не содержит нечетного цикла .

Предположим, что граф разбит на две части и такое, что любое ребро соединяет вершину графа с вершиной графа . Рассмотрим любой цикл. Этот цикл проходит поочередно через две части и до прихода в начальной вершине и , следовательно , имеет четное длину. U V U V U V

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

Обратное показать труднее. Предположим, у нас есть граф, в котором есть только циклы четной длины. Для простоты давайте также предположим, что он подключен (если его не было, мы могли бы рассуждать индивидуально о каждом подключенном компоненте). грамм грамм

Как уже упоминалось, у него есть остовное дерево . Обозначим корень этого дерева. Давайте создадим два множества вершин и выглядит следующим образом : грамм Т р U V

• U содержит и все вершины из четного числа ребер ; р Т р
• V содержит вершины, являющиеся нечетным числом ребер из . Т р

Множества вершин и не пересекаются и содержат все вершины из . Однако этого недостаточно, чтобы показать, что это двудольное: действительно, ничто априори не гарантирует, что у нас нет «лишнего» ребра, которое, например, соединяет две вершины . U V грамм грамм грамм U

Рассмотрим две вершины и de в одной части ( или ), соединенные ребром . Путь, который соединяется с in , обязательно должен быть одинаковой длины по конструкции и из . Если добавить ребро , получится цикл нечетной длины, что запрещено предположением. Икс у грамм U V е Икс у Т U V е

Следовательно, невозможно иметь такие вершины и соединять их «коротким замыканием». Все ребра графа соединяют вершины графа с вершинами графа , что в итоге показывает, что граф является двудольным. Икс у U V грамм

По спектру Если граф двудольный, то его спектр удовлетворяет следующему свойству: Если это собственное значение из матрицы смежности графа, то также собственное значение , с той же кратностью , что и . λ — λ λ По многогранникам Граф является двудольным тогда и только тогда, когда его стабильный многогранник описывается ограничениями клики размера 2.

Частные двудольные графы

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

Кроме того, мы определяем следующие двудольные графы:

• Двудольный граф называется полным двудольным (или снова называется бикликой ), если каждая вершина графа соединена с каждой вершиной графа . U V
• Двудольный граф называется бирегулярным, если все вершины графа имеют одинаковую степень и если все вершины графа имеют одинаковую степень. U V
• В двудольных графах Кнезера представляют собой семейство двудольных графов для описания включения между множествами.
• 110-граф Иофинова-Иванова

Примечания и ссылки

1. ↑ (in) Армен С. Асратян, Тристан Дж. Денли и Роланд Хэггквист , « Двудольные графы и их приложения » , Cambridge Tracts in Mathematics , Cambridge University Press, Vol. 131, 1998 г. ( ISBN9780521593458 ) , Теорема 2.1.3, с. 8. Авторы приписывают эту характеристику Денесу Кёнигу в статье 1916 года.
2. ↑ (in) Норман Биггс , Алгебраическая теория графов , Издательство Кембриджского университета , 1994 г. , 2- е изд. , 205 с. ( ISBN978-0-521-45897-9 , читать онлайн ) , стр. 53 .

Смотрите также

Статьи по Теме

Источник

Деревья и двудольные графы

В двудольном граф циклы, если они есть, имеют чётную длину. Дерево – это связный двудольный граф (без циклов, естественно) Если доли вершин двудольного графа перемешаны, то можно по рисунку графа эти доли определить. Надо взять любую вершину и пометить её, как принадлежащую к первой доле (буквой А, например). Тогда все смежные к этой вершине вершины будут из второй доли (буква Б), и, в свою очередь, смежные к вершинам второй доли вершины будут из первой доли, и так далее. Таким же способом можно определять и «двудольность» произвольного графа. Если вершины одной доли смежны, то это не двудольный граф.

Любое дерево может быть задано его двоичным кодом. Код дерева имеет длину 2mи состоит изmнулей иmединиц. Для любого начального отрезка кода дерева число единиц в нём не больше числа нулей. Код дерева всегда начинается с 0 и заканчивается 1. Код дерева зависит от того, какую вершину мы выберем в качестве корня. Дерево с одним ребром и двумя вершинами имеет код 01. Каждое ребро дерева имеет в коде свой ноль и свою единицу, причем единица всегда находится в коде далее нуля. Код получается в результат обхода дерева. Обход начинается и заканчивается в корне дерева. Если ребро дерева встречается при обходе первый раз, то в коде появляется 0 этого ребра, а если второй (и последний), то в коде появляется 1 этого ребра. Например, цепочка из 5 вершин (C) является простейшим деревом и имеет код 00001111.

Колесо с nвершинами (W) имеет одну вершину степениn-1 в центре (ось колеса) иn-1 вершину степени три по окружности колеса. У колеса есть спицы (рёбра, выходящие из оси колеса)..W=K, например, (тетраэдр).

Число Каталана – это число бинарных деревьев с nвершинами. Бинарное дерево сn=0 – это пустое дерево, а сn>0 вершинами – это тройка Д=(Л, К, П), где К – вершина, называемая корнем дерева, Л – левое поддерево с Л вершинами и П – правое поддерево с П вершинами иn=Л+1+П. С— число различных бинарных деревьев сkвершинами (число Каталана).C=C=1 и если 0Cразличных бинарных деревьев вида (s, К,k-1-s). s принимает значения от 0 доk-1, и, значит, С=CС+CС+ . . . + СCиk>0. С помощью производящей функции получается, что С=C/(k+1).

Остовное дерево связного графа содержит все его вершины и некоторые рёбра. Для получения остовного дерева в графе находят цикл и убирают из него произвольное ребро. Затем опять находят цикл и убирают ребро, пока циклов в графе не останется. Остовных деревьев может быть несколько. Цикломатическое число графа – это число рёбер, которые надо удалить из графа, чтобы превратить граф в лес (в дерево, если граф связен).=p+m-n. Цикломатическое число леса (и дерева) равно нулю.

Задания по деревьям и двудольным графам

Определить число попарно различных двудольных графов с а) n=6 m=8; б) n=5 m=9; в) n1=3 n2=4 m=9. n=n1+n2

Доказать, что существует ровно 6 неизоморфных деревьев с 6 вершинами и 11 – с 7 вершинами.

Доказать, что во всяком дереве с n>1 вершинами содержится не менее 2 висячих вершин.

Пусть n1 – число висячих вершин n-вершинного дерева, не содержащего вершин степени 2. Доказать, что n1>n/2.

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

Изобразить все попарно неизоморфные деревья: а) с 6 рёбрами и 3 висячими вершинами; б) с 6 рёбрами и 4 висячими вершинами; в) с 7 рёбрами и 3 висячими вершинами; г) с 8 рёбрами и 3 вершинами степени 3.

Подсчитать число попарно неизоморфных 7-вершинных деревьев, у которых сумма квадратов степеней вершин меньше 27.

Существуют ли двудольные кубические (регулярные, степени 3) графы? Нарисовать, если да. Может ли быть различным число вершин в долях в регулярном двудольном графе?

Если графы G и H (без петель и кратных рёбер) изоморфны, то для каждого d>-1 число вершин степени d в графах G и H одинаково. Показать, что а) это условие (подчёркнуто выше) является достаточным для изоморфизма графов с 4 и менее вершинами; б) условие не является достаточным для изоморфизма графов с 5 и более вершинами, причём, если число вершин не менее 6, то даже для деревьев.

Описать и нарисовать все графы, являющиеся деревьями вместе со своими дополнениями.

Построить все попарно неизоморфные растущие деревья (в них существует источник с полустепенью захода, равной нулю) с а) 4 вершинами; б) 5 вершинами; в) 6 вершинами, не содержащие ориентированных цепей длины, превосходящей 3.

Доказать, что слабо связный орграф является растущим деревом (в нём существует источник с полустепенью захода, равной нулю) тогда и только тогда, когда лишь одна его вершина имеет нулевую полустепень захода, а полустепень захода любой из остальных вершин равна 1.

Построить дерево по его коду: а) 0010100111; б) 00110101000111; в) 0000010011011111;

По вектору установить, является ли он кодом дерева (если да, то построить дерево): а) 001011; б) 110 0110; в) 001001; г) 010011; д) 00111001; е) 0001100111.

Доказать по индукции, что для каждого дерева в его коде число нулей совпадает с числом единиц, и число единиц среди первых k координат кода (km) не превосходит числа нулей среди тех же координат. Длина кода дерева равна 2m, где m – число рёбер в дереве.

Длина кода дерева равна 2m, где m – число рёбер в дереве. В коде дерева m нулей и m единиц, код начинается с нуля и заканчивается единицей. Пусть f(m) – количество различных кодов деревьев с m рёбрами. Доказать: а) f(m)+1; б)f(m)+1; в) f(m)+1.

Длина кода дерева равна 2m, где m – число рёбер в дереве. В коде дерева m нулей и m единиц, код начинается с нуля и заканчивается единицей. Пусть f(m) – количество различных кодов деревьев с m рёбрами. Доказать: f(m)=. f(0)=f(1)=1

Вершина корневого дерева называется висячей,

если она отлична от корня и имеет степень, равную 1. а) у дерева k висячих вершин и нет вершин степени 2, отличных от корня. Доказать, что при k>1 n

Диаметр дерева – длина максимальной простой цепи в нём. Доказать, что в дереве с нечётным диаметром любые две простые цепи максимальной длины имеют хотя бы общее ребро. А с чётным?

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

Расстояние между вершинами – это длина кратчайшей цепи, соединяющей их. Диаметр графа – это max расстояний в нём. а) для каждого d>2 указать граф, диаметр которого равен d, а диаметр любого его связного остовного (содержащего все вершины графа) дерева равен 2d.

Вычислить цикломатическое число а) полного графа с n вершинами (K); б) полного двудольного графа сn1 и n2 вершинами в долях (K); в) пустого графа сn вершинами (n изолированных вершин — N); г) колеса сn вершинами (W); д) платоновых графов: тетраэдра (K), куба, октаэдра, додекаэдра; е) графа Петерсена; ж) любого связного регулярного степениr (степени всех вершин равны r) графа с n вершинами.

Остовное дерево графа содержит все вершины графа и некоторые его рёбра. Найти остовное дерево: а) полного графа с 5 вершинами (K); б) полного двудольного графа с тремя вершинами в каждой из долей (K); в) колеса с 5 вершинами (W); г) циклического графа с 6 вершинами (C); д) графа Петерсена; е) платоновых графов: тетраэдра (K), куба, октаэдра, додекаэдра.

Остовное дерево графа содержит все вершины графа и некоторые его рёбра. Пусть T1 и T2 – остовные деревья графа G. Доказать, что для каждого ребра e из T1 существует ребро f из T2, и если в T1 заменить e на f, то получим опять остовное дерево графа G. Доказать, что T1 можно перевести в T2 , меняя по очереди рёбра из T1 на рёбра из T2.

Приведите примеры (когда это возможно) а) регулярного (степени всех вершин равны) двудольного графа; б) двудольного платонова графа (тетраэдр (K), куб, октаэдра, додекаэдр); в) бесконечного двудольного графа.

Что можно сказать о дополнении полного двудольного графа? Дополнение графа – это граф с те ми же вершинами и с рёбрами, которых нет в самом графе. Опишите матрицу смежности двудольного графа. Что можно сказать о матрицах смежности двудольного графа и его дополнения?

Люди – это вершины, а знакомых людей связывает ребро. Доказать, что среди 6 человек всегда найдутся 3 таких, которые либо все знают друг друга (цикл длины 3), либо ни один из них не знает двух других.

G – двудольный граф с наибольшей степенью вершин d. Покажите, что существует двудольный граф G1(v1,v2), в котором v1 и v2 содержат одинаковое число вершин и G1 — регулярный граф степени d, причём G – это подграф G1. Показать алгоритм построения G1 из G.

Расстояние между вершинами – это длина кратчайшей цепи, соединяющей их. Диаметр графа – это max расстояний в нём. Диаметр дерева – длина максимальной простой цепи в нём. Доказать, что для каждого связного графа существует его остовное дерево, диаметр которого не более чем в два раза превосходит диаметр графа.

Источник