Графы пересечений

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

Теорема о графах пересечений. Для любого графа существует такое семейство множеств F, что .

Задачи

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. Граф пересечений семейства дуг окружности называют графом дуг. Какие из

графов предыдущей задачи являются графами дуг?