2018-02-13
466
Тема: Ейлерові та Гамільтонові цикли в графах.
Мета: Навчитися використовувати парадигму циклів.
Вступ. Цикл – це шлях на графі, який починається та закінчується на одній і той самій вершині. Ейлерів цикл – це цикл, який проходить через кожне ребро графа рівно один раз. Гамільтонів цикл – це цикл, який може не проходити через всі ребра, але обов’язково повинен пройти через кожну вершину рівно один раз.
Застосування таких циклів можна знайти в теорії кодування, наприклад, якщо необхідно, щоб код зберігав неповторність при зсуві (вправо, або вліво), то можна скористатися Ейлеревими циклами, а якщо необхідно згенерувати коди Грея, які відрізняються лише одним бітом, то необхідно знайти Гамільтонів цикл на решітці 2n.
Розв’язок задачі про Ейлерв цикл почнемо з побудови графу, який задає можливі переходи між кодовими комбінаціями. Цей граф виглядає як відношення gr(X,Y,Z), в якому X означає вхідний код, Y означає вихідний код, а Z – символ, який переводить вхідний код у вихідний.
Наприклад, якщо вхідним кодом задати X = 010, то для вихідного коду буде два варіанти: Y = 101 для Z = 1, або Y = 100 для Z = 0. Очевидно, що вихідний код ми отримали за допомогою зсуву вхідного коду на 1 біт вліво, дописавши в кінці на вільне місце Z. Якщо всі коди є довжиною 3 біти, то символ, який вийшов за межі розрядної сітки пропадає.
Автоматом називається граф переходів між кодами, в якому альтернативний вибір робиться за зовнішнім впливом. У нашому випадку X – це попередній стан автомату, Y – це наступний стан автомату, а Z – це зовнішній вплив, який робить вибір між дописуванням одинички або нуля.
Приклад програми наведений нижче. В ньому відношення gr(X,Y,Z) задається однойменною табличкою, з якої викреслюється вибраний код. Для того, щоб отримати всі неповторні коди, необхідно досягнути стану, коли табличка порожня. Якщо процес заходить у тупиковий стан, то PRL автоматично скасовує попередній вибір, і шукає іншу альтернативу аж доти, доки не знайде рішення.
Eiler_cycle:- A=011, C=0, suppose(code_Liu(C)),
gr(A,B,C), take(B), Print_code.
take(A):- C=1, gr(A,B,C), suppose(code_Liu(C)), take(B).
take(A):- C=0, gr(A,B,C), suppose(code_Liu(C)), take(B).
take(A):- not(gr(S1,S2,S3)).
Print_code:- code_Liu(C), C<2, write(C), fail.
Print_code:- write().
code_Liu(2).; Двійка використовується як кінець кодової послідовності.
gr(000, 000, 0). gr(000, 001, 1). gr(001, 010, 0). gr(001, 011, 1).
gr(010, 100, 0). gr(010, 101, 1). gr(011, 110, 0). gr(011, 111, 1).
gr(100, 000, 0). gr(100, 001, 1). gr(101, 010, 0). gr(101, 011, 1).
gr(110, 100, 0). gr(110, 101, 1). gr(111, 110, 0). gr(111, 111, 1).
Програма видає результат: 0 1 1 1 1 0 0 1 0 1 0 0 0 0 1 1 – це циклічний неповторний код N4, у якому будь-який фрагмент, що складається з 4-х біт, є унікальним. Незважаючи на те, що кожна вершина має 3-бітний код, у вихідній послідовності буде додано ще один біт, який вказує, по якому ребру буде рухатися цикл. Це пояснюється тим, що до 3-бітного коду можна дописати як 0, так і 1. Тобто, з кожною вершиною інцидентні два вихідних ребра.
Завдання 1. Необхідно намалювати граф, що заданий відношенням gr(X,Y,Z).
Завдання 2. Переробіть програму для пошуку неповторних кодів N5.
Завдання 3. Переробіть програму так, щоб вона видавала код, який починається з двійкового коду вашого номера у журналі групи студентів.
Завдання 4. Переробіть програму так, щоб вона у першу чергу надавала перевагу нулям.
Завдання 5. Переробіть програму так, щоб неповторна послідовність, яку вона видає, утворювалася б зсувом попереднього коду вправо.
Лабораторна робота №7
Тема: Елементарні задачі на графах.
Мета: Навчитися формулювати твердження на графовій моделі абстрагування.
Вступ. Конструктивний підхід до побудови математичних моделей полягає у тому, що він вимагає від цих моделей конкретних алгоритмів розв’язку задач. Отже, з позицій конструктивізму, модель є безперспективною в тому випадку, якщо вона не дозволяє розв’язати якусь задачу. Які можуть бути задачі на графах?
Пошук шляху від вершини A до вершини B, при якому вершини не повторюються, є найбільш поширеною задачею на графі. Спробуємо представити розв’язок цієї задачі за допомогою наступної програми:
Знайти_всі_шляхи_довжиною_N:- N=5, X=1, Y=4,
write("Всі шляхи довжиною",N), way(X,Y, N), write(),
prn_список, fail.
; вершини 1-8 зв'язані наступними ребрами:
gr(1,2). gr(1,3). gr(1,4). gr(6,2). gr(6,3). gr(5,4). gr(5,2). gr(7,3).
gr(7,4). gr(8,6). gr(8,5). gr(8,7).
; По кожному ребру можна рухатись в протилежних напрямках:
rebro(X,Y):-gr(X,Y).
rebro(X,Y):-gr(Y,X).
; шлях від пункту X до пункту Y за N кроків:
way(X,Y,N):- N=1,rebro(X,Y),not(список(X)),not(список(Y)),
suppose(список(Y)),suppose(список(X)).
way(X,Y,N):- rebro(X,Z),way(Z,Y,M),not(список(X)),suppose(список(X)),N=M+1.
; Роздрукувати список пройдених вершин:
prn_список:- Y=0, список(Y), WRITE(" список вершин:"),список(X),write(X),fail.
prn_список:- WRITE("----------").
список(0).; Початковий список пройдених вершин:
Завдання 1. Доповнити дану програму так, щоб вона шукала довжину шляху. Для цього змінити факти gr(A,B) на gr(A,B,C), де C – це число, що означає довжину вказаного ребра. Введені значення A,B,C беруться з IMEI вашого мобільного (по одній цифрі 0..9). Намалювати отриманий граф.
Завдання 2. Доповнити програму так, щоб вона шукала шляхи, які проходять (не проходять) через задані додатковим списком вершини.
Завдання 3. Доповнити програму так, щоб вона шукала цикли довжиною L, які проходять (не проходять) через задані додатковим списком вершини.
Завдання 4. Доповнити програму так, щоб вона шукала всі шляхи, довжина яких менше (більше) заданого значення.
