Графы
учебно-методический материал по информатике и икт (10 класс)

Государственное бюджетное

общеобразовательное учреждение

средняя общеобразовательная школа №13

с углубленным изучением

английского языка

Невского района Санкт-Петербурга

учитель информатики

Лесбуридис Елена Василис

Граф – набор вершин и соединяющих их ребер, описывается в виде таблицы (матрицы смежности или весовой матрицы).

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

Граф – непустое конечное множество вершин и конечное множество пар различных вершин. Ребром формально называют пару вершин графа. Неформально ребро изображают графически линией, соединяющей пару вершин.. Эту линию также называют ребром. Говорят, что ребро соединяет две вершины графа или что две вершины графа соединены ребром.

        Граф называется неориентированным, если для любого ребра не указывается, какая вершина ребра начальная, а какая конечная.

Примеры графов:

Схемы железных дорог стран, схемы автомобильных дорог с двусторонним движением. В физике вершины графа могут соответствовать атомам, а ребра – связям между атомами. Граф знакомств между людьми – вершины этого графа соответствуют людям, а ребра соединяют людей, которые знакомы друг с другом.

Вершинам графа часто дают имена. Это могут быть заглавные буквы или слова.

Вершины, соединенные ребром, называются соседними. Количество ребер, выходящих из вершины, называется степенью вершины.

Графы могут быть связные, в которых из любой вершины по ребрам можно пройти в любую другую, и несвязные.

Граф называется полным, если в нем каждая вершина соединена с каждой.

Взвешанные графы. Часто в практических применениях приписывают ребрам графа веса для того, чтобы моделировать такие величины, как расстояние, время переезда или стоимость переезда или доставки между двумя пунктами (точками). Взвешанный граф(сеть) –это граф, ребрам или дугам которого поставлены в соответствие числовые величины. Вес сети равен сумме весов его ребер.

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

Весовая матрица

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

Подграфом графа G называется граф, у которого все вершины и ребра принадлежат графу G. Остовной связный подграф = это подграф графа G, который содержит все его вершины и каждая его вершина достижима из любой другой.

Дерево – это граф, в котором нет циклов, т.е. граф, в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину.

Если в город R можно приехать только из городов X, Y, Z, то число различных путей из города А в город R равна сумме числа различных путей из А в Х, из А в Y, из А в Z.

NR = NX + NY + NZ,

где NR  обозначает число путей из вершины А в некоторую  вершину R.

Задание 1.

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

Сколько существует различных путей из А в М, проходящих через В?

• нас интересуют пути, проходящие через город В, поэтому на первом этапе отсекаем все ребра, которые позволяют на пути от А к М обойти город В; это рёбра БЕ, ГЗ и ДЗ;
• получается, что вершину Е тоже можно убрать, потому что в неё не ведёт ни одна стрелка;
• начальную вершину помечаем единицей (1 путь из А в А, никуда не ехать):
• в вершины Б и Д можно ехать только из А, поэтому помечаем их тоже единицами; в вершину Г можно приехать из А (метка 1) и из Д, поэтому метка вершины Г – 2:

• в вершину В можно приехать из Б (метка 1), А (метка 1) и Г (метка 2), так что метка вершины В равна 1 + 1 + 2 = 4
• в вершину З можно ехать только из В, поэтому её метка тоже равна 4; для вершины Ж складываем метки В и З

(4 + 4 = 8), а для И – складываем метки Ж и З (8 + 4 = 12)

для вершин К и М получаем по 12 путей, а для М - 24

Ответ: 24.

Литература:

1.А. Г. Кушниренко и др. Информатика 9 класс, Москва, Дрофа, 2020

2.Н. Д. Угринович, Информатика и ИКТ 11 класс, Москва, БИНОМ, 2009

3.К. Поляков, kpolyakov.spb.ru