11(b)-Lesson №10

Графы — это удобный способ представления различных объектов и их связей. Например, графом можно изобразить схему дорог между городами, сеть интернет-сайтов, структуру молекулы или социальные отношения между людьми. В математике и информатике граф  — это абстрактное понятие, которое состоит из двух множеств: множества вершин (или узлов) и множества ребер (или дуг), которые соединяют пары вершин.

Графы бывают разных видов в зависимости от того, какие свойства и ограничения на них наложены. Вот некоторые из них:

• Простой граф  — это граф, в котором нет петель (ребер, соединяющих вершину саму с собой) и кратных ребер (ребер, соединяющих одну и ту же пару вершин). Примером простого графа может быть схема дорог между городами, где вершины — это города, а ребра — это дороги.

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

• Мультиграф  — это граф, в котором могут быть кратные ребра, но не петли. Примером мультиграфа может быть схема перелетов авиакомпании, где вершины — это аэропорты, а ребра — это рейсы.

• Ориентированный граф (или орграф)  — это граф, в котором ребра имеют направление. Такие ребра называются дугами. Примером ориентированного графа может быть схема интернет-сайтов, где вершины — это страницы сайтов, а дуги — это ссылки.

• Смешанный граф  — это граф, в котором есть как ориентированные, так и неориентированные ребра. Примером смешанного графа может быть схема железнодорожной сети, где вершины — это станции, а ребра — это пути: однонаправленные или двунаправленные.

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

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

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

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

• граф – это набор вершин и соединяющих их ребер; он описывается в виде таблицы (матрицы смежности или весовой матрицы)
• чаще всего используется взвешенный граф, где с каждым ребром связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки
• рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 4 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во-вторых, вес этого ребра равен 4; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет

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

Задача №1.

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Г в пункт Ж. В ответе запишите целое число – так, как оно указано в таблице.

Решение:

1) определим для каждой вершины её степень, то есть, количество рёбер, в которыми она связана; в таблице степень вершины – это количество заполненных клеток в строке (или в столбце)

2) сопоставление степеней вершин в таблице и на рисунке позволяет сразу обнаружить в таблице вершины А (она имеет № 3), Ж (№ 4) и Б (№ 6)

3) нас интересуют вершины Г и Ж; вершину Ж мы нашли, вершина Г имеет степень 2 и связана, кроме вершины Ж, с вершиной Д степени 3;

4) степень 2 имеют вершины № 1 и 2, но только вершина № 1 связана, кроме Ж, с вершиной степени 3 (№ 7), поэтому вершина № 1 – это Г

5) по таблице определяем протяжённость дороги из пункта Г в пункт Ж, она равна 9.

Ответ: 9

Задача №2.

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15. Определите, какова длина кратчайшего пути из пункта Д в пункт В. В ответе запишите целое число – так, как оно указано в таблице.

Решение:

1) сложность этой задачи в том, что схема симметрична; легко понять, что без дополнительных данных (используя только степени вершин – количество связанных с ними ребёр) мы не сможем различить вершины А и В, Г и Е, Д и Ж

2) определим степени вершин:

3) как и видно из рисунка, у нас две вершины степени 2 (А и В), две вершины степени 3 (Д и Ж) и три вершины степени 4 (Б, Г и Е), причем вершина Б однозначно определяется как вершина степени 4, которая связана с двумя вершинами степени 2

4) для того, чтобы различить оставшиеся вершины, определим длины путей ЖГА, ЖЕВ, ДГА и ДЕВ; мы не знаем, где какой маршрут, но точно знаем, что эти четыре маршрута

П3 → П1 → П7 = 7 + 12 = 19

П3 → П6 → П5 = 10 + 6 = 16

П4 → П1 → П7 = 5 + 12 = 17

П4 → П6 → П5 = 9 + 6 = 15

5) из дополнительного условия (Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15.) находим, что маршрут ЖГА – последний, так что П4 = Ж, П6 = Г и П5 = А; в итоге получается

5) кратчайший путь из Д в В можно найти с помощью дерева возможных маршрутов – это будет путь ДЕВ длиной 19

Ответ: 19.

Выполнить домашнюю работу