Упражнения для самостоятельного решения

Сколько всего: а) связных графов на множестве из 3 вершин; б) неизоморфных графов на множестве из 4 вершин? Ответ: а) 2; б) 11.
Сколько всего неизоморфных деревьев с 6 вершинами? Ответ: 6.
Сколько всего неизоморфных графов, имеющих 10 вершин, а количество рёбер равно: а) 45; б) 44; в) 43? Ответ: а) 1; б) 2; в) 2.
Сколько компонент связности может иметь граф, у которого 12 вершин и 40 рёбер? Ответ: 1,2,3.
Построить матрицу смежности и матрицу инцидентности графов, изображённых на рисунке.

Ответ: а)

Изобразить граф, имеющий следующую матрицу смежности: а) б)

Ответ:

Изобразить граф, имеющий следующую матрицу инцидентности: а) б)

Ответ:

Является ли связным граф со следующей матрицей смежности: Ответ: нет.
Существует ли граф со следующим набором степеней вершин: а) 1,1,1,2,2,3,3; б) 1,1,2,2,2,3,3,4? Ответ: а) нет; б) да.
Пусть – граф. Противоположным графом назовём граф с тем же множеством вершин, что и у причём Доказать, что если граф несвязный, то граф связный.
Доказать, что граф с вершинами, имеющий более рёбер, является связным.
Построить двоичный код дерева (начало обхода помечено крестиком и стрелкой):

Ответ: (0010100101001111).

Построить код Прюфера дерева

Ответ: [2343311].

Построить дерево по его двоичному коду: (0010010010111011).

Ответ:

Построить дерево по его коду Прюфера: [2442778].

Ответ:

Построить базис пространства циклов графа, изображённого на рисунке.

Ответ: (ответ неоднозначен).

В графе рассмотрим цикл Дополнить его до базиса пространства циклов. Ответ: например, так:
Чему равна размерность пространства циклов графа Сколько в всего обобщённых циклов? Ответ: 6; 64.
Сколько компонент связности имеет лес, у которого 25 вершин и 11 рёбер? Ответ: 14.
Сколько граней имеет планарный граф, у которого 12 вершин и 30 рёбер? Ответ: 20.
Являются ли планарными графы: а) б) Ответ: а) да; б) нет.
Граф представляет собой трёхмерный куб, в котором проведена диагональ. Планарен ли этот граф? Ответ: нет.
Сколько рёбер следует удалить из графа чтобы получилось дерево? Ответ: 25.
Чему равно наименьшее количество рёбер, удаление которых из графа делает граф несвязным? Ответ: 5.
Чему равно наименьшее число обладающее свойством: удаление из графа любых рёбер делает граф несвязным? Ответ: 26.
Связный планарный граф без петель, висячих вершин и кратных рёбер имеет 6 вершин. Сколько рёбер может иметь этот граф? Ответ:
Связный планарный граф без петель, висячих вершин и кратных рёбер имеет 5 вершин. Сколько граней может быть в его плоской укладке? Ответ:
Связный планарный граф без петель и висячих вершин имеет 19 рёбер. Сколько граней может быть в его плоской укладке? Ответ:
Найти хроматическое число графа, изображённого на рисунке