ДМ графы, способы задания, геометрическая реализация

Примеры задач на графы

Графом G наз-ся пара объектов V и E (G=áV,Eñ). V={a₁, a₂, …} мн_­­­­‑во вершин, E={(a_i, a_j)}- мн-во ребер. Каждое ребро может быть либо упорядоченно, либо нет; в зависимости от этого граф ориентированный или неориентир-ый.

Пусть m=|V| - число вершин, n=|E| - число ребер. Если m и n конечны, то граф конечный.

Пр1: V={1,2,3,4}, E={(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}

Путь из a_i в a_j:

Путь из вершины в саму себя, не содержащий дважды одно и тоже ребро, наз‑ся циклом. Если цикл состоит из одного ребра, то его называют петлей.

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

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

Т

Геометрическая реализация графов: геом. фигуру Г называют геом. реализацией графа G, если сущ‑ет взаимнооднозначное соотв‑ие между вершинами G и точками фигуры Г, и между ребрами G и дугами Г.

[Т] каждый конечный граф G м.б. реализован в трехмерном евклидовом пространстве.

Граф, который м.б. реализован в 2-мерном пр-ве - плоский (планарный).

Пр2: не планарный граф:

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

Дерево – любой связный ациклический граф.

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

Маршрут из u₀ в u_k = u₀l₁u₁l₂…l_ku_k, где l_i=(u_i-1u_i). Если все ребра маршрута различны, то это цепь.

Эйлеровой цепью в графе наз-ся замкнутая цепь, сод-ая все ребра.

Т

Граф, содержащий эйлерову цепь, наз-ся эйлеровым графом.

граф явл-ся эйлеровым т.тогда, когда степень каждой вершины четная.

Гамельтоновым циклом наз-ся простой цикл, содержащий все вершины.

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

Задачи на графы: задача комивояжера (нахождение минимального гамильтонова цикла на графе с N вершинами), транспортная задача
7. ДМ теория кодирования, алфавитное кодирование, проблема однозначности кодирования, префиксные коды

сообщение®[кодер]®код сообщ.®[канал связи]®код сообщ.®[декодер]®сообщ. на выходе

Проблемы: однозначность кодирования, оптимизация кодирования, обнаружение и исправление ошибок

Пусть a={a₁,a₂,…,a_n}-исх. алф., A=, l(A) – длина слова, S(A)-мн‑во всех слов в алф. A, S¢(A)ÌS(A)-мн‑во всех возм-х сообщ. на входе;
b={b₁,b₂,…,b_q}-алфавит, В- слово в нем.

Пусть задано отобр. F: "AÎS¢(A)® BÎS¢(B). Слово B – код сообщения A. Процесс перехода от A к B – кодирование. Отобр. F- некоторый алгоритм.

Алфавитное кодирование: задается схема кодирования å, которая каждому символу алфавита a ставит в соответствие слово B из алфавита b:

å:	a1 – B1	Слова B1…Br нас-ся элементарными кодами. Могут иметь произвольную конечную длину
a2 – B2
…
ar – Br

Рассмотри проблему однозначности кодирования:

Будем считать, чт S¢(a)=S(a). Пусть S_å(B)ÌS(B) – образ мн-ва S(A) при кодировании. Если отображение S(A)®S_å(B) взаимнооднозначно, то проблема декодирования решается однозначно.

Пр1:	å:	a1 – b1	-однозначна
a2 – b1b2

Пусть слово B=B¢B¢¢. Тогда B¢ - префикс, B¢¢ - суффикс.

Т

Схема кодирования å обладает св-вом префикса, если "I,j (i¹j) B_i не является префиксом B_j.

если схема кодирования å обл-ет св-вом префикса, то кодирование будет взаимнооднозначным.

Пр2:	å:	a1 – b1b2	-обдадает св-вом префикса Þ однозначна
a2 – b1b1
a3 – b3

Теорема Маркова:

l(B)-длина слова B, l_i=l(B_i), -длина схемы кодирования

Т

Пусть B_i – элементарный код и имеется его разложение вида B_i=b¢B_i1… B_iwb¢¢, где b¢, b¢¢ - цепочки, отличные от элемент-х кодов, причем b¢ не оканчивается элем-м кодом, b¢¢ - не начинается им. Для любого B_i есть конечное число таких разложений. Обозначим через W максимум величины w по всем возможным разложениям всех B_i.
(Маркова) для любой схемы кодирования å такое, что проблема однозначности кодирования сводится к проверке однозначности на некотором множестве S^N(a)- мн-во всех слов в алфавите а, длина которых £N.

Т

Эта теорема позволяет построить чисто практический алгоритм распознавания однозначности: для каждого B_i рассм. все разложения. Построим мн-во D={L, bⁱ}. Построим граф Г(å), вершинами которогоявл-ся эл-ты мн-ва D так: если сущ-ет разложение Bi==b¢B_i1… B_iwb¢¢, то соединим b¢ и b¢¢ ориентир‑м ребром, которое пометим цепочкой B_i1… B_iw.

Алфавитное кодирование со схемой å явл-ся неодн‑м т.тогда, когда граф Г(å) содержит ориентированный цикл, проходящий через вершину L.