На эту неделю у нас практика к двум базовым теориям по графам:

• 11.1 Терминология графов — https://olprog.ru/articles/olprog/graphs/basics/terminology/
• 11.2 Представление графов — https://olprog.ru/articles/olprog/graphs/basics/representation/

Это самые первые и самые важные темы в разделе графов. Именно здесь формируется понимание того, что такое вершины и рёбра, как распознавать граф внутри условия, что такое путь, цикл, связность, компоненты связности, дерево, а также как граф удобно хранить в программе.

Без этих основ дальше трудно двигаться к обходам, кратчайшим путям и более сложным алгоритмам, поэтому здесь особенно важно не просто прочитать теорию, а закрепить её на задачах.

Практика к теме:

• Космическая станция — https://judje.olprog.ru/problem/spacehub
• Судья часового квартала — https://judje.olprog.ru/problem/watchdistrictjudge
• Школа магии — https://judje.olprog.ru/problem/magicportals
• Центральный фонарь — https://judje.olprog.ru/problem/lanternhub
• Древние руины — https://judje.olprog.ru/problem/ancientruinsexchange
• Часовщики в мастерской — https://judje.olprog.ru/problem/watchmakersrow
• Сеть музеев и хранилищ артефактов — https://judje.olprog.ru/problem/museumnetwork
• Бездна и кольцевой риф — https://judje.olprog.ru/problem/abysscycle
• Лесная сеть сигналов — https://judje.olprog.ru/problem/forestsignal
• Кольцевые маршруты — https://judje.olprog.ru/problem/cycleroutes

Эта подборка подойдёт тем, кто хочет:

• научиться видеть граф в условии задачи;
• уверенно различать вершины, рёбра, пути, циклы и компоненты связности;
• понять, когда удобно использовать список смежности и как вообще хранить граф в коде;
• подготовить базу для следующих тем по обходам графов.

Во время решения особенно полезно задавать себе такие вопросы:

• что в этой задаче является вершинами;
• что считается ребром;
• граф ориентированный или неориентированный;
• есть ли в нём цикл;
• связный ли граф или нужно думать о нескольких компонентах;
• как удобнее всего записать его в программе.

Рекомендуем идти так: сначала прочитать обе теории, затем решать задачи по порядку — от самых интуитивных к тем, где граф уже чуть менее очевиден. На этом этапе особенно важно научиться правильно переводить текст условия в графовую модель. Очень часто главная сложность задачи не в коде, а в том, чтобы вообще понять, что перед вами граф.

Если какая-то задача кажется непривычной, полезно сначала просто нарисовать несколько маленьких примеров вручную. Это часто сразу проясняет структуру вершин, рёбер и связей между ними.

Удачи в решении!

Ждём ваши результаты, вопросы и впечатления от задач.