Основные законы булевой алгебры. СДНФ и СКНФ

2.1. По таблице истинности формулы найти её СДНФ и СКНФ и упростить:

Номера вариантов

2.2. Упростить формулу двумя способами: при помощи таблицы истинности (использовать СДНФ или СКНФ) и элементарными преобразованиями.

Основные структуры:

1.	112.	23.
2.	113.	24.
3.	1 14.	25.
4.	1 15.	26.
5.	1 16.	27.
6.	1 17.	28.
7.	1 18.	29.
8.	1 19.	30.
9.	2 20.	31.
10.	2 21.	32.
11.	2 22.	33.

Раздел III. Составные структуры.

Тема III. 1. Основные понятия теории графов.

Определение графа, его элементы. Виды графов. Матрицы смежности и инцидентности.

3.1.1. Для графов, приведенных на рис.1., выполните следующие задания:

1) определите степени и полустепени вершин;

2) укажите содержащиеся в них:

а) контуры (циклы),

б) петли,

в) узлы,

г) висячие вершины;

3) определите, какие из графов являются:

а) ориентированными,

б) однородными,

в) полными,

г) мультиграфами.

1. х₂х₃ 2. х₂х₃

х₁х₄

х₁ х₄

х₃ х₃

3. х₂ 4.

х₄х₂ х₄

х₁х₅

х₁ х₅

3.1.2. По заданным полустепеням вершин постройте, если это возможно, ориентированный граф:

1) Р₊(х_i)=1, P_(x_i)=1, i=1,…,4;

2) P₊(x₁)=P₊(x₂)=P_(x₂)=P_(x₃)=1,

P₊(x₃)=P_(x₁)=2;

3) P₊(x_i)=i, P_(x_i)=6-i, i=1,…,5.

3.1.3. По заданным степеням вершин постройте, если это возможно, неориентированный граф:

1) P(x_i)=3, i= 1,…,4;

2) P(x_i)=i, i=1,…,5;

3) P (x₁)=1, P (x₂)=2, P (x₃)=7.

3.1.4. Определите, являются ли следующие графы эйлеровыми (гамильтоновыми). Если да, то укажите эйлеров (гамильтонов) цикл.

1. х₂ х₃ 2. х₂х₃

х₆

х₅х₆ х₄

х₁х₄х₁ х₅

х₃х₄х₅

3. х₁ х₉х₁₀ х₆х₂ х₃

х₁х₈х₁ х₇х₈ х₄

х₆ х₅

3.1.5. Укажите, если он существует, изоморфизм следующих графов:

1. х₂ х₃ у₂ у₃

х₁ х₄

у₁ у₄

у₂ у₃

2. х₂ х₃

у₁ у₄

х₁ х₄

3. х₂

у₂ у₃

х₄

х₁ х₃у₁ у₄

х₃у₂ у₃

х₂ х₄

у₁ у₄

х₁ х₅

у₅

3.1.6. Перечислите все неизоморфные между собой подграфы данного графа:

1. 2.

3.1.7. Являются ли следующие графы плоскими:

1. 2. х₃ х₄ х₅

х₂х₆

х₇

х₁ х₈

3.1.8. В графе 4) из №1.4.:

1) слейте вершины: а) х₂ и х₄, б) х₂ и х₅;

2) стяните ребро: а) (х₈х₄), б) (х₇х₅).

3.1.9. Для графов из №1.1. составьте матрицы смежности и инцидентности.

3.1.10. По данной матрице смежности постройте ориентированный граф и, если это возможно, неориентированный граф. Определите степени и полустепени вершин.

1) 0 1 0 2) 0 1 1 3) 0 1 1 1 4) 0 1 1 1