Алкоголь і алкоголізм. Нікотин і нікотиноманія

Нікотин і нікотиноманія

Наркотики й наркоманія.

Класифікація соціальних небезпек.

ОСНОВНА ЧАСТИНА

ВСТУП

Member(edge(Y, X), E).

Incident(А, В, Tree),

Not(path(А, В, Tree, _))).

Tree(Tree), covers(Tree, G).

Постановка 12.

Expand(Tree2, Tree, G).

Conedge(Tree1, Tree2, G),

expand (Tree, Tree, G):- % Додавання будь-якого

ребра приводить до циклу

not(conedge(Tree,_, G)).

conedge(Tree, [A-В| Tree ], G):- %Додавання ребра

incident (А, В, G), % А і В - суміжні вершини

top (А, Tree), % А втримується в Tree

not(top (В, Tree)). % А - В не породжує циклу

incident(А, В, G):-

member(А - В, G);

member( В-А, G).

top (А, Tree):- % А належить графу, якщо

incident (А,_, G). % А суміжна деякій вершині

Програму побудови остовного дерева можна написати зовсім іншим, повністю декларативним способом, лише формулюючи на Прологу деякі математичні визначення. Нехай, так само, як і попередньо, і графи, і дерева задані списками своїх ребер.

Використаємо наступні визначення:

(1) Т є остовним деревом графа G, якщо:

· Т - це підмножина графа G і

· Т - дерево і

· Т "накриває" (covers) G, тобто кожна вершина з G також є у Т.

(2) Множина ребер Т є дерево, якщо

· Т - зв'язний граф і

· Т не містить циклів.

Ці визначення можна сформулювати на Прологу з використанням попередньої програми path(A, Z, G, Р).

% Побудова остовного дерева

% Графи й дерева представлені списками ребер.

tree_column(G, Tree):- subset(G, Tree),

subset([ ], [ ]).

subset([Х | L], [Х | L1]):- subset(L, L1).

tree(Tree):- connect(Tree),not(cycle(Tree)).

connect(Tree):-not(top(А, Tree), top(В, Tree),

top (А, G):- incident (А,_, G).

cycle(Tree):-

path(А,B,Tree,[А,X |_]). % Довжина шляху>1

path(A, Z, G, Р):- path1(А, [Z], G, Р).

path1(А, [А | Р1], _, [А | Р1]).

path1(А, [Y | Р1], G, Р):- incident(X, Y, G),

not(member(X, Р1)), % Умова відсутності циклу

path1(А, [ X, Y | Р1], G, Р).

incident(X, Y, g(V, E)):- member(edge(X, Y), E);

covers(Tree, G):-not(top(А, G), not(top(А, Tree))).

member(A,[A|_]):-!.

member(A,[_|T]):-member(A,T).

Зауважимо, що ця програма не має практичного інтересу через свою неефективність.

Самостійна робота.

1. Розгляньте використання наведених рішень задач на конкретних прикладах графів.

2. Розгляньте остовні дерева у випадку, коли кожному ребру графа приписана його вартість. Нехай вартість остовного дерева визначена, як сума вартостей складових його ребер. Напишіть програми:

a. визначення для заданого графа вартості його остовного дерева;

b. побудови для заданого графа його остовного дерева мінімальної вартості.

ЛІТЕРАТУРА

1. Типова навчальна програма нормативної дисципліни «безпека життєдіяльності» для вищих навчальних закладів, затверджена заступником міністра освіти і науки, молоді та спорту України 31.03.2011р.

2. Безпека життєдіяльності: Навч. посіб. / О.С. Баб’як, О.М. Сітенко, І.В. Ківва та ін. – Х.: Ранок, 2000. – 304 с.

3. Заплатинський В. М. Полімовний тлумачний словник з безпеки. Підручник. – К.: Центр учбової літератури, 2009. – 120 с. ISBN 978-911-01-0002-1

4. Заплатинський В., Матис Й. Безопасность в эру глобализации. Монография. – ЦУЛ, 2010.- 142.

5. Іванова І.В., Заплатинський В.М., Гвоздій С.П. "Безпека життєдіяльності" навчально-контролюючі тести. – Київ: "Саміт-книга", 2005. – 148 с.

Дата добавления: 2014-01-04