Теория графов

Включено в курс

Чему вы научитесь

• Определять изоморфные графы
• Работать со смежными и разомкнутыми графами
• Понимать эйлеровы схемы и гамильтонов цикл

Описание

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

Перед этим курсом рекомендуем пройти курс Функции.

Программа курса

• 1

  Введение

  Познакомиться с курсом

  теория
• 2

  Типы графов

  Разобрать типы графов с примерами

  теория
• 3

  Оптимизация маршрутов

  Рассматриваем, как работает оптимизация маршрутов

  теория
• 4

  Нотации

  Изучаем нотации к теории графов

  теория
• 5

  Подграфы

  Изучаем подграфы, клики и другие базовые понятия

  теория
• 6

  Связанность графов

  Изучаем связанные и разомкнутые графы, а также их компоненты

  теория
• 7

  Изоморфизм

  Рассмотрим изоморфные графы и доказательство изоморфности

  теория
• 8

  Двудольные графы

  Рассмотрим еще один вид графов и его доказательство

  теория
• 9

  Деревья

  Изучаем древовидные графы и индукцию

  теория
• 10

  Остовные деревья

  Знакомимся с древовидными остовными графами и деревьями разветвления

  теория
• 11

  Взвешенный граф

  Изучаем взвешенные графы и алгоритм Крусала

  теория
• 12

  Алгоритм Дейкстры

  Учимся находить кратчайший путь на графе

  теория
• 13

  Эйлеровы схемы

  Изучаем решение проблемы мостов Кенинсберга

  теория
• 14

  Гамильтонов цикл

  Познакомимся с еще одним способом работы с циклом

  теория
• 15

  Доказательство гамильтонова цикла

  Продолжаем изучать циклы с условием Дирака

  теория
• 16

  NP-полнота

  Знакомимся с NP-полнотой и связанными нерешенными проблемами математики

  теория
• 17

  Раскрашивание графа

  Обсуждаем принципы разметки вершин

  теория
• 18

  Диграфы

  Изучаем и доказываем теоремы о диграфах

  теория
• 19

  Связанность

  Рассмотрим графы с разными степенями связанности

  теория
• 20

  Теорема Менгера

  Учимся прокладывать путь между вершинами

  теория
• 21

  Поточная сеть

  Объединяем графы и практические задачи

  теория
• 22

  Самостоятельная работа

  Дополнительные задания, которые позволяют закрепить полученную теорию
• 23

  Дополнительные материалы

  Статьи и видео, подобранные командой Хекслета. Помогут глубже погрузиться в тему курса

Формат обучения