Комбинаторика и теория графов

Практические занятия

Комментарии к задачам ИДЗ 3.

  1. Формула Эйлера
  2. В задаче спрашивается, есть ли в графе Эйлеров цикл (эйлеров граф), Эйлеров путь (полуэйлеров), аналогично про гамильтоновы пути и циклы.
  3. Хроматический многочлен с удалением вершин.
  4. Хроматический многочлен с добавлением ребер до полного графа.
  5. Код Прюфера
  6. Вспомните алгоритм, в котором мы сначала делали поиск в глубину в графе, а потом поиск в глубину по графу с обратными ребрами, в порядке убывания обратной нумерации. Граф конденсации — это граф ребер между компонентами сильной связности.
  7. Максимальный поток
  8. Максимальное паросочетание сведением к задаче о максимальном потоке.
  9. Здесь предполагается, что нужно выполнить алгоритм Флойда из предыдущего ИДЗ, только смысл цифр в матрице другой. 0 означает, что ребра нет, т.е. в алгоритме Флойда в таблице ставится бесконечность, кроме того, не нужно считать точное расстояние между вершинами, т.е. вместо расстояний 1, 2, 3 в таблице можно писать всегда 1. Фактически, это алгоритм Флойда, но проверка заменяется на if a[i,k] + a[k,j] > 0 then a[i,j] = 1.
  10. Напишите в каждой вершине дерева расстояние до самой удаленной вершины. Радиус это минимум из написанных чисел, диаметр — максимум. Центр — это вершины, в которых записан радиус.
  11. Эта задача аналогична предыдущей, но вычислять расстояние до самой удалённой вершины намного сложнее. Ожидается, что для этого вы составите таблицу расстояний между всеми парами вершин, такая таблица потребует от вас достаточно много времени. Не пользуйтесь для нее алгоритмом Флойда, это займет еще больше времени, попробуйте посчитать расстояния вручную.