80. Критичні графи

Граф G називається критичним, якщо в результаті вилучення будь-якої вершини

з G утворюється граф G', хроматичне число якого строго менше χ(G). Критичний

граф G, для якого χ(G) = k, називається k-критичним.

81. 1. Встановлен початкових умов(вводиться к-ть вершин та матриця вагів С=||Сij||).

2. к=0; величини і(0)=оо для всіх вершин крім х1 1(0)=0;

3. в циклі по к:=1 до n-1 в кожній вершині Хі приписати індекс і(к)=min{і(к-1)+ Сij }. Для всіх вершин крім Хі 1(к)=0. В результаті роботи алгоритму форм таблиця і(к).

4. Відновлен min шляху. Для б.д. вершини Хs попередня Хs визн з співвідношення r(n-2)+Crs=s(n-1). Для знах вершини Хs Xa визн із співвідн r(n-3)+Crs=s(n-2)

82. Алгоритм Форда-Беллмана д/знах. Макс. Шляху

для роботи алгоритму необхідним є відсутність контурів додатної довжини.

На першому кроці необхідно провести заміну знаків.

Всі інші кроки здійснюються аналогічно як в алгоритмі знах макс. шляху.

Після виконання третього кроку знаки в таблиці індексів замінюються на протилежні.

83. Алгоритм Форда-Фалкерсона – знах. Макс. Потоку в мережі

1.Встановити попередника кожної вершини і резерв рівними символами непомічених «-«. Вершина помічена, якщо її резерв не познач. «-«. Встановити резерв вершина а= , S={a}.2. Якщо S-порожня множина, то потік мах. Якщо S- не порожня, то обираємо будь-який елемент і видаляємо,вважаємо цей елемент рівний V 3. якщо вершинаW- не помічена і ребро(v,w),f(v,w)≤ c(v,w), тоді вважати резерв w=мін (e(v,w)=f(v,w)) і величини резерву вершини v. Якщо w≠z, додати в w множину S. 4. Якщо w- не помічена, (w, v)-ребро і f(v,w)>0, то вважати резерв w= мін з f(v,w) і резерва вершини v. Встановити попередника вершини w у вершині v. Додати w в S. 5. Якщо z- помічена, то викор формулу передування, повернутися до вершини а і для кожного ланцюга ребра додати резерв вершини z , до потоку кожного вірно орієнтованого ребра і відняти резерв z з потоку кожного нерівно орієнтованого ребра. Повернутися до 1 6. Повернутися до 2

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

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.