Алгоритм Хафмана

1)вибрати 2 найменші частоти з таблиці частот та сформувати з них дерево: більший ел – вправо, менший – вліво. Помістити «0» на ребро лівого сина, «1» - на ребро правого

2) видалити з таблиці частот 2 використані, замінивши їх - їх сумою.

Надалі вибирати 2 найменші частоти і формув. дерево, роблячи його синами символи або дерева, розташовуючи менший елемент або дерево вліво, більший – вправо…

див. листок А4…

85. Поняття ізоморфізму графів

Буквальний переклад слова “ізоморфізм” означає “однаковість форми”. Форма графа — це його структура. Таким чином, ізоморфізм графів означає однаковість їх структури.Два графи G1 = (V1, E1) і G2 = (V2, E2) називаються ізоморфними, якщо між множинами їх вершин існує взаємно однозначне відображення

ϕ : V1→V2, яке зберігає суміжність, тобто для довільних вершин v і w (v, w)∈E1 тоді

й тільки тоді, коли (ϕ(v), ϕ(w))∈E2. При цьому ϕ називається ізоморфним відображенням або ізоморфізмом графа G1 на граф G2 Ізоморфізм графа на себе називається автоморфізмом. Теорема 33. Графи ізоморфні тоді й тільки тоді, коли ізоморфні їхні доповнення. Теорема 34. Якщо ϕ — ізоморфізм графа G1 на G2, то вершини v у графі G1 і ϕ(v) у G2 мають однакові степені. Під інваріантом графа G розуміють числовий параметр, пов’язаний з G,

значення якого однакові для всіх графів, ізоморфних G. Деякі найпростіші

інваріанти представлено в наступних теоремах. Теорема 35. Ізоморфні графи мають однакову кількість вершин Теорема 36. Ізоморфні графи мають однакову кількість ребер.

Теорема 37. Ізоморфні графи для довільного k (k ≥ 0) мають однакову кількістьвершин степеня k.Теорема 38. В ізоморфних графах для довільного k (k ≥0) існує взаємно однозначна відповідність:1) між множинами простих ланцюгів довжини k; 2) між множинами простих циклів довжини k. Висновок 38.1. Ізоморфізм зберігає відстань між вершинами графа. Висновок 38.2. Для зв’язного графа ексцентриситет вершин, діаметр та радіус є інваріантами.

86. Поняття самодоповнювальних графівСамодоповнювальним називається граф, ізоморфний своєму доповненню Самодоповнювальним також є тривіальний граф. Теорема 39. Кількість вершин будь-якого нетривіального самодоповнювального графа дорівнює або 4k, або 4k+1, k∈N. Нехай самодоповнювальний граф G = (V, E) має n вершин. G≅G , тому граф і його доповнення мають однакові кількості ребер. Тоді з того, що G∪G = Kn випливає, що |E| = n(n-1)/4. Це число буде цілим, якщо n чи n-1 ділиться на 4 без остачі, тобто n = 4k чи n-1 = 4k, або n = 4k+1, при деякому натуральному k. При n = 4k+3 або n = 4k+2 число n(n-1)/4 не є цілим і не може виражати кількість ребер. Висновок 39.1. Довільний самодоповнювальний граф містить або 4k2−k, або 4k2+k ребер, k ∈N. Для тривіального графа твердження очевидне. Якщо n = 4k, то |E| = n(n-1)/4 = k(4k-1) = 4k2-k. Якщо n = 4k+1, то |E| = n(n-1)/4 = (4k+1)k = 4k2+k.

87.