по мотивам: С. Скиена, Т. Кормен, Р. Седжвикafter: S. Skiena, T. Cormen, R. Sedgewick

Теория и Алгоритмы на ГрафахGraph Theory & Algorithms

Представление и базовый обход графов, кратчайшие пути и минимальные остовы, сетевые потоки, паросочетания, прикладные графовые модели — все 9 карточек этих тем заполнены: с нуля объясняют терминологию, дают диаграммы для каждого понятия и минимум 5 примеров из реальной жизни на страницу. Плюс новый каркас 3.3b «Особые структуры графа» (Эйлеровы/гамильтоновы пути, раскраска, планарность) — классический материал, отсутствовавший в исходном плане раздела.Graph representation and basic traversal, shortest paths and minimum spanning trees, network flows, matchings, applied graph models — all 9 cards on these topics are filled in: each explains terminology from scratch, gives diagrams for every concept, and at least 5 real-world examples per page. Plus a new skeleton, 3.3b "Special graph structures" (Eulerian/Hamiltonian paths, coloring, planarity) — classic material that was missing from the section's original plan.

3.1 Представление и Базовый Обход Графов3.1 Graph representation & basic traversal

3.1.1 Топология и хранение графовGraph topology & storageМатрица смежности, списки смежности, CSR (Compressed Sparse Row) для оптимизации L1/L2 кэша.Adjacency matrix, adjacency lists, CSR (Compressed Sparse Row) for L1/L2 cache optimization. 3.1.2 Фундаментальные обходыFundamental traversalsBFS, DFS, поиск мостов и точек сочленения, классы рёбер (древесные, обратные, прямые, перекрёстные).BFS, DFS, finding bridges and articulation points, edge classes (tree, back, forward, cross).interview 3.1.3 Связность и топологическая сортировкаConnectivity & topological sortАлгоритм Кана, алгоритмы Тарьяна и Косарайю для поиска компонент сильной связности (SCC).Kahn's algorithm, Tarjan's and Kosaraju's algorithms for finding strongly connected components (SCC).interview

3.2 Кратчайшие Пути и Минимальные Остовы3.2 Shortest paths & minimum spanning trees

3.2.1 Single-Source Shortest PathАлгоритм Дейкстры (с Fibonacci Heap), Беллмана-Форда (детекция отрицательных циклов), SPFA.Dijkstra's algorithm (with a Fibonacci heap), Bellman-Ford (negative-cycle detection), SPFA.interview 3.2.2 All-Pairs Shortest PathАлгоритм Флойда-Уоршелла, алгоритм Джонсона для разреженных графов.Floyd-Warshall, Johnson's algorithm for sparse graphs. 3.2.3 Минимальное остовное дерево (MST)Minimum spanning tree (MST)Алгоритмы Прима, Крускала (с Disjoint Set Union — DSU), Борувки.Prim's, Kruskal's (with disjoint set union — DSU), and Borůvka's algorithms.interview

3.3 Сетевые Потоки, Паросочетания и Графовые Модели3.3 Network flows, matchings & graph models

3.3.1 Максимальный поток и минимальный разрезMax-flow min-cutФорд-Фалкерсон, алгоритм Эдмондса-Карпа, алгоритм Диница, теорема о максимальном потоке и минимальном разрезе.Ford-Fulkerson, Edmonds-Karp, Dinic's algorithm, the max-flow min-cut theorem. 3.3.2 Двудольные графы и паросочетанияBipartite graphs & matchingsАлгоритм Куна, алгоритм Хопкрофта-Карпа, венгерский алгоритм для взвешенных паросочетаний.Kuhn's algorithm, Hopcroft-Karp, the Hungarian algorithm for weighted matchings. 3.3.3 Прикладные графовые моделиApplied graph modelsПоиск кратчайших путей на картах (A*, Contraction Hierarchies), алгоритмы ранжирования (PageRank, HITS).Shortest paths on maps (A*, contraction hierarchies), ranking algorithms (PageRank, HITS).

3.3b Особые Структуры Графа3.3b Special graph structures

новый подраздел — каркасnew subsection — skeleton

3.3b.1 Эйлеровы и гамильтоновы путиEulerian & Hamiltonian pathsКритерий Эйлера (чётность степеней вершин), алгоритм Хирхольцера для построения эйлерова цикла, гамильтонов путь как NP-полная задача и её связь с задачей коммивояжёра (TSP).Euler's criterion (vertex degree parity), Hierholzer's algorithm for constructing an Eulerian circuit, the Hamiltonian path as an NP-complete problem and its connection to the traveling salesman problem (TSP).interview 3.3b.2 Раскраска графовGraph coloringХроматическое число, жадная раскраска и её неоптимальность, раскраска рёбер (теорема Визинга), практическое применение — распределение регистров в компиляторах.The chromatic number, greedy coloring and why it's suboptimal, edge coloring (Vizing's theorem), a practical application — register allocation in compilers. 3.3b.3 ПланарностьPlanarityТеорема Понтрягина-Куратовского (запрещённые подграфы K5 и K3,3), формула Эйлера для планарных графов, алгоритмы проверки планарности за линейное время.The Pontryagin-Kuratowski theorem (forbidden subgraphs K5 and K3,3), Euler's formula for planar graphs, linear-time planarity-testing algorithms.

3.4 Решённые задачи из примеров3.4 Worked problems from the examples

решения на бумаге + C++paper solutions + C++

Каждая карточка — сценарий из "5 примеров из реальной жизни" на страницах выше, доведённый до конкретного входа/выхода: постановка → перевод условия на язык теории графов → разбор на бумаге со схемой → рабочий код на C++ → типичные ошибки.Each card is a scenario from the "5 real-world examples" on the pages above, taken to a concrete input/output: statement → translating it into graph-theory terms → a paper walkthrough with a diagram → working C++ code → common mistakes.

Детект дедлока через wait-for графDeadlock detection via a wait-for graphDFS и back edge — из примера в теме 3.1.2.DFS and back edges — from the example in topic 3.1.2.3.1.2 Цикл зависимостей пакетовPackage dependency cycleАлгоритм Кана — из примера в теме 3.1.3.Kahn's algorithm — from the example in topic 3.1.3.3.1.3 Валютный арбитражCurrency arbitrageБеллман-Форд и отрицательный цикл — из примера в теме 3.2.1.Bellman-Ford and a negative cycle — from the example in topic 3.2.1.3.2.1 Таблица расстояний между городамиCity distance tableФлойд-Уоршелл — из примера в теме 3.2.2.Floyd-Warshall — from the example in topic 3.2.2.3.2.2 Кабельная сеть кампусаCampus cable networkКрускал и DSU — из примера в теме 3.2.3.Kruskal's algorithm and DSU — from the example in topic 3.2.3.3.2.3 Узкое место энергосетиPower-grid bottleneckЭдмондс-Карп и восстановление min-cut — из примера в теме 3.3.1.Edmonds-Karp and recovering the min-cut — from the example in topic 3.3.1.3.3.1 Распределение студентов по группамStudent group matchingАлгоритм Куна и увеличивающие цепи — из примера в теме 3.3.2.Kuhn's algorithm and augmenting paths — from the example in topic 3.3.2.3.3.2

3.5 Примеры, решённые из LeetCode3.5 Worked LeetCode problems

решения на бумаге + C++paper solutions + C++

Задачи с LeetCode, привязанные к темам выше, разобранные в том же формате: постановка → разбор на бумаге → рабочий код на C++ → типичные ошибки. Наполняется поэтапно.LeetCode problems tied to the topics above, worked in the same format: statement → paper walkthrough → working C++ code → common mistakes. Filled in incrementally.

Find the Town JudgeLeetCode 997 — degree-счётчик без явного построения графа, задача по теме 3.1.1.LeetCode 997 — a degree counter with no explicit graph built, a problem on topic 3.1.1.LC 997 — в работе— coming upСледующая задача добавится по мере проработки.The next problem will be added as this section is filled in.

статусstatus

3 исходных теоретических подраздела и 9 пунктов заполнены полным содержанием: терминология с нуля, SVG-диаграммы для каждого ключевого понятия, минимум 5 примеров из реальной жизни на каждой странице. Добавлен подраздел 3.3b «Особые структуры графа» (Эйлеровы/гамильтоновы пути, раскраска, планарность) — каркас, страницы ещё не написаны; эти темы — стандартная часть курса теории графов (CLRS, Седжвик), отсутствовавшая в исходном плане. Практика поверх теории разделена по источнику: 3.4 доводит примеры из теоретических страниц до конкретного входа/выхода (7 задач), 3.5 разбирает задачи с LeetCode тем же способом (1 задача, наполняется поэтапно) — оба раздела решают на бумаге со схемой и на C++. Метка interview отмечает темы, которые встречаются на технических собеседованиях чаще всего.The 3 original theory subsections and 9 items are fully written: terminology from scratch, SVG diagrams for every key concept, at least 5 real-world examples per page. Subsection 3.3b "Special graph structures" was added (Eulerian/Hamiltonian paths, coloring, planarity) — a skeleton, pages not yet written; these topics are a standard part of any graph-theory curriculum (CLRS, Sedgewick) that was missing from the original plan. Practice on top of the theory is split by source: 3.4 takes examples from the theory pages to a concrete input/output (7 problems), 3.5 works LeetCode problems the same way (1 problem, filled in incrementally) — both sections solve on paper with a diagram and in C++. The interview tag marks the topics that come up most often in technical interviews.