Математика EN

Тренажёры · Глава 46

Задачи о графах

Степени вершин и лемма о рукопожатиях, можно ли обойти все рёбра по разу, кратчайший путь по алгоритму Дейкстры и формула Эйлера V − E + F = 2.

Как решать

Граф — точки (вершины) и линии между ними (рёбра). Знакомства, дороги, мосты — всё это графы. Многое о графе говорят степени вершин — число рёбер у каждой: их сумма вдвое больше числа рёбер, а нечётных степеней всегда чётное количество.

По шагам

  1. Степени: сумма степеней равна $2E$, поэтому должна быть чётной. Если нечётна — такого графа нет.
  2. Обход всех рёбер по разу (эйлеров путь): граф связен и нечётных вершин $0$ (можно вернуться в начало) или $2$ (путь от одной нечётной до другой). Иначе нельзя.
  3. Кратчайший путь (Дейкстра): отмечайте вершины по одной — каждый раз ближайшую к старту из неотмеченных — и обновляйте расстояния до её соседей.
  4. Плоский связный граф: $V - E + F = 2$, где грани считаются вместе с внешней.
Число вершин. Число рёбер. Число граней — частей плоскости, включая внешнюю. Пример: $14$ вершин и $29$ рёбер: $F = 2 - 14 + 29 = 17$ граней.

Где ошибаются

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

Пример

Математика

Главы курса

Вступление

  1. 0 Что такое математика

I Числа

  1. 1 Счёт
  2. 2 Ноль и минус
  3. 3 Простые числа
  4. 4 Делимость
  5. 5 Дроби
  6. 6 Корень из двух

II Алгебра

  1. 7 Буквы
  2. 8 Уравнения
  3. 9 Функции и графики
  4. 10 Квадратные уравнения
  5. 11 Системы и неравенства
  6. 12 Степени и логарифмы
  7. 13 Последовательности
  8. 14 Многочлены
  9. 15 Комплексные числа

III Геометрия

  1. 16 Начала Евклида
  2. 17 Треугольник
  3. 18 Теорема Пифагора
  4. 19 Окружность и π
  5. 20 Площадь и объём
  6. 21 Тригонометрия
  7. 22 Векторы
  8. 23 Симметрия
  9. 24 Конические сечения

IV Анализ

  1. 25 Пределы
  2. 26 Производная
  3. 27 Экстремумы
  4. 28 Интеграл
  5. 29 Число e
  6. 30 Ряды
  7. 31 Дифференциальные уравнения
  8. 32 Многие переменные
  9. 33 Ряды Фурье
  10. 34 Комплексный анализ

V Линейная алгебра

  1. 35 Матрицы
  2. 36 Метод Гаусса
  3. 37 Векторные пространства
  4. 38 Собственные векторы
  5. 39 МНК и SVD

VI Структуры

  1. 40 Группы
  2. 41 Остатки и шифры
  3. 42 Кольца и поля
  4. 43 Теория Галуа
  5. 44 Дзета и кривые

VII Случай и данные

  1. 45 Комбинаторика
  2. 46 Графы
  3. 47 Вероятность
  4. 48 Случайные величины
  5. 49 Статистика
  6. 50 Марков и информация

VIII Основания

  1. 51 Логика и множества
  2. 52 Бесконечности
  3. 53 Строгий анализ
  4. 54 Мера и интеграл
  5. 55 Функциональный анализ
  6. 56 Гёдель и Тьюринг

IX Горизонты

  1. 57 Топология
  2. 58 Неевклидовы геометрии
  3. 59 Хаос и фракталы
  4. 60 Передний край