Часть 2

§1

1.1. а) неорграф, псевдограф;

б) (v₁)=3; (v₅)=4;

в) 2;0;

г) (v₁,v₃),(v₂,v₃);

ж) v₆, v₅.

1.2 а)

б)

в)

1.3. ⁺(v₁)=2, ⁺(v₄)=1, ^-(v₃)=2.

1.4. а) нет контуров;

б) есть контуры;

в) есть контуры;

1.6. количество путей длины 1 из v₃ в v₂ равно 0;из v₂ в v₄ равно 0;

количество путей длины 2 из v₃ в v₂ равно 3; из v₂ в v₄ равно 6;

количество путей длины 3 из v₃ в v₂ равно 6;из v₂ в v₄ равно 12;

орграф имеет контур.

1.7. количество путей длины 2 из v₁ в v₂ равно 2;

количество путей длины 3 из v₁ в v₂ равно 2;

количество путей длины 4 из v₁ в v₂ равно 2.

§3

а) несвязный, k=2.

б) не является сильно связным, слабо связным, односторонне связный. р=3.

в) связный, к=1.

2. а) б) в)

3.3. а)р=3 Д₁: . v₂ Д₂: v₄

Д₃:

б) р=3 Д₁: Д₂: v₃

Д₃:

v₅

§ 4.

4.1. Для графа K₆: m = 15, (v_i) = 5;

для графа K₇: m = 21, (v_i) = 6;

для графа K₈: m = 28, (v_i) = 7.

4.2. 24; 15; 6.

4.3. 4; 12; 32; 80

4.4. 0.

4.5. 10.

4.7. n = 21, m = 210

4.10. m = 8

§ 5

5.1. a) v₁ v₄ v₃ v₂ v_7; v₁ v₄ v₅ v₂ v_7;

v₁ v₆ v₃ v₂ v_7; v₁ v₆ v₅ v₂ v_7; v₂ v_5.

б) v₁ v₅ v₃ v₂ v_7; v₁ v₅ v₄ v₂ v_7;

v₁ v₆ v₃ v₂ v_7; v₁ v₆ v₄ v₂ v_7; v₂ v_5.

§ 6

6.1. а) d=2; r=1;

б) d=3; r=2;

в) d=2; r=1.

6.2. а) d=r=1;

б) d=r=2;

в) d=r=3.

6.3. а) d=3; r=2;

б) d=5; r=3.

§ 7

7.1. а) б)

§ 8.

8.1. а) имеется эйлерова цепь;

б) имеется эйлеров цикл;

в) имеется эйлеров цикл.

8.5. Сможет

8.6. В 19 комнате

§9

9.1. а) d = 4, r = 2

б) d = 5, r = 2

в) d = 3, r = 1

г) d = 4, r = 2

9.2. n!

9.3. 14 способами

наименьшая длина пути равна 2

наибольшая длина пути равна 7

9.4. в позицию 2

9.9. а) 6; б) 2

9.10. а)

9.11. а) 8

б) 5

в) 4

§10

10.1. а) 6; б) 2; в) 2; г) 2

10.3. 3

Тест по теории множеств и отношений

1. Подмножество обозначается:

а) ;

б) ;

в) ;

г) .

2. Операция «+» в теории множеств называется

а) суммой;	в) симметрической разностью;
б) сложением по модулю 2;	г) объединением.

3. Отображение f: АВ называется ____________, если оно инъективно и сюръективно

а) симметричным; б) биективным;

в) унарным; г) несимметричным.

4. Всякое отношение эквивалентности ρ, заданное на множестве А, определяет на этом множестве

а) разбиение;

б) порядок;

в) элемент;

г) структуру.

5. Отношение (а,в)| (в,а)ρ называется:

а) тождественным; б) универсальным отношением;

в) дополнением; г) инверсией.

6. Разбиением множества 1,2,3 является

а) {1}, {1, 2}, {3};

б) 1, 2,3;

в) 1,2, 2,3;

г) 1,2,3, 2,3;

7. Бинарное отношение ρ, заданное на множестве А, для которого выполняется условие: если (х,у)ρ  (у,х)ρ, называется

а) симметричным; б) транзитивным

в) антисимметричным; г) несимметричным

8. Множество R_ρ=в | вВ а (а,в) ρ называется

а) областью значений; б) бинарным отношением;

в) композицией; г) областью определения.

9.Отношение частичного порядка на множестве А, для которого любые два элемента сравнимы, называется

а) квазипорядком; б) строгим порядком;

в) линейным порядком; г) нестрогим порядком.

10. Отношение I_А=(а,а) | аА называется

а) универсальным; б) тождественным;

в) дополнением; г) обратным;

11. Из отношений f₁=(4, 5), (5, 6), (6, 5), f₂=(4, 5), (4, 6), (5, 6), f₃=(4, 6), (5, 6), (6, 4) функциями являются

а) f2, f3;

б) f1, f2, f3;

в) f1, f2;

г) f1, f3.

12. Собственное подмножество обозначается символом

а) ;

б) ;

в) ;

г) ;

13. Множество [х]_ρ=у | уА и (х,у)ρ называется:

а) бинарным отношением; б) классом эквивалентности;

в) областью определения; г) областью значений.

14. Декартово произведение множеств обозначается:

а) АВ;

б) АВ;

в) АВ;

г) А*В;

15. Даны множества А=1, 1, 0, 2, В=1, 0, 2, С=1, 0, 0, 2, D=1, 1, 0, 0, 2, Е= 1, 1,0 ,2 ,2.

16. Равными являются множества

а) А, D;

б) А, С, Е;

в) А, D, Е;

г) А, В, D, Е.