Часть 2

§1

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

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

в) 2;0;

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

ж) v₆, v₅.

1.2 а)

б)

в)

1.3. d⁺(v₁)=2, d⁺(v₄)=1, d^-(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.

3.2. а) б) в)

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

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

§ 4.

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

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

для графа K₈: m = 28, d(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