Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Найти количество целых положительных чисел, не превосходящих 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 задан матрицей смежности. Найти количество компонент сильной связности орграфа и определить матрицы смежности этих компонент. Постройте изображения орграфа и его компонент сильной связности.

    V1 V2 V3 V4 V5 V6
  V1            
  V2            
A(D)= V3            
  V4            
  V5            
  V6            

 

Решение.

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

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

P=1

 

 

  V1 V4 V6
V1      
V4      
V6      

A(D1)=

 

 

P=2

 

  V2
V2  

A(D2)=

 

P=3

 

  V3
V3  

 

A(D3)=

 

P=4

 

 

  V5
V5  

A(D4)=

 

V2 V3

 


V1 V4

 


V6 V5

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

 

    V1 V2 V3 V4 V5 V6 V7
  V1 ¥   ¥   ¥    
  V2 ¥ ¥     ¥    
C(D)= V3     ¥     ¥  
  V4 ¥     ¥   ¥  
  V5 ¥ ¥     ¥    
  V6     ¥     ¥ ¥
  V7   ¥   ¥     ¥

 

Решение.

 

V1 * V2* V3 V4* V5 V6* V7
0
  V1   V1   V1 V1
    V2 V1   V1 V2
    V2 V1 V6    
    V2   V6   V2

 

l(μ)=8 μ =V1, V2, V7

16. Определить минимальное остовное дерево нагруженного графа:

    V1 V2 V3 V4 V5 V6 V7
  V1 ¥            
  V2   ¥          
C(D)= V3     ¥        
  V4       ¥      
  V5         ¥    
  V6           ¥  
  V7             ¥

 

V1 * V2* V3* V4* V5* V6* V7*
  V1 V1 V1 V1 V1 V1
  V3   V1 V3 V1 V3
  V7   V7 V7 V7  
  V5   V7   V7  
      V2   V7  
          V4, V7  

 

4+5+5+8+6+14=42

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.