Томск, Детский технопарк «Кванториум»
Теория графов 1.0
Основное из теории графов, что может пригодиться при решении олимпиадных задач
Теория графов появилась в 19 веке и использовалась при решении различных логистических задач.
Еще недавно, первые задачи которые приходили в голову при мысли о теории графов были задача о Кёнигсбергских мостах, о четырех красках и задача коммивояжёра.
Однако сейчас теория графов активно используется при изучении социальных сетей и при работе с большими данными.
Если говорить об олимпиадных задачах, то во многих из них встречаются графы, например, в профиле Олимпиады НТИ "Большие данные и машинное обучение" - почти в каждой задаче используют графы, а в профиле "Интеллектуальные робототехнические системы" - есть целый блок задач на работу с графами.
Еще недавно, первые задачи которые приходили в голову при мысли о теории графов были задача о Кёнигсбергских мостах, о четырех красках и задача коммивояжёра.
Однако сейчас теория графов активно используется при изучении социальных сетей и при работе с большими данными.
Если говорить об олимпиадных задачах, то во многих из них встречаются графы, например, в профиле Олимпиады НТИ "Большие данные и машинное обучение" - почти в каждой задаче используют графы, а в профиле "Интеллектуальные робототехнические системы" - есть целый блок задач на работу с графами.
Виды графов
Рассмотрим графы наиболее часто встречающиеся в практических и олимпиадных задачах и сопутствующие им определения
Ориентированный граф (directed graph)
- это пара (V, E), где:
V - непустое конечное множество элементов - множество вершин графа (vertex set),
E - множество упорядоченных пар элементов из V - множество ребер графа (edge set).
В случае ориентированного графа или орграфа (digraph) ребра называют дугами.
V - непустое конечное множество элементов - множество вершин графа (vertex set),
E - множество упорядоченных пар элементов из V - множество ребер графа (edge set).
В случае ориентированного графа или орграфа (digraph) ребра называют дугами.
Неориентированный граф (undirected graph)
- это пара (V, E), где:
V - непустое конечное множество элементов - множество вершин графа (vertex set),
E - множество неупорядоченных пар элементов из V - множество ребер графа (edge set).
Две вершины соединенные ребром называют смежными вершинами (adjacent), а количество ребер выходящих из вершины - степенью вершины (degree).
V - непустое конечное множество элементов - множество вершин графа (vertex set),
E - множество неупорядоченных пар элементов из V - множество ребер графа (edge set).
Две вершины соединенные ребром называют смежными вершинами (adjacent), а количество ребер выходящих из вершины - степенью вершины (degree).
Кратные ребра (multi-edge) и мультиграф (multigraph)
Кратными ребрами (multi-edge) называют ребра соединяющие одну и ту же пару вершин.
Граф с кратными ребрами принято называть мультиграфом (multigraph).
Граф с кратными ребрами принято называть мультиграфом (multigraph).
Петли и псевдограф (pseudograph)
Псевдографом (pseudograph) называют мультиграф (multigraph) в котором присутствуют петли.
Петли - это ребра соединяющие вершины сами с собой.
Петли - это ребра соединяющие вершины сами с собой.
Путь (path) и длина пути (path length)
Путем (path) - в графе называется последовательность вершин и соединяющих их ребер.
Длина пути (path length) - количество ребер входящих в последовательность, задающую этот путь.
Длина пути (path length) - количество ребер входящих в последовательность, задающую этот путь.
Простой путь (simple)
Путь (path) - называется простым если все вершины в нем различны.
Например путь с вершинами {1,2,7,5} будет простым, а путь {6,3,2,6} не будет. Кстати, длина обоих путей в данном примере равна трем.
Например путь с вершинами {1,2,7,5} будет простым, а путь {6,3,2,6} не будет. Кстати, длина обоих путей в данном примере равна трем.
Цикл (cycle)
Циклом (cycle) - в графе называется путь в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро.
Цикл называется простым если в нем нет одинаковых вершин (кроме первой и последней), т.е. если все вершины различны.
Например: на графе расположенном слева пути {1,2,3,4,5,1}, {1,2,5,1}, {2,3,4,2} - циклы.
Цикл называется простым если в нем нет одинаковых вершин (кроме первой и последней), т.е. если все вершины различны.
Например: на графе расположенном слева пути {1,2,3,4,5,1}, {1,2,5,1}, {2,3,4,2} - циклы.
Связный граф (connected graph)
Неориентированный граф называется связным (connected), если для любой пары вершин существует путь из одной вершины в другую.
Связными компонентами (connected components) графа называются те части графа в которых для выбранных вершин существует путь из одной вершины в другие. Таким образом граф может содержать несколько связных компонент но при этом не быть связным.
Неориентированный граф связен тогда и только тогда, когда он состоит из единственной связной компоненты.
Например: на графе слева компоненты {2,3,7,6}, {2,5,6}, {1,2} - связные.
Связными компонентами (connected components) графа называются те части графа в которых для выбранных вершин существует путь из одной вершины в другие. Таким образом граф может содержать несколько связных компонент но при этом не быть связным.
Неориентированный граф связен тогда и только тогда, когда он состоит из единственной связной компоненты.
Например: на графе слева компоненты {2,3,7,6}, {2,5,6}, {1,2} - связные.
Сильно связный граф (strongly connected graph)
Ориентированный граф называется сильно связным (strongly connected), если из любой его вершины достижима (по ориентированным путям) любая другая.
Любой ориентированный граф можно разбить на сильно связные компоненты (strongly connected components), когда из одной вершины можно достичь другой и наоборот.
Например: на графе слева компоненты {2,3}, {7,6}, {6} - сильно связные.
Любой ориентированный граф можно разбить на сильно связные компоненты (strongly connected components), когда из одной вершины можно достичь другой и наоборот.
Например: на графе слева компоненты {2,3}, {7,6}, {6} - сильно связные.
Полный граф (complete graph)
Полным графом (complete graph) - называют неориентированный граф, содержащий все возможные ребра для данного множества вершин (любая вершина смежна любой другой).
Двудольный граф или биграф (bipartite graph)
Неориентированный граф (V, E) - называют двудольным (bipartite), если множество вершин V можно разбить на две части U и V таким образом, что концы любого ребра оказываются в разных частях.
То есть не существует ребра соединяющего две вершины из одной и той же части.
То есть не существует ребра соединяющего две вершины из одной и той же части.
Отлично! Почти половина пути пройдена!
Теперь, после того как мы познакомились с основными видами графов мы можем перейти к способам представления графов.
Теперь, после того как мы познакомились с основными видами графов мы можем перейти к способам представления графов.
Представление графов
Работать с графами представленными в виде двумерного изображения не очень удобно, потому чаще всего графы записывают с помощью матриц смежностей и инциденций.
При обработке больших данных очень часто входные данные поступают в виде матриц смежностей, так что с нее и начнем!
А уж получить из матрицы список смежностей вообще проще простого:)
А уж получить из матрицы список смежностей вообще проще простого:)
Матрица смежностей (adjacency matrix)
Матрицей смежностей (adjacency matrix) для графа G = G (V, E) с n вершинами называется матрица размером (n x n), в которой элементы:
a (i, j) = 1, если вершина V(i) смежна с V(j)
a (i, j) = 0, если вершины V(i) и V(j) не являются смежными.
Напомним определение смежности:
Две вершины соединенные ребром называют смежными вершинами (adjacent).
a (i, j) = 1, если вершина V(i) смежна с V(j)
a (i, j) = 0, если вершины V(i) и V(j) не являются смежными.
Напомним определение смежности:
Две вершины соединенные ребром называют смежными вершинами (adjacent).
Список смежностей (adjacency list)
Хранение матрицы смежности требует O (|V|^2) памяти, что во многих случаях неэкономно. В ряде алгоритмов удобнее пользоваться не матрицей смежностей графа, а списком смежности.
В списке смежности (adjacency list) для каждой вершины указываются вершины, смежные с ней. Хранение списка смежности требует O (|V| +|Е|) памяти.
В списке смежности (adjacency list) для каждой вершины указываются вершины, смежные с ней. Хранение списка смежности требует O (|V| +|Е|) памяти.
На примерах ведь все сразу становится намного понятнее?)
Рассмотрим пример записи матрицы и списка смежностей для неориентированного графа!
Рассмотрим пример записи матрицы и списка смежностей для неориентированного графа!
Неориентированный граф
G=G(V, E), n=5
Матрица смежностей
Матрица размером (n x n) = (5 x 5)
Список смежностей
Требует O (|V| +|Е|) памяти, вместо O (|V|^2)
Чтобы закрепить результат рассмотрим пример записи матрицы и списка смежностей для ориентированного графа!
Неориентированный граф
G=G(V, E), n=5
Матрица смежностей
Матрица размером (n x n) = (5 x 5)
Список смежностей
Здесь особенно заметно, что список требует намного меньше памяти чем матрица
Заодно с матрицами смежностей рассмотрим и взвешенные графы.
Взвешенный граф (weighted graph) и вес ребра (weight edge)
Взвешенный граф (weighted graph) ставит в соответствие каждому ребру некоторое значение - вес ребра (weight edge).
Например: карта местности. Представим что вершины это города, а ребра соединяющие вершины - дороги между ними. Тогда вес ребра может означать расстояние между вершинами - городами или пропускную способность дороги.
Например: карта местности. Представим что вершины это города, а ребра соединяющие вершины - дороги между ними. Тогда вес ребра может означать расстояние между вершинами - городами или пропускную способность дороги.
Логично что раз существуют взвешенные графы то есть и матрицы смежностей для них! Просто если в примерах рассмотренных выше матрицы смежностей состояли из 0 и 1 (так как вес ребра мы по умолчанию принимали равным 1 или если ребра нет то 0), то теперь значения весов будут самыми различными и матрицы соответственно тоже.
Давайте рассмотри еще один пример, чтобы закрепить знания:)
Давайте рассмотри еще один пример, чтобы закрепить знания:)
Неориентированный граф
G=G(V, E), n=5
Матрица смежностей
Если нет петель то 0;
Если есть петля то 2;
Если нет ребра между двумя разными вершинами то 0;
Если ребро есть то 1;
Если ребра кратные то количество ребер.
Если есть петля то 2;
Если нет ребра между двумя разными вершинами то 0;
Если ребро есть то 1;
Если ребра кратные то количество ребер.
Взвешенный граф
Пример неориентированного взвешенного графа.
Матрица смежностей
Если нет петель то 0;
Если нет ребра между двумя разными вершинами то бесконечность.
Если нет ребра между двумя разными вершинами то бесконечность.
Теперь рассмотрим матрицу инциденций.
Она похожа на матрицу смежностей и встречается в задачах почти также часто, так что она точно тебе пригодится!
Она похожа на матрицу смежностей и встречается в задачах почти также часто, так что она точно тебе пригодится!
Инцидентность
Для того чтобы разобрать это понятие вернемся к ориентированному графу. Рассмотрим вершины 3 и 4 и ребро 6 связывающее их:
ребро 6 выходит из (incident from) вершины 3 и входит в (incident to) вершину 4.
Здесь для описание связи ребра и вершины используется глагол incident.
А в неориентированном графе связь между вершиной и ребром описывают так: ребро 6 инцидентно (incident on vertices) вершинам 3 и 4.
Таким образом инцидентность означает существование связи между ребром и вершиной.
ребро 6 выходит из (incident from) вершины 3 и входит в (incident to) вершину 4.
Здесь для описание связи ребра и вершины используется глагол incident.
А в неориентированном графе связь между вершиной и ребром описывают так: ребро 6 инцидентно (incident on vertices) вершинам 3 и 4.
Таким образом инцидентность означает существование связи между ребром и вершиной.
Матрица инциденций (incidence matrix) для неориентированного графа
Матрицей инциденций (incidence matrix) для неориентированного графа G = G (V, E) с n вершинами и q ребрами называется матрица размером (n x q), в которой элементы:
b (i, j) = 1, если вершина V(i) инцидентна ребру E(j)
b (i, j) = 0, если вершинаV(i) и ребро E(j) не являются инцидентными.
b (i, j) = 1, если вершина V(i) инцидентна ребру E(j)
b (i, j) = 0, если вершинаV(i) и ребро E(j) не являются инцидентными.
Матрица инциденций (incidence matrix) для ориентированного графа
Матрицей инциденций (incidence matrix) для ориентированного графа G = G (V, E) с n вершинами и q ребрами называется матрица размером (n x q), в которой элементы:
b (i, j) = 1, если вершина V(i) является началом дуги E(j)
b (i, j) = -1, если вершина V(i) является концом дуги E(j)
b (i, j) = 0, в остальных случаях.
b (i, j) = 1, если вершина V(i) является началом дуги E(j)
b (i, j) = -1, если вершина V(i) является концом дуги E(j)
b (i, j) = 0, в остальных случаях.
Мы уже поняли что на примерах все становится понятнее, так что вперед!
Рассмотрим пример записи матрицы инциденций для неориентированного и ориентированного графа.
Рассмотрим пример записи матрицы инциденций для неориентированного и ориентированного графа.
Неориентированный граф
G=G(V, E), n=5, q=6
Матрица инциденций
Размер матрицы:
(n x q) = (5 x 6)
(n x q) = (5 x 6)
Ориентированный граф
G=G(V, E), n=5, q=6
Матрица инциденций
Размер матрицы:
(n x q) = (5 x 6)
(n x q) = (5 x 6)
Ура! Больше половины пути пройдено!
Теперь, после того как мы познакомились с основными видами графов и способами их представления мы переходим к главному: алгоритмам поиска кратчайшего пути в графе.
Теперь, после того как мы познакомились с основными видами графов и способами их представления мы переходим к главному: алгоритмам поиска кратчайшего пути в графе.
Алгоритмы поиска
Обычно графы используются для нахождения пути или проверки связности между вершинами.
Вспомним транспортную задачу, когда необходимо найти кратчайший путь для доставки товара из склада в аэропорт.
Или, что более актуально сейчас, вспомним социальную сеть. Например дана группа людей и необходимо проверить выполняется ли дня них "правило шести рукопожатий".
Для решения подобных задач и были созданы алгоритмы поиска.
Вспомним транспортную задачу, когда необходимо найти кратчайший путь для доставки товара из склада в аэропорт.
Или, что более актуально сейчас, вспомним социальную сеть. Например дана группа людей и необходимо проверить выполняется ли дня них "правило шести рукопожатий".
Для решения подобных задач и были созданы алгоритмы поиска.
Начнем с одного из основных алгоритмов - алгоритм поиска в ширину.
Он составляет основу многим алгоритмам, таким как алгоритм Дейкстры или Прима.
Если смотреть по профилям олимпиады НТИ, то в профилях "Большие данные и машинное обучение" и "Интеллектуальные робототехнические системы" в большинстве задач используются алгоритмы поиска в ширину или глубину.
Он составляет основу многим алгоритмам, таким как алгоритм Дейкстры или Прима.
Если смотреть по профилям олимпиады НТИ, то в профилях "Большие данные и машинное обучение" и "Интеллектуальные робототехнические системы" в большинстве задач используются алгоритмы поиска в ширину или глубину.
Поиск в ширину BFS (breadth-first search)
В результате поиска в ширину находится путь кратчайшей длины в невзвешенном графе (ребра которого не имеют весов), то есть путь, содержащий наименьшее число рёбер.
Сложность работы алгоритма равна O (|V|+|E|).
Сложность работы алгоритма равна O (|V|+|E|).
Суть алгоритма:
1) сначала просматривают стартовую вершину 0,
2) затем просматривают те вершины, которые удалены от нее на расстояние 1 и так далее слоями:
3) затем просматриваем вершины, которые удалены на расстояние d, далее d+1...
Для этого в алгоритме используется очередь Q, в которую сначала заносится стартовая вершина 0. Затем повторяем следующие итерации: пока очередь не пуста, достаем из ее головы очередную вершину и просматриваем всех соседей этой вершины, и если какие-то из них еще не помещены в очередь, то помещаем их в конец очереди. При таком обходе, когда очередь станет пуста, все вершины будут просмотрены, причем в порядке увеличения расстояния от стартовой вершины.
1) сначала просматривают стартовую вершину 0,
2) затем просматривают те вершины, которые удалены от нее на расстояние 1 и так далее слоями:
3) затем просматриваем вершины, которые удалены на расстояние d, далее d+1...
Для этого в алгоритме используется очередь Q, в которую сначала заносится стартовая вершина 0. Затем повторяем следующие итерации: пока очередь не пуста, достаем из ее головы очередную вершину и просматриваем всех соседей этой вершины, и если какие-то из них еще не помещены в очередь, то помещаем их в конец очереди. При таком обходе, когда очередь станет пуста, все вершины будут просмотрены, причем в порядке увеличения расстояния от стартовой вершины.
Алгоритм поиска в ширину.
Сразу рассмотрим пример, чтобы суть алгоритма уложилась в голове)
Пример обхода графа в ширину
1) выбираем начальную вершину 0.
2) выбираем вершины находящиеся от вершины 0 на расстоянии 1, и заносим их в очередь: 1, 4, 2.
3) просматриваем первую вершину из очереди, это вершина 1, и смотрим какие вершины находятся от нее на расстоянии 1. Это вершины 3 и 4. Чтобы сразу избежать избыточного заполнения памяти мы не будем вносить в очередь вершины которые уже там есть. Тогда очередь будет выглядеть следующим образом: 4, 2, 3.
4) Далее рассматриваем следующую вершину - 4. Из нее на расстоянии 1 есть две вершины, это вершины 1 и 3. Так как вы вершину один мы уже просмотрели, а вершина 3 уже есть в очереди, то мы пропускаем их. Очередь остается неизменной: 2, 3.
5) рассматриваем вершину 2. Она связана только с начальной вершиной, так что пропускаем ее. Очередь: 3.
6) рассматриваем вершину 3. Она связана только с теми вершинами, которые уже были рассмотрены. Алгоритм выполнен.
2) выбираем вершины находящиеся от вершины 0 на расстоянии 1, и заносим их в очередь: 1, 4, 2.
3) просматриваем первую вершину из очереди, это вершина 1, и смотрим какие вершины находятся от нее на расстоянии 1. Это вершины 3 и 4. Чтобы сразу избежать избыточного заполнения памяти мы не будем вносить в очередь вершины которые уже там есть. Тогда очередь будет выглядеть следующим образом: 4, 2, 3.
4) Далее рассматриваем следующую вершину - 4. Из нее на расстоянии 1 есть две вершины, это вершины 1 и 3. Так как вы вершину один мы уже просмотрели, а вершина 3 уже есть в очереди, то мы пропускаем их. Очередь остается неизменной: 2, 3.
5) рассматриваем вершину 2. Она связана только с начальной вершиной, так что пропускаем ее. Очередь: 3.
6) рассматриваем вершину 3. Она связана только с теми вершинами, которые уже были рассмотрены. Алгоритм выполнен.
Конечно же это очень простой пример, но достаточно наглядный. Главное что нужно не забывать - начальной вершиной может быть любая.
Теперь для сравнения сразу разберем алгоритм поиска в глубину.
Теперь для сравнения сразу разберем алгоритм поиска в глубину.
Поиск в глубину DFS (depth-first search)
Обход графа в глубину DFS позволяет определить вершины, достижимые из данной вершины.
Сложность работы алгоритма равна O (|V|+|E|) (такая же как у алгоритма BFS).
Сложность работы алгоритма равна O (|V|+|E|) (такая же как у алгоритма BFS).
Суть алгоритма:
1) сначала просматривают стартовую вершину 0,
2) далее находят первую вершину удаленную от стартовой на ближайшее расстояние и просматривают все вершины достижимые из выбранной вершины и так далее.
3) когда дальше идти некуда, то необходимо вернуться к последней встречной развилке и продолжать заново.
Для этого при обходе графа используется массив хранящий информацию о том, была ли посещена вершина. В начале работы алгоритма все вершины являются непосещеными. Функция DFS получает на вход очередную вершину и вызывает себя рекурсивно для всех еще непосещенных вершин, достижимых из данной.
Иными словами, мы так же составляем очередь, только новые вершины добавляем не в конец очереди, а в ее начало.
1) сначала просматривают стартовую вершину 0,
2) далее находят первую вершину удаленную от стартовой на ближайшее расстояние и просматривают все вершины достижимые из выбранной вершины и так далее.
3) когда дальше идти некуда, то необходимо вернуться к последней встречной развилке и продолжать заново.
Для этого при обходе графа используется массив хранящий информацию о том, была ли посещена вершина. В начале работы алгоритма все вершины являются непосещеными. Функция DFS получает на вход очередную вершину и вызывает себя рекурсивно для всех еще непосещенных вершин, достижимых из данной.
Иными словами, мы так же составляем очередь, только новые вершины добавляем не в конец очереди, а в ее начало.
Алгоритм поиска в глубину.
Рассмотрим пример для алгоритма поиска в глубину. Для этого выберем простой граф без циклов.
Пример обхода графа в глубину
1) выбираем начальную вершину 0.
2) выбираем вершину расположенную ближе всего к стартовой. Пусть это будет вершина 1.
3) просматриваем вершину 1 и проверяем ее на наличие связи с непосещенной вершиной. Выбираем вершину 4.
4) просматриваем вершину 4 на наличие связи с непосещенной вершиной - такой вершины нет, так что возвращаемся назад.
5) опять просматриваем и проверяем вершину 1. Она связана с еще одной непосещенной вершиной - вершиной 8. Выбираем ее.
6) так как у вершины 8 больше нет связей возвращаемся к вершине 1. От нее уже возвращаемся к вершине 0 и через нее переходим к вершине 2.
7) далее выполняем ту же проверку на связь с непосещеными вершинами. Когда непосещенных вершин не останется завершаем алгоритм.
Итоговый путь обхода: 0 1 4 8 2 5 3 6 7 9.
2) выбираем вершину расположенную ближе всего к стартовой. Пусть это будет вершина 1.
3) просматриваем вершину 1 и проверяем ее на наличие связи с непосещенной вершиной. Выбираем вершину 4.
4) просматриваем вершину 4 на наличие связи с непосещенной вершиной - такой вершины нет, так что возвращаемся назад.
5) опять просматриваем и проверяем вершину 1. Она связана с еще одной непосещенной вершиной - вершиной 8. Выбираем ее.
6) так как у вершины 8 больше нет связей возвращаемся к вершине 1. От нее уже возвращаемся к вершине 0 и через нее переходим к вершине 2.
7) далее выполняем ту же проверку на связь с непосещеными вершинами. Когда непосещенных вершин не останется завершаем алгоритм.
Итоговый путь обхода: 0 1 4 8 2 5 3 6 7 9.
В данном примере был выбран граф не содержащий циклов, так как для этого требуется более сложный алгоритм.
Посмотреть алгоритм, для нахождения циклов в графе можно по следующей ссылке:
Посмотреть алгоритм, для нахождения циклов в графе можно по следующей ссылке:
Прекрасно! Ты не заметил, но все самое основное мы рассмотрели!
Теперь тебе остается только больше практиковаться в решении задач с использованием графов. А начать ты можешь с раздела с решением нескольких задач встречающихся на олимпиадах.
Теперь тебе остается только больше практиковаться в решении задач с использованием графов. А начать ты можешь с раздела с решением нескольких задач встречающихся на олимпиадах.
Разбор задач
Некоторые считают что теория без практики мертва, так что вперед решать задачки!
В этом разделе собраны некоторые задачи из сборников олимпиады НТИ. Давай разомнемся и решим их!
Начнем с профиля "Большие данные и машинное обучение":
Начнем с профиля "Большие данные и машинное обучение":
Пример на нахождение пути.
Автобус едет из пункта А в пункт В. При этом в любой момент времени он движется вправо, чтобы приближаться к пункту В иногда вправо вверх, иногда вправо вниз. Найдите количество способов доехать. На картинке приведена схема дорог между городами.
Решение.
Расставим количество способов доехать до каждой вершины, двигаясь слева направо.
Но сначала попробуй решить самостоятельно, а процесс решения ты сможешь увидеть пролистав изображения ниже.
А чтобы увидеть ответ, просто нажми на него:)
Но сначала попробуй решить самостоятельно, а процесс решения ты сможешь увидеть пролистав изображения ниже.
А чтобы увидеть ответ, просто нажми на него:)
Ответ.
Ответ: 7 + 3 = 10 способов
Рассмотрим еще одну подобную задачку, но посложнее?
Пример на нахождение пути (более сложный).
Автобус едет из пункта А в пункт В. При этом в любой момент времени он движется вправо, чтобы приближаться к пункту В, иногда вправо вверх, иногда вправо вниз. Найдите количество способов доехать. На картинке приведена схема дорог между городами.
Решение.
Расставим количество способов доехать до каждой вершины, двигаясь слева направо.
Но сначала попробуй решить самостоятельно, а процесс решения ты сможешь увидеть пролистав изображения ниже.
А чтобы увидеть ответ, просто нажми на него:)
Но сначала попробуй решить самостоятельно, а процесс решения ты сможешь увидеть пролистав изображения ниже.
А чтобы увидеть ответ, просто нажми на него:)
Ответ.
Ответ: 17 + 69 + 144 + 54 = 284 способа
В профиле "Большие данные и машинное обучение" еще очень много задач, но приступать к их решению вручную не стоит. В этом лонгриде мы в основном рассматриваем те задачи, которые можно решить не прибегая к программированию)
Так что сейчас рассмотрим задачу из профиля "Интеллектуальные робототехнические системы", она отлично демонстрирует то, что знание основ и теории также необходимо при решении олимпиадных задач!
Так что сейчас рассмотрим задачу из профиля "Интеллектуальные робототехнические системы", она отлично демонстрирует то, что знание основ и теории также необходимо при решении олимпиадных задач!
Пример на знание основ теории графов.
Попробуй сначала самостоятельно подумать какие утверждения верны, а какие нет. Знаний, которые ты приобрел в процессе чтения этого лонгрида как раз хватит для решения задачи)
Главное не торопись и старайся рассуждать логично.
Главное не торопись и старайся рассуждать логично.
Решение.
Будем рассматривать утверждения по порядку.
1) Вспомним то, что элементы матрицы смежности отражают то, являются ли вершины смежными или нет. По условию задачи, длина ребер равна 1, а также в графе отсутствуют кратные ребра. Следовательно, элемент (i, j) может быть равен только 1 или 0.
Данное утверждение вполне может сработать в каком-то единичном случае, а это не то что нам необходимо, то есть утверждение неверно)
2) Да, по условию в графе отсутствуют петли, то есть диагональные элементы (i, i) равны 0. Но так как в утверждении рассматривают матрицу в квадрате, то утверждение уже не является верным. Это доказывает следующий пример:
1) Вспомним то, что элементы матрицы смежности отражают то, являются ли вершины смежными или нет. По условию задачи, длина ребер равна 1, а также в графе отсутствуют кратные ребра. Следовательно, элемент (i, j) может быть равен только 1 или 0.
Данное утверждение вполне может сработать в каком-то единичном случае, а это не то что нам необходимо, то есть утверждение неверно)
2) Да, по условию в графе отсутствуют петли, то есть диагональные элементы (i, i) равны 0. Но так как в утверждении рассматривают матрицу в квадрате, то утверждение уже не является верным. Это доказывает следующий пример:
Здесь x и y равны 1 или 0 (точнее они точно равны 1, так как иначе мы получим уже два графа состоящих из одной вершины каждый). Как прекрасно видно, после возведения в квадрат, диагональные элементы стали ненулевыми.
3) Сразу рассмотрим утверждение на примерах. В первой строчке записана матрица смежности для графа представляющего собой треугольник. Во второй строчке - матрица смежности для графа в виде двух треугольников с одним общим ребром.
3) Сразу рассмотрим утверждение на примерах. В первой строчке записана матрица смежности для графа представляющего собой треугольник. Во второй строчке - матрица смежности для графа в виде двух треугольников с одним общим ребром.
Как сразу видно из примеров, это утверждение верно)
4) Утверждение верно, так как связный граф представляет собой матрицу смежности состоящую целиком из единиц кроме диагональных элементов. И всегда при ее возведении в степень все элементы (i, j) будут равны значению степени.
Замечание: в данном утверждении матрицу возводят в третью степень и больше, так как при возведении матрицы размером (2 х 2) с нулевой диагональю в степень 2 элементы (i, j) наоборот становятся равными 0, что противоречит условию утверждения.
5) Здесь сразу заметно что утверждение неверно, так как граф считается двудольным не только в представленной в утверждении ситуации. Если ты немного поразмыслишь, то сразу вспомнишь несколько других примером матриц смежностей двудольных графов)
6) Рассмотрим пример, чтобы показать что утверждение верно. Для этого возьмем матрицу смежности двудольного графа с тремя вершинами и возведем в нечетную степень:
4) Утверждение верно, так как связный граф представляет собой матрицу смежности состоящую целиком из единиц кроме диагональных элементов. И всегда при ее возведении в степень все элементы (i, j) будут равны значению степени.
Замечание: в данном утверждении матрицу возводят в третью степень и больше, так как при возведении матрицы размером (2 х 2) с нулевой диагональю в степень 2 элементы (i, j) наоборот становятся равными 0, что противоречит условию утверждения.
5) Здесь сразу заметно что утверждение неверно, так как граф считается двудольным не только в представленной в утверждении ситуации. Если ты немного поразмыслишь, то сразу вспомнишь несколько других примером матриц смежностей двудольных графов)
6) Рассмотрим пример, чтобы показать что утверждение верно. Для этого возьмем матрицу смежности двудольного графа с тремя вершинами и возведем в нечетную степень:
Получается что при возведении в любую нечетную степень матрицы смежности двудольного графа, мы получаем двудольный граф только с кратными ребрами.
7) Утверждение неверно, так как такой формулы просто нет. Насколько я знаю, формул для вычисления количества циклов в графе вообще не существует)
8) Вспомним определение: степенью вершины графа называют количество ребер выходящих из вершины. Так как граф неориентированный, то элементы матрицы состоят из 1 и 0, следовательно сумма элементов строки как раз будет равна степени вершины.
Ответ: 00110101.
7) Утверждение неверно, так как такой формулы просто нет. Насколько я знаю, формул для вычисления количества циклов в графе вообще не существует)
8) Вспомним определение: степенью вершины графа называют количество ребер выходящих из вершины. Так как граф неориентированный, то элементы матрицы состоят из 1 и 0, следовательно сумма элементов строки как раз будет равна степени вершины.
Ответ: 00110101.
Следующая задача, которую мы рассмотрим, это задача на поиск кратчайшего пути в графе. Алгоритмы поиска очень важны и часто встречаются в задачах. Чтобы у тебя получилось правильно написать код, давай еще раз проверим как ты понял суть алгоритма поиска в ширину.
Пример на повторение поиска в ширину.
Для предложенного графа записать алгоритма поиска в ширину по шагам.
Перезаписать алгоритм с учетом запрета на дублирование.
За начальную вершину выберем вершину 0.
Попробуй записать шаги сам, а потом уже заглядывай в решение:)
Перезаписать алгоритм с учетом запрета на дублирование.
За начальную вершину выберем вершину 0.
Попробуй записать шаги сам, а потом уже заглядывай в решение:)
Решение (без запрета на дублирование).
Возьмем за начальную вершину 0.
Шаг 1: 0 – 7,5,2,1,6
Шаг 2: 7 – 5,2,1,6,1,2,4
Шаг 3: 5 – 2,1,6,1,2,4,4,3
Шаг 4: 2 – 1,6,1,2,4,4,3
Шаг 5: 1 – 6,1,2,4,4,3
Шаг 6: 6 – 1,2,4,4,3,4
Шаг 7: 2,4,4,3,4
Шаг 8: 4,4,3,4
Шаг 9: 4 – 4,3,4,3
Шаг 10: 3,4,3
Шаг 11: 3 – 4,3
Шаг 12: 3
Шаг 1: 0 – 7,5,2,1,6
Шаг 2: 7 – 5,2,1,6,1,2,4
Шаг 3: 5 – 2,1,6,1,2,4,4,3
Шаг 4: 2 – 1,6,1,2,4,4,3
Шаг 5: 1 – 6,1,2,4,4,3
Шаг 6: 6 – 1,2,4,4,3,4
Шаг 7: 2,4,4,3,4
Шаг 8: 4,4,3,4
Шаг 9: 4 – 4,3,4,3
Шаг 10: 3,4,3
Шаг 11: 3 – 4,3
Шаг 12: 3
Решение (с запретом на дублирование).
Запишем алгоритм запрещая дублирование через стратегию «игнорирования нового элемента».
Возьмем за начальную вершину 0.
Шаг 1: 0 – 7,5,2,1,6
Шаг 2: 7 – 5,2,1,6,4
Шаг 3: 5 – 2,1,6,4,3
Шаг 4: 2 – 1,6,4,3
Шаг 5: 1 – 6,4,3
Шаг 6: 6 – 4,3
Шаг 7: 4 – 3
Шаг 8: 3
Возьмем за начальную вершину 0.
Шаг 1: 0 – 7,5,2,1,6
Шаг 2: 7 – 5,2,1,6,4
Шаг 3: 5 – 2,1,6,4,3
Шаг 4: 2 – 1,6,4,3
Шаг 5: 1 – 6,4,3
Шаг 6: 6 – 4,3
Шаг 7: 4 – 3
Шаг 8: 3
Все самое основное мы уже рассмотрели, теперь ты можешь практиковаться самостоятельно. Но учти, большинство задач с графами решаются с помощью программирования, так что думаю не лишним будет почитать лонгрид про программирование на python. Ссылку на него и на сборники в которых ты сможешь найти еще больше задач оставляю ниже:
И еще пару ссылочек на учебники. Да, сейчас есть интернет и многое можно найти там, но старая школа есть старая школа.
Вдруг ты захочешь поподробнее узнать про графы, алгоритмы, сортировки и много не менее крутого:
Вдруг ты захочешь поподробнее узнать про графы, алгоритмы, сортировки и много не менее крутого:
