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

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. х₂ х₃

х₆

х₅ х₆ х₄

х₁ х₄ х₁ х₅

х₃ х₄ х₅

4.

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

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

х₆ х₅

`

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

1. х₂ х₃ у₂ у₃

и

х₁ х₄

у₁ у₄

у₂ у₃

2. х₂ х₃

и

у₁ у₄

х₁ х₄

3. х₂

у₂ у₃

и

х₄

х₁ х₃ у₁ у₄

х₃ у₂ у₃

4.

х₂ х₄

и

у₁ у₄

х₁ х₅

у₅

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

1 0 1 1 0 0 0 0 0 0 1 0 0 0

1 0 0 1 0 0 0 1 0 1 0 1 0 1

0 1 1 0 1 0 0 1

3.1.11. По данной матрице инцидентности постройте граф. Определите степени (полустепени) вершин.

1) 2) ; 3) ; 4)

5) ; 6)

Тема III.2. Приложение теории графов к решению задач.