Что такое графы в программировании

Практическое применение графов — Алгоритмы на графах

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

Выбираем оптимальный путь на метро

Представьте себе схему метро крупного города: скорее всего, в центре будут пересекаться несколько разных веток. Из-за этого получается, что проехать между станциями можно разными способами.

Например, в московском метро от станции «Фрунзенская» до станции «Полянка» можно доехать двумя способами:

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

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

Теперь можно вычислить полное время на каждом маршруте и выбрать самый короткий. Решение выглядит обманчиво простым. Люди интуитивно отбрасывают заведомо плохие варианты и сразу видят два подходящих маршрута. У компьютера интуиции нет — он переберет все маршруты, которых в действительности гораздо больше двух.

Задачи такого рода в программировании относят к классу «задачи о кратчайшем пути». Число, приписанное каждому ребру, называют весом ребра, а сам граф называют взвешенным.

Неочевидно, почему используют слово «вес», а не «длительность пути». Этому есть объяснение. За названием «взвешенные графы» скрываются разные задачи, решаемые одним и тем же способом. Для некоторых задач числа обозначают время, для других — расстояния, для третьих — денежные суммы, для четвертых — вес.

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

Строим маршрут по автомобильным дорогам

Рассмотрим еще одну задачу — построение автомобильного маршрута. Для начала нужно определиться с ребрами и вершинами:

• Ребрами будут считаться сами дороги
• Вершинами — развилки и пересечения дорог

Здесь мы сталкиваемся с одной сложностью, которой не было в задаче с метро. В отличие от метро, автомобильные дороги могут быть с односторонним движением. Рисуя граф, мы должны учитывать эту особенность.

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

На этот граф мы добавили стрелки, которые показывают направление движения:

• Если дорога односторонняя, мы рисуем ребро со стрелкой
• Если дорога двухсторонняя, мы рисуем два ребра с противоположными стрелками

Если у ребер графа задано направление, такой граф называют направленным или ориентированным. Часто название «ориентированный граф» сокращают до «орграфа».

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

Выбираемся из лабиринта

Иногда нам не нужно выискивать идеальный маршрут — достаточно выяснить, можно ли его построить. Для примера представьте, что нам надо выбраться из лабиринта:

В таком случае мы согласимся на любой путь и не будем уточнять, если ли пути покороче.

Есть несколько стратегий выхода из лабиринта. Например, есть правило правой руки, которое предлагает такую стратегию:

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

Конечно, коридоры можно обходить и слева направо, тогда речь будет идти о правиле левой руки — оно работает абсолютно так же. Здесь важно придерживаться всегда одной стороны, не смешивая повороты направо и налево.

Как и в случае с автомобильной картой, вершинами графа будут только места развилок и тупики. Посмотрим, как будет выглядеть маршрут по лабиринту:

Рассмотрим этот рисунок подробнее:

• Красными линиями обозначены ребра графа
• Кружками обозначены вершины
• Направление обхода графа показано синим цветом

Стратегия предполагает, что мы пытаемся пройти как можно глубже, а если попадаем в тупик, возвращаемся назад. На рисунке это тоже видно — синяя линия часто идет в двух направлениях.

Такой способ движения по графу называется обходом в глубину. Этот алгоритм применяется для поиска вершины с определенными свойствами, поэтому часто употребляют похожий термин — «поиск в глубину». В профессиональной литературе вы можете встретить аббревиатуру DFS — depth first search, то есть «поиск сначала в глубину».

Этот алгоритм прекрасно работает, если в лабиринте нет замкнутых коридоров или петель. Если мы попадем на петлю, мы можем вечно ходить по одному и тому же коридору, как показано на рисунке:

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

Обходя лабиринт с петлями, можно помечать посещенные развилки мелом. Встретив пометку, мы узнаем, что попали в цикл. Действовать в этом случае надо так же, как и в тупике — развернуться и идти назад.

Обходим препятствия

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

Игровая карта может выглядеть так:

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

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

Представим, что нам надо добраться из вершины Н в вершину К:

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

Сначала мы проверяем соседей начальной вершины, затем — соседей соседей, и так далее, каждый раз удаляясь от начальной вершины на один шаг. В какой-то момент очередной круг доберется до конечной вершины. Это будет означать, что путь найден:

Другое название этого алгоритма — поиск в ширину или BFS, breadth first search. Он позволяет найти маршрут с наименьшим количеством ребер. Впрочем, у него гораздо больше применений. В частности, одна из его модификаций позволяет закрашивать на изображениях замкнутые области произвольной формы.

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

Считаем сдачу

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

Номиналы монет подбираются так, чтобы ими можно было выдать любую сумму. Например, сдачу в 8 рублей можно выдать тремя монетами: 5 рублей, 2 рубля и 1 рубль.

Чтобы посчитать сдачу, можно использовать простой алгоритм выбора монет:

• Пока можем, набираем сумму самыми крупными монетами
• Затем переходим к следующим по номиналу монетам, и так далее

Проблема в том, что иногда в автомате заканчиваются монеты определенного номинала. Отсутствие двухрублевых монет не скажется на работе алгоритма: он выберет одну пятирублевую монету и три однорублевых.

Но если в автомате закончатся рублевые монеты, алгоритм не сможет вернуть сдачу в 8 рублей. Сначала он выберет монету в 5 рублей, потом монету в 2 рубля, а дальше начинаются сложности — надо выбрать монету в 1 рубль, а они закончились.

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

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

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

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

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

Хорошим кандидатом для решения задачи о монетах будет алгоритм поиска в ширину. Мы продвигаемся во всех направлениях от пустого узла, в поисках узлов, содержащих сумму 8 рублей.

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

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

При работе с графами программисты часто используют подобную информацию для того, чтобы ускорить алгоритм. Такие модификации называются информированными алгоритмами. Классические алгоритмы без дополнительной информации называют неинформированными.

Выводы

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

• Находить кратчайшие маршруты на карте метро — решать задачи о кратчайшем пути с помощью взвешенных графов
• Строить пути на автомобильных картах с помощью ориентированных графов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

• 130 курсов, 2000+ часов теории
• 1000 практических заданий в браузере
• 360 000 студентов

Наши выпускники работают в компаниях:

Графы: основы теории, алгоритмы поиска

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

Одной из важнейших составляющих спортивного программирования является изучение алгоритмов. В этой статье мы охватим большое количество алгоритмов, в том числе все алгоритмы на графах, знание которых понадобится вам для успешного решения задач из теории графов на соревнованиях по программированию. Конечно, одних теоретических знаний алгоритмов недостаточно, и вам придётся набить руку в решении практических задач на таких сайтах, как Codeforces. Настоящая же статья представит вам инструменты, необходимые для освоения важных графовых алгоритмов. Итак, приступим.

Что такое граф?

Графы, в понимании программистов, — это не те графики, которые мы изучали в школе. Это не столбиковые диаграммы или гистограммы.

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

В условиях задач из теории графов на соревнованиях по программированию обычно говорится о таких вещах, как сети и решётки.

Вот список всех терминов, относящихся к теории графов, которые вам нужно знать:

• путь — последовательность рёбер, соединяющая разные (неповторяющиеся) вершины;
• маршруты — это те же пути, только они не требуют последовательности разных вершин;
• цикл — группа вершин, связанных вместе в замкнутую цепь. На рисунке выше вершины [1,2,4] составляют цикл;
• связный граф — граф, в котором между любой парой вершин имеется один путь;
• дерево — связный граф, не содержащий цикла;
• неориентированный граф — граф, в котором рёбра не имеют направления. На рисунке выше показан как раз неориентированный граф. В таком неориентированном графе можно перемещаться вдоль ребра в любом из двух направлений;
• ориентированный граф — граф, в котором рёбра имеют направления и обозначаются стрелками. В таком ориентированном графе можно перемещаться вдоль ребра только в указанном направлении.

Представление графов в коде

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

Будут показаны два способа представления графов: матрицы смежности и списки смежности. Больше вам пригодится представление графов в виде списка смежности.

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

Матрица смежности представляет собой граф в виде двумерной матрицы с размерами V x V, где V — количество вершин графа. Матрицы смежности лучше всего применять, когда V² примерно равно E (числу рёбер), то есть когда граф плотный. Запись a_ij обозначает, сколько рёбер соединяют вершину i и вершину j.

Код:

Следующий код используется для создания матрицы смежности неориентированного графа. Чтобы код создавал матрицу смежности для ориентированного графа, измените функцию add_edge , удалив вторую строку внутри неё: matrix[v][u] = 1;

#include
using namespace std;
int matrix[20][20]; //матрица смежности изначально 0
int count = 0;
//следующая функция используется для вывода
void displayMatrix(int v) int i, j; 
for(i = 0; i < v; i++) for(j = 0; j < v; j++) cout > 
cout >
>
void add_edge(int u, int v) < //функция добавления ребра в матрицу
matrix[u][v] = 1; 
matrix[v][u] = 1;
>
main(int argc, char* argv[]) int v = 6; //в графе 6 вершин 
add_edge(0, 4); 
add_edge(0, 3); 
add_edge(1, 2); 
add_edge(1, 4); 
add_edge(1, 5); 
add_edge(2, 3); 
add_edge(2, 5); 
add_edge(5, 3); 
add_edge(5, 4); 
displayMatrix(v);
>

Списки смежности

Другой распространенный способ представления графов в коде — списки смежности. Суть в том, что вы создаёте списки соседей для каждой вершины, а затем помещаете все эти списки в другой список. Их лучше всего применять, когда в графе небольшое количество рёбер, то есть когда граф разрежённый. Если у вас взвешенный граф, т.е. каждое ребро графа имеет какой-то вес, то в списке будут содержаться пары для рёбер (сосед, вес).

Код:

#includeusing namespace std;void addEdge(vector adj[], int u, int v) adj[u].push_back(v); 
adj[v].push_back(u);//удаляем эту строку для ориентированных графов
>int main() int v = 5; //5 вершин 
vector adj[v]; 
addEdge(adj, 0, 1); 
addEdge(adj, 0, 4); 
addEdge(adj, 1, 2); 
addEdge(adj, 1, 3); 
addEdge(adj, 1, 4); 
addEdge(adj, 2, 3); 
addEdge(adj, 3, 4); 
>

Поиск в глубину

Теперь, когда мы научились представлять графы в коде, можем приступить к изучению некоторых алгоритмов на графах! Начнём с поиска в глубину (DFS) и завершим поиском в ширину (BFS). Чтобы не загромождать статью, алгоритмы поиска пути не будут здесь рассматриваться (интересующиеся могут ознакомиться с алгоритмом поиска кратчайшего пути Беллмана-Форда).

Поиск в глубину — это один из базовых алгоритмов на графах. Он применяется для поиска расстояния от одной вершины до других вершин в графе. Это алгоритм обхода.

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

1. Помещаем любую из вершин графа на стек.
2. Берём элемент со стека и добавляем его в список посещённых.
3. Создаём список соседей этой вершины. Добавляем в стек те, что не находятся в списке посещённых.
4. Повторяем 2 и 3 пункты, пока стек не опустеет.

Код:

#include using namespace std;const int N = 100000;
vector adj[N];
bool visited[N];void dfs(int s) if (visited[s]) return; 
visited[s] = true; 
for (auto u: adj[s]) dfs(u); 
>
>

Поиск в ширину

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

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

1. Помещаем любую вершину в графе в конец очереди.
2. Берём элемент в начале очереди и добавляем его в список посещённых.
3. Создаём список соседей этой вершины. Добавляем в конец очереди непосещённые.
4. Повторяем 2 и 3 пункты, пока очередь не опустеет.

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

Код:

// Быстрая реализация алгоритма поиска в ширину с использованием
// векторов и очереди
#include 
#define pb push_backusing namespace std;vector v;
vector > g;void edge(int a, int b) g[a].pb(b); 
// для неориентированного графа добавляем эту строку 
// g[b].pb(a);
>void bfs(int u) queue q; 
q.push(u); 
v[u] = true; 
while (!q.empty()) int f = q.front(); 
q.pop(); 
// Ставим в очередь все соседние F и помечаем их как посещённые 
for (auto i = g[f].begin(); i != g[f].end(); i++) if (!v[*i]) q.push(*i); 
v[*i] = true; 
> 
> 
>
>

Заключение

Освоив теоретическую часть, касающуюся двух самых важных алгоритмов обхода на графах, вам остаётся только практиковаться, чтобы использовать эти алгоритмы в соревнованиях по программированию. Я бы порекомендовал для начала Codeforces: решайте задачи, помеченные тегами bfs и dfs с рейтингом до 1400. Когда почувствуете, что справляетесь с ними, увеличьте сложность.

Отработка навыков решения алгоритмических задач, особенно алгоритмов на графах, поможет вам побеждать на соревнованиях по программированию и успешно проходить технические собеседования. Вперёд — к успехам!

• Как создавать анимированные графы в Python
• Графы и пути: Алгоритм Брона-Кербоша, максимальные группы
• Гравафы и пути — алгоритм Дейкстры

Графы и программирование

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

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

Характеристика связности графов часто описывается достижимостью из некоторой вершины графа всех других, а очевидное средство такой достижимости – проложенный между парой вершин путь. Наличие множества путей, покрывающих вершины и\или ребра (дуги) графа, обеспечивает часто решение целевых задач таких, например, как минимизация контрольных точек или тестирование программ. Затрагиваются вопросы и цикломатической сложности графа.

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

Задачи обеспечения информационной безопасности (ИБ) ресурсов напрямую связаны с IT- технологиями и моделированием явлений с целью прогноза развития ситуации и процессов информационного взаимодействия приобретают главенствующее значение. Из всех возможных подходов к подобному моделированию самый эффективный, но не самый затратный считается метод математического моделирования. Применение алгебры, дискретной математики, теории графов и результатов их теории не обошло вниманием область IT- технологий и непосредственно программирования. Здесь рассмотрим задачи представления программ средствами теории графов (графами) и представления самих графов средствами алгебры (матрицами, списками и др.)

Представление графа в памяти компьютера

Представление матрицами

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

Матрицей смежностей А(G) графа G c n вершинами (без петель) называется квадратная матрица размера (порядка) n×n с элементами а_ij: а_ij = 1, если в графе существует дуга (ребро) (x_i, x_j); a_ij = 0 в противном случае. Эта матрица симметрична относительно главной диагонали для неориентированного графа.

В случае орграфа входу в вершины графа соответствует столбец из нулей, выходу из вершин графа – строка из нулей, число единиц в i –й строке равно полустепени исхода вершины x_i, число единиц в j-м столбце равно полустепени захода вершины x_j.

Матрицей инцидентности В(G) графа G c n вершинами, которые соответствуют строкам матрицы и m дугами, соответствующими столбцам, называется прямоугольная матрица размера n×m с элементами b_ij: b_ij =1, если в графе существует вершина x_i, начало дуги u_j; b_ij = –1, если вершина x_i есть конец дуги u_j; b_ij = 0 противном случае.

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

Теорема 1. Ранг матрицы инциденций связного графа G (V, U) равен rank = |V| – 1.

Следствие. Ранг матрицы инциденций произвольного графа G (V, U) равен разности числа вершин и числа компонент связности.

Теорема 2. В матрице инциденций значение любого минора равно 0, 1 или – 1.

Матрицей достижимости R(G) графа G c n вершинами называется квадратная матрица размера (порядка) n×n с элементами r_ij: r_ij = 1, если в графе вершина x_j достижима из вершины x_i; r_ij = 0 в противном случае.

Представление графа списками смежности

Список смежности для вершины х – это множество смежных с ней вершин или концов дуг, исходящих из вершины х. На рис. 2 представлены два графа G₁ и G₂: ориентированный и неориентированный с шестью вершинами каждый и их матрицами смежности. Граф представляется числом |Х| списков смежности, по одному для каждой вершины (рис. 3).

Ниже приводится пример задания графов G₁ и G₂ с помощью списков смежности. Такое представление графа удобно при решении ряда задач, например, при перечислении контуров в графе (алгоритм Джонсона). Предварительно в графе отыскиваются бикомпоненты

Эффективность алгоритма

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

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

Время, затрачиваемое алгоритмом на получение результата, в зависимости от размерности задачи, называют временной сложностью или трудоемкостью алгоритма. Асимптотической временной сложностью (трудоемкостью) алгоритма называют предельное значение сложности при неограниченном увеличении размерности.

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

При обработке алгоритмом входов размерностью n за время сn 2 , где с – некоторая постоянная, определяемая реализацией алгоритма, то говорят, что временная сложность этого алгоритма есть О(n 2 ).

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

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

Определение. Цикломатическим числом l(G) графа G c n вершинами и m дугами называется величина

l(G) = m(G) – n(G) + k(G), где k– число компонент связности. Характеристика l(G) определена только для неориентированного графа. Для связного графа k = 1, l(G) = m – n + 1.

Теорема 3. В сильно связном графе цикломатическое число равно числу линейно независимых контуров.

Пример. Изображение управляющего графа G приведено на рис. 4. В графе G выявлено 5 независимых контуров (цикломатическое число графа l(G) = m – n +1): [s, v₁, v₄, t, s], [v₁, v₄, v₁], [s, v₁, v₄, s], [s, v₂, t, s], [s, v₃, v₂, t, s]. При этом путь [s, v₁, v₄, s, v₁, v₄, v₁, v₄, v₁, v₄, t] может быть представлен линейной комбинацией [s, v₁, v₄, t, s] + 2[v₁, v₄, v₁] + [s, v₁, v₄, t, s]. Вычисление числа всех линейно независимых путей может служить оценкой сложности программы через цикломатическое число.

Определение. Цикломатической сложностью программы называется величина v(G) = l(G) + 2, где l(G) – цикломатическое число соответствующего управляющего графа. Величина v(G) зависит только от логической структуры управляющего графа.

Цикломатической матрицей H = ||h_ij|| орграфа G называется прямоугольная (0, 1)–матрица размера c×n, где с – число контуров, а n – число вершин, а

Матрицей бикомпонент М(G) = R×R Т графа G c n вершинами называется квадратная матрица размера (порядка) n×n с элементами r_ij: r_ij = 1, если в графе вершина x_j достижима из вершины x_i; r_ij = 0 в противном случае.

Графы как модели программ, данных и процессов

Формулируя задачи, предназначенные для решения на ПК, мы используем различные средства, математические, языковые, логические и др. Например, при анализе программ, при оптимизации, трансляции, проверке правильности, тестировании и т.п. традиционно используются различные графы. При этом, как правило, сами задачи значительно упрощаются при их рассмотрении на теоретико-графовых моделях. В основе многих задач и их моделей лежат управляющий и\или информационный графы программы.

Будем представлять программу (код) некоторой задачи текстом в некотором языке программирования. В тексте выделяются входы и выходы не только для кода в целом, но и для каждого отдельного оператора. Такие входы объединяются в множество В + и выходы – в множество В – , причем В + UВ – =B, а В + ∩ В – = ∅.

Определение. Орграф G = (X, U) называется управляющим графом (р-графом, графом переходов), если выполнены следующие условия:

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

Поясним определение примером. Пусть задан небольшой текст (программа BUBBLE) в алголоподобном языке

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

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

Каждая вершина графа G (рис. 7а)) соответствует одному оператору, а дугам – передачи управления.

Справа на рис. 7) приведен редуцированный граф G, в котором линейные участки управляющего графа G представлены одной вершиной. В управляющем графе G можно рассматривать пути различного уровня. Уровень отражает глубину вложенности оператора. Путь уровня 0 есть простой s – t путь; путь уровня 1 есть простой путь или контур, который начинается или заканчивается в вершинах путей уровня 0.

Путь уровня i есть простой путь или контур, который начинается или заканчивается в вершинах путей меньшего уровня, и у которого ни одна другая вершина или дуга не входит в путь меньшего уровня. Ниже в таблице приводится полный список путей i-го уровня, i = 0,1, 2, управляющего графа программы

Тестирование

Определение. Тестирование – это проверка правильности программы посредством множества контрольных примеров – тестов.

Определение. Тестом, проверяющим программу, называется тройка t = x, μ(G), y >, где х ⊆ Х – подмножество значений входных данных; μ(G) – это
s – t путь в управляющем графе G, соответствующий входным данным х;
y ⊆Y – подмножество значений выходных данных при прохождении программой пути s – t.

Очевидно, что полное тестирование согласно определению, требует прохода программы по всем путям управляющего графа G. Это очень трудозатратное и времязатратное действие (мероприятие), которое фактически не реализуется. Заменой тотального тестирования является разработка и реализация различных стратегий.

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

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

Определение. Орграф без петель I = (B, U) называется информационным графом, если его вершинами являются входы и выходы операторов программы, а дуга (х, у) принадлежит множеству дуг U тогда и только тогда, когда х ϵ В – и у ϵ В + . Дуги информационного графа называются информационными парами, сохраняя традиционное название «дуга» для дуг управляющего графа.

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

В общем случае предполагается, что каждой вершине сопоставлен вес w >0, который можно интерпретировать как сложность оператора (или отдельного блока) программы, изображаемого данной вершиной. Отыскание тестирующих данных для тестирующего пути тем проще, чем меньше вершин будет в нем содержаться из множества K вершин, не подлежащих проверке. Это соответствует задаче отыскания (s–t) -пути с наибольшим весом при условии, что вершинам из множества K приписан небольшой отрицательный вес.

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

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

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

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

Однако существует приближенное решение, при котором отыскивается множество дуг, принадлежащих как можно большему числу контуров, алгоритм его можно записать следующим образом. Пусть K – множество дуг, разрывающих все контуры. На вход алгоритма поступает множество простых контуров, заданных перечислением дуг, входящих в контуры.

Шаг 1. Построить матрицу H = ||h_ij|| , контуры-дуги которой определяются:
h_ij = 1, если дуга u_j принадлежит контуру С_i, в противном случае, h_ij = 0.

Шаг 2. Включить в множество K те дуги, которым в матрице H соответствуют строки, содержащие только одну единицу (тем самым в множество K включаются все петли графа).

Шаг 3. Удалить из H строки и столбцы, соответствующие этим петлям.

Шаг 4. Пока Н не пусто цикл.

Шаг 5. Исключить из H все мажорируемые столбцы, то есть те, для которых найдется хотя бы один столбец, имеющий единицу в тех же строках, что и рассматриваемые.

Шаг 6. Включить в множество K дугу u_r , соответствующую столбцу с наибольшим числом единиц.

Шаг 7. Вычеркнуть из H строки, соответствующие единицам в r-м столбце, и сам r-й столбец. Проверка условия H = Ø, если оно не выполняется, необходимо вернуться к шагу 4. Если условие выполнено, конец алгоритма, K – искомое множество дуг, принадлежащих как можно большему числу контуров

Заключение

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

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

В статье «Сети и графы» рассматривается задача классификации графов по основным признакам: вершины, ребра (дуги), распределение степеней вершин (РСВ), изоморфизм; построение (синтез) отдельных классов. Приводится пример формирования полного класса. По результатам анализа элементов класса и характеристике связности находится граф с наилучшей структурой в своем классе. Результаты для класса графов иллюстрируются в матричном и рисуночном представлении. Единственный комментатор навел критику.

Литература

1. Авондо-Бодино Дж. Применение в экономике теории графов –М.: Прогресс,1966. –160с.
2. Харари Ф., Палмер 3. Харари Ф. Теория графов. –М.: Мир, 1973. – 300 с. 4. Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука,1985.- 352 с. 5. Стечкин Б. С., Матиясевич Ю. В. Сито Эратосфена // Труды международной школы С. Б. Стечкина по теории функций. — Екатеринбург, 1999. – с. 148.
6. Трост Э. Простые числа. — М.: ГИФМЛ, 1959. — 136 с.
7. Касселс Дж. В. С. Введение в геометрию чисел. – М.: МИР, 1965. – 430 с.
8. Кнут Д. Искусство программирования. Т.2. Получисленные алгоритмы. – М.: Вильямс, 2000. 3-е издание. – 280 с.
9. Коблиц Н. Курс теории чисел и криптографии. — М.: Научное издательство ТВП, 2001.— 254 с.
10. Коваленко Д. В., Сидоров Д. П. Факторизация больших чисел распределенными вычислениями // Материалы научной конференции «XXX Огаревские чтения» (естественные и технические науки), Саранск, 2001. — С. 230-232.
11. Коваленко Д. В., Сидоров Д. П., Федосин С.А. Применение распределенных вычислительных систем для факторизации больших чисел // Тезисы международного семинара «Супервычисления и математическое моделирование», Саров, 2002. – С. 53-56.
12. Манин Ю. Н., Панчишкин А.А. Введение в современную теорию чисел. -М.: МЦНМО, 2013.-552 с.

∨ ∧ ∍ ∌ ∊ ∉ ∄ ∃ ∀ ∪ ∩ ≣ ≢ ≠ ≤ ≥ ⊆ ⊇ ⊃ ⊂ ≡ τ σ φ ω ψ χ υ ρ π ξ μ λ ζ η α β γ δ ε ρ ά ℓ ∅ ∞ ∩ ∛ ∜ ± ≠ ~ × ÷ ≤ ≥ ≈ ∀ ℃ °∈∋∃∅ Ω

• Программирование
• Анализ и проектирование систем
• Алгоритмы
• Математика

Основные понятия теории графов

Перед тем как начать изучение непосредственно алгоритмов, необходимо обладать базовыми знаниями касательно самих графов, понимать, как они представляются в компьютере. Здесь не будут подробно описаны все аспекты теории графов (этого и не требуется), но только те, незнание которых заметно усложнит усвоение данной области программирования. Несколько примеров дадут немного поверхностного представления о графе. Так типичным графом является схема метро или какой-либо другой маршрут. В частности программисту знакома компьютерная сеть, также являющаяся графом. Общее здесь это наличие точек, соединенных линиями. Так в компьютерной сети точки – это отдельные серверы, а линии – различные виды электрических сигналов. В метрополитене первое – станции, второе – туннели, проложенные между ними. В теории графов точки именуется вершинами (узлами), а линии – ребрами (дугами). Таким образом, граф – это совокупность вершин, соединённых ребрами. Математика оперирует не содержанием вещей, а их структурой, абстрагируя ее из всего того, что дано как целое. Пользуясь именно этим приемом, мы можем заключать о каких-либо объектах как о графах. А поскольку теория графов это часть математики, то для нее нет абсолютно никакого значения, что в принципе представляет собой объект; важно лишь то, является ли он графом, т. е. обладает ли обязательными для графов свойствами. Поэтому, прежде чем привести примеры, мы выделяем в рассматриваемом объекте лишь то, что как нам кажется, позволит показать аналогию, отыскиваем общее. Вернемся к компьютерной сети. Она обладает определенной топологией, и может быть условно изображена в виде некоторого числа компьютеров и путей их соединяющих. На рисунке ниже в качестве примера показана полносвязная топология. Это по сути граф. Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними – ребрами. Заменив компьютеры вершинами, мы получим математический объект – граф, который имеет 10 ребер и 5 вершин. Пронумеровать вершины можно произвольным образом, а не обязательно так, как это сделано на рисунке. Стоит отметить, что в данном примере не используется ни одной петли, то есть такого ребра, которое выходит из вершины и сразу же входит в нее, но петли могут встречаться в задачах. Вот некоторые важные обозначения, используемые в теории графов:

• G=(V, E) , здесь G – граф, V – его вершины, а E – ребра;
• |V| – порядок (число вершин);
• |E| – размер графа (число рёбер).

В нашем случае (рис. 1) |V|=5, |E|=10 ;

Когда из любой вершины доступна любая другая вершина, то такой граф называется неориентированным связным графом (рис. 1). Если же граф связный, но это условие не выполняется, тогда такой граф называется ориентированным или орграфом (рис. 2).

В ориентированных и неориентированных графах имеется понятие степени вершины. Степень вершины – это количество ребер, соединяющих ее с другими вершинами. Сумма всех степеней графа равна удвоенному количеству всех его ребер. Для рисунка 2 сумма всех степеней равна 20.

В орграфе, в отличие от неориентированного графа, имеется возможность двигаться из вершины h в вершину s без промежуточных вершин, лишь тогда когда ребро выходит из h и входит в s, но не наоборот.

Ориентированные графы имеют следующую форму записи: G=(V, A) , где V – вершины, A – направленные ребра.

Третий тип графов – смешанные графы (рис. 3). Они имеют как направленные ребра, так и ненаправленные. Формально смешанный граф записывается так: G=(V, E, A) , где каждая из букв в скобках обозначает тоже, что ей приписывалось ранее.

В графе на рисунке 3 одни дуги направленные [(e, a), (e, c), (a, b), (c, a), (d, b)] , другие – ненаправленные [(e, d), (e, b), (d, c)…] .

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

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

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

В любом из рассмотренных нами графов имеется возможность выделить путь и, причем не один. Путь – это последовательность вершин, каждая из которых соединена с последующей посредством ребра. Если первая и последняя вершины совпадают, то такой путь называется циклом. Длина пути определяется количеством составляющих его ребер. Например, на рисунке 4.а путем служит последовательность [(e), (a), (b), (c)] . Этот путь является подграфом, так как к нему применимо определение последнего, а именно: граф G’=(V’, E’) является подграфом графа G=(V, E) , только тогда когда V’ и E’ принадлежат V, E.