Найти количество целых положительных чисел, не превосходящих 200 и не делящихся ни на одно из простых чисел 2, 3, 7.

Решение.

Х₂ – делятся на 2

Х₃ – делятся на 3

Х₇ – делятся на 7

Х₂ÈХ₃ÈХ₇ – множество чисел, которые делятся хотя бы на одно из чисел 2, 3, 7.

N₀ – не делятся на 2, 3, 7

N₀=200-| Х₂ÈХ₃ÈХ₇ |=200-|X₂|+|X₃|+|X₇|-|X₂ÇX₃|-|X₂ÇX₇|-|X₃ÇX₇|+| Х₂ÇХ₃ÇХ₇ |=200-100+66+28-33-14-9+4=134

Ответ: 134 целых числа.

13. Даны орграфы D₁, D₂. Найдите D₁È D₂, D₁Ç D₂ . Для орграфа D₁È D₂ запишите все формы представления, определите полустепени исхода и захода вершин, постройте частичный граф, подграф, дополнительный орграф.

D₁: 1 2 D₂: 1

4 3 3 2

Решение.

D₁È D₂ 1 2 D₁Ç D₂ 1 2

4 3 3

Формы представления:

1. Массив ребер

D=(V,X)

V={1,2,3,4}

X={X₁=(1,2),X₂=(1,3),X₃=(2,4),X₄=(3,2),X₅=(4,3)}

2. Списки смежности

D=(V,Г)

V={1,2,3,4}

Г₁={2,3}

Г₂={4}

Г₃={2}

Г₄={3}

3. Матричный

Матрица смежности

A(D)=

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

δ^-(V)- полустепень исхода

δ^-(1)=2

δ^-(2)=1

δ^-(3)=1

δ^-(4)=1

δ⁺(V)- полустепень захода

δ⁺(1)=0

δ⁺(2)=2

δ⁺(3)=2

δ⁺(4)=1

Частичный граф- граф, полученный из исходного графа исключением некоторых ребер.

1 2

4 3

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

1 2

Дополнительный граф-граф, состоящий из вершин и ребер, которыми исходный граф отличается от полного графа.

1 2

4 3

Пусть орграф D задан матрицей смежности. Найти количество компонент сильной связности орграфа и определить матрицы смежности этих компонент. Постройте изображения орграфа и его компонент сильной связности.

Решение.

Найдем прямое транзитивное замыкание(вершины, в которые можно попасть из вершины V),

Найдем обратное транзитивное замыкание(множество вершин, из которых можно попасть в вершину V)

P=1

A(D₁)=

P=2

A(D₂)=

P=3

A(D₃)=

P=4

A(D₄)=

V₂ V₃

V₁ V₄

V₆ V₅

15. Определить минимальный путь из v₁ в v₇ в нагруженном орграфе с заданной матрицей длин дуг: