I тур

Знакомство с теорией графов

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

За последние десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов математики. Это связано с тем, что теория графов, родившаяся при решении головоломок и занимательных задач, стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся   к широкому кругу проблем. В виде графа можно интерпретировать схемы дорог, электронные схемы, географические карты, молекулы химических соединений, связи между людьми и многое другое. С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. Помогают графы в решении математических и экономических задач.

Это привело к широкому использованию теории графов в физике, кибернетике, химии, биологии, экономике, статистике. Особенно важна роль  теории графов в современном программировании.

В рамках I тура дистанционной целевой открытой образовательной программы «Логика и информатика» вам предстоит познакомиться с разными вариантами использования графов.

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

Примеры использования графов

Пример 1. Схема метрополитена.

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

Пример 2.  Использование в медицине.

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

Пример 3. В виде графа можно представить устройство какой-либо системы.

Пример 4. Граф-дерево.

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

Строится он следующим образом. Сначала рисуем «главную» вершину, которая не зависит ни от одной другой вершины. Эта вершина является корнем дерева и является  единственной вершиной «1-го уровня». Далее добавляем вершины «2-го уровня». Их может быть сколько угодно, и все они обязательно связаны с корнем – вершиной 1-го уровня, но не связаны между собой. На следующем шаге добавим вершины 3-го уровня. Каждая из них будет  связана ровно с одной вершиной 2-го уровня и не связан ни с одной другой вершиной. На каждом шаге добавляем вершины очередного уровня, каждая из которых будет связана ровно  с одной  вершиной предыдущего уровня и не будет иметь никаких других связей.  

Пример 5. Иерархическая структура.

В виде дерева можно отразить иерархическую структуру чего-либо, например, учебника географии:

Пример 6. Анализ запутанных  ситуаций.

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

Боксеры с твердою походкой

Не моют пол зубною щеткой.

Кто моет пол зубною щеткой,

Тот наделен душою кроткой

Суровый нрав у тех бывает

Кто книжек вовсе не читает.

Фосс враг и книжек и газет,

Ответь, боксер он или нет?

Для описания ситуации используется ряд утверждений. Представим эти утверждения в виде графа, например, такого:

Глядя на этот граф, ответить на поставленный вопрос совсем просто: мистер Фосс не читает книг, следовательно, он имеет суровый нрав, следовательно, он не моет пол зубной щеткой, следовательно, он боксер.

Пример 7. Вычисление математических выражений.

Смысл математического выражения заключается в определяемой им последовательности вычислительных операций.  Чтобы его понять, нужно знать  правила старшинства операций, правила раскрытия скобок.  Наглядным средством изображения последовательности вычисления математических выражений являются графы. Такой граф представляет собой  дерево, листьями которого являются числа, а прочими вершинами – операции. Дуги связывают вершину-операцию с вершинами операндами. Например, для формулы 5 × (3 + 7) × (8 - 2) дерево будет иметь такой вид:

Пример 8. Компьютерная лингвистика.

В искусственном интеллекте существует раздел, который называется компьютерная лингвистика. Задача этой науки – научить компьютер общаться с человеком на естественном языке. Смысл любой фразы зависит не только от слов, ее составляющих, но и от связей между словами. Классический пример: «казнить, нельзя помиловать!» или «Казнить нельзя, помиловать!». Для того, чтобы выяснить смысл фразы, надо разобраться в ее структуре. А для этого удобно использовать графы. Например, структуру фразы «С утра на улице шел теплый грибной дождь» можно представить графом: