Основные понятия из теории графов

ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В КОДИРОВАНИИ И ДЕКОДИРОВАНИИ ИНФОРМАЦИИ

Васильева Марина Владимировна

студент 3 курса, факультет информатики СГАУ им. академика С.П. Королева, РФ, г. Самара

E -mail: vasmarishka1994@mail.ru

Додонова Наталья Леонидовна

научный руководитель, канд. физ.-мат. наук, доцент, кафедра прикладной математики СГАУ им. академика С.П. Королева, РФ, г. Самара

 

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

Значительно возросла популярность теории графов — ветви дискретной математики.

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

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

В настоящее время, с развитием научно-технического прогресса, изучение теории графов обрело актуальность в связи с применением при разработке эффективных алгоритмов оптимизации тех или иных процессов.

В настоящее время теория графов охватывает большой материал и активно развивается.

Цель работы: с помощью теории графов закодировать и декодировать информацию.

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

Основные понятия из теории графов

Граф — это средство для наглядного представления состава и структуры системы. Граф состоит из вершин, связанных дугами или ребрами. Вершины могут быть изображены кругами, овалами, точками, прямоугольниками и пр. Связи между вершинами изображаются линиями — ребрами. Если линия направленная (т.е. со стрелкой), то она называется дугой, если не направленная, то такой граф называется ориентированным графом. Две вершины, соединенные дугой или ребром, называются смежными.

Взвешенный (размеченный) граф — это граф, в котором с вершинами или линиями связана дополнительная информация. Эта информация называется весом вершины или линии. Вес позволяет отобразить на графе не только структуру системы, но и различные свойства компонент и связей, количественные характеристики и пр.

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

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

Граф, не содержащий циклов, называется ациклическим.

Связный ациклический граф называется деревом (свободным деревом).

Основные свойства деревьев в виде теоремы:

Теорема. Для графа G следующие утверждения эквивалентны:

1. G — дерево;

2. Любые две вершины в графе G соединены единственной простой цепью;

3. G — связный граф и p=q+1;

4. G — ациклический граф и p=q+1;

5. G — ациклический граф, и если любую пару несмежных вершин соединить ребром х, то в графе G+х будет точно один цикл;

6. G — связный граф, отличный от Кр для р=3, и если любую пару несмежных вершин соединить ребром х, то в графе G+х будет точно один цикл;

7. G — граф, отличный от и, p=q+1, и если любую пару несмежных вершин соединить ребром х, то в графе G+х будет точно один цикл.

Любое из утверждений теоремы можно использовать в качестве определения дерева.

Дерево — граф, обладающий следующими свойствами:

· ни в один из углов не входит более одной дуги;

· только в один узел (он называется корнем) не входит ни одной дуги;

· перемещаясь от корня по дугам, можно попасть в любой узел.

Неориентированное дерево (или просто дерево)— это конечный связный граф с выделенной вершиной (корнем) без циклов. Дерево не имеет петель и кратных рёбер.

Дерево и названо дерево, поскольку, будучи нарисованным, выглядит как дерево, только перевёрнутое «вверх ногами». Граф, изображённый на рисунке 1, является примером дерева.

 

Рисунок 1. Дерево

 

Для каждой пары вершин дерева — узлов — существует единственный маршрут, поэтому вершины удобно классифицировать по степени удалённости от корневой вершины.

Упорядоченным деревом называется дерево, в котором поддеревья каждого узла образуют упорядоченное подмножество.

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

На рисунке 2 приведен пример упорядоченного дерева и соответствующего ему бинарного.

 

Рисунок 2. Упорядоченное дерево и соответствующее ему бинарное

Лист дерева — это узел, из которого не выходит ни одной дуги. Два листа, имеющие общий узел, называются родственными.

Двоичное дерево — дерево, у которого из каждого угла выходит только две дуги.

H-дерево — двоичное дерево кодирования, у которого каждый узел имеет вес, причем вес родителя равен сумме весов детей.