Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Найти количество целых положительных чисел, не превосходящих 200 и не делящихся ни на одно из простых чисел 2, 3, 7.
Решение. Х2 – делятся на 2 Х3 – делятся на 3 Х7 – делятся на 7 Х2 È Х3È Х7 – множество чисел, которые делятся хотя бы на одно из чисел 2, 3, 7. N0 – не делятся на 2, 3, 7 N0=200-| Х2È Х3È Х7 |=200-|X2|+|X3|+|X7|-|X2Ç X3|-|X2Ç X7|-|X3Ç X7|+| Х2Ç Х3Ç Х7 |=200-100+66+28-33-14-9+4=134 Ответ: 134 целых числа. 13. Даны орграфы D1, D2. Найдите D1È D2, D1Ç D2. Для орграфа D1È D2 запишите все формы представления, определите полустепени исхода и захода вершин, постройте частичный граф, подграф, дополнительный орграф.
D1: 1 2 D2: 1
4 3 3 2
Решение. D1È D2 1 2 D1Ç D2 1 2
4 3 3 Формы представления: 1. Массив ребер D=(V, X) V={1, 2, 3, 4} X={X1=(1, 2), X2=(1, 3), X3=(2, 4), X4=(3, 2), X5=(4, 3)}
2. Списки смежности D=(V, Г) V={1, 2, 3, 4} Г1={2, 3} Г2={4} Г3={2} Г4={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(D1)=
P=2
A(D2)=
P=3
A(D3)=
P=4
A(D4)=
V2 V3
V1 V4
V6 V5 15. Определить минимальный путь из v1 в v7 в нагруженном орграфе с заданной матрицей длин дуг:
Решение.
l(μ)=8 μ =V1, V2, V7 16. Определить минимальное остовное дерево нагруженного графа:
4+5+5+8+6+14=42
|