Рівень с

186. За картою Карно визначити мінімальну ДНФ функції, яка задана формулою .

а) ;

б) ;

в) ;

г) інша відповідь.

187. Визначити ДДНФ функції, що задана формулою .

а) ;

б) ;

в) ;

г) .

188. Визначити ДКНФ функції, що задана формулою .

а) ;

б) ;

в) ;

г) .

189. Мінімізувати функцію методом Квайна-Мак-Класкі

.

а) ;

б) ;

в) ;

г) .

190. Побудувати за таблицею істинності функції ДДНФ.

а) ;

б) ;

в) ;

г) .

191. За картою Карно мінімізувати функцію, яка задана формулою .

а) ;

б) ;

в) ;

г) .

192. По каналу зв’язку можуть передаватися три повідомлення А, В і С. Відомо, що в часі виконується кожна з трьох подій:

А) передаватися не більше ніж одне з повідомлень А і В;

Б) повідомлення А може бути передане тільки в тому випадку, якщо передані обидва повідомлення В і С;

В) передається хоч би одне з повідомлень А і С.

Побудуйте булеву функцію, яку реалізує канал зв’язку.

а) ;

б) ;

в) ;

г) .

193. Використовуючи перетворення, звести функцію до базису (+, )

а)

б) ;

в) ;

г) .

194. Побудувати ДКНФ функції, що задана формулою .

а) ;

б) ;

в) ;

г) .

195. За картою Карно мінімізувати функцію . (Примітка: так як варіантів склеювання є досить багато визначіть функцію з мінімальною кількістю змінних).

а) ;

б) ;

в) ;

г) .

196. За картою Карно мінімізувати функцію . (Примітка: так як варіантів склеювання є досить багато визначіть функцію з мінімальною кількістю змінних).

а) ;

б) ;

в) ;

г) .

197. Знайти ДДНФ функції .

а) ;

б) ;

в) ;

г) .

198. Побудувати таблицю істинності функції . Результат записати вектором.

а) (11101111);

б) (10101101);

в) (01110110);

г) (10101010).

199. Побудувати таблицю істинності функції . Результат записати вектором значень функції.

а) (11101111);

б) (10101101);

в) (01110110);

г) (10101010).

200. Побудувати таблицю істинності функції . Результат записати вектором значень функції.

а) (11111110);

б) (11101111);

в) (10101101);

г) (01110110).

201. Побудувати таблицю істинності функції . Результат записати вектором значень функції.

а) (10000100);

б) (11101111);

в) (10101101);

г) (01110110).

202. Побудувати таблицю істинності функції . Результат записати вектором значень функції.

а) (11111110);

б) (11101111);

в) (10101101);

г) (01111111).

203. Спростити вираз (звести до базису І, НЕ, АБО і виконати всі операції склеювання і поглинання) .

а) ;

б) ;

в) ;

г) .

204. Спростити вираз (звести до базису І, НЕ, АБО і виконати всі операції склеювання і поглинання) .

а) ;

б) ;

в) ;

г) .

205. Спростити вираз (звести до базису І, НЕ, АБО і виконати всі операції склеювання і поглинання) .

а) ;

б) ;

в) ;

г) .

206. Записати ДДНФ функції, що задана формулою .

а) ;

б) ;

в) ;

г) .

207. Записати ДДНФ функції, що задана формулою .

а) ;

б) ;

в) ;

г) .

208. За допомогою карти Карно мінімізувати функцію, що задана вектором своїх значень .

а) ;

б) ;

в) ;

г) .

209. Представити у ДКНФ наступну функцію .

а)

б) ;

в) ;

г) .

210. Побудувати поліном Жегалкіна для функції .

а) ;

б) ;

в) ;

г) .

ТЕМА 3

211. Намалюйте за допомогою графа договірні выдносини між піприємствами А, Б, В, Г, Д, Е, якщо: А має угоду зі всіма підприємствами, Б з Г іД; В зі всіма, крім Е. Скільки вершин і ребер має граф?

а) 5 вершин і 10 ребер;
б) 6 вершин і 12 ребер;

в) 6 вершин і 11 ребер;

г) 6 вершин і 19 ребер.

212. Серед 7 країн встановлені взаємовідносини, причому кожна країна має економічні угоди з іншими. Зобразіть відповідний граф. Скільки ребер має отриманий граф?

а) 49;

б) 36;

в) 21;

г) 42.

213. Скільки ребер потрібно провести щоб добудувати граф на малюнку до повного?

а) 1

б) 2

в) 4

г) 6

214. Графом називається

а) набір вершин та набір ребер;

б) множина вершин та множина ребер;

в) скінчена множина вершин V та скынчена множина ребер Е;

г) впорядкована пара G=(V, E), що складається з множини V вершин та сукупності Е ребер.

215. Граф називається скінченим, якщо

а) кількість вершин можна перерахувати;

б) кількість ребер можна перерахувати;

в) кількість вершин і ребер є скінченим числом;

г) інша відповідь.

216. Дані фігури зображують

1) 2) 3)
а) один і той самий граф;

б) різні графи;

в) фігура 1 і 3 – однакові графи;

г) фігура 2 і 3 – однакові графи.

217. Порядком графа називається

а) кількість вершин графа;

б) кількість ребер графа;

в) кількість ребер графа, інцидентних деякій вершині ;

г) інша відповідь.

218. Нульовий граф – це

а) тільки сукупність ребер графа;

б) тільки сукупність вершин графа;

в) граф, в якому не побудовані всі можливі ребра;

г) граф, який містить тільки кратні ребра.

219. Локальна степінь вершин графа – це

а) загальна кількість ребер графа;

б) загальна кількість вершин графа;

в) кількість ребер, що виходять з певної вершини графа;

г) кількість сусідних вершин графа.

220. Чи можуть різні ребра бути інцидентними одній і тій самій вершині?

а) можуть в будь-якому графі;

б) не можуть в будь-якому графі;

в) можуть тільки в мультиграфах;

г) можуть тільки в псевдографах.

221. Що таке мультиграф?

а) це псевдограф з петлями;

б) це граф, в якому жодна пара ребер не зустрічається більше одного разу;

в) це граф, що містить кратні ребра;

г) це граф, в якому кратність всіх ребер не більше 2.

222.

Кратність ребра – це

а) кількість суміжних ребер при одній вершигі;

б) кількість однакових пар ребер між двома вершинами;

в) кількість ребер інцидентних одній і тій самій вершині;

г) кількість кратних ребер при певій вершині.

223. Псевдограф – це

а) це граф з кратними ребрами і петлями;

б) це граф, в якому жодна пара ребер не зустрічається більше одного разу;

в) це граф, що містить кратні ребра;

г) це граф, в якому кратність всіх ребер не більше 2.

224. Повний граф – це граф

а) це граф з кратними ребрами і петлями;

б) це граф, в якому локільні степені всіх вершин рівні;

в) це граф, в якому локальна степінь всіх вершин рівна n-1, де n – кількість вершин в графі;

г) це граф, в якому локальна степінь всіх вершин менша n-1, де n – кількість вершин в графі;

225. Кількість ребер у повному графі з n вершинами дорівнює

а) n²/2;

б) n(n-1);

в) n/2;

г) n(n-1)/2;

226. Звичайний граф – це

а) скінчений неорієнтований граф без кратних ребер і петель;

б) скінчений неорієнтований граф з кратними ребрами і петлями;

в) Скінчений орієнтований граф без кратних ребер і петель;

г) скінчений орієнтований граф з кратними ребрами і петлями.

227. Однорідний граф –

а) це граф, в якому локільні степені всіх вершин рівні;

б) це граф, в якому жодна пара ребер не зустрічається більше одного разу;

в) це граф, що містить кратні ребра;

г) це граф, в якому локальна степінь всіх вершин рівна n-1, де n – кількість вершин в графі;

228. Сума локальних степеней всіх вершин графа дорівнює (n – кількість вершин в графі, m – кількість ребер)

а) 2n;

б) m(m-1);

в) 2m;

г) n(n-1).

229. Граф називається Ейлеровим, якщо

а) існує маршрут без повторення ребер, що обходить всі вершини графа;

б) існує цикл без повторення ребер, що обходить всі вершини графа;

в) він містить непарну кількість вершин з непарним степенем;

г) він містить парну кількість вершин з парним степенем.

230. Граф називається напівейлеровим, якщо

а) існує маршрут без повторення ребер, що обходить всі вершини графа;

б) існує цикл без повторення ребер, що обходить всі вершини графа;

в) він містить непарну кількість вершин з непарним степенем;

г) він містить парну кількість вершин з парним степенем.

231. Теорема Ейлера формулюється: Для того щоб зв'язний граф (можливо, мультиграф без петель) був Ейлеровим, необхідно й достатньо, щоб

а) існував маршрут без повторення ребер, що обходить всі вершини графа;

б) існував цикл без повторення ребер, що обходить всі вершини графа;

в) степені всіх вершин були парними;

г) він містив парну кількість вершин з парним степенем.

232. Теорема Ейлера формулюється: зв'язний граф (можливо, мультиграф без петель) буде напівейлеровим, тоді і тільки тоді, коли

а) існує маршрут без повторення ребер, що обходить всі вершини графа;

б) існує цикл без повторення ребер, що обходить всі вершини графа;

в) він містить непарну кількість вершин з непарним степенем;

г) степені двох вершин будуть непарними, а степені інших вершин – парними.

233. Якщо в графі парна кількість вершин з непарним степенем, то на скільки графів, які можна намалювати одним «розчерком», можна розбити даний граф?

(к – кількість вершин з непарним ступенем; n – загальна кількість вершин графа)

а) (n-k)/2;

б) n/2;

в) k/2;

г) (n+k)/2.

234. Для того, щоб зобразити напівейлеровий граф одним «розчерком» необхідно почати і завершити у вершині, яка

а) обов’язково має мати парний локальний степінь;

б) обов’язково має мати непарний локальний степінь;

в) починати і закінчувати граф можна з будь-якої вершини;

г) напівейлеровий граф одним «розчерком» не можливо зобразити.

235. Гамільтонів граф – це граф

а) для кого існує цикл, що обходить всі вершини графа (крім початкової) тільки один раз;

б) для кого існує маршрут, що обходить всі вершини графа тільки один раз;

в) для кого існує цикл, при якому кожне ребро проходиться принаймні один раз і сумарна вага всіх ребер, що ввійшли в цикл, мінімальна;

г) для кого існує маршрут, при якому кожне ребро проходиться принаймні один раз і сумарна вага всіх ребер, що ввійшли в маршрут, мінімальна.

236. Напівгамільтонів граф – це граф

а) для кого існує цикл, що обходить всі вершини графа (крім початкової) тільки один раз;

б) для кого існує маршрут, що обходить всі вершини графа тільки один раз;

в) для кого існує цикл, при якому кожне ребро проходиться принаймні один раз і сумарна вага всіх ребер, що ввійшли в цикл, мінімальна;

г) для кого існує маршрут, при якому кожне ребро проходиться принаймні один раз і сумарна вага всіх ребер, що ввійшли в маршрут, мінімальна.

237. За теоремою Дирака, граф буде гамільтонів, якщо

а) існує цикл, що обходить всі вершини графа (крім початкової) тільки один раз;

б) у зв'язному графі з n вершинами (n³ 3) степені всіх вершин більше або рівні n /2

в) існує маршрут, що обходить всі вершини графа тільки один раз;

г) в ньому існує гамільтонів цикл.

238. Маршрутом у графі називається

а) скінченна або не скінченна послідовність вершин і ребер, які чергуються;

б) скінченна послідовність вершин і ребер, які чергуються;

в) нескінченна послідовність вершин і ребер, які чергуються;

г) скінченна або не скінченна послідовність вершин і ребер, які чергуються і кожні два сусідні ребра e_s-1 і e_s є інцидентними до вершини v_s.

238. Чи можна маршрут у графі задати тільки послідовністю або вершин, або ребер?

а) тільки послідовністю вершин, що є інцидентними;

б) тільки послідовністю ребер, що є кратними;

в) а) і б);

г) не можна, маршрут задається тільки послідовністю вершин і ребер, які чергуються.

239. Нехай D =(V, Е) орієнтований граф, V ={ v ₁,..., v _n}, Е ={ е ₁,..., е_m}. Матриця суміжност і орієнтованого графа D – це

а) квадратна матриця A(D)=[a_ij] порядку nхn, де

б) матриця B (D)=[ b_ij ] порядку n ´ m, де

в) матриця B (D)=[ b_ij ] порядку n ´ m, де

г) матриця, яка має - рядків (кількість ребер або дуг) і один стовпчик, в якому записані номера вершин інцидентних ребру або дузі.

240. Нехай D =(V, Е) неорієнтований граф, V ={ v ₁,..., v _n}, Е ={ е ₁,..., е_m}. Матриця суміжност і неорієнтованого графа D – це

а) квадратна матриця A(D)=[a_ij] порядку nхn, де

б) матриця B (D)=[ b_ij ] порядку n ´ m, де

в) матриця B (D)=[ b_ij ] порядку n ´ m, де

г) матриця, яка має - рядків (кількість ребер або дуг) і один стовпчик, в якому записані номера вершин інцидентних ребру або дузі.

241. Нехай D =(V, Е) орієнтований граф, V ={ v ₁,..., v _n}, Е ={ е ₁,..., е_m}. Матриця інцидентності орієнтованого графа D – це

а) квадратна матриця A (D)=[ a_ij ] порядку n х n, де

б) матриця B(D)=[b_ij] порядку n´ m, де

в) матриця B (D)=[ b_ij ] порядку n ´ m, де

г) матриця, яка має - рядків (кількість ребер або дуг) і один стовпчик, в якому записані номера вершин інцидентних ребру або дузі.

242. Ланцюгом графа називається

а) маршрут М(e₁, e₂,..., e_n), який має початок у вершині v₀ і кінець v_n;

б) маршрут М(e₁, e₂,..., e_n), який має початок і кінець у вершині v₀ (v₀= v_n);

в) маршрут М(e₁, e₂,..., e_n), якщо кожне ребро в ньому зустрічається не більше ніж один раз;

г) скінченна або не скінченна послідовність вершин і ребер, які чергуються.

243. Простим ланцюгом графа називається

а) маршрут М(e₁, e₂,..., e_n), який має початок у вершині v₀ і кінець v_n;

б) маршрут М(e₁, e₂,..., e_n), який має початок і кінець у вершині v₀ (v₀= v_n);

в) маршрут, в якому кожна вершина (можливо, крім початкової) в ньому зустрічається не більше ніж один раз;

г) маршрут М(e₁, e₂,..., e_n), якщо кожне ребро в ньому зустрічається не більше ніж один раз.

244. Простим циклом графа називається

а) ланцюг, який має початок у вершині v₀ і кінець v_n;

б) ланцюг, який має початок і кінець у вершині v₀ (v₀= v_n);

в) ланцюг, в якому кожна вершина (можливо, крім початкової) в ньому зустрічається не більше ніж один раз;

г) ланцюг, в якому кожне ребро в ньому зустрічається не більше ніж один раз.

245. Циклом графа називається

а) ланцюг, який має початок у вершині v₀ і кінець v_n;

б) ланцюг, який має початок і кінець у вершині v₀ (v₀= v_n);

в) ланцюг, в якому кожна вершина (можливо, крім початкової) в ньому зустрічається не більше ніж один раз;

г) ланцюг, в якому кожне ребро в ньому зустрічається не більше ніж один раз.

246. Маршрут в орграфі називається

а) шляхом;

б) контуром;

в) ланцюгом;

г) циклом.

247. Цикл в орграфі називається

а)шляхом;

б) контуром;

в) ланцюгом;

г) маршрутом.

248.

Граф називається зв’язаним, якщо

а) всі його ребра є індидентними;

б) будь-яка пара його вершин є зв’язаною;

в) локальні степені його вершин парні;

г) якщо кожній вершині із її дуг поставлено у відповідність вагу l.

249. Граф називається зваженим, якщо

а) всі його ребра є індидентними;

б) будь-яка пара його вершин є зв’язаною;

в) локальні степені його вершин парні;

г) якщо кожній вершині із її дуг поставлено у відповідність вагу l.

250. Граф називається плоским, якщо

а) він намальований на площині, причому будь-які 2 ребра можуть перетинатися тільки у вершині;

б) існує така нумерація вершин у графі, що матриця суміжності є однаковою;

в) він ізоморфний планарному графу;

г) всі його ребра є попарно індидентними.

251. Графи називаються ізоморфними, якщо

а) вони намальовані на площині, причому будь-які 2 їхні ребра можуть перетинатися у вершині;

б) існує така нумерація вершин у цих графах, що вони мають ту саму матрицю суміжності;

в) функція Гранди для цих графів однакова;

г) хроматичні числа графів рівні.

252. Якщо в графі максимальний ступінь вершин дорівнює r, то реберно-хроматичне число дорівнює

а) r;

б) r +1;

в) або r, або r +1;

г) або r, або r -1.

253. Мережею називається

а) орграф, у якому задані “пропускні здатності” ребер;

б) зв'язаний граф, у якому задані “пропускні здатності” ребер;

в) мультиграф, у якому задані “пропускні здатності” ребер;

г) звичайний граф, у якому задані “пропускні здатності” ребер.

254. За теоремою Форда - Фалкерсона максимальний потік між вершинами t й s дорівнює

а) величині макчимального перетину між цими вершинами;

б) величині мінімального перетину між цими вершинами;

в) сумі пропускних здатностей ребер між цими вершинами;

г) сумі перетинів між цими вершинами.