1. Используя алгоритм генерации варианта GV (приложение А), построить неориентированный граф G: GV(7,{2,3}).
2. Описать граф матрицей смежности и матрицей инцидентности.
3.Изобразить графически граф G и его дополнение .
4. Построить произвольный остовный подграф и подграф, порожденный вершинами {1,2,5,6,7};
5. Построить все помеченные 5-графы, изоморфно вложимые в граф G. Определить классы изоморфных графов, построив биекцию их вершин.
Для каждого класса изоморфных графов привести рисунок абстрактного графа.
6. Построить все помеченные (5-7)-графы (до 20 штук), изоморфные некоторому подграфу G. Определить классы изоморфных графов, построив биекцию их вершин. Для каждого класса изоморфных графов привести рисунок абстрактного графа.
7. Найти все максимальные и наибольшие независимые множества исходного графа, определить число независимости.
8. Найти все максимальные и наибольшие клики данного графа. Определить плотность графа G.
9. Найти все минимальные и наименьшие доминирующие множества, определить число доминирования.
10. Найти полный двудольный подграфKp,q, изоморфно вложимый в Gс максимальным количеством вершин p+q (p≠1). Найти звезду , изоморфно вложимую в Gс максимальным q.
старший 24 мин на 1 снег;
младший --- 40 мин на 1 снег;
сестра ?мин на 1 снег:
Решение:
Алгебраический
Х время в минутах за которое сестра сможет слепить одного снеговика;
1/Х часть снеговика, которую сестра может слепить за 1 минуту;
1/24 часть снеговика, которую может слепить старший брат за минуту;
1/40 часть снеговика, которую может слепить младший брат за минуту;
1/12 часть снеговика, которую слепят за 1 минуту все вместе!
1/Х + 1/24 + 1/40 = 1/12 уравнение, показывающее вклад каждого в слепленную за минуту часть снеговика.
1/Х = 1/12 - 1/24 - 1/40 уравнений, выделяющее часть сестры в общей работе за 1 мин;
1/Х = 10/120 - 5/120 - 3/120 приведение к общему знаменателю дробей в правой части уравнения;
1/Х = (10-5-3)/120 = 2/120 = 1/60 --- часть снеговика которую слепит сестра за 1 мин;
Х = 60 (мин) понадобится сестре, чтобы слепить одного снеговика.
ответ: сестра сможет слепить снеговика за 60 мин
Проверка: 1/60 + 1/24 +1/40 = 1/12; 1/12 = 1/12
Арифметический
1 час = 60 мин
60 : 12 = 5(снег.) слепят все вместе за час
60 : 24 = 60/24 = 2 ц12/24 = 2ц2/2 (снег.) слепит старший брат за час;
60 : 40 = 60/40 = 1 ц20/40 = 1ц1/2 (снег.) слепит младший брат за час;
2ц 1/2 + 1ц 1/2 = 4 (снег.) слепят братья за час
5 - 4 = 1 (снег) слепит сестра за час, т.е. чтобы слепить 1 снеговика ей понадобится 1 час или 60 мин;
ответ: Сестре понадобится 60 мин, чтобы слепить снеговика!
Проверка; 1/60 +1/24 + 1/40 = 1/12