Дискретная математика

К.р. 1

Задание 1
Построить граф, состоящий из Z изолированных компонент мощностью N1, N2б,...,Nz и T изолированных вершин. Во всем графе должно быть I истоков, S стоков, V висячих вершин, R регулярных вершины, три из которых имеют степени r1, r2, r3. Максимальная степень кратности дуг графа должна быть K. В графе должно быть не менее, чем M пар противоположных дуг. В отчете представить построенный граф с выделением всех построенных элементов. Надписать полустепени исхода и захода для каждой вершины.
Задание 2
Построить ориентированный граф из 7 вершин и 14 дуг, содержащий один исток, один сток, одну изолированную вершину, одну регулярную вершину, одну петлю, пару одинаково направленных дуг, пару противоположно направленных дуг. С истоком и со стоком должно быть связано более двух дуг. Построить и проанализировать следующие способы представления графов: матрица смежности, матрица инцидентности, матрицы окрестностей вершин по входам и по выходам, список дуг. В отчете представить построенный граф и матричные представления графа с описанием.
Задание 3
Построить связанный граф из N вершин, не содержащих висячих и изолированных вершин, но содержащий T точкек сочленения так, чтобы они не были смежными. Рассчитать ранги вершин этого графа. В отчете представить построенный граф с выделенными точками сочленения и подписанными рангами каждой вершины.
Задание 4
Построить связанный ориентированный граф, содержащий K сильных компонент связанности мощностью N1, N2,...,Nk. Свернуть граф по найденным компонентам. В отчете представить граф, раскрашенный по компонентам и граф-свертку.
Задание 5
Построить связанный ориентированный ациклический непоследовательный граф, состоящий из L порядковых уровней мощностью N1,N2,...,NL. Граф содержит N1 истоков и NL стоков. Свернуть граф по найденным уровням. В отчете представить граф, упорядоченный по уровням слева направо и граф-свертку.
Задание 6
Построить связанный граф из P вершин и Q дуг. Используя метод, описанный в учебном пособии, перечислить все маршруты этого графа, длиной 1, 2, 3. В отчете привести граф и выкладки по вычислению матриц.
Задание 7
Построить связанный ориентированный граф из N вершин, содержащий один исток и один сток, не содержащий петель. Задать веса на дугах графа и пронумеровать все вершины. Между истоком и стоком построить не менее P путей через остальные вершины, длиной больше k-дуг.
Изменяя веса на дугах модифицировать граф так, чтобы кратчайшие пути по сумме весов и по количеству дуг между истоком и стоком не имели ни одной общей дуги. В отчете представить граф с выделенными путями, указать длину путей по весам и по количеству дуг.
На этом же графе построить исходящее дерево кратчайших путей с корнем в истоке и заходящее дерево кратчайших путей с корнем в стоке.
Задание 8
Построить связанный ориентированный граф, имеющий как минимум две центральные вершины, как минимум две периферийные вершины, как минимум две обычные вершины так, чтобы его радиус был не равен нулю и не равен диаметру. Начать построение с 6 вершин, добиться результата добавлением и удалением дуг и вершин. Построить максимальное покрывающее дерево кратчайших путей. В отчете представить построенные граф с выделенным деревом, центром и периферией, над вершинами надписать их эксцентриситеты, указать значения радиуса и диаметра графа.
Задание 9
Придумать Q свойств некой системы из N элементов. Построить ориентированный граф системы, задать в качестве вспомогательного веса вершин текстовые идентификаторы, а в качестве основного веса – бинарные цепочки (ширина равна количеству свойств). Проставить на вершинах основные веса в виде цепочки нулей и единиц в зависимости от того, обладает вершина соответствующим свойством (1) или нет (0). Используя метод «свертка по кодам» выполнить три свертки построенного графа при различных сочетаниях нулей и единиц в маске макросвойств. В отчете представить описание свойств, описание элементов системы, исходные граф системы с бинарными вершинами, три графа свертки по трем маскам макросвойств.

Дата выполнения: 26/02/2010

К.р.2

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

Дата выполнения: 25/02/2010

К.р.3

Построить схему из функциональных элементов, соответствующую заданной логической формуле. Упростить заданную логическую формулу и указать, какие правила и законы булевой алгебры были применены на каждом шаге преобразований. Построить схему из функциональных элементов, соответствующую упрощенной логической формуле.

Дата выполнения: 25/02/2010

Контрольная 1. Вариант 1 (А)

Исходные данные:


 

Контрольная 2. Вариант 1 (А)

Исходные данные:
Задание 1.Т=1 и Z=3; N1=6, N2=8; N3=9; I=2, S=3, V=2; R=4: r1=2, r2=3, r4=4; K=4 и M>2.
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=17 и T=4
Задание 4. K=5:N1=2, N2=3, N3=4, N4=5, N5=6
Задание 5. L=5:N1=2, N2=3, N3=4, N4=5, N5=6
Задание 6.Перечислить маршруты:

Задание 7. N=20//P>4 и k>4
Задание 8. общее для всех
Задание 9. Q=6 и N=12

Контрольная 3. Вариант 1 (А)

Исходные данные:

Контрольная 1. Вариант 2 (Б)

Исходные данные:

Контрольная 2. Вариант 2 (Б)

Исходные данные:
Задание 1.Т=1 и Z=4; N1=2, N2=5; N3=6; N4=7 // I=3, S=3, V=3;  R=4: r1=2, r2=3, r4=4; K=4 и M>3.
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=12 и T=3
Задание 4. K=5:N1=4, N2=3, N3=1, N4=5, N5=6
Задание 5. L=5:N1=3, N2=4, N3=2, N4=4, N5=3
Задание 6.Перечислить маршруты:

Задание 7. N=23//P>5 и k>4
Задание 8. общее для всех
Задание 9. Q=6 и N=14

Контрольная 3. Вариант 2 (Б)

Исходные данные:

Контрольная 1. Вариант 3 (В)

Исходные данные:

Контрольная 2. Вариант 3 (В)

Исходные данные:
Задание 1.Т=2 и Z=4; N1=3, N2=4; N3=6; N4=6 // I=2, S=2, V=2 //  R=5: r1=3, r2=4, r4=5 // K=5 и M>3.
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=11 и T=3
Задание 4. K=4:N1=4, N2=5, N3=6, N4=7
Задание 5. L=5:N1=3, N2=1, N3=2, N4=4, N5=2
Задание 6.Перечислить маршруты:

Задание 7. N=20//P>4 и k>5
Задание 8. общее для всех
Задание 9. Q=7 и N=16

Контрольная 3. Вариант 3 (В)

Исходные данные:

Контрольная 1. Вариант 4 (Г)

Исходные данные:

Контрольная 2. Вариант 4 (Г)

Исходные данные:
Задание 1.Т=2 и Z=4; N1=4, N2=5; N3=6; N4=7 // I=2, S=3, V=3 //  R=5: r1=1, r2=2, r4=3 // K=3 и M>3.
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=9 и T=2
Задание 4. K=4:N1=3, N2=4, N3=5, N4=6
Задание 5. L=5:N1=3, N2=2, N3=4, N4=2, N5=3
Задание 6.Перечислить маршруты:

Задание 7. N=20//P>4 и k>4
Задание 8. общее для всех
Задание 9. Q=7 и N=14

Контрольная 3. Вариант 4 (Г)

Исходные данные:

Контрольная 1. Вариант 5 (Д)

Исходные данные:

Контрольная 2. Вариант 5 (Д)

Исходные данные:
Задание 1.Т=2 и Z=3; N1=6, N2=7; N3=8 // I=3, S=2, V=3 //  R=4: r1=2, r2=3, r4=4 // K=5 и M>4
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=8 и T=2
Задание 4. K=5:N1=3, N2=4, N3=5, N4=6, N4=7
Задание 5. L=5:N1=2, N2=1, N3=4, N4=4, N5=2
Задание 6.Перечислить маршруты:

Задание 7. N=22//P>3 и k>6
Задание 8. общее для всех
Задание 9. Q=7 и N=15

Контрольная 3. Вариант 5 (Д)

Исходные данные:

Контрольная 1. Вариант 6 (ЕЁ)

Исходные данные:

Контрольная 2. Вариант 6 (ЕЁ)

Исходные данные:
Задание 1.Т=3 и Z=3; N1=5, N2=6; N3=7 // I=2, S=2, V=2 //  R=3: r1=2, r2=3, r4=4 // K=5 и M>3
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=18 и T=4
Задание 4. K=5:N1=4, N2=5, N3=6, N4=7, N4=1
Задание 5. L=5:N1=3, N2=4, N3=5, N4=5, N5=2
Задание 6.Перечислить маршруты:

Задание 7. N=25//P>5 и k>5
Задание 8. общее для всех
Задание 9. Q=6 и N=15

Контрольная 3. Вариант 6 (ЕЁ)

Исходные данные:

Контрольная 1. Вариант 7 (Ж)

Исходные данные:

Контрольная 2. Вариант 7 (Ж)

Исходные данные:
Задание 1.Т=1 и Z=5; N1=2, N2=4; N3=5, N4=6, N5=7 // I=4, S=3, V=3 //  R=5: r1=3, r2=4, r4=5 // K=5 и M>4
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=14 и T=4
Задание 4. K=6:N1=4, N2=4, N3=3, N4=3, N4=5, N6=5
Задание 5. L=5:N1=1, N2=3, N3=1, N4=2, N5=2
Задание 6.Перечислить маршруты:

Задание 7. N=25//P>6 и k>4
Задание 8. общее для всех
Задание 9. Q=8 и N=14

Контрольная 3. Вариант 7 (Ж)

Исходные данные:

Контрольная 1. Вариант 8 (З)

Исходные данные:

Контрольная 2. Вариант 8 (З)

Исходные данные:
Задание 1.Т=2 и Z=5; N1=3, N2=4; N3=5, N4=6, N5=7 // I=3, S=4, V=3 //  R=5: r1=2, r2=3, r4=4 // K=4 и M>4
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=15 и T=4
Задание 4. K=4:N1=2, N2=3, N3=4, N4=5
Задание 5. L=6:N1=2, N2=2, N3=1, N4=3, N5=3, N6=2
Задание 6.Перечислить маршруты:

Задание 7. N=23//P>4 и k>6
Задание 8. общее для всех
Задание 9. Q=8 и N=12

Контрольная 3. Вариант 8 (З)

Исходные данные:

Контрольная 1. Вариант 9 (ИЙ)

Исходные данные:

Контрольная 2. Вариант 9 (ИЙ)

Исходные данные:
Задание 1.Т=3 и Z=5; N1=3, N2=5; N3=5, N4=6, N5=6 // I=3, S=3, V=2 //  R=4: r1=3, r2=4, r4=5 // K=5 и M>3
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=13 и T=4
Задание 4. K=6:N1=3, N2=3, N3=4, N4=4, N5=5, N6=5
Задание 5. L=5:N1=2, N2=3, N3=4, N4=3, N5=2
Задание 6.Перечислить маршруты:

Задание 7. N=25//P>6 и k>4
Задание 8. общее для всех
Задание 9. Q=6 и N=13

Контрольная 3. Вариант 9 (ИЙ)

Исходные данные:

Контрольная 1. Вариант 10 (К)

Исходные данные:

Контрольная 2. Вариант 10 (К)

Исходные данные:
Задание 1.Т=3 и Z=5; N1=2, N2=5; N3=5, N4=7, N5=7 // I=2, S=2, V=2 //  R=4: r1=2, r2=4, r4=6 // K=6 и M>4
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=11 и T=2
Задание 4. K=6:N1=4, N2=4, N3=5, N4=5, N5=6, N6=6
Задание 5. L=5:N1=2, N2=3, N3=4, N4=3, N5=2
Задание 6.Перечислить маршруты:

Задание 7. N=25//P>7 и k>4
Задание 8. общее для всех
Задание 9. Q=7 и N=13

Контрольная 3. Вариант 10 (К)

Исходные данные:

Контрольная 1. Вариант 11 (Л)

Исходные данные:

Контрольная 2. Вариант 11 (Л)

Исходные данные:
Задание 1.Т=2 и Z=6; N1=3, N2=5; N3=5, N4=6, N5=6, N6=7 // I=3, S=4, V=3 //  R=5: r1=4, r2=5, r4=6 // K=5 и M>4
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=14 и T=3
Задание 4. K=6:N1=2, N2=3, N3=3, N4=4, N5=4, N6=5
Задание 5. L=4:N1=2, N2=4, N3=4, N4=3
Задание 6.Перечислить маршруты:

Задание 7. N=22//P>6 и k>6
Задание 8. общее для всех
Задание 9. Q=8 и N=13

Контрольная 3. Вариант 11 (Л)

Исходные данные:

Контрольная 1. Вариант 12 (М)

Исходные данные:

Контрольная 2. Вариант 12 (М)

Исходные данные:
Задание 1.Т=3 и Z=6; N1=4, N2=4; N3=5, N4=5, N5=6, N6=6 // I=4, S=4, V=3 //  R=5: r1=3, r2=4, r4=5 // K=5 и M>4
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=10 и T=2
Задание 4. K=6:N1=1, N2=2, N3=3, N4=4, N5=5, N6=6
Задание 5. L=4:N1=3, N2=2, N3=4, N4=3
Задание 6.Перечислить маршруты:

Задание 7. N=22//P>3 и k>7
Задание 8. общее для всех
Задание 9. Q=8 и N=15

Контрольная 3. Вариант 12 (М)

Исходные данные:

Контрольная 1. Вариант 13 (Н)

Исходные данные:

Контрольная 2. Вариант 13 (Н)

Исходные данные:
Задание 1.Т=1 и Z=3; N1=5, N2=6; N3=7 // I=2, S=2, V=1 //  R=3: r1=1, r2=2, r4=3 // K=3 и M>2
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=10 и T=2
Задание 4. K=5:N1=3, N2=4, N3=5, N4=6, N5=6
Задание 5. L=5:N1=2, N2=1, N3=2, N4=3, N5=2
Задание 6.Перечислить маршруты:

Задание 7. N=18//P>3 и k>3
Задание 8. общее для всех
Задание 9. Q=5 и N=12

Контрольная 3. Вариант 13 (Н)

Исходные данные:

Контрольная 1. Вариант 14 (О)

Исходные данные:

Контрольная 2. Вариант 14 (О)

Исходные данные:
Задание 1.Т=2 и Z=5; N1=3, N2=8, N3=4, N4=5, N5=6 // I=4, S=3, V=2 //  R=6: r1=1, r2=2, r4=3 // K=5 и M>3
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=20 и T=5
Задание 4. K=6:N1=3, N2=3, N3=4, N4=4, N5=5, N6=5
Задание 5. L=7:N1=2, N2=3, N3=4, N4=3, N5=2, N6=3, N7=2
Задание 6.Перечислить маршруты:

Задание 7. N=24//P>6 и k>5
Задание 8. общее для всех
Задание 9. Q=6 и N=15

Контрольная 3. Вариант 14 (О)

Исходные данные:

Контрольная 1. Вариант 15 (П)

Исходные данные:

Контрольная 2. Вариант 15 (П)

Исходные данные:
Задание 1.Т=2 и Z=4; N1=6, N2=6, N3=5, N4=5 // I=3, S=3, V=1 //  R=4: r1=2, r2=3, r4=4 // K=4 и M>2
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=12 и T=3
Задание 4. K=5:N1=4, N2=4, N3=5, N4=5, N5=6
Задание 5. L=7:N1=2, N2=1, N3=3, N4=2, N5=1, N6=3, N7=2
Задание 6.Перечислить маршруты:

Задание 7. N=25//P>5 и k>4
Задание 8. общее для всех
Задание 9. Q=6 и N=20

Контрольная 3. Вариант 15 (П)

Исходные данные:

Контрольная 1. Вариант 17 (С)

Исходные данные:

Контрольная 2. Вариант 17 (С)

Исходные данные:
Задание 1.Т=2 и Z=5; N1=5, N2=6, N3=7, N4=8, N5=9 // I=4, S=4, V=3 //  R=6: r1=3, r2=4, r4=6 // K=6 и M>4
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=20 и T=5
Задание 4. K=8:N1=3, N2=3, N3=4, N4=4, N5=5, N6=5, N7=6, N8=6
Задание 5. L=8:N1=2, N2=3, N3=1, N4=4, N5=2, N6=2, N7=3, N8=3
Задание 6.Перечислить маршруты:

Задание 7. N=26//P>6 и k>5
Задание 8. общее для всех
Задание 9. Q=7 и N=20

Контрольная 3. Вариант 17 (С)

Исходные данные:

Контрольная 1. Вариант 19 (У)

Исходные данные:

Контрольная 2. Вариант 19 (У)

Исходные данные:
Задание 1.Т=1 и Z=5; N1=2, N2=4, N3=6, N4=8, N5=10 // I=3, S=5, V=3 //  R=6: r1=3, r2=4, r4=5 // K=6 и M>4
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=23 и T=6
Задание 4. K=6:N1=4, N2=4, N3=5, N4=5, N5=6, N6=6
Задание 5. L=9:N1=2, N2=2, N3=3, N4=1, N5=2, N6=2, N7=3, N8=4, N9=3
Задание 6.Перечислить маршруты:

Задание 7. N=25//P>4 и k>7
Задание 8. общее для всех
Задание 9. Q=4 и N=10

Контрольная 3. Вариант 19 (У)

Исходные данные:

Контрольная 1. Вариант 20 (Ф)

Исходные данные:

Контрольная 2. Вариант 20 (Ф)

Исходные данные:
Задание 1.Т=3 и Z=5; N1=6, N2=6, N3=7, N4=7, N5=8 // I=4, S=4, V=2 //  R=5: r1=3, r2=4, r4=5 // K=6 и M>3
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=25 и T=6
Задание 4. K=6:N1=3, N2=6, N3=5, N4=5, N5=4, N6=8
Задание 5. L=8:N1=3, N2=2, N3=1, N4=2, N5=4, N6=3, N7=4, N8=3
Задание 6.Перечислить маршруты:

Задание 7. N=25//P>4 и k>5
Задание 8. общее для всех
Задание 9. Q=7 и N=15

Контрольная 3. Вариант 20 (Ф)

Исходные данные:

Контрольная 1. Вариант 21 (Х)

Исходные данные:

Контрольная 2. Вариант 21 (Х)

Исходные данные:
Задание 1.Т=2 и Z=3; N1=10, N2=9, N3=8 // I=4, S=4, V=2 //  R=5: r1=3, r2=4, r4=5 // K=5 и M>3
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=14 и T=2
Задание 4. K=6:N1=2, N2=3, N3=4, N4=5, N5=6, N6=7
Задание 5. L=7:N1=2, N2=3, N3=2, N4=4, N5=3, N6=2, N7=3
Задание 6.Перечислить маршруты:

Задание 7. N=20//P>3 и k>5
Задание 8. общее для всех
Задание 9. Q=6 и N=12

Контрольная 3. Вариант 21 (Х)

Исходные данные:

Контрольная 1. Вариант 23 (Ч)

Исходные данные:

Контрольная 2. Вариант 23 (Ч)

Исходные данные:
Задание 1.Т=2 и Z=3; N1=10, N2=9, N3=8 // I=4, S=4, V=2 //  R=5: r1=3, r2=4, r4=5 // K=5 и M>3
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=14 и T=3
Задание 4. K=6:N1=2, N2=3, N3=4, N4=5, N5=6, N6=7
Задание 5. L=5:N1=2, N2=3, N3=2, N4=4, N5=3
Задание 6.Перечислить маршруты:

Задание 7. N=20//P>3 и k>5
Задание 8. общее для всех
Задание 9. Q=6 и N=12

Контрольная 3. Вариант 23 (Ч)

Исходные данные:

Контрольная 1. Вариант 24 (ШЩ)

Исходные данные:

Контрольная 2. Вариант 24 (ШЩ)

Исходные данные:
Задание 1.Т=2 и Z=2; N1=12, N2=14 // I=2, S=2, V=2 //  R=4: r1=1, r2=2, r4=3 // K=5 и M>4
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=12 и T=2
Задание 4. K=5:N1=2, N2=3, N3=4, N4=5, N5=6
Задание 5. L=8:N1=3, N2=2, N3=3, N4=3, N5=2, N6=4, N7=3, N8=2
Задание 6.Перечислить маршруты:

Задание 7. N=22//P>5 и k>7
Задание 8. общее для всех
Задание 9. Q=6 и N=18

Контрольная 3. Вариант 24 (ШЩ)

Исходные данные:

Контрольная 1. Вариант 25 (ЭЯ)

Исходные данные:

Контрольная 2. Вариант 25 (ЭЯ)

Исходные данные:
Задание 1.Т=1 и Z=3; N1=6, N2=8, N3=9 // I=2, S=3, V=2 //  R=4: r1=2, r2=3, r4=5 // K=4 и M>2
Задание 2. Матрицы: VV, VU, FO, FI, IO
Задание 3. N=12 и T=3
Задание 4. K=5:N1=2, N2=3, N3=4, N4=5, N5=6
Задание 5. L=5:N1=3, N2=4, N3=2, N4=4, N5=3
Задание 6.Перечислить маршруты:

Задание 7. N=20//P>4 и k>4
Задание 8. общее для всех
Задание 9. Q=6 и N=12

Контрольная 3. Вариант 25 (ЭЯ)

Исходные данные: