Формальное определение:
Графом \(G\) называется пара множеств \(G = (V, E\), где \(V(G)\) — непустое конечное множество элементов, называемых вершинами графа, а \(E\) — множество пар элементов из \(V\) (необязательно различных), называемых ребрами графа. \(E = \{(u , v)\ | u, v \in V\}\) — множество ребер графа \(G\), состоящее из пар вершин \((u, v)\). Ребро \((u, v)\) соединяет вершины \(u\) и \(v\).
Простое определение:
Граф - это набор вершин (точек) и соединяющих их отрезков (рёбер).
Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах \(N\) - количество вершин, а \(M\) - ребер. Количество ребер, исходящее из вершины называют степенью вершины \(d(v)\). Для вершины \(a\) ребро \((a, b)\) называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10).
Назовите степень 1-ой и 6-ой вершины и какие ребра инциденты им.
Если какие-то две вершины соединены более, чем одним ребром, то говорят, что граф содержит кратные ребра. Если ребро соединяет вершину саму с собой, то такое ребро называют петлей.
Простой граф не содержит петель и кратных ребер. Если не сказано ничего про наличие петель и кратных ребер, мы будем всегда считать, что граф простой.
Сколько может быть рёбер в простом графе в \(N\) вершинами?
Найдите цикл размера 4 и петлю в этом непростом графе.
Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.
Чаще всего в задачах по программмированию вершины графа - это числа от \(0\) до \(N-1\), чтобы удобно было обращаться к ним как к индексам в разных массивах.
Также чаще всего вам дают считать граф как просто список всех рёбер в нем (но не всегда, конечно). Как оптимально считать и сохранить граф? Есть 3 способа.
Для графа существуют несколько основных способов хранения:
Мы храним для каждой из \(N\) вершин информацию, есть ли ребро в другие вершины, то есть суммарно мы храним \(N^2\) ячеек, а следовательно асимптотика по памяти - \(O(N^2)\).
// как сделать список по матрице
vector<vector<int> > g(n);
for (int i = 0; i < n; ++i){
for (int j = 0;j < n;++j){
cin >> a;
if (a) g[i].push_back(j);
}
}
// список по списку ребер
cin >> n >> m;
vector<vector<int> > g(n);
for (int i = 0; i < m; ++i){
cin >> v1 >> v2;
g[v1].push_back(v2);
g[v2].push_back(v1);
}Здесь асимптотика по памяти и времени считывания - \(O(N + M)\), так как мы храним для каждой вершины, куда есть ребра, то есть \(2 M\) ребер, а также суммарно \(N\) векторов.
Плотные графы, имеющие большое количество ребер следует хранить при помощи матрицы смежности, а разреженные графы, имеющие малое количество ребер, оптимальнее при помощи списка.
Заметьте, что все эти способы обощаются на случай ориентированных графов - при этом матрица смежности становится неориетированной: если есть ребро из вершины \(i\) в вершину \(j\), то сделаем \(A_{ij} = 1\), а \(A_{ji} = 0\), если только нет обратного ребра тоже. А в списке смежности в ориентированном случае при считывании ребра \((u, v)\) будем добавлять только \(v\) в список соседей \(u\), но не наоборот.
Для окончательного закрепления темы советую решить первые 2 задачи.
Дерево - это связный неориентированный граф без циклов.
Свойства дерева:
Действительно, если начать из любой вершины идти по непосещенным ранее вершинам, то в какой-то момент мы прекратим это делать, ведь граф конечный. При этом если из этой вершины не может быть ребер в непосещенные вершины - ведь тогда прекращать рано, и не может быть ребер в посещенные ребра (помимо предыдущей) - ведь тогда есть цикл. А значит, есть ребро только в предыдущую вершину, значит степень равна 1.
Действительно, если предыдущий алгоритм начать из висячей вершины, то мы уткнемся в другую висячую вершину.
Давайте отрезать от дерева его висячие вершины - при этом число вершин уменьшится на один, число ребер тоже уменьшится на один, а граф останется деревом. Раз граф остается деревом, у него все время будет висячая вершина, пока \(N > 1\). В какой-то момент останется только одна вершина и ноль ребер. Раз мы отрезали столько же вершин, сколько ребер, и получили 1 вершину и 0 ребер, значит изначально вершин было ровно на одну больше.
Действительно, если их два, то в графе есть цикл. Быть ноль их не может - ведь граф связный.
Действительно, если есть связный граф, в котором меньше, чем \(N-1\) ребро, то давайте уберем из его цикла ребро. Граф при этом остается связным, а число ребер уменьшается. Давайте повторять это, пока в какой-то момент циклов в графе не будет, а значит осталось дерево. Но мы уже доказали, что в дереве \(N-1\) ребро, это противоречие, ведь у нас сначала было меньше ребер, а мы еще и удалили сколько-то.
Обход в глубину — простой, но многофункциональный алгоритм обхода графа по ребрам. Самое главное, что он может — это проверить, какие вершины достижимы из данной.
При обходе графа мы используем вспомогательный массив used, в котором храним 1, если вершина была посещена или 0 иначе. В начале мы считаем, что все вершины не использовались, затем мы выбираем одну вершину, помечаем ее посещенной и запускаемся рекурсивно из всех ее соседей, тогда мы посетим все вершины, которые достижимы из данной, если же остались вершины с used = 0 значит они недостижимы.
Красивая визуализация: https://visualgo.net/en/dfsbfs
void dfs (int v) {
used[v] = 1;
for (auto to : g[v]) {
if (!used[to]) {
dfs(to);
}
}
}Давайте оценим сложность алгоритма. Так как мы проверяем, что вершина еще не использовалась, то всего мы пройдет каждую вершину 1 раз, но при этом и ребро между двумя вершинами, мы рассматриваем только когда рассматривается один конец, то есть мы просмотрим каждое ребро не более одного раза, суммарно получаем оценку \(O(N + M)\).
Задачи 3-5 в контесте.
Путем в графе называется последовательность вершин \(v_i \in 𝑉\), \(i = 1...k\) таких, что две последовательные вершины в пути соединены ребром, \(k\) - длина пути. Граф называется связным, если для любых двух его вершин существует путь между ними. Граф всегда можно разбить на непересекающиеся связные подмножества (возможно одно), между которыми рёбер нет, они называются компонентами связности.
Поиск в глубину dfs будет обходить ту компоненту связности, из вершины которой, он был вызван. Поэтому для поиска компонент связности можно каждый раз вызываться из любой непосещенной вершины и тогда в результате мы посетим все вершины, а следовательно и найдем все компоненты связности.
for (int i = 0; i < n; ++i){
if (!used[i]) {
amount++;
dfs(i);
}
}На данную тему задачи 6 и 10 в контесте.
Остованым деревом в связном графе называется любое подмножество ребер, которое является деревом на всех вершинах. То есть любой способ выкинуть несколько ребер так, чтобы осталось дерево на N вершинах и N-1 ребро выделяет в графе остовное дерево.
Обход графа удобно использовать для выделения этого остовного дерева - если выделить каждое ребро, по которому мы прошли в обходе, то получится остовное дерево. Действительно, мы обойдем все вершины, и при этом никогда не пойдем в вершину, в которой уже были, поэтому циклов там не будет. Так что достаточно после прохода по любому ребру добавлять его в ответ.
7 задача в контесте на выделение остовного дерева в графе.
Корректной раскраской графа в два цвета назывется такая раскраска, что никакое ребро не соединяет две вершины одного цвета. Графы, которые можно так раскрасить, называют еще двудольными.
С помощью обхода графа легко проверить граф на двудольность и даже вывести цвет каждой вершины - достаточно выделить каждую.
8 задача в контесте на раскраску графа в два цвета
Циклом в графе \(G\) называется ненулевой путь, ведущий из вершины \(v\) в саму себя. Граф называют ацикличным, если в нем нет циклов.
В обычном dfs мы используем два цвета (1 - вершина посещена, 0 - не посещена), если же нам надо найти цикл, то давайте хранить 3 цвета:
Заметим, что цикл будет тогда и только тогда, когда мы пытаемся войти в вершину с цветом 1.
void dfs (int v) {
used[v] = 1;
for (size_t i=0; i < g[v].size(); ++i) {
int to = g[v][i];
if (used[to] == 0){
p[to] = v;
dfs (to);
}
else if (used[to] == 1 && to != p[v]) {
cycle = true;
}
}
used[v] = 2;
}В неориентированном графе также надо дополнительно рассмотреть случай, когда мы идем в предка - это циклом все-таки не считается, для этого нужно отдельно добавить второй аргумент prev, где хранить предыдущую вершину в dfs, и никогда не идти в неё.
9 задача в контесте на поиск цикла в графе.
#Ссылка на контест
https://informatics.msk.ru/mod/statements/view3.php?id=33377