👏Основные теоремы для решения задач олимпиадных по комбинаторике. 😀Теорема Бёрнсайда (Burnside's Lemma) — используется для подсчета количества эквивалентных классов, которые возникают при действии группы на множестве. 😀Теорема Холла (Hall's Marriage Theorem) — утверждает, что существует совершенное паросочетание в двудольном графе тогда и только тогда, когда для любого подмножества вершин левой доли размера k количество соседей в правой доле не меньше k. 😀Теорема Пойа (Pólya's Enumeration Theorem) — позволяет находить число различных комбинаций элементов, которые остаются неизменными при действии некоторой группы симметрий. 😀Теорема о взвешенных графах (Weighted Graph Theorem) — утверждает, что при определенных условиях минимальное взвешенное дерево графа может быть найдено с помощью построения графа дополнений и выполнения простых операций на нем. 😀Теорема Кирхгофа о матрице дерева (Kirchhoff's Matrix Tree Theorem) — утверждает, что количество остовных деревьев в связном графе можно найти с помощью вычисления определителя матрицы, которая получается из матрицы смежности графа путем замены каждого элемента на противоположный его степени степени вершины. 😀Теорема Реди (Redei's Theorem) — утверждает, что если граф является r-регулярным (то есть каждая вершина имеет степень r), то количество гамильтоновых циклов в нем равно r^n/n, где n — количество вершин в графе. 🔝🔝🔝Если будет много шеров и лайков, буду больше выкладывать красоты, готовых решений и полезных материалов🔝🔝🔝