Инфознайка
Главная

Информация вокруг нас

Виды информации
Измерения информации
Алфавитный подход
Содержательный подход
Файловая система
Кодирование графики
Кодирование звука
Скорость передачи
Электронная таблица Excel
Графы
Система счисления
Кодирование информации
Логика
Адресация в Интернете
Поиск в Интернете
Алгоритмы
Кумир
Массивы

Тема: Графы

Коротко о главном

Граф - это средство для наглядного представления состава и структуры системы.

Граф состоит из вершин, связанных линиями.

Направленная линия (со стрелкой) называется дугой.

Линия ненаправленная (без стрелки) называется ребром.

Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей.

 

                                                                                                      

Неориентированный граф - граф, вершины которого соединены ребрами. С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений

 

 Ориентированный граф -граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы односторонних отношений.

 

Взвешенный граф - граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).

                                                                                                               

 Что еще нужно знать:

·      если в город Q можно приехать только из городов X, Y, и Z, то число различных путей из города A в город Q равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть

NQ = Nx  +  Ny  +  Nz

где NQ обозначает число путей из вершины A в некоторую вершину Q

·      число путей конечно, если в графе нет циклов – замкнутых путей

 Пример задания:

На схеме нарисованы дороги между четырьмя населенными пунктами A, B, C, D и указаны протяженности данных дорог. Определите, какие два пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими пунктами.

1)10;

2) 15;

3) 16;

4) 17.

Решение:

Заносим данные из схемы в таблицу:  

 

А

В

С

D

А

 

9

7

8

В

 

 

17

7

С

 

 

 

10

D

 

 

 

 

 

 

 

Ответ: 3.

 Еще пример задания:

Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:

           Аэропорт вылета     Аэропорт прилета             Время вылета        Время прилета

                     СОСНОВО                          КРАСНЫЙ                                  06:20                              08:35

                     КРАСНЫЙ                           ОКТЯБРЬ                                   10:25                              12:35

                      ОКТЯБРЬ                           КРАСНЫЙ                                  11:45                              13:30

                         БЕРЕГ                               СОСНОВО                                  12:15                              14:25

                     СОСНОВО                           ОКТЯБРЬ                                   12:45                              16:35

                     КРАСНЫЙ                          СОСНОВО                                  13:15                              15:40

                      ОКТЯБРЬ                           СОСНОВО                                  13:40                              17:25

                      ОКТЯБРЬ                                БЕРЕГ                                       15:30                              17:15

                     СОСНОВО                               БЕРЕГ                                       17:35                              19:30

                         БЕРЕГ                                ОКТЯБРЬ                                   19:40                              21:55

Путешественник оказался в аэропорту ОКТЯБРЬ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт СОСНОВО.

1) 15:40                   2) 16:35                            3)17:15                       4) 17:25

 Решение:

 

1)      для решения можно построить граф, показывающий, куда может попасть путешественник из аэропорта ОКТЯБРЬ

2)      из аэропорта ОКТЯБРЬ есть три рейса:

                      ОКТЯБРЬ                           СОСНОВО                                  13:40                              17:25

                      ОКТЯБРЬ                           КРАСНЫЙ                                  11:45                              13:30

                      ОКТЯБРЬ                                БЕРЕГ                                       15:30                              17:15

3) построим граф, около каждого пункта запишем время прибытия

 

4)проверим, не будет ли быстрее лететь с пересадкой: рейс «КРАСНЫЙ-СОСНОВО» вылетает в 13:15, то есть, путешественник на него не успевает; он не успеет также и на рейс  «БЕРЕГ-СОСНОВО», вылетающий в 12:15

5)      таким образом, правильный ответ – 4 (прямой рейс).

 

 

 

 

 

 

 

 

 

Еще пример задания:

 

 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

   

 

 

 

 

 

 

Решение:

1)      начнем считать количество путей с конца маршрута – с города К

2)      записываем для каждой вершины, из каких вершин можно в нее попасть

 

 

И ¬ Д

Ж ¬ ВЕ

Е ¬ Г

Д ¬ БВ

Г ¬ А

В ¬ АБГ

Б ¬ А

 

 

 

 

3)     

 

 

 

 

 

 

 

 

 

теперь для удобства «обратного хода» вершины можно отсортировать так, чтобы сначала шли все вершины, в которые можно доехать только из начальной точки А:

Б ¬ А

Г ¬ А

затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки):

В ¬ АБГ

Е ¬ Г

далее добавляем все вершины, куда можно доехать из А, Б, Г, В и Е:

Д ¬ БВ

Ж ¬ ВЕ

на следующем шаге добавляем вершину И

И ¬ Д

и, наконец, конечную. вершину

К ¬ ИДЖЕ

именно в таком порядке мы и будем вычислять количество путей для каждой вершины

 

 

 4)    

 

 

 

 

 

 

 

 

 

 

 

  теперь идем по полученному списку вершин, полагая, что количество вариантов попасть в вершину равно суммарному количеству вариантов попасть в ее непосредственных предшественников.

NБ = 1,                  NГ = 1

NВ = 1+1+1 = 3,                NЕ = 1

NД = 1+3 = 4,     NЖ = 3 + 1 = 4

NИ = 4,                

N = NК = 4 + 4 + 4 + 1 = 13

5)      заметим, что вершины можно и не сортировать специально, а просто выбирать возможный порядке вычисления: проверять, какие значения известны и какие можно рассчитать с их помощью на следующем шаге

6)      Ответ: 13.

Возможные ловушки и проблемы:

·    очень важна аккуратность и последовательность; сначала идем от конечной точки к начальной, выписывая все вершины, из которых можно приехать в данную; затем идем обратно, определяя числовые значения

·    построение полного дерева маршрутов – занятие трудоемкое и достаточно бесперспективное, даже грамотные учителя информатики здесь в большинстве случаев что-то забывают и ошибаются 

 Еще пример задания:

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A

B

C

D

E

F

A

 

2

4

 

 

 

B

2

 

1

 

7

 

C

4

1

 

3

4

 

D

 

 

3

 

3

 

E

 

7

4

3

 

2

F

 

 

 

 

2

 

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

1) 9                        2) 10                         3) 11                            4) 12

Решение:

1) построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):

 2) для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее

3) например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7):

4)      новые маршруты из С – в D и E (длины путей соответственно 3 и 4):

5)      новый маршрут из D – в E (длина пути 3):

6)      новый маршрут из E – в F (длина пути 2):

7)      нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E

8)      попробуем перечислить возможные маршруты из А в Е:

А – В – Е                    длина 9

А – В – С – Е             длина 7

А – В – C D – Е     длина 9

А –C – Е                     длина 8

А –C B – Е              длина 12

А –C D – Е              длина 10

9)      из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9

10)      таким образом, правильный ответ – 1.

Проверочные задания

  1. На схеме нарисованы дороги между четырьмя населенными пунктами A, B, C, D и указаны протяженности данных дорог. Определите, какие два пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими пунктами.

    9
    13
    15
    17


  2. В таблице приведена стоимость перевозок между пятью железнодорожными станциями, обозначенными буквами A, B, C, D и E. Укажите схему, соответствующую таблице.

     

    1
    2
    3
    4

     

     


  3. В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта C до пункта B не больше 6». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом через любой насеченный пункт маршрут должен проходить не более одного раза.

    1
    2
    3
    4.

     


  4. Путешественник пришел в 08:00 на автостанцию поселка ЛИСЬЕ и увидел следующее расписание автобусов: Определите самое раннее время, когда путешественник сможет оказаться в пункте ЗАЙЦЕВО согласно этому расписанию.

    9:05
    12:15
    12:25
    13:25

     

     

     

     

  5.  На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?

    8
    9
     10
    11