1. Граф задан таблицей отношений:

а) постройте этот граф;

б) составьте матрицу смежности;

в) составьте матрицу инцидентности;

с) если в графе висячие вершины, если да укажите их;

д)  есть ли в графе точки сочленения (разделяющие вершины), если да укажите их;

е) постройте дополнительный граф;

ж) сколько компонент связности у этого графа?

з) определите степени вершин графа и их эксцентриситеты;

и) изобразите граф, получаемый из исходного после удаления 2-ой  вершины;

к) изобразите граф, получаемый из исходного после удаления 3-го  ребра;

л) найдите диаметр графа; его радиус, центральные и периферийные вершины;

м) приведите пример простого цикла в этом графе;

н)  обладает ли данный граф эйлеровым циклом, эйлеровой цепью?

о) обладает ли данный граф гамильтоновым циклом, гамильтоновой цепью?

п) найдите хроматическое число данного графа.

р) найдите размерность циклового базиса данного графа.

2. Орграф задан таблицей отношений:

а) постройте этот орграф;

б) составьте матрицу смежности;

в) составьте матрицу инцидентности;

с)  сколько компонент сильной связности у этого графа?;

д) определите полу-степени исхода и захода вершин графа;

е) приведите пример простого цикла в этом графе;

3. Нагруженный орграф задан таблицей отношений и расстояний:

а) постройте этот граф;

б) составьте матрицу длин дуг данного орграфа;

в) Используя алгоритм Форда-Беллмана построить матрицу минимальных путей из v₁ в v_j j=1,2,3,4,5.

8 стр.