Задачи

1. Нарисуйте неориентированный граф, выпишите таблицу инциденций. Найдите путь на графе. Указание: взять, например, путь из первой вершины в последнюю.
2. Нарисуйте ориентированный граф и выпишите таблицу смежности. Найдите путь на графе. Указание: взять, например, путь из первой вершины в последнюю.
3. Нарисуйте некоторый взвешенный граф и выпишите его таблицу инциденций, таблицу смежности. Найдите некоторый путь на графе. Посчитайте сумму весов на ребрах пути. Указание: взять, например, путь из первой вершины в последнюю.

4. Постройте ориентированный граф по задаваемой его таблице смежности:

   \[ G =\left \| \begin{array}{ccc}1 &0 &1 \\1&1&1 \\1&1&0 \end{array} \right \| \]

   Указание: граф имеет три вершины.

5. Постройте взвешенный неориентированный орграф, задав веса и по таблице инциденций:

   \[ G =\left \| \begin{array}{ccc}1 &0 &1 \\0&1&0 \\1&1&0 \end{array} \right \| \]

   Указание: граф имеет три вершины.

6. Постройте неориентированный граф по задаваемой его таблице смежности:

   \[ G =\left \| \begin{array}{cccccc}1&1&0&0&1&0\\1&1&1&1&0&0\\0&1&1&1&1&0\\0&1&1&1&1&0\\1&0&1&1&1&1\\0&0&0&0&1&1\end{array} \right \| \]

   Указание: неориентированный граф "не имеет стрелок".
7. Оценить количество памяти и действий, необходимых для хранения и анализа графов в задачах 4-6. Указание: под анализом понимается поиск путей.
8. Постройте сетевой график поездки студента в свой вуз несколькими маршрутами. Указание: определить промежуточные пункты, длительность поездок от пункта к пункту.
9. Постройте сетевой график изучения студентами предмета учебной программы курса. Указание: определить связи тем (последовательность их изучения) и необходимое время изучения каждой темы.
10. Составьте сетевой график переездов на поездах из города A в город B с помощью каких-то промежуточных городов (станций пересадок). Указание: взять не более 5 - 6 промежуточных пересадок.

Темы научных исследований и рефератов (Интернет-листов)

1. Геометрические графы и их приложения.
2. Алгебраические графы и их приложения.
3. Кто впервые ввел и изучал графы?
4. Сравнительный анализ форм представления графов.
5. Наиболее экономические структуры представления графов.
6. Расчеты на графовых структурах.
7. Генеалогическое дерево, его построение для своего рода.
8. Сетевые графики и их история. Приложения сетевых графиков.
9. Метод ПЕРТ (PERT).
10. Когнитивные схемы (карты).