Здравствуйте, товарищи!! Мы собрали для вас материалы по такой важной теме, как теория графов. Это один из тех разделов, который встречается практически на каждой олимпиаде😎 Основные термины Граф — абстрактное представление множества объектов и связей между ними. Состоит из вершин и рёбер. Вершина — отдельный объект графа. Может иметь значение, цвет, или быть просто точкой. Ребро — связь между двумя вершинами. Может быть взвешенным (с числовым значением) или невзвешенным. Смежность вершин — две вершины называются смежными, если они соединены ребром. Смежность рёбер — два ребра называются смежными, если они соединены одной вершиной. Инцидентность — вершина и ребро называются инцидентными, если вершина является концом ребра. Степень вершины — количество рёбер, инцидентных вершине. Изолированная вершина — степень 0. Висячая вершина — степень 1. Подграф — часть графа, выделенная из исходного графа с некоторыми вершинами и рёбрами. Виды графов По направленности: Неориентированные графы — связь двусторонняя. Ориентированные графы — рёбра имеют направление (стрелки). По наличию циклов: Ациклические графы — не содержат циклов. Циклические графы — содержат хотя бы один цикл. По весу ребер: Взвешенные графы — каждое ребро имеет вес. Невзвешенные графы — ребра без веса. По связности: Связные графы — существует путь между любыми двумя вершинами. Несвязные графы — есть хотя бы две вершины без пути между ними. Особые типы графов Дерево — связный ациклический граф, у которого |E| = |V| - 1 и ровно один путь между любыми двумя вершинами. Полный граф (Kₙ) — каждая пара вершин соединена ребром. Двудольный граф — вершины можно разбить на два множества так, что каждое ребро соединяет вершины из разных множеств. Нет нечётных циклов. Планарный граф — граф, который можно изобразить на плоскости без пересечения рёбер. Способы обхода графа (тыкайте на ссылки, если хотите прочитать про алгос поподробнее) DFS (поиск в глубину) — стратегия обхода графа «вглубь»: мы идём по пути до конца, потом возвращаемся и пробуем другие ветки. BFS (поиск в ширину) — стратегия обхода графа «вширь»: мы сначала посещаем все вершины на расстоянии 1 от старта, потом на расстоянии 2 и так далее.Способы обхода графа Практика на codeforces Слух Бейджик Распространение новостей Мишка и условие дружбы Хобби Сакурако Путешествие Секретные пароли @postupashki_prog