Докажите что дерево это двудольный граф

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

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

Любое дерево может быть задано его двоичным кодом. Код дерева имеет длину 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 и если 0<=s<=k, то существуетCCразличных бинарных деревьев вида (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 координат кода (k<2m) не превосходит числа нулей среди тех же координат. Длина кода дерева равна 2m, где m – число рёбер в дереве.

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

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

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

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

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

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

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

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

Двудольный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.

Содержание

Определение

Полный двудольный граф называется двудольным, если множество его вершин можно разбить на две части , , , так, что

• ни одна вершина в не соединена с вершинами в и
• ни одна вершина в не соединена с вершинами в

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

такой граф называется

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

Применения

• Factor graph
• Tanner graph

См. также

Ссылки

• Теория графов

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое «Двудольный граф» в других словарях:

двудольный граф — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN bipartite graph … Справочник технического переводчика

Двудольный граф (теория графов) — Биграф Биграф, двудольный граф или чётный граф это математический термин теории графов, который обозначает множество вершин и связей между ними, таких, что если множество вершин разбить на два непересекающихся подмножества U и V, то связи будут… … Википедия

ГРАФ ЭКСТРЕМАЛЬНЫЙ — граф, на к ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек рой одной числовой характеристики при ограничениях на другие числовые характеристики и… … Математическая энциклопедия

Граф ожидания — (или граф ожидания транзакций)  инструмент, используемый при разработке СУБД и многопоточных систем и используемый, в частности, для определения ситуации взаимной блокировки (deadlock). Фактически, граф ожидания транзакций представляет собой … Википедия

Двудольный ориентированный граф — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия

ГРАФ ПЛОСКИЙ — планарный граф, граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… … Математическая энциклопедия

ГРАФ ДВУДОЛЬНЫЙ — бихроматический граф, граф, множество вершин к рого можно разбить на два непересекающихся подмножества и , (т … Математическая энциклопедия

Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

Чётный граф (теория графов) — Биграф Биграф, двудольный граф или чётный граф это математический термин теории графов, который обозначает множество вершин и связей между ними, таких, что если множество вершин разбить на два непересекающихся подмножества U и V, то связи будут… … Википедия

Планарный граф — Планарный граф  граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим … Википедия

Докажите что дерево это двудольный граф

Напоминание. Лемма о рукопожатиях: количество вершин нечётной степени в графе — чётно.
Граф называется двудольным, если его вершины можно раскрасить в два цвета так, что не будет ребер с концами одинакового цвета. Вершины белого и чёрного цвета называются белой и чёрной долями соответственно.
(Понятно, что раскраска, в которой белый цвет заменили чёрным, а чёрный белым, также подходит. Поэтому важен не цвет каждой вершины, а то, в одну долю с какими вершинами она попала.)
Двудольный граф, в котором между долями проведены все возможные рёбра, называется полным двудольным графом. Он обозначается \(K_\), где n — число вершин в одной доли, а m — в другой.