Juk_Ilyenko_Moklyachuk_Orlovskiy_DM_praktikum

остовне дерево. Тому мiнiмальна кiлькiсть ребер буде 2000 − 1 = 1999. Вiдповiдно, можна зробити 3842 − 1999 = 1843 розрiз до того, як сiтка розпадеться.

Задачi для аудиторної та домашньої роботи

№15.3. У товариствi з 20 осiб кожен знайомий рiвно з трьома iншими членами. Чи можливо таке товариство?

№15.4. Проводиться шаховий турнiр, в якому беруть участь 16 гравцiв. Виявилось, що в деякий момент лише двоє шахiстiв зiграли рiвну кiлькiсть партiй. Довести, що в цей момент iснує єдиний учасник, який не зiграв жодної партiї, або ж єдиний учасник, що зiграв всi.

№15.5. У футбольному турнiрi беруть участь 29 команд. Довести, що в будь-який момент знайдеться команда, яка зiграла парну кiлькiсть матчiв.

№15.6. У заданому графi:

1.Знайти всi можливi ланцюги з 1 в 12;

2.Знайти всi простi ланцюги з 1 в 12;

3.Знайти ланцюг, що веде з 1 в 12 та мiстить усi вершини графа;

4.Знайти, яко вiн iснує, простий ланцюг, що веде з 1 в 12 та мiстить усi вершини графа;

5.Знайти маршрут у графi, який веде з з 1 в 12 та не є ланцюгом;

6.Знайти всi простi цикла графа.

150

10

12

3 5

89

4

№ 15.7. Знайти такi маршрути через музей, щоб пройти всi кiмнати лише один раз.

№ 15.8. Знайти в лабiринтi такий маршрут, щоб пройти через усi дверi по одному разу i повернутися.

151

№ 15.9. Чи є iзоморфними наступнi пари графiв? Вiдповiдь обгрунтувати.

1.

2.

3.

4.

152

5.

6.

7.

8.

9.

10.

153

Звiдси ( + 1) = − , i

= − + 1 = −1 + +1 1.

Так як має належати , то + 1 має бути дiльником 1, тобто

+ 1 = ±1, звiдки = 0, = 0 або = −2, = −2. Отже, обернений елемент iснує лише для елементi = 0 та = −2, тому вiдносно заданої операцiї групу не утворює.

№ 16.2. Нехай на множинi цiлих чисел введено операцiю * =

+ + 5. Чи iзоморфнi множини ( , *) та ( , +)?

Розв’язок. Нехай - нейтральний елемент в за операцiєю *. Тодi

* =, тобто + + 5 = , тому = −5. Якщо : ( , *) → ( , +) - iзоморфiзм, то (0) = 5, звiдки можна припустити, що ( ) = − 5.

Доведемо, що це iзоморфiзм. Зрозумiло, що ( ) : → взаємно однозначне. Покажемо, що ( + ) = ( ) * ( ). Маємо:

( + ) = + − 5; ( ) = − 5; ( ) = − 5;

( ) * ( ) = ( − 5) + ( − 5) + 5 = + − 5.

Отже, ( ) = − 5 – iзоморфiзм.

№ 16.3. Нехай = ( , +) - група цiлих чисел вiдносно операцiї додавання, = (3 , +) - група цiлих чисел, що дiляться на 3 нацiло, вiдносно додавання. Довести, що - пiдгрупа та знайти сумiжнi класи / .

Розв’язок. Доведемо, що пiдгрупа . Дiйсно, якщо , 3 , то = 3 , = 3 , , , звiдки + = 3 + 3 = 3( + ) ,

(− ) = −3 = 3(− ) . Отже, - пiдгрупа .

155

Знайдемо сумiжнi класи / . Оскiльки комутативна, то - теж, тому лiвi сумiжнi класи будуть рiвнi вiдповiдним правим. Числа ,

потрапляють в один клас сумiжностi, якщо − = 3 , тобто коли та

при дiленнi на 3 дають однакову остачу. Можливi три варiанти остачi: 0, 1, 2. Отже, маємо три сумiжнi класи:

0 = { | = 3 , } = {0, 3, −3, 6, −6, . . .};

1 = { | = 3 + 1, } = {1, 4, −2, 7, −5, . . .};

2 = { | = 3 + 2, } = {2, 5, −1, 8, −4, . . .}.

Задачi для аудиторної та домашньої роботи

№ 16.4. Дослiдити, чи будуть утворювати моноїд або групу наступнi алгебраїчнi операцiї на множинi .

1.= {0, 1}, * = ;

2.= {0, 1}, * = ;

5.= , * = − ;

6.= (0, +∞), * = ;

7.= , * = НСД( , );

8.= , * = НСК( , );

156

9.= 2, ( 1, 1) * ( 2, 2) = ( 1 2 + 1 2, 0);

10.= 2, ( 1, 1) * ( 2, 2) = ( 1 2, 1 2 + 1);

11.= , * = + − ;

12.= , * = + − ;

13.= 2, ( 1, 1) * ( 2, 2) = ( 1 2 + 1, 1 2;

14.= { ( ) : → }, ( * )( ) = ( ( ));

15.= { ( ) = + | , }, ( * )( ) = ( ( ));

16.= = {0, 1, . . . , − 1}, * = + ( );

17.= 5 = {0, 1, 2, 3, 4}, * = + ( 5);

18.= 2( ) - множина квадратних матриць другого порядку з дiйсними елементами, * - операцiя множення матриць;

19.= 2( ) - множина квадратних матриць другого порядку з ненульовим визначником, * - операцiя множення матриць;

20.= 2( ) - множина квадратних матриць другого порядку з одиничним визначником, * - операцiя множення матриць;

21.= , * = sin sin ;

22.= [0, 1], * = + − [ + ];

23.- множина симетричних матриць -го порядку, * - операцiя додавання матриць;

157

24.- множина антисиметричних матриць -го порядку, * - операцiя додавання матриць;

25.- множина симетричних матриць 2-го порядку, * - операцiя множення матриць;

26.- множина антисиметричних матриць 2-го порядку, * - операцiя множення матриць;

27.- множина верхнiх трикутних матриць 2-го порядку, * - опе-

рацiя множення матриць;

№ 16.5. Скiльки рiзних алгебраїчних операцiй можна задати на множинi

, що має елементiв?

№16.6. Скiльки рiзних комутативних операцiй можна задати на множинi , що має елементiв?

№16.7. Дослiдити, чи будуть наступнi множини iз заданими алгебраїчними операцiями ( , ) та ( , *) iзоморфними.

1.= = [ , ], = { , }, * = { , };

2.= = , = + , * = + − 3;

√

3. = = , = + , * = 2 + 2;

4.= = , = + , * = ;

5.= (0, +∞), = , = * = + ;

158

6. = = 0, 1, = , * = ;

√

7.= = , = + , * = 3 3 + 3;

8.= , = + , = 3, * = + ( 3);

9.= = 0, 1, = , * = .

№16.8. Нехай = ( , +) - група з цiлих чисел. Знайти всi сумiжнi класи групи по пiдгрупi = (5 , +).

№16.9. Знайти всi пiдгрупи групи 4.

№16.10. Знайти сумiжнi класи групи 4 по пiдгрупi 2.

№16.11. Знайти всi пiдгрупи симетричної групи 3.

№16.12. Знайти лiвi сумiжнi класи симетричної групи 3 по пiдгрупi

= { , (3, 2)}

№ 16.13. Знайти правi сумiжнi класи симетричної групи 3 по пiдгрупi

= { , (3, 2)}

№16.15. Довести, що симетрiї ромба утворюють групу.

№16.16. Чи iзоморфна група симетрiй ромба циклiчнiй групi 4?

№16.17. Довести, що кожна циклiчна група iзоморфна або при деякому .

№16.18. Обчислити порядки кожного з елементiв групи:

159