Остовное дерево

(Spanning tree)

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

Любое остовное дерево в графе с вершинами содержит ребро.

Остовное дерево может быть построено практически любым алгоритмом обхода графа, например поиском в глубину или поиском в ширину рассмотренными ранее. Остовные деревья, построенные при обходе графа с помощью алгоритма Дейкстры, начиная от вершины , обладают тем свойством, что кратчайший путь в графе из до любой другой вершины - это единственный путь до этой вершины в построенном остовном дереве. Существует также несколько параллельных и распределённых алгоритмов нахождения остовного дерева. Как практический пример распределённого алгоритма можно привести протокол STP.

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

Матрица Кирхгофа

Для работы с остовными деревьями в теории графов графы пряно обозначать в виде матрицы Кирхгофа. Благодаря представлению графа в таком виде, матрица Кирхгофа может использоваться вместе с теоремой Кирхгофа для расчета количества остовных деревьев в графе.

Матрица Кирхгофа это комбинация матрицы степеней вершин и матрицы смежности L=A+B. Матрица степеней вершин. А это матрица размерностью где на главной диагонали расположены степени вершин графа (определение степени вершины графа дано в начале раздела).

Матрица степеней вершин для данного графа будет иметь вид :

Матрица смежности для данного графа будет иметь вид (заметим, что для смежных вершин используется обозначение -1, а не 1 как в классическом варианте матрицы смежности, в этом особенность матрицы Кирхгофа):

Матрица Кирхгофа будет иметь вид:

В общем виде матрица Кирхгофа записывается как:

Теорема:

Пусть — связный помеченный граф с матрицей Кирхгофа . Все алгебраические дополнения матрицы Кирхгофа равны между собой и их общее значение есть число остовных деревьев графа .

Пример. Дан граф , рассчитаем количество остовных деревьев графа:

Матрица Кирхгофа для данного графа будет иметь вид:

Найдём алгебраическое дополнение

На основе данного графа может быть получено 3 остовных дерева:

5.6 Конечные автоматы

(Finite-state machines)

Конечный автомат (Finite-state machines, или сокращённо FSM) – это машина или программа, содержащая конечное число состояний, которые могут изменяться от полученных входных данных.

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

Один из узлов автомата всегда соответствует начальному состоянию машины или программы. На диаграмме это ребро, входящее в узел и не соединённое с другими узлами графа. Также конечный автомат имеет заключительное состояние, которое соответствует нормальному завершению работы программы или машины. Для перехода из одного состояния в другое автомат должен “принять” определённую строку символов (слово), заданных во входном алфавите.

Определения:

Символ — любой атомарный блок данных, который может производить эффект на машину.

Слово — строка символов, создаваемая с помощью операции конкатенации.

Входной алфавит — конечный набор различных символов.

Язык — множество слов, формируемых символами данного алфавита. Может быть конечным или бесконечным.

С математической точки зрения автомат состоит из 4 основных элементов:

Q — множество состояний (states) конечного автомата Σ — входной алфавит языка (alphabet), который понимает автомат.

δ — функция перехода (transitions), позволяющей автомату перейти в новое состояние.

S₀ — начальное состояние конечного автомата (start state)

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

Конечные автоматы широко используются при разработке синтаксических и лексических анализаторов, а также для построения событийно-ориетированный приложений, т.е. приложений использующих графический интерфейс пользователя (GUI), например, программы Windows Forms или Windows Presentation Foundation (WPF) для платформы .NET.

Удобным инструментом для проектирования и разработки конечных автоматов является ещё одна технология .NET: Windows Workflow Foundation (WWF).Особенно широко она используется при проектировании различных бизнес-процессов, которые могут пребывать в различной степени готовности. Подробнее с этой замечательной технологией можно познакомиться в книге Э. Троелсена “Язык программирования С# 2010 и платформа .NET 4”.