Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. I.Задания части А
  2. I.Способы задания графов. Степени вершин, матрицы инцидентности и смежности.
  3. II. Задания на множественный выбор.
  4. II. Задания на множественный выбор.
  5. II. Оснащение транспортных средств тахографами
  6. А. Пример тестового задания для текущего контроля знаний
  7. А.Д. В чем летали на задания?
М. Определить число попарно различных двудольных графов с а) 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; г) 01001000110111; д) 00100010110111; е) 00010111010000101111.
У. По вектору установить, является ли он кодом дерева (если да, то построить дерево): а) 001011; б) 110 0110; в) 001001; г) 010011; д) 00111001; е) 0001100111.
Ф. Множество векторов разбить на классы так, чтобы каждый класс состоял из кодов попарно изоморфных деревьев: а) {0100101101, 0101000111, 0001110101, 0101001011, 010001101}; б) {010001011011, 000110011101, 001001011101, 010010010111, 010001100111}; в) {0011010011, 0100110011, 00100110101, 0100101101, 0011001101}.

 

Х. Доказать по индукции, что для каждого дерева в его коде число нулей совпадает с числом единиц, и число единиц среди первых k координат кода (k<2 m) не превосходит числа нулей среди тех же координат. Длина кода дерева равна 2 m, где m – число рёбер в дереве.
Ц. Длина кода дерева равна 2 m, где m – число рёбер в дереве. В коде дерева m нулей и m единиц, код начинается с нуля и заканчивается единицей. Пусть f(m) – количество различных кодов деревьев с m рёбрами. Доказать: а) f(m)<4 +1; б) f(m)<C +1; в) f(m)<C +1.
Ч. Длина кода дерева равна 2 m, где m – число рёбер в дереве. В коде дерева m нулей и m единиц, код начинается с нуля и заканчивается единицей. Пусть f(m) – количество различных кодов деревьев с m рёбрами. Доказать: f(m)= . f(0)=f(1)=1 (Число Каталана)
Ъ. Вершина корневого дерева называется висячей, если она отлична от корня и имеет степень, равную 1. а) у дерева k висячих вершин и нет вершин степени 2, отличных от корня. Доказать, что при k>1 n<2 k+1; б) пусть степени всех n вершин, кроме корня, не превышают 3, а степень корня не превышает 2. Доказать, что число висячих вершин не больше n/2.
S. Диаметр дерева – длина максимальной простой цепи в нём. Доказать, что в дереве с нечётным диаметром любые две простые цепи максимальной длины имеют хотя бы общее ребро. А с чётным?
Я. Доказать, что некорневое дерево однозначно с точностью до изоморфизма восстанавливается, если заданы все попарные расстояния между его висячими вершинами.
Ю. Расстояние между вершинами – это длина кратчайшей цепи, соединяющей их. Диаметр графа – это max расстояний в нём. а) для каждого d>2 указать граф, диаметр которого равен d, а диаметр любого его связного остовного (содержащего все вершины графа) дерева равен 2 d.
Ы. Вычислить цикломатическое число а) полного графа с 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.
G. Расстояние между вершинами – это длина кратчайшей цепи, соединяющей их. Диаметр графа – это max расстояний в нём. Диаметр дерева – длина максимальной простой цепи в нём. Доказать, что для каждого связного графа существует его остовное дерево, диаметр которого не более чем в два раза превосходит диаметр графа.
С. Построить коды деревьев:    

 

 


Дата добавления: 2015-10-13; просмотров: 629 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Деревья и двудольные графы| Теорема Холла и цепи Маркова

mybiblioteka.su - 2015-2024 год. (0.007 сек.)