ДМ графы, способы задания, геометрическая реализация
Примеры задач на графы
Графом G наз-ся пара объектов V и E (G=áV,Eñ). V={a1, a2, …} мн‑во вершин, E={(ai, aj)}- мн-во ребер. Каждое ребро может быть либо упорядоченно, либо нет; в зависимости от этого граф ориентированный или неориентир-ый.
Пусть 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)}
Путь из ai в aj:
Путь из вершины в саму себя, не содержащий дважды одно и тоже ребро, наз‑ся циклом. Если цикл состоит из одного ребра, то его называют петлей.
Граф, не сод-ий циклов, наз-ся ациклическим.
Граф наз-ся связным, если между любыми его вершинами существует путь.
|
[Т] каждый конечный граф G м.б. реализован в трехмерном евклидовом пространстве.
Граф, который м.б. реализован в 2-мерном пр-ве - плоский (планарный).
Пр2: не планарный граф:
Два графа наз-ся изоморфными, если они имеют одинаковое кол‑во вершин и ребер и сущ-ет взаимнооднозначное соответствие между вершинами и ребрами этих графов, при котором соотв. ребра соед-ся с соотв. верш-ми.
Дерево – любой связный ациклический граф.
Деревом графа наз-ся любой связный ациклический подграф. Если дерево графа содержит все его вершины, то оно наз-ся остов.
Маршрут из u0 в uk = u0l1u1l2…lkuk, где li=(ui-1ui). Если все ребра маршрута различны, то это цепь.
Эйлеровой цепью в графе наз-ся замкнутая цепь, сод-ая все ребра.
|
граф явл-ся эйлеровым т.тогда, когда степень каждой вершины четная.
Гамельтоновым циклом наз-ся простой цикл, содержащий все вершины.
Алгоритм построения остовного дерева минимальной стоимости: ребра в графе упорядочиваем по возрастанию. последовательно выбираем ребра (из упорядоченной последовательности) до тех пор, пока выбранные ребра не дадут дерева. Очередное ребро выбираем только в том случае, если при его добавлении не возникает цикла.
Задачи на графы: задача комивояжера (нахождение минимального гамильтонова цикла на графе с N вершинами), транспортная задача
7. ДМ теория кодирования, алфавитное кодирование, проблема однозначности кодирования, префиксные коды
сообщение®[кодер]®код сообщ.®[канал связи]®код сообщ.®[декодер]®сообщ. на выходе
Проблемы: однозначность кодирования, оптимизация кодирования, обнаружение и исправление ошибок
Пусть a={a1,a2,…,an}-исх. алф., A= , l(A) – длина слова, S(A)-мн‑во всех слов в алф. A, S¢(A)ÌS(A)-мн‑во всех возм-х сообщ. на входе;
b={b1,b2,…,bq}-алфавит, В- слово в нем.
Пусть задано отобр. 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¢¢ - суффикс.
|
если схема кодирования å обл-ет св-вом префикса, то кодирование будет взаимнооднозначным.
Пр2: | å: | a1 – b1b2 | -обдадает св-вом префикса Þ однозначна |
a2 – b1b1 | |||
a3 – b3 |
Теорема Маркова:
l(B)-длина слова B, li=l(Bi), -длина схемы кодирования
|
(Маркова) для любой схемы кодирования å такое, что проблема однозначности кодирования сводится к проверке однозначности на некотором множестве SN(a)- мн-во всех слов в алфавите а, длина которых £N.
|
Алфавитное кодирование со схемой å явл-ся неодн‑м т.тогда, когда граф Г(å) содержит ориентированный цикл, проходящий через вершину L.