Связность графа. Отыскание компонент связности при графическом задании графа.

Г раф (ор-граф) называется связным (сильно связным), если любая пара его вершин соединяется хотя бы одной цепью.

- сильно связан - слабо связан

Возьмем ор-граф и уберем стрелки, тогда получим неор. граф, о котором говорят, что он ассоциирован с данным. Ор-граф называется слабосвязным, если ассоциированный с ним граф является связным. Максимально связанный (сильно связанный) подграф данного графа называется компонентой связности (сильной связности). Очевидно, если граф G имеет Р компонент связности G1,G2,G3,…,Gp, то число вершин графа G равно числу компонент связности. Если граф неор., то число его ребер равно сумме ребер его компонент связности.

Рассмотрим алгорит выделения компонент связности для неор. графа и этот же алгоритм даст возможность определить, будет ли граф связным. Этот алгоритм может работать и для выделения компонент слабой связности графа.

1) возьмем какую-нибудь вершину, 2) запишем все вершины, ей смежные, получим список, 3) к каждой вершине списка пункта 2 присоединяем смежные вершины, причем если вершина уже есть в списке, то ее уже не пишем, список при этом дополняется, 4) к полученным вершинам снова добавляем смежные к ним, не вошедшие в список, и так до тех пор, пока список не будет расширяться. При этом если в список вошли все вершины графа, то граф связный, в противном случае м ы выделим одну компоненту связности. Тогда берем любую вершину, не вошедшую в первую компоненту связности и повторяем алгоритм.

26. Понятие логической функции. Способы задания логических функций.

E={0,1}. f: Eⁿ®E – отображение ЕЕЕ…Е®Е называется булева функция от переменных y=f(x1,…,xn), (x1,…,xn)Eⁿ. БФ – двоичная функция двоичных переменных. f (x̃)=f(x1,…,xn). f(0…0)=f(0̃), f(1…1)=f(1̃). y=f(x), x=0,1; y=f(x1,x2). БФ можно задать кубически. При этом область определения – вершины n – мерного куба.

БФ может быть задана таблично, причем все наборы f(x,y,z) условимся заносить в порядке возрастания их десятичных эквивалентов.

x y z f f(10101110) – канонический набор. Если мы имеем 0 0 0 1 функцию n переменных, то количество наборов = 2ⁿ=к … Т.к. переменные принимают конечное число значений,

1 1 1 0 то и БФ-й от n переменных будет конечное число. 2^α=2^к

Изучать БФ, используя табличное задание можно, если число переменных невелико. Иногда удается в функции сократить число переменных, причем свойства функции от этого не меняются. Переменная x_i называется существенной, если удается найти такой набор α_i, что значения f(α₁,…, α_i-1,0, α_i+1,… α_n)≠ f(α₁,…, α_i-1,1, α_i+1,… α_n). Существенная зависимость означает невозможность определения значений функции без использования переменной x_i. Переменная x_i называется фиктивной, если для всех наборов f(α₁,…, α_i-1,0, α_i+1,… α_n)= f(α₁,…, α_i-1,1, α_i+1,… α_n).

Способы задания булевых функций не отличаются от способов задания обычных функций анализа. К таковым способам задания стандартно относятся: 1) табличный; 2) графический; 3) аналитический.