Задачи
1.1. Граф задан множеством вершин и множеством ребер
. Нарисуйте этот граф, постройте для него матрицы
смежности и инцидентности, списки смежности.
1.2. Постройте матрицу инцидентности для графа, заданного списками смежности:
1.3. В графе 30 вершин и 80 ребер, каждая вершина имеет степень 5 или 6. Сколько в нем
вершин степени 5?
1.4. В графе каждая вершина имеет степень 3, а число ребер заключено между 16 и 20.
Сколько вершин в этом графе?
1.5. Найдите все абстрактные графы с 4 вершинами.
1.6. Найдите все абстрактные графы с набором степеней а) (2,2,2,3,3,4);
б) (2,2,2,3,3,3).
1.7. Восстановите граф по его
а) порожденным подграфам, полученным удалением одной вершины:
б) остовным подграфам, полученным удалением одного ребра:
1.8. Граф имеет n вершин и m ребер. Сколько у него различных а) остовных;
б) порожденных подграфов?
1.9. 1) Представьте граф как объединение трех графов с множествами вершин
{1,2,3,4}, {1,2,5,6}, {3,4,5,6}.
2) Верно ли, что любой граф с 6 вершинами можно представить как объединение трех
|
|
графов с такими множествами вершин?
3) Верно ли, что любой граф с 6 вершинами можно представить как объединение трех
графов с множествами вершин {1,2,3}, {3,4,5}, {5,6,1}?
1.10. Верно ли, что для любых графов и выполняется равенство
?
1.11. Найдите граф с минимальным числом вершин такой, что оба графа и
связны.
1.12. Найдите граф с минимальным числом вершин такой, что оба графа и
несвязны.
1.13. Изоморфны ли графы 1) и ; 2)и ; 3) и ?
1.14. Найдите граф с минимальным числом вершин , который не является суммой
или соединением меньших графов.
1.15. Граф задан матрицей смежности:
.
Постройте для него матрицу расстояний между вершинами, найдите
эксцентриситеты вершин, диаметр, радиус, центр. Изоморфны ли этот граф и
дополнительный к нему?
1.16. Каково расстояние между вершинами (0,0,..., 0) и (1,1,...,1) в графе ? Сколько
имеется кратчайших путей между этими вершинами?
1.17. Какой наибольший диаметр может быть у графа с вершинами? Сколько имеется
(абстрактных) графов с таким диаметром?
1.18. Найдите все (с точностью до изоморфизма) графы с 5 вершинами диаметра 3.
1.19. Может ли радиус графа в результате добавления одного нового ребра а) увеличиться;
б) уменьшиться; в) остаться прежним?
1.20. Найдите все (с точностью до изоморфизма) графы с 5 вершинами радиуса 1.
1.21. Найдите все (с точностью до изоморфизма) графы с 4 вершинами, имеющие точно
одну центральную вершину.
1.22. Постройте граф пересечений а) граней трехмерного куба; б) ребер графа .
1.23. Сколько ребер в графе пересечений ребер графа ?
1.24. Граф пересечений семейства интервалов на прямой называют графом интервалов.
|
|
Какие из следующих графов являются графами интервалов: , , , , ,
, ?
1.25. Граф пересечений семейства дуг окружности называют графом дуг. Какие из
графов предыдущей задачи являются графами дуг?