Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Деревья

Класс деревьев занимает особое положение в теории графов. Это связано с тем, что деревья, во-первых, достаточно просто устроены (среди связных графов с фиксированным числом вершин дерево имеет наименьшее число ребер), а во-вторых, часто встречаются в прикладных задачах.

Определение ^.32. Деревом называется связный граф, не содержащий циклов.

На рис. 37 изображены все (с точностью до изоморфизма) деревья с шестью вершинами.

Рис. 37

Определение J^.33. Произвольный граф без циклов называется лесом (ациклическим графом). Любая компонента связности леса является деревом.

Существуют другие эквивалентные определения дерева, что отражено в следующей теореме ([16], глава 4).

Теорема 4.18. Для (п,ш)-графа G следующие утверждения эквивалентны:

  • (1) G - дерево;
  • (2) G - связный граф и rn = n— 1;
  • (3) G - ациклический граф (лес) и т—п — 1;
  • (4) в графе G любые две различные вершины соединены единственной простой цепью;
  • (5) G — ациклический граф со свойством: если пару его несмежных вершин соединить ребром, то G будет содержать ровно один цикл.

В качестве следствия получаем следующее утверждение: в любом дереве с числом вершин 2 имеется не менее двух концевых вертят (и хотя, бы одно концевое ребро).

гие. 38

Действительно, если V = {гц,..., vn} - множество вершин дерева G и <Д, ..., dn - степени соответствующих вершин, то d + ... + dn = = 2rn = 2(n — 1). Но поскольку слагаемых п и каждое из них положительно, то, по крайней мере, два из них равны 1. Это означает наличие не менее двух вершин степени 1, т. е. концевых. Справедливость утверждения для ребер следует из того, что концевым называется ребро, инцидентное концевой вершине, а при п — 2 паре концевых вершин соответствует одно концевое ребро.

Теорема 4.19. Каждое дерево имеет центр, состоящий из одной или из двух смежных вершин.

Из доказательства теоремы, приведенного в [16] глава 4, следует, что найти центр дерева можно постепенно удаляя концевые вершины дерева.

Определение 4-34- Ветвью к вершине и дерева называется максимальное поддерево, содержащее и в качестве концевой вершины. Вес вершины и определяется как наибольшее число ребер по всем ветвям дерева. Вершина называется центроидной вершиной дерева, если она имеет наименьший вес.

П р и м ер 4.15. Найти центральные вершины и центроид дерева, изображенного на рис. 38.

Данное дерево имеет одну центральную вершину гъ, которая имеет минимальный эксцентриситет 2, и две центроидные вершины v и гь с максимальным весом 3.

Определение 4-35. Остовным деревом связного графа G называется любой его подграф Н, который содержит все вершины графа G и является деревом.

Если G - связный (п,ш)-граф, то остовное дерево (если оно существует) должно содержать п— 1 ребро (см. теорему 4.18). Таким образом, любое остовное дерево связного графа G есть результат удаления из множества всех ребер ровно т — (п — 1 )=т — п + 1 ребер. Число гп — п +1 называется цикломатическим числом связного графа С и обозначается через v{G).

Остовное дерево связного графа может быть выделено, вообще говоря, не единственным способом. Общее число остовных деревьев связного графа может оказаться весьма большим. Например, для полного графа с п вершинами оно равно п"~2.

Определение 4-36. Пусть Н - остовной подграф графа G. Если он на любой области связности графа G порождает дерево, то Н называется остовом, или каркасом графа G.

Существование каркаса в любом графе G достаточно очевидно. Разрушая в каждой компоненте связности графа G циклы, т. е. удаляя «лишние» ребра, приходим к остову (каркасу). Число v{G) ребер произвольного графа G. которое необходимо удалить для получения остова, не зависит от последовательности их удаления и определяется равенством v(G) = т—п+k, где п - число вершин, т - число ребер, к - число компонент связности графа G. Число v{G) называется цикломатическим числом графа G. Очевидны следующие утверждения:

  • (1) v(G) = 0 тогда и только тогда, когда G - лес;
  • (2) v(G) = 1 тогда и только тогда, когда G имеет только один цикл;
  • (3) граф О, в котором число ребер т не меньше числа вершин п (ш^гг), содержит цикл.

Рис. 39

Опишем алгоритм, позволяющий найти минимальное остовное дерево взвешенного графа G=(V,E).

  • 1. Строим граф G = (V., Е = {ei}), где е имеет наименьший вес.
  • 2. Каждый следующий граф Gi+ строим, добавляя к множеству ребер графа бф ребро е*+1, имеющее минимальный вес среди ребер, не входящих в Gi и не составляющих циклов с ребрами ИЗ G;.

На рис. 39 показано минимальное остовное дерево взвешенного графа.

Заметим, что построенное минимальное дерево не является единственным. Предлагаем читателю самостоятельно найти другие минимальные деревья данного графа,

  • 1. Что называется графом, ориентированным графом? Приведите примеры.
  • 2. Найдите степени всех вершин неориентированного графа G= (V, Е), V — {vi,г>2,гд, щ,vb}, Е = {ех = (щ,v2), е2 = (щ,и3), е3 =

= {Vl,V4l),e4 = (V2,Vz)}.

  • 3. Какие вершины графа называются смежными? Как задается матрица смежности графа? Чем отличаются матрицы смежности графа и орграфа?
  • 4. Запишите матрицы смежности орграфа G=(V,E), V = = {vi,v2, V3, v4,v5}, Е= {(гл, vo), (vi, и3), (t>i, vs), (^2, г>з), (г>2, v4), (v3, v4), (^4,^5)} и соответствующего неориентированного графа.
  • 5. Как определяется отношение инцидентности между вершинами и ребрами графа? Чем отличаются матрицы инцидентности графа и орграфа?
  • 6. Запишите матрицы инцидентности орграфа (см. задание 4) и соответствующего неориентированного графа.
  • 7. Поясните, почему в любом графе всегда четное число вершин нечетной степени (или их нет).
  • 8. Какой граф называется планарным, что такое карта графа? Приведите пример планарного графа.
  • 9. Какой граф называется полным? Сколько ребер в полном графе с десятью вершинами?
  • 10. Что такое дополнительный граф? Как связаны матрицы смежности основного и дополнительного графа?
  • 11. Какой граф называется связным? Что изменится в связном графе, если удалить точку сочленения (мост)?
  • 12. Запишите неравенство, которое связывает три основные числовые характеристики графа: п - число вершин, т - число ребер, к - число компонент связности.
  • 13. Дайте определение эйлерова графа. Сформулируйте необходимое и достаточное условие того, что граф является эйлеровым.
  • 14. Какой граф называется гамильтоновым? Может ли гамильтонов граф быть эйлеровым? Приведите пример.
  • 15. Какой граф называется деревом? Сформулируйте характеристические свойства дерева. Какой граф называется лесом?
  • 16. Как связаны понятия «остовное дерево» и «дипломатическое число» связного графа? Как определяется дипломатическое число произвольного графа?

1. Доказать (по определению) указанное равенство для произвольных множеств Л, В, и С. Проиллюстрировать диаграммами Эйлера - Венпа.

3. Даны два бинарных отношения рСАхВ, тСВ хА. Задать эти отношения явно (перечислением). Найти: 1) отношения р-1, рт, ~рт, тр; 2) область определения и область значений отношений р и р-1; 3) матрицу и графическое представление отношений р и рт.

4. Найти область определения, область значений отношения Р. Указать какими из свойств (рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность) обладает отношение Р. Ответ обосновать.

5. Сформулировать высказывание, соответствующее формуле.

6. Найти СДНФ и СКНФ формулы а) по таблице истинности, 6) с помощью эквивалентных преобразований. Составить её многочлен Же- галкииа.

7. Минимизировать в классе ДНФ логическую функцию f(x, Т‘2, Жз, -М), которая принимает значение 1 па следующих наборах переменных.

8. Составить логическую формулу, которая соответствует указанной схеме переключателей, упростить её. Изобразить упрощенную схему.

Ill

  • 9. Записать утверждение на язьже логики предикатов.
  • 9.1. Через любые 2 точки можно провести прямую.
  • 9.2. Для любой прямой и не лежащей на ней точки существует прямая, проходящая через данную точку, параллельно данной прямой.
  • 9.3. Для любых 3-х точек существует содержащая их плоскость.
  • 9.4. Определение рефлексивности бинарного отношения.
  • 9.5. Определение симметричности бинарного отношения.
  • 9.6. Определение антисимметричности бинарного отношения.
  • 9.7. Определение транзитивности бинарного отношения.
  • 9.8. Определение подмножества.
  • 9.9. Определение равенства множеств.
  • 9.10. Для любых двух натуральных чисел существует наибольший общий делитель.
  • 9.11. Определение линейно упорядоченного множества.
  • 9.12. Определение ограниченной функции (функция f(x) называется ограниченной на множестве М, если существует такое неотрицательное число L, что для всех х ? Л/ справедливо неравенство /{х) <Ь).
  • 9.13. Определение четной функции (функция /(а) называется четной, если область ее определения симметрична относительно начала координат и для каждого х из области определения справедливо равенство

/(-Ц=/Щ).

  • 9.14. Определение нечетной функции (функция f(x) называется нечетной, если область ее определения симметрична относительно начала координат и для каждого х из области определения справедливо равенство f(—x) = —f(x)).
  • 9.15. Определение возрастающей функции (функция f(x) называется возрастающей на множестве М, если для любых чисел х и хо:, принадлежащих множеству М, из неравенства Х < х~> следует неравенство f{x) 2)).
  • 9.16. Определение убывающей функции (функция f(x) называется убывающей на множестве М, если для любых чисел Х и ал, принадлежащих множеству М, из неравенства Х<Х2 следует неравенство f{xi)2)).
  • 9.17. Определение бесконечно большой функции (функция f(x) называется бесконечно большой в точке х = а, если существует окрестность этой точки, в которой для любого х справедливо неравенство f(x)>A при любом Л>0).
  • 9.18. Определение бесконечно малой функции (функция /(а) называется бесконечно малой в точке х — а, если существует окрестность этой точки, в которой для любого х справедливо неравенство f(x)при любом ?>0).
  • 9.19. Определение ограниченной последовательности (числовая последовательность п} называется ограниченной, если существует такое неотрицательное число Л/, что для всех членов последовательности справедливо неравенство хп ф Л/).
  • 9.20. Определение верхней грани числового множества (число S называется верхней гранью числового множества Л/, если для любого элемента х еМ справедливо неравенство x^S).
  • 9.21. Определение нижней грани числового множества (число S называется нижней гранью числового множества Л/, если для любого элемента х? М справедливо неравенство x^S).
  • 9.22. Определение периодической функции (функция f(x) называется периодической, если существует такое число Т> 0, что при любом х из области определения функции элементы х + Т и х — Т также принадлежат этой области, и справедливо равенство /(ж=ЬТ) = f(x)).
  • 9.23. Определение невозрастающей числовой последовательности (числовая последовательность п} называется невозрастающей, если для любых номеров щ и гы из неравенства гц <гы следует неравенство Х"П ^ Xl%2 ) •
  • 9.24. Условие равносильности двух уравнений: f (х) = 0 и f‘>{x) = 0.

о or v „ / /Цж, г/)=о

9.25. Условие несовместности системы уравнении <

f2(x,y) = 0

10. Проверить истинность формулы логики предикатов.

из

12. Граф G задан одним из 3-х основных способов: а) матрицей смежности Aq (12.1-12.8), б) матрицей инцидентности Вс (12.9-12.16), в) графически (12.17-12.25).

Для графа С: (1) рассчитать степени вершин; (2) задать двумя другими способами; (3) привести пример цикла и оетовного ациклического подграфа.

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

Для графов G и G: (1) определить являются ли они изоморфными, связными, планарными, двудольными, эйлеровыми, гамильтоновыми; (2) найти число компонент связности, мосты и точки сочленения.

13. Ориентированный граф G задан одним из 3-х основных способов: а) графически (13.1-13.8), б) матрицей смежности Aq (13.9-13.16), в) матрицей инцидентности Вс (13.17-13.25). Для орграфа G: (1) задать его двумя другими способами, (2) рассчитать полустепени вершин, (3) составить матрицу достижимости, (4) определить тип (характер) связности, (5) выделить компоненты связности.

14. Взвешенный граф задан матрицей весов. Построить его графическое представление, с помощью алгоритма Дейкстры определить матрицу расстояний. Найти радиус, центр и диаметр графа,

Настоящее учебное пособие предназначено для студентов инженерно-технических специальностей (направлений), в образовательные программы которых включена дисциплина «Дискретная математика». Кроме того, его можно использовать при изучении отдельных разделов дискретной математики в общем курсе математики. Современные ЭВМ и информационные технологии, которые широко используются в различных областях знаний, техники, технологических процессов немыслимы без знания (или хотя бы знакомства) с основами дискретной математики.

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

По окончании изучения курса «Дискретная математика» студент должен

знать:

основные понятия, теоремы и методы математической логики, теории множеств и теории графов;

основные методы упрощения логических формул, переключательных схем и схем из логических элементов;

- теоретико-множественные подходы к постановке и решению задач;

приемы моделирования прикладных задач методами дискретной математики;

уметь:

- применять математическую символику для выражения количественных и качественных отношений объектов;

применять аналитические и численные методы дискретной математики.

Пособие предлагается студентам для освоения теоретического материала в ходе изучения дискретной математики, самостоятельной работы, подготовки к тестированию, зачету или экзамену.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>