Графы в обучении математике
Дипломная работа - Педагогика
Другие дипломы по предмету Педагогика
iепленные между собой в вершинах. Такой граф называется несвязным.
Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.
Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их.
Пример. В графе Г вершины А и В - связные, а вершины А и Н - несвязные.
Граф называется связным, если каждые две вершины его связные, т.е. от любой вершины существует маршрут.
Граф называется несвязным, если хотя бы две вершины его несвязные.
3. Графы деревья. Лес
Ребро и произвольного графа G называется циклическим, если оно принадлежит хотя бы одному элементарному циклу в графе и ациклическим в противном случае. Примером ациклического ребра является висячее справедливы два простых утверждения:
) при удалении из связного графа циклического ребра граф остается связным;
) при удалении ациклического ребра граф становится несвязным.
Первое подтверждается возможностью для любой цепи заменить циклическое ребро цепью из остальных ребер цикла. Второе доказывается от противного: если бы граф оставался связным, то концы удаленного ребра были бы связаны элементарной цепью: возвратив удаленное ребро, получили бы элементарный цикл вопреки тому, что ребро ациклическое.
Связный граф без циклов называется деревом. Это определение исключает наличие на дереве петель и кратных ребер. Прямая сумма несвязных деревьев, рассматриваемая в целом, как граф, называется лесом.
Дерево - это граф, все ребра которого ациклические. Имеется несколько эквивалентных определений дерева, устанавливающих ряд его характеристических свойств:
) связный граф, который становится несвязным при удалении любого ребра;
) связный граф, у которого число ребер на единицу меньше числа вершин;
) граф, любые две вершины которого связаны единственной элементарной цепью;
) граф без циклов, в котором после добавления ребра, связывающего две любые вершины, появляется цикл.
Выберем в дереве произвольную вершину ?0 и назовем ее корнем, или вершиной нулевого яруса. Соседние вершины назовем вершинами первого яруса и т.д., вершины, соседние вершинам (i-1)-го яруса не отнесенные еще ни к одному ярусу, назовем вершинами i-го яруса. Каждая вершина дерева принадлежит ровно одному ярусу. Очевидно, что номер яруса совпадает с расстоянием между его вершинами и корнем дерева. В силу свойства (3) каждая вершина i-го яруса связана ребром ровно с одной вершиной (i-1)-го яруса и не связана ребром ни с какой вершиной i-го яруса.
Такое представление дерева часто является удобным. Оно показывает, в частности, что в конечном дереве всегда существуют концевые вершины (например, вершины последнего яруса, но, возможно, и другие).
Выделение корня в дереве Д определяет на множестве его вершин частичный порядок: ? < ?, если ? ? ? и элементарная цепь из корня в вершину ? содержит ?. Корень ?0 является частично упорядоченном множестве вершин, а все концевые вершины (исключая корень: он может быть, но может и не быть концевой вершиной) - максимальными. Каждая вершина ? однозначно определяет корневое поддерево Д?, натянутое на множество таких вершин ?, что ? ? ?. В каждом таком поддереве Д? (в том числе в Д?0 = Д) можно выделить вершины, непосредственно подчиненные корню поддерева, т.е. такие вершины ?1, что ? < ?, и не существует промежуточных вершин ?i, для которых ? < ?i < ?i. Для каждой такой вершины ?i определяем ветвь Д? ?; дерева Д? как корневое поддерево с корнем ?, натянутое на множество вершин {?} u {? : ? ? ?}. Все поддерево Д? получается из своих ветвей склеиванием в корне ?.
Каждую логическую формулу, т.е. формулу, выражающую булеву функцию, можно представить корневым деревом: корень соответствует внешней булевой операции, вершины 1-го яруса - функциям, подставляемым на место ее аргументов, и т.д. Концевыми вершинами являются независимые переменные и константы.
Пример. Формула (Х V ( Y + Z)) > ( X& (1 ~ Y)) изображаемая деревом.
Теорема. Дерево с n вершинами содержит n-1 ребро.
Доказательство. Проведем индукцией по n. При n=2 утверждение очевидно. Пусть дерево G содержит n вершин. Удалим из него какую-нибудь концевую вершину и инцидентное ей концевое ребро. Получим новое дерево, содержащее n-1 вершину и, по предположению индукции, n-2 ребра. Следовательно, исходное дерево содержит (n+2)-1 = n - 1 ребро.
Турнир по олимпийской системе (с выбыванием проигравшего) изображается корневым дихотомическим деревом: корень соответствует победителю.
Замечание. Так называемое генеалогическое дерево не является, вообще говоря, деревом, так как множества предков по отцовской и материнской линиям могут пересекаться.
В связном графе G будем последовательно удалять циклические ребра до тех пор, пока это возможно, т.е. пока не останется ни одного циклического ребра. Мы приведем к связному подграфу графа G с тем же множеством вершин, но без элементарных циклов, т.е. к дереву, называемому остовом графа G. Остов выбирается, вообще говоря, неоднозначно, однако все ациклические ребра обязательно входят в любой остов, относительно остова Д все ребра подграфа G/Д называется хордами. Каждая хорда связывает две вершины остова.
Удобнее строить остов графа следующим образом. Упорядочив произвольно множество ребер графа, будем, начиная с первого из них, последовательно добавлять ребра, не образующие цикла вместе с какими-нибудь из ранее выбранных. Для этого достаточно выбирать очередное ребро еi так, чтобы одна из его вершин была ин