Шпоры по дискретной математике2
Число компонент связности графа G обозначим c(G). Граф G является связным тогда и только тогда, когда c(G)=1. Если c(G)>1, то G — несвязный граф. Граф, состоящий только из изолированных вершин, называется вполне несвязным.
19. Сильная связность. Две вершины u, v в орграфе G связаны отношением двусторонней достижимости, если существует маршрут из u в v, и из v в u. Орграф, в котором любые две вершины двусторонне достижимы, называется сильно связным. Тривиальный граф, состоящий из изолированной вершины, по определению считается сильно связным.
Отношение двусторонней достижимости вершин является отношением эквивалентности. Компонентой сильной связности орграфа G называется его сильно связный подграф, который не является собственным подграфом никакого другого сильно связного подграфа орграфа G. Классы эквивалентности по отношению двусторонней достижимости, являются разбиением множества вершин орграфа G на подмножества вершин, входящих в одну компоненту сильной связности. Для построения компоненты сильной связности достаточно взять один класс эквивалентности и перенести на множество его вершин связи (дуги) из орграфа G. Число компонент сильной связности орграфа G обозначим k(G). Орграф G является сильно связным тогда и только тогда, когда k(G)=1. Если k(G)>1, то G — не является сильно связным орграфом.
Односторонняя связность. Орграф G называется односторонне связанным, если для любых вершин u, v существует маршрут хотя бы в одну сторону.
Если орграф является сильно связным, то он будет и односторонне связным.
Слабая связность. Псевдографом ассоциированным с орграфом G=(V,E) называется псевдограф G1=(V1,E1), в котором E1 получается из E заменой всех дуг (упорядоченных пар) на ребра (неупорядоченные пары).
Орграф G=(V,E) называется слабо связным, если ассоциированный с ним неориентированный граф является связным.
20. Пусть G=(V,E) граф (орграф) с n вершинами и q ребрами. Если A=A(G) — матрица смежности графа (орграфа) G, то aij элемент матрицы Аk есть число маршрутов из vi в vj длины k. В n вершинном графе (орграфе) G тогда и только тогда существует маршрут из vi в vj (i∫j), когда (i,j)-й элемент матрицы не равен нулю.
В n вершинном графе (орграфе) G тогда и только тогда существует цикл; содержащий вершину ai, когда (i,i)-й элемент матрицы не равен нулю. Образуем из матрицы B матрицу C=(cij) порядка n по следующему правилу: Cij=1, если bij≠0; Cij=0, если bij=0, где bij элементы матрицы B.
Матрица C называется матрицей связности, если G -неориентированный граф, и матрицей достижимости, если G — орграф. В графе G существует маршрут из vi в vj когда cij=1. В матрице C содержится информация о существовании связей между различными элементами графа посредством маршрутов. Если G — связный неориентированный граф, то все элементы матрицы связности C равны единице. В общем случае матрица связности неориентированного графа является матрицей отношения эквивалентности, соответствующего разбиению множества вершин графа на компоненты связности.
Выход: последовательность вершин обхода.
for vсV do x[v]:=0
Источник
4.11.5. Упорядоченные и бинарные деревья
2) если T1, T2. Тп непустые упорядоченные деревья, a некоторый новый элемент, то список Т = (a, T1, T2, . Тn) образует упорядоченное дерево. При этом элемент а называемся корнем упорядоченного дерева Т;
3) любое упорядоченное дерево строится в соответствии с п.п. 1 и 2.
Если T1, T2, . Тn упорядоченные деревья, то список (T1, T2, . Тn) называется упорядоченным лесом.
Для заданного упорядоченного дерева Т определим множество S(Т) его упорядоченных поддеревьев:
если Т = , то S(T) = ;
если Т = (а), то S(T) = <(a)>;
если Т=(a, T1, T2, . Тn), то S(T)=S(T1). S(Tn).
Непустое упорядоченное дерево Т может интерпретироваться в виде системы пронумерованных непустых множеств, каждое из которых взаимно однозначно соответствует упорядоченному поддереву из S(Т) так, что:
1) если Т’ поддерево упорядоченного дерева Т», Т’,Т»S(T), то для соответствующих множеств X‘ и X« выполняется включение X‘ X«;
2) если Т’ не является поддеревом упорядоченного дерева Т«, Т’,Т»S(T), то соответствующие множества не пересекаются.
Пример. Упорядоченному дереву
соответствует система множеств, изображенная на рис. 4.38.
Упорядоченное дерево может также интерпретироваться в виде так называемого уступчатого списка, который используется в оглавлениях. На рис. 4.39 представлен уступчатый список, соответствующий упорядоченному списку из примера.
Согласно следующему тезису любая схема, в которой заданы определенные приоритеты между элементами, может рассматриваться как некоторое упорядоченное дерево.
Тезис. Любая иерархическая классификационная схема интерпретируется некоторым упорядоченным деревом.
Например, и виде упорядоченного дерева представляется любой терм. На рис. 4.40 изображено упорядоченное дерево, соответствующее терму t=a—b(c:d+e:f).
Частным случаем упорядоченного дерева является бинарное дерево. Определение понятия бинарного дерева повторяет определение для упорядоченного дерева с ограничением п в п.2. При этом для бинарного дерева Т = ((a),T1,T2), бинарное поддерево T1 называется левым поддеревом, а T2 – правым поддеревом.
Бинарные деревья имеют более простое устройство, чем упорядоченные, и вместе с тем любой упорядоченный лес взаимно однозначно соответствует некоторому бинарному дереву.
Опишем алгоритм преобразования упорядоченною леса Т = (T1, T2, . Tn) в бинарное дерево В (Т).
Шаг 1. Если n = 0, В(Т) = .
Шаг 2. Если п > 0, то корнем бинарного дерева В(Т) является корень упорядоченного дерева Т1, левое поддерево дерева В(Т) — бинарное дерево В(Т11, Т12, …, Т1m), где Т1= ((a1),T11, T12, . T1m), правое поддерево дерева В(Т) — бинарное дерево В(Т2, . Тn).
Источник
Тема 3.7 Деревья
Определение: Деревом называется связный, ориентированный граф без петель и кратных ребер, не содержащий в себе циклов, удовлетворяющий следующим условиям:
- имеется в точности один узел, называемый корнем, в который не входит ни одно ребро,
- В каждый узел, кроме корня, входит ровно одно ребро,
- Из корня к каждому узлу идет путь ( который, как легко показать единственный).
Деревья являются простейшим видом связных графов. Любое дерево с n вершинами содержит n-1 ребер. Число различных деревьев, которые можно построить на n вершинах равно 
Определение Дерево с одной выделенной вершиной называется корневым деревом. Определение Ориентированный граф, состоящий из нескольких деревьев, называется лесом. Определение: Пусть G=(Х, Г) – граф, являющийся лесом. Если дуга (v,w) принадлежит Г, то v называется отцом узла w, а w – сыном узла v. Определение: Если есть путь из v в w, то v называется предком узла w, а w – потомком узла v. Определение: Узел без потомков называется листом. Определение: Узел v и его потомки вместе образуют поддерево леса G, и узел v называется корнем этого поддерева. Определение:Глубина узла v в дереве – это длина пути из корня в v. Определение:Высота узла в дереве – это длина самого длинного пути из этого узла в какой-нибудь лист. Определение:Высотой дерева называется высота его корня. Пример 
Глубина узла b, в данном примере, = 1, а его высота = 2. Высота дерева = 3. Определение:Упорядоченным деревом называется дерево, в котором множество сыновей каждого узла упорядоченно. При изображении упорядоченного дерева, как правило, считается, что множество сыновей каждого узла упорядоченно слева направо. Определение:Бинарным деревом называется такое упорядоченное дерево, что
- Каждый сын произвольного узла идентифицируется либо как левый сын, либо как правый сын.
- Каждый узел имеет не более одного левого и не более одного правого сына.
Обратите внимание, что бинарное дерево не является частным случаем дерева, это совершенно иное, хотя и тесно связанное понятие. Н
апример: Указанные бинарные деревья различны между собой ( в первом случае корень имеет пустое правое поддерево, а во втором левое поддерево пусто), хотя как деревья они изоморфны, и мы можем рассматривать их как одно дерево. Определение: Бинарное дерево называется полным, если для некоторого целого числа K каждый узел, глубины меньшей k имеет как левого, так и правого сына, и каждый узел глубины k является листом. Полное дерево глубины k имеет 
узлов. Очень часто используются алгоритмы, которые проходят дерево (посещают каждый его узел) в некотором порядке. Известно несколько способов сделать это. Мы рассмотрим три широко известных способа: прохождение дерева в прямом порядке, обратном порядке и внутреннем. Будем считать, что Т – дерево с корнем r и сыновьями при k >=0. При k = 0 это дерево состоит из единственного узла r.
Прохождение дерева т в прямом порядке определяется следующим алгоритмом:
- Посетить корень r
- Посетить слева на право поддеревья с корнями v1 . . . vk в указанной последовательности.
П
ример Прохождение дерева Т в обратном порядке определяется следующим алгоритмом: Посетить в обратном порядке поддеревья с корнями v1 . . . vk в указанной последовательности. Посетить корень r П
ример Прохождение дерева Т во внутреннем порядке определяется следующим алгоритмом: Посетить во внутреннем порядке левое поддерево корня (если оно существует). Посетить корень Посетить во внутреннем порядке правое поддерево корня (если оно существует). Пример П
режде чем дать описание одного из этих алгоритмов на некотором формальном языке программирования, поговорим о способах задания и хранения деревьев и бинарных деревьев. Очень многие объекты представимы в виде деревьев. Например: сложная нумерация глав лекций – типичный информационный объект, сохраняемый и обрабатываемый в виде дерева. 1. Теория графов 1.1. Основные определения теории графа 1.2. Операции над графами 1.2.1. Одноместные операции 1.2.2. Двуместные операции 1.3. Отношения 1.3.1. Отношение порядка 1.3.2. Отношение эквивалентности
- Числовые характеристики графа
1.5. Понятие обхода графа 1.5.1. Эйлеров цикл 1.5.2. Гамильтонов цикл
- Изоморфизм графов
- Понятие дерева
- Бинарные деревья
- Алгоритмы нумерации узлов графа
- Нумерация в прямом порядке
- Нумерация в обратном порядке
- Нумерация во внутреннем порядке
Подобная система нумерации часто называется десятичной системой обозначения Дьюи. В
ведем интуитивное понятие линейного списка. Мы еще не раз будем говорить об этом способе представления и хранения информации. Одним из распространенных способов хранения деревьев является массив списков. Это одномерный массив, размерностиn – количество узлов дерева. Каждый элемент этого массива – это упорядоченный или неупорядоченный список сыновей этого отца. Например Бинарные деревья, как правило, хранятся посредством двух массивов ЛЕВЫЙСЫН и ПРАВЫЙСЫН, где номер элемента массива – это номер узла, а значение этого элемента – номер левого или правого узла – сына. Если элемент — сын отсутствует, то значение равно 0. Пример Теперь опишем алгоритм нумерации узлов двоичного дерева в соответствии с внутренним порядком. Для этого будем пользоваться неким подобием языка программирования, специально предназначенного для прозрачного и понятного описания алгоритмов. Вход: Двоичное дерево, представленное массивами ЛЕВЫЙСЫН и ПРАВЫЙСЫН. Выход: Массив, называемый НОМЕР, такой, что НОМЕР[i] – номер i – того узла во внутреннем порядке. Метод: Будем использовать глобальную переменную СЧЕТ, значение которой – номер очередного узла в соответствии с внутренним порядком. Начальное значение переменной СЧЕТ = 1. Программа выглядит так: begin СЧЕТ 1 ВНУТРПОРЯДОК(КОРЕНЬ) EndProcedure ВНУТРПОРЯДОК(УЗЕЛ) Begin 1. if ЛЕВЫЙСЫН[УЗЕЛ]0 then ВНУТРПОРЯДОК(ЛЕВЫЙСЫН[УЗЕЛ]); 2. НОМЕР[УЗЕЛ] СЧЕТ;
- СЧЕТ СЧЕТ+1
4. if ПРАВЫЙСЫН[УЗЕЛ]0 then ВНУТРПОРЯДОК(ПРАВЫЙСЫН[УЗЕЛ]); End Такая процедура, которая явно или неявно вызывает сама себя, называется рекурсивной. Применение рекурсии часто дает возможность давать более прозрачное и сжатое описание алгоритма, чем это же можно было бы сделать, не используя рекурсию. Если бы приведенный алгоритм не был записан рекурсивно, надо было бы строить явный механизм для прохождения дерева. Двигаться вниз по дереву нетрудно, но чтобы обеспечить возможность вернуться к предку, надо запомнить всех предков в стеке, а операторы работы со стеком усложнили бы алгоритм, лишив его наглядности.
Источник