А.А. Вороненко, В.С. Федорова - Дискретная математика. Задачи и упражнения с решениями (1060726), страница 4
Текст из файла (страница 4)
. + (|Vs | − 1) = |V | − s = n − s.Докажем верхнюю оценку числа рёбер. При фиксированном числе вершин, компонент связности и мощности компонент связности максимальное число ребер достигается на графе, в котором каждая из компонент23связности является полным графом. Тогда при фиксированных n и sвыясним, возможно ли при перенесении вершины из одной компонентысвязности в другую каким-то образом увеличить число рёбер во всемграфе.Рассмотрим две компоненты связности sl и sm с l и m вершинами соответственно. Считая, что первоначально компоненты содержали маки m(m−1), перенесём из компонентысимальное число рёбер, то есть l(l−1)22sl в компоненту sm одну вершину и посчитаем, насколько изменилосьчисло рёбер в компонентах sl и sm .Число изменится на величину m − (l − 1), которая положительна приm > l > 2.При l = 1 сократить число вершин в меньшей компоненте невозможно:это приведет к уменьшению числа компонент.Таким образом, количество рёбер в графе максимально тогда и толькотогда, когда s − 1 компонент связности состоят из одной вершины, аоставшаяся — из остальных вершин.При этом число рёбер в графе(n − (s − 1))(n − (s − 1) − 1) (n − s)(n − s + 1)=.q=22Последнее утверждение задачи доказывается от противного предположением, что граф не связен, то есть у него как минимум две компонентысвязности.IVI.1.20(1).
Граф (без петель и кратных рёбер) называется самодополнительным, если он изоморфен своему дополнению. Показать, чтоесли граф самодополнительный, то число вершин в нем равно либо 4l(l > 1), либо 4l + 1 (l > 0).J Из изоморфности графа G своему дополнению G следует, что количества рёбер в них совпадают: |EG | = |EG |. Но по определению дополнения|EG |+|EG | = n(n−1)— число рёбер в полном графе на n вершинах. Чтобы2n(n−1)число 4 рёбер в графе G было целым, необходимо, чтобы выполнялось следующее условие:n = 4l,l > 1,In = 4l + 1, l > 0.VI.1.21(1). Выяснить, сколько существует попарно неизоморфныхграфов без петель и кратных рёбер, имеющих 6 вершин и 11 рёбер.J В полном графе с 6 вершинами число рёбер равно 6(6−1)= 15, следо2вательно, в дополнении графа с одиннадцатью рёбрами будет 15−11 = 4ребра.24Рассмотрим все попарно неизоморфные графы с шестью вершинамии четырьмя рёбрами.
Их количество будет совпадать с искомым.(1) Рассмотрим графы, содержащие циклы:(a) цикл из четырёх рёбер;(b) цикл из трёх рёбер; тогда четвёртое ребро— либо входит в ту же компоненту связности, что и цикл;— либо образует вторую компоненту.(2) Рассмотрим ациклические графы. Ациклический связный граф,состоящий из 6 вершин и 4 рёбер, имеет 2 компоненты связности.(a) В одной компоненте связности 5 вершин, в другой — 1. Такихграфов несколько:— максимальная степень вершин равна 2;— максимальная степень вершин равна 3;— максимальная степень вершин равна 4.(b) В одной компоненте связности 4 вершины, в другой — 2.Возможны два варианта:25— максимальная степень вершин равна 2;— максимальная степень вершин равна 3.(c) В каждой из компонент связности по 3 вершины.IДругих вариантов нет. Всего мы получили 9 попарно неизоморфныхграфов.Занятие № 1.8Графы: деревья, гомеоморфизмVI.1.26.
Доказать, что во всяком дереве с n > 2 вершинами содержится не менее двух висячих вершин.J Пусть у дерева p вершин, q рёбер и p0 висячих вершин.pPdeg vi = 2qi=1для любого графа. Кроме того, для любого дерева выполнено равенствоp − q = 1. Таким образом,2q =pXi=1deg vi = p0 +Xdeg vi > p0 + 2(p − p0 ) ⇒deg vi >1⇒ p0 > 2(p − q) = 2.IVI.1.29(2).
Изобразить все попарно неизоморфные деревья с 6 рёбрами и 4 висячими вершинами.J В дереве, удовлетворяющем условию, есть либо одна вершина степени4, либо две вершины степени 3.26IVI.3.1(в). Построить код плоского корневого дерева, изображённогона рис. 1.J 1-й способ. По определению код искомого дерева D равен 0eα1 1, гдеαe1 — код его поддерева D1 .
Код D1 по определению равен αe2 αe3 , где αe2и αe3 — коды его левого и правого поддеревьев. Аналогично получимαe2 = 0eα3 1. Код αe3 из определения вычисляется без труда: αe3 = 001011.Поэтому код дерева D равенαe = 0eα1 1 = 0eα2 αe3 1 = 00eα3 1eα3 1 = 0000101110010111.2-й способ. Так как код дерева можно получить с помощью обхода(учитывая, что рёбра укладки дерева, инцидентные корню, пронумерованы по часовой стрелке), сразу получаем искомый код:αe = 0000101110010111.IVI.3.2(2). Построить плоское корневое дерево по его коду:αe = 00110101000111.J Представляем искомый код в виде αe = αe1 αe2 αe3 αe4 , где αe1 = 0011,αe2 = αe3 = 01, αe4 = 000111 — коды поддеревьев дерева с кодом αe.Учитывая, что αe1 = 0eα2 1, αe4 = 0eα1 1, строим данное дерево:27IVI.1.36(1).
Выяснить, существуют ли в графах, изображённых нарис. 1–3, подграфы, гомеоморфные K4 (рис. 4).Рис.1Рис.3Рис.2Рис.4J Да, существуют (см. рис. 5, 6, 7).Рис.5Рис.6Рис.7IЗанятие № 1.9Графы: планарность, раскраски, орграфыVI.2.1(2). Применяя критерий Понтрягина-Куратовского, выяснить,планарны ли изображённые на рис. 1–3 графы.28Рис.1Рис.3Рис.2J В каждом из этих графов существует подграф, гомеоморфный K3,3(см. рис. 4, 5, 6), поэтому по критерию Понтрягина-Куратовского они неявляются планарными.21222121212111211Рис.42Рис.5Рис.6IVI.2.13. Плоский связный граф без висячих вершин, каждая гранькоторого, включая и внешнюю, ограничена циклом длины 3, называетсятриангуляцией.
Показать, что триангуляция с n > 3 вершинами имеет3n − 6 рёбер и 2n − 4 граней.J Пусть триангуляция с n вершинами имеет m рёбер и f граней, тогда,поскольку каждой грани трангуляции по условию принадлежит ровно 3ребра, а каждое ребро принадлежит ровно 2 различным граням, имеемm = 3f /2. Далее, по формуле Эйлераn − m + f = 2 ⇒ n − 3f /2 + f = 2 ⇒⇒ f = 2n − 4, m = 3n − 6.IVI.2.17(1). Показать, что плоский кубический граф, граница каждойграни которого имеет не менее 5 вершин, содержит по крайней мере 20вершин.
Привести пример такого графа.J Так как граф кубический, то степень каждой вершины равна 3, следовательно, количество рёбер в графе m = 3n/2 (так как каждому ребрупринадлежат ровно 2 вершины). Поскольку по условию каждой грани29принадлежит не менее 5 вершин, количество граней в графе f 6 3n/5.Из формулы Эйлера n − m + f = 2 получаем2 6 n − 3n/2 + 3n/5,откуда n > 20. Отметим, что примером удовлетворяющего условию графа может служить центральная проекция на плоскость правильного двенадцатигранника (додекаэдра).IVI.2.18. Найти хроматические числа и хроматические индексы графов, изображённых на рис. 1–6.Рис.1Рис.2Рис.3Рис.4Рис.5Рис.6J Все шесть графов имеют циклы нечетной длины.
Поэтому их хроматические числа не меньше трех. Заметим, что граф, изображённый нарис. 1, изоморфен графу, изображённому на рис. 2, а граф, изображённый на рис. 3, изоморфен графу, изображённому на рис. 4, поэтому иххроматические индексы и хроматические числа совпадают.Легко проверить, что χ(G) > ω(G), где ω(G) — число вершин наибольшего полного подграфа G; а χ0 (G) > max deg v.v∈GНайдем χ(G) и χ0 (G) для графов на рис.
1, 3, 5, 6.Для графа на рис. 1 χ(G) = 3, χ0 (G) = 3.30231112213323231Для графа на рис. 3 χ(G) = 3, χ0 (G) = 4.Для графа на рис. 5 χ(G) = 3, χ0 (G) = 3.211123231223131 3 1 22323121Для графа на рис. 6 χ(G) = 3, χ0 (G) = 3.IVI.1.54. Бесконтурным ориентированным мультиграфом называется мультиграф, не содержащий контуров (ориентированных простыхциклов).
Доказать, что в бесконтурном ориентированном мультиграфесуществует вершина с нулевой полустепенью исхода.31J Начнём движение из любой вершины и на очередном шаге в качествеследующей будем выбирать любую вершину, в которую ведёт дуга изтекущей. Так как граф бесконтурный, то на каждом шаге мы будемпопадать в непосещённую ранее вершину. С другой стороны, множествовершин графа конечно, поэтому рано или поздно мы придем в вершину,полустепень исхода которой равна 0.IVI.1.60.
Турниром называется полный направленный граф. Гамильтоновой цепью называется ориентированная простая цепь, включающая все вершины графа. Показать, что в любом турнире существуетгамильтонова цепь.J Докажем утверждение методом математической индукции. Для турнира с n = 1 вершиной утверждение верно. Далее, пусть оно вернодля некоторого турнира Gn с n вершинами. Добавим к нему еще одну вершину vn+1 с дугами и получим новый турнир Gn+1 .
Пусть v1 →v2 → . . . → vn — гамильтонова цепь в турнире Gn . Если в турнире Gn+1есть дуга vn+1 → v1 , то в нем есть путь vn+1 → v1 → . . . → vn . Если в турнире Gn+1 есть дуга vi → vn+1 и vn+1 → vi+1 , то в нем естьпуть v1 → . . . → vi → vn+1 → vi+1 → . .
. → vn . Иначе есть путьv1 → v2 → . . . → vn → vn+1 . В каждом из трёх случаев в турнире Gn+1есть гамильтонова цепь.v1vn+1v1vn+1v2...v1vn+1v2...vnvn+1v2...vnv1v2...vnvnIЗанятие № 1.10Алфавитное кодирование. Оптимальные коды32VII.1.3(1). Выяснить, является ли слово P = 10120121012100 в алфавите {0, 1, 2} кодом сообщения в кодировании, задаваемом схемой1 → 10,2 → 12,Σ : 3 → 012,4 → 101,5 → 2100.Если да, то выяснить, является ли P кодом ровно одного сообщения.J Cлово P является кодом единственного сообщения, поскольку— единственное кодовое слово, оканчивающееся двумя нулями, — это2100, значит, P = 1012012101 2100|{z};— единственное кодовое слово, оканчивающееся единицей, — 101,следовательно, P = 1012012 |{z}101 2100|{z};— предположим, первое кодовое слово — 101. В этом случае оставшаяся часть слова не декодируется: P = |{z}101 2012 |{z}101 2100|{z}. Следовательно, первое кодовое слово — 10, далее — 12 и 012:P = |{z}10 |{z}12 |{z}012 |{z}101 2100|{z} .Итак, P является кодом единственного сообщения 12345.IVII.1.2(1, 3).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
