Вопросы и задачи

3.1 Граф задан списком отношений:

ri	r1	r2	r3	r4	r5	r6
(xi; xj)	(x1; x3)	(x2; x4)	(x2; x5)	(x3; x4)	)x3; x5)	(x4; x5)

а) нарисуйте граф;

b) укажите разрез для X={x₁, x₂, x₄} и X\X={x₃, x₅, x₆};

c) нарисуйте частичный граф на рёбрах {r₂, r₄, r₆};

d) нарисуйте суграф на рёбрах {r₁, r₃, r₅, r₇};

e) нарисуйте подграф на вершинах x₂,x₄,x₅,x₆;

f) составьте матрицу инциденции и матрицу смежности.

3. 2 Граф задан списком отображений :

xi	x1	x2	x3	x4	x5	x6
hXi	x2	x1, x4	x4	x2, x3, x5, x6	x4	x4

а) нарисуйте граф;

b) укажите маршрут и переход из вершины x₃ в вершину x₆;

с) укажите разрез для X={x₁, x₂, x₄} и X\X={x₃, x₅, x₆};

4. cоставьте матрицу инциденции и матрицу смежности.

3.3 Реберно-взвешенный граф задан списком отношений:

ri	r1	r2	r3	r4	r5	r6
(xi; xj)	(x1; x3)	(x2; x4)	(x2; x5)	(x3; x4)	)x3; x5)	(x4; x5)
li	4	8	6	10	2	5

а) нарисуйте граф;

b) составьте матрицу весов.

3. 4. Найти число компонент связности графа

3.5. Найти цикломатические и хроматические числа, числа внутренней и внешней устойчивости для графов. Изоморфны ли графы?

3 .6. Для четырех графов найти: дополнение, объединение графов a) и d), пересечение графов b) и d), композицию графов c) и d).

3. 7. Найти основные числа графа (n, m, k, , , , , , , ).

3.8. Найти кратчайшие пути между любой парой вершин.

3.9 Найти распределение максимального потока в сети. Вершина x₁ – исток, вершина x₉ – сток. На каждой дуге указано:

[величина потока - (i, j), пропускная способность – C(i,j)].

3.10 Найти критический путь по алгоритму управления проектом (СПУ),. Продолжительности работ (длина дуги) приведены на рисунке.

Глава 4. Основы математической логики

Математическая логика - это формальная система, носителем которой являются символы и последовательности символов формального языка, а множество операций используется для формирования и вывода суждений формального языка.

Выделяют несколько видов математической логики: логику высказываний и логику предикатов, реляционную логику и нечеткую логику и др.

Логика высказываний (prepositional logic) есть модель формальной системы, предметом которой являются повествовательные предложения, взятые целиком без учета их внутренней структуры.

Логика предикатов (predicate logic) есть формальная сис­тема, предметом которой являются предложения с учетом их внутренних состава и струк­туры.

Логика реляционная (relation logic) есть формальная система, предметом кото­рой являются отношения в виде множества однородных предложений, существенно расширяющие логику предикатов.

Логика нечеткая (fuzzi logic) есть также формальная система, предметом кото­рой являются предложения при нечетком задании - характер­ных признаков отдельных составляющих элементов или отношений между ними.