Задания по графу

Вот граф

Задания:
1. Постройте список смежности для данного оргафа

2. Определите центр Графа

3. Определите число деревьев в глубинном остовном лесу (перебор вершин производить строго в лексикографическом порядке)

4. Определите число поперечных и число прямых дуг в глубинном остовном лесу (перебор вершин производить строго в лексикографическом порядке)

5. Какова высота дерева, построенного обходом в ширину, начиная с вершины d (перебор вершин производить строго в лексикографическом порядке).

6. Определите, чему будет равно значение P[2] в алгоритме Дейкстры, если источником является вершина d (узел а – 1-ый в нумерации узлов, … узел e – 5-ый)

7. Определите, чему будет равна 5-ая строка массива A (кратчайших расстояний) в алгоритме Флойда после k = 2

8. Чему равна стоимость остовного дерева минимальной стоимости для данного графа (граф рассматривать как неориентированный)

9. Сколько сильно связных компонент в графе?

10. Какая вершина будет добавлена во множество U четвертой по счету в алгоритме Прима при построении остовного дерева минимальной стоимости (перебор вершин производить строго в лексикографическом порядке) (граф рассматривать как неориентированный)

11. Какая дуга будет добавлена в в остовное дерево минимальной стоимости третьей по счету в алгоритме Крускала (перебор вершин производить строго в лексикографическом порядке) (граф рассматривать как неориентированный)

12. Определив обратные дуги в глубинном остовном лесу, постройте граф G2 на основе исходного Графа, удалив найденные обратные дуги. Для графа G2 вычислите матрицу транзитивного замыкания.

13. Рассмотрим граф G2 в качестве сети N2, задав источник и сток изобразите сеть N2(G2, c), где в качестве пропускных способностей дуг положите значение веса соответствующей дуги графа G2.

14. Для сети N2 определите её максимальный поток и найдите все минимальные разрезы.

15. Определите хроматическое число орграфа

Если не сложно, то с объяснением, пожалуйста, хочу понять решение, спасибо!

0