Банк задач по математике

Задача 2.3.1

Грубо говоря, графы изоморфны, если они одинаковы (при этом их изображения на плоскости могут быть разными). Формально, графы $G_{1}$ и $G_{2}$ называются изоморфными, если существует взаимно однозначное отображение $f: V(G_{1}) \to V(G_{2})$ , удовлетворяющее условию: вершины $A, B \in V(G_{1})$ соединены ребром в том и только в том случае, если вершины $f(A), f(B) \in V(G_{2})$ соединены ребром.

Какие из графов на рис. 3 изоморфны?

Рис. 3. Какие из графов на рисунке изоморфны?

?

Задача 2.3.2

Для произвольных $k,l,m,n \in \mathbb {N}$ найдите количество

?

(1)

клик размера $k$ в графе $K_{n}$ ,

(2)

клик размера $k$ в графе $K_{m,n}$ ,

(3)

независимых множеств размера $k$ в графе $K_{n}$ ,

(4)

независимых множеств размера $k$ в графе $K_{m,n}$ ,

(5)

подграфов в $K_{n}$ , изоморфных $K_{k,l}$ ,

(6)

подграфов в $K_{m,n}$ , изоморфных $K_{k,l}$ .

Будьте внимательны: эти задачи простые, но почти все требуют разбора случаев.

Задача 2.3.3

(1)(2)(3)

Перечислите все попарно неизоморфные

?

(1)

графы с четырьмя вершинами,

(2)

связные графы с пятью вершинами и пятью рёбрами,

(3)

несвязные графы с пятью вершинами.

Задача 2.3.4

Сколько существует попарно неизоморфных графов, имеющих 8 вершин и 25 рёбер?

?

Задача 2.3.5

Количество классов изоморфизма деревьев с $n$ вершинами (т.е. количество различных деревьев с $n$ незанумерованными вершинами) меньше $4^{n}$ .

?

Графы с точностью до изоморфизма