Графы. Разные виды представления графов. Пути в лабиринте. Выход из лабиринта (поиск в глубину). Кратчайший путь (поиск в ширину). Алгоритмы на графах. Алгоритмы Дейкстры и Флойда. Примеры задач. Алгоритмы на графах: Флойда, Дейкстры, Краскала
Метод обхода графа при котором в первую очередь переход делается из последней посещённой вершины (вершины хранятся в стеке). Обход в глубину получается естественным образом при рекурсивном обходе графа.
Порядок обхода вершин при поиске в глубину
Поиск в ширину — ПВШ (Breadth First Search — BFS)
Метод обхода графа при котором в первую очередь переход делается из первой вершины, из которой мы ещё не ходили (вершины хранятся в очереди). Обход в глубину получается естественным образов при рекурсивном обходе графа.
Порядок обхода вершин при поиске в ширину
Поиск кратчайших путей в графах (объединение разделов по Дейкстре и Флойду)
Алгоритм Дейкстры
Алгоритм Дейкстры (Dijkstra’s algorithm) — алгоритм на графах, находящий кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса (без рёбер с отрицательной "длиной").
Примеры формулировки задачи
Вариант 1. Дана сеть автомобильных дорог, соединяющих города. Некоторые дороги односторонние. Найти кратчайшие пути от заданного города до каждого другого города (если двигаться можно только по дорогам).
Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.
Идея алгоритма Дейкстры
Алгоритм состоит и 2 повторяющихся шагов:
- Добавление новой вершины ("Расти" — GROW)
- "Релаксация", т.е. пересчёт расстояний до других вершин с учётом добавленной вершины (RELAX).
Более подробное описание:
Обозначения:
Граф $G = (V,E)$, где $V$ — вершины, $E$ — рёбра.
$v_0$ — начальная вершина (от которой мы ищем кратчайшее растояние до всех остальных)
$R_i$ — известное нам расстояние от вершиеы $v_0$ до вершины $i$-ой.
$D$ — множество вершин до которых мы знаем кратчайшее расстояние от $v_0$.
Граф $G=(V,E)$, где $V$ — вершины, $E$ — рёбра.
$v_0$ — начальная вершина
$R_i$ — кратчайщее расстояние от $v_0$ до $i$-ой вершины
Инициализация алгоритма:
$D = \<\>$ — пустое множество.
$R_
$v = v_0$ — расти будем от вершины $v$.
Повторять (общий шаг алгоритма)
$GROW(V/D,v)$ — Добавляем вершину $v$ из множества $V/D$ в множество $D$.
$RELAX(V/D,v)$ — пробегаем достижимые из $v$ вершины до которых мы ещё не знаем кратчайшее расстояние и обновляем расстояния $R_i$ от вершины $v$.
$v$ — вершина с минимальным $R$ из множества $V/D$.
Алгоритм
Каждой вершине v из V сопоставим значение a[v] — минимальное известное расстояние от этой вершины до начальной s. Алгоритм работает пошагово — на каждом шаге он рассматривает одну вершину и пытается улучшить текущее расстояние до этой вершины. Работа алгоритма завершается, когда все вершины посещены, либо когда вычислены расстояния до всех вершин, достижимых из начальной.
Инициализация. Значение a[s] самой начальной вершины полагается равным 0, значение остальных вершин — бесконечности (в программировании это реализуется присваиванием большого, к примеру, максимально возможного для данного типа, значения). Это отражает то, что расстояния от s до других вершин пока неизвестны.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина v, имеющая минимальное расстояние от начальной вершины s и добавляется в список посещенных. Эта вершина находится, используя перебор всех непосещенных вершин. При этом суммируется расстояние от старта до одной из посещенных вершин u до непосещенной v. Для первого шага s — единственная посещенная вершина с расстоянием от старта (то есть от себя самой), равным 0.
Алгоритм Флойда
Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.
Пусть вершины графа пронумерованы от 1 до $n$ и введено обозначение $d_
Существует два варианта значения $d_^
- Кратчайший путь между $i,\;j$ не проходит через вершину $k$, тогда $d_^
=d_^ $ - Существует более короткий путь между $i,\;j$, проходящий через $k$, тогда он сначала идёт от $i$ до $k$, а потом от $k$ до $j$. В этом случае, очевидно, $d_^
=d_^ + d_ ^ $
Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.
Тогда рекуррентная формула для $d_^k$ имеет вид:
$d_^0$ — длина ребра $(i,\;j)$
Алгоритм Флойда — Уоршелла последовательно вычисляет все значения $d_^
Алгоритм Прима
Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.
Построение начинается с дерева, включающего в себя одну (произвольную) вершину. В течение работы алгоритма дерево разрастается, пока не охватит все вершины исходного графа. На каждом шаге алгоритма к текущему дереву присоединяется самое лёгкое из рёбер, соединяющих вершину из построенного дерева, и вершину не из дерева.
Вход: Связный неориентированный граф $G(V,E)$
Выход: Множество $T$ рёбер минимального остовного дерева
10 Графовых алгоритмов
Графы превратились в невероятно сильное средство моделирования и получения данных из соцсетей, веб-страниц и ссылок, а также определения местоположения и маршрутов в GPS. Любой набор объектов, которые связаны друг с другом, можно сейчас представить с помощью графа.
В статье опишем 10 основных графовых алгоритмов, которые становятся очень полезными для анализа, а также области их применения.
Начнём с того, что приведём определение графа.
Что такое граф?
Граф состоит из конечного множества вершин (узлов) и набора рёбер, соединяющих эти вершины. Две вершины считаются смежными, если они соединены друг с другом одним и тем же ребром.
Ниже приведён ряд базовых понятий, относящихся к графам. Они проиллюстрированы примерами на рисунке 1.
- Порядок: число вершин в графе.
- Размер: число рёбер в графе.
- Степень вершины: число рёбер, инцидентных вершине.
- Изолированная вершина: вершина, которая не связана ни с одной другой вершиной графа.
- Петля: ребро, вершины которого совпадают.
- Ориентированный граф: граф, в котором все рёбра имеют направление, определяющее начальную и конечную вершину.
- Неориентированный граф: граф с рёбрами, которые не имеют направления.
- Взвешенный граф: рёбра такого графа имеют определённый вес.
- Невзвешенный граф: рёбра такого графа не имеют никаких весов.
1. Поиск в ширину
Обход или поиск — это одна из фундаментальных операций, выполняемых на графах. Поиск в ширину начинается с определённой вершины, затем исследуются все её соседи на данной глубине и происходит переход к вершинам следующего уровня. В графах, в отличие от деревьев, могут быть циклы — пути, в которых первая и последняя вершины совпадают. Поэтому необходимо отслеживать посещённые алгоритмом вершины. При реализации алгоритма поиска в ширину используется структура данных «очередь».
На рисунке 2 показан пример того, как выглядит поиск в ширину на графе. Жёлтым цветом помечаются обнаруженные вершины, красным — посещённые.
Применяется для:
- определения кратчайших путей и минимальных остовных деревьев;
- индексации веб-страниц поисковыми ботами;
- поиска в соцсетях;
- нахождения доступных соседних узлов в одноуровневых сетях, таких как BitTorrent.
2. Поиск в глубину
Поиск в глубину начинается с определённой вершины, затем уходит как можно дальше вдоль каждой ветви и возвращается обратно. Здесь тоже необходимо отслеживать посещённые алгоритмом вершины. Для того, чтобы стало возможным возвращение обратно, при реализации алгоритма поиска в глубину используется структура данных «стек».
На рисунке 3 показан пример того, как выглядит поиск в глубину на том же графе, который использован на рисунке 2. Граф обходится на всю глубину каждой ветви с возвращением обратно.
Применяется:
- для нахождения пути между двумя вершинами;
- для обнаружения циклов на графе;
- в топологической сортировке;
- в головоломках с единственным решением (например, лабиринтах).
3. Кратчайший путь
Кратчайший путь от одной вершины графа к другой — это путь, при котором сумма весов рёбер, его составляющих, должна быть минимальна.
На рисунке 4 показан кратчайший путь на графе от вершины 1 до вершины 6.
Алгоритмы нахождения кратчайшего пути:
- Алгоритм Дейкстры.
- Алгоритм Беллмана-Форда.
Применяются в:
- картографических сервисах типа Google maps или Apple maps для прокладки маршрутов и определения местоположения;
- сетях для решения проблемы минимальной задержки пути;
- абстрактных автоматах для определения через переход между различными состояниями возможных вариантов достижения некоторого целевого состояния, например минимально возможного количества ходов, необходимого для победы в игре.
4. Обнаружение циклов
Цикл — это путь, в котором первая и последняя вершины графа совпадают. То есть путь, начинающийся и завершающийся в одной и той же вершине, называется циклом. Обнаружение циклов — это процесс выявления таких циклов. На рисунке 5 показано, как происходит обнаружение цикла.
Алгоритмы обнаружения цикла:
- Алгоритм Флойда.
- Алгоритм Брента.
Применяются:
- в распределённых алгоритмах, использующих сообщения;
- для обработки крупных графов с использованием распределённой системы обработки в кластере;
- для обнаружения взаимоблокировок в системах с параллельным выполнением;
- в криптографических приложениях для выявления ключей сообщения, которые могут соответствовать одному и тому же зашифрованному значению.
5. Минимальное остовное дерево
Минимальное остовное дерево — это подмножество рёбер графа, которое соединяет все вершины, имеющие минимальную сумму весов рёбер, и без циклов.
На рисунке 6 показан процесс получения минимального остовного дерева.
Алгоритмы поиска минимального остовного дерева:
- Алгоритм Прима.
- Алгоритм Крускала.
Применяются:
- для создания деревьев для распределения данных в компьютерных сетях;
- в кластерном анализе с использованием графов;
- при сегментации изображений;
- при социально-географическом районировании, когда смежные регионы объединяются.
6. Сильно связные компоненты
Граф считается сильно связным, если все вершины в графе достижимы из всех остальных вершин.
На рисунке 7 показан пример того, как выглядит граф с тремя сильно связными компонентами, вершины которых окрашены в красный, зелёный и жёлтый цвета.
Алгоритмы поиска сильных компонент связности:
- Алгоритм Косараджу.
- Алгоритм Тарьяна.
Применяются:
- для вычисления декомпозиции Далмейджа-Мендельсона, которая представляет собой разделение вершин двудольного графа на подмножества;
- в соцсетях для поиска групп сильно связанных между собой людей и выдачи рекомендаций на основе общих интересов.
7. Топологическая сортировка
Топологическая сортировка графа — это такое линейное упорядочение его вершин, в котором для каждого направленного ребра, например (u, v), вершина u предшествует вершине v.
На рисунке 8 показан пример топологического упорядочения вершин, согласно которому вершина 5 должна следовать за вершинами 2 и 3, а вершина 6 — за вершинами 4 и 5.
Алгоритмы поиска топологической сортировки:
- Алгоритм Кана.
- Алгоритм на основе поиска в глубину.
Применяются:
- при планировании выполнения команд;
- при сериализации данных;
- определения порядка выполняемых при компиляции задач в Makefiles;
- для разрешения зависимостей символов в компоновщиках.
8. Раскраска графов
При раскраске графов элементам графа присваиваются цвета с учётом определённых условий. Раскраска вершин — наиболее часто используемый метод окраски графов. При этом вершины графа окрашиваются с использованием k цветов, а любым двум соседним вершинам должны соответствовать разные цвета. Другие методы окраски — раскраска рёбер и раскраска граней.
Хроматическое число графа — это наименьшее количество цветов, необходимых для окрашивания графа.
На рисунке 9 показан пример того, как выглядит раскраска вершин графа с использованием 4-х цветов.
Алгоритмы с раскраской графов:
- Алгоритмы, использующие поиск в ширину или поиск в глубину.
- Жадная раскраска.
Применяются для:
- составления расписаний;
- назначения радиочастот мобильных сетей;
- моделирования и решения головоломок типа судоку;
- проверки того, является ли граф двудольным;
- раскрашивания географических карт стран или штатов, на которых соседние страны или штаты имеют разные цвета.
9. Максимальный поток
Можно смоделировать граф в виде сети потоков с весами рёбер в качестве пропускной способности этих потоков. В задаче максимального потока требуется найти такой путь потока, который может обеспечить максимально интенсивность потока.
На рисунке 10 показан пример того, как выглядит нахождение максимального потока сети и определение конечного значения потока.
Алгоритмы нахождения максимального потока:
- Алгоритм Форда-Фулкерсона.
- Алгоритм Эдмондса-Карпа.
- Алгоритм Диница.
Применяются:
- в авиакомпаниях для составления полётного расписания экипажей;
- при сегментации изображений для определения фона и переднего плана изображения.
10. Паросочетания
Паросочетание на графе — это набор рёбер, которые не имеют общих вершин (т.е. хотя бы двух рёбер, не имеющих общей вершины). Паросочетание называется максимальным, если оно содержит максимально возможное число рёбер, сочетающихся с как можно большим количеством вершин.
На рисунке 11 показано получение полного паросочетания в двудольном графе с двумя наборами вершин, обозначенных оранжевым и синим цветами.
Алгоритмы нахождения паросочетаний:
- Алгоритм Хопкрофта-Карпа.
- Венгерский алгоритм.
- Алгоритм сжатия цветков.
Применяются:
- в подборе пары для жениха или невесты (задача о стабильных браках);
- для определения вершинного покрытия;
- в теории транспорта для решения задачи распределения ресурсов и оптимизации перевозок.
Заключение
Надеюсь, статья была полезной и в простой и краткой форме познакомила вас с графовыми алгоритмами. ��
А с реализациями графовых алгоритмов можно ознакомиться в модулях на Python networkx и igraph.
Базовые алгоритмы нахождения кратчайших путей во взвешенных графах
Наверняка многим из гейм-девелоперов (или просто людям, увлекающимися програмировагнием) будет интересно услышать эти четыре важнейших алгоритма, решающих задачи о кратчайших путях.
Сформулируем определения и задачу.
Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами). Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины.
Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из одного города в другой, проехав как можно меньший путь.
Считаем, что в графе n вершин и m рёбер.
Пойдём от простого к сложному.
Алгоритм Флойда-Уоршелла
Находит расстояние от каждой вершины до каждой за количество операций порядка n^3. Веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер (иначе мы можем ходить по нему сколько душе угодно и каждый раз уменьшать сумму, так не интересно).
В массиве d[0… n — 1][0… n — 1] на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в качестве «пересадочных» в пути мы будем использовать вершины с номером строго меньше i — 1 (вершины нумеруем с нуля). Пусть идёт i-ая итерация, и мы хотим обновить массив до i + 1-ой. Для этого для каждой пары вершин просто попытаемся взять в качестве пересадочной i — 1-ую вершину, и если это улучшает ответ, то так и оставим. Всего сделаем n + 1 итерацию, после её завершения в качестве «пересадочных» мы сможем использовать любую, и массив d будет являться ответом.
n итераций по n итераций по n итераций, итого порядка n^3 операций.
Псевдокод:
Алгоритм Форда-Беллмана
Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n * m. Аналогично предыдущему алгоритму, веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер.
Заведём массив d[0… n — 1], в котором на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в путь должно входить строго меньше i рёбер. Если таких путей до вершины j нет, то d[j] = 2000000000 (это должна быть какая-то недостижимая константа, «бесконечность»). В самом начале d заполнен 2000000000. Чтобы обновлять на i-ой итерации массив, надо просто пройти по каждому ребру и попробовать улучшить расстояние до вершин, которые оно соединяет. Кратчайшие пути не содержат циклов, так как все циклы неотрицательны, и мы можем убрать цикл из путя, при этом длина пути не ухудшится (хочется также отметить, что именно так можно найти отрицательные циклы в графе: надо сделать ещё одну итерацию и посмотреть, не улучшилось ли расстояние до какой-нибудь вершины). Поэтому длина кратчайшего пути не больше n — 1, значит, после n-ой итерации d будет ответом на задачу.
n итераций по m итераций, итого порядка n * m операций.
Псевдокод:
Алгоритм Дейкстры
Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n^2. Все веса неотрицательны.
На каждой итерации какие-то вершины будут помечены, а какие-то нет. Заведём два массива: mark[0… n — 1] — True, если вершина помечена, False иначе, d[0… n — 1] — для каждой вершины будет храниться длина кратчайшего пути, проходящего только по помеченным вершинам в качестве «пересадочных». Также поддерживается инвариант того, что для помеченных вершин длина, указанная в d, и есть ответ. Сначала помечена только вершина 0, а g[i] равно x, если 0 и i соединяет ребро весом x, равно 2000000000, если их не соединяет ребро, и равно 0, если i = 0.
На каждой итерации мы находим вершину, с наименьшим значением в d среди непомеченных, пусть это вершина v. Тогда значение d[v] является ответом для v. Докажем. Пусть, кратчайший путь до v из 0 проходит не только по помеченным вершинам в качестве «пересадочных», и при этом он короче d[v]. Возьмём первую встретившуюся непомеченную вершину на этом пути, назовём её u. Длина пройденной части пути (от 0 до u) — d[u]. len >= d[u], где len — длина кратчайшего пути из 0 до v (т. к. отрицательных рёбер нет), но по нашему предположению len меньше d[v]. Значит, d[v] > len >= d[u]. Но тогда v не подходит под своё описание — у неё не наименьшее значение d[v] среди непомеченных. Противоречие.
Теперь смело помечаем вершину v и пересчитываем d. Так делаем, пока все вершины не станут помеченными, и d не станет ответом на задачу.
n итераций по n итераций (на поиск вершины v), итого порядка n^2 операций.
Псевдокод:
Как найти кратчайший путь в графе
Кратчайший путь между вершинами графа
Графы как информационные модели находят широкое применение во многих сферах нашей жизни. Поиск оптимального транспортного маршрута, кратчайшего объездного пути, расположения торговых точек, проектирования инженерных сетей и линий электропередач приводят к задаче поиска кратчайшего пути.
Путь между вершинами А и В графа считается кратчайшим, если:
— эти вершины соединены минимальным числом ребер (в случае, если граф не является взвешенным)
— сумма весов ребер, соединяющих эти вершины, минимальна (для взвешенного графа)
Построение дерева решений
Алгоритм построения дерева решений , как правило, используется для нахождения кратчайшего пути в ориентированном графе.
На рисунке представлена схема дорог, связывающих населённые пункты A, B, C, D, E, F. Вес ребра означает стоимость проезда между двумя населенными пунктами. Определить минимальную стоимость проезда из пункта E в пункт C .
Алгоритм Дейкстры
Алгоритм Дейкстры служит для нахождения кратчайшего пути между вершиной (источником) и всеми остальными вершинами графа.
Определить минимальное расстояние от вершины A до F .
Найдем вершину с минимальной меткой, определим минимальное расстояние до смежных вершин, отметим вершину как рассмотренную и проверим есть ли непосещенные вершины
Повторим выше перечисленные действия.
Метод динамического программирования
Все улицы одного из кварталов города N прямые с односторонним движением и пересекаются под прямым углом. Если не поворачивать, то можно проехать с южной окраины на северную или с западной на восточную. Длины переулков равны, но каждый участок характеризуется количеством ям на дороге. Необходимо выбрать лучший маршрут проезда от пункта A в пункт B .
Попасть в вершину B можно только из двух вершин. Значение лучшего варианта зависит не только от веса ребер, но и от того, с каким «результатом» можно добраться до этих двух вершин.
Существует рекурсивное решение этой задачи, но оно не оптимально по скорости выполнения.
Значение стартовой вершины A [1, 1] равно нулю.
Значения последующих вершин – сумма значений предшествующих участков.
Значение в вершине X [ i , j ] равно меньшему из значений вершин X [ i -1, j ] и X [ i , j -1] с учетом весовых значений дуг, направленных к X [ i , j ].
При заполнении будем двигаться от левого нижнего угла к правому верхнему.
2+7<4+8 Вариант проезда от начала движения сначала на север, потом на восток лучше.
Определим величины всех вершин
Как же определить маршрут движения?
Начиная с конечной точки, отметим вершины с меньшими значениями – это и будет маршрут движения.
Знакомство с теорией игр
Теория игр — раздел современной математики, связанный с решением многих задач экономики, социологии, политологии, биологии, искусственного интеллекта и ряда других областей, где необходимо изучение поведения человека и животных в различных ситуациях.
Игра выступает в качестве математической модели некоторой ситуации и понимается как процесс, в котором участвуют две и более стороны, ведущие борьбу за реализацию своих интересов.
Игра может быть представлена в виде дерева, каждая вершина которого соответствует ситуации выбора игроком своей стратегии. В играх с полной информацией участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им предсказать варианты развития игры.
Чеширский кот предложил сыграть в игру с одной фигурой на части шахматной доски. Вы и кот ходите по очереди. За один ход фигуру можно переместить на одну клетку в направлении, указанном стрелками. Выигрывает тот, кто сделал последний ход.
Найдем такую клетку, ход в которую означает выигрыш для игрока, занявшего эту позицию, и проигрыш для соперника.
Отметим эту клетку как проигрышную – X 0 (для того, кто должен сейчас выполнять ход).
Индекс означает количество ходов из этой позиции до развязки игры.
Найдем клетки, из которых можно поставить фигуру в позицию X 0 . Отметим их знаком В1.
Для четырех позиций определено возможное развитие игры, при условии грамотной игры обоих игроков.
Из отмеченных клеток существует только один вариант хода игрока.
Клетки являются проигрышными в один ход (ходящего игрока) – X 1 . Из каждой существует единственный вариант развития событий.
Из клеток можно пойти в три различные клетки. Какие варианты следует выбрать?
Метки клеток В2.
Из клетки X 2 можно пойти в три клетки (В1, В2).
Проанализируем оставшиеся клетки.
В таблице представлена вся информация об игре. Обозначены все клетки являющиеся выигрышными и все клетки, которые необходимо избегать. Игрок, который делает первый ход, обладает выигрышной стратегией.
Выигрышная стратегия – это правило, следуя которому игрок выигрывает независимо от того, как играет противник. Выигрышная стратегия может быть только у одного игрока. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации при различной игре противника.
Выигрышная стратегия может быть только у одного игрока. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации при различной игре противника.
Признаки игры:
— присутствием нескольких игроков;
— неопределённостью, связанной с поведением игроков, у каждого из которых есть несколько вариантов действий;
— различием (несовпадением) интересов игроков;
— взаимосвязанностью поведения игроков (результат, получаемый каждым из них, зависит от поведения всех игроков);