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

Источник Теория графов. Учебное пособие

Ряд задач на графах.

1. «Связность». Установление форм записи цепей, установление видов цепей, отыскание всех цепей, связывающих две заданные вершины, определение числа таких цепей. Удобно использовать матрицу инцидентности графа.

2. Разбиение графа на компоненты связности. Кроме матриц инцидентности при решении этой задачи можно использовать матрицы смежности. В частности, путем решения «задачи транзитивного замыкания графа».

3. Определение устойчивого относительно связности графа блока. Определение критических относительно связности вершин графа (точек сочленения). Установление критических ребер или дуг (мостов, разрезов). Построение графа блоков.

4. Определение расстояния между двумя вершинами графа, построение матрицы расстояний графа.

5. Определение инвариантов графа, являющихся инвариантами матрицы смежности графа. Формулировка необходимых условий изоморфизма графа, установление верхнего предела необходимых переборов при решении задачи об изоморфизме графов.

6. Шестой задачей является выделение в графе цепей специального вида (эйлеров цикл, гамильтонов цикл). Разбиение множества ребер графа на замкнутые и открытые цепи.

7. Разбиение множества всех вершин на подмножества несмежных друг с другом вершин (вершинная раскраска графа). Нахождение минимального числа подмножеств разбиения (хроматическое число). Раскраска карты.

8. Разбиение множества всех ребер на подмножества несмежных друг с другом ребер (реберная раскраска графа, паросочетания).

9. Выделение максимального подмножества вершин смежных друг с другом. Выделение максимального полного подграфа («клики»).

10. Покрытия — подмножества вершин (ребер) инцидентных всем ребрам (вершинам). Экстремальные задачи на покрытия.

11. Геометрические графы. Планарные графы и укладка графов.

12. Визуализация графов.