Введение в математику. Практикум

Графы и их использование

Показывать лекцию целиком

Задачи

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

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

    $$G =\left \| \begin{array}{ccc}1 0 1 \\111 \\110 \end{array} \right \|$$

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

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

    $$G =\left \| \begin{array}{ccc}1 0 1 \\010 \\110 \end{array} \right \|$$

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

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

    $$G =\left \| \begin{array}{cccccc}110010\\111100\\011110\\011110\\101111\\000011\end{array} \right \|$$

    Указание: неориентированный граф "не имеет стрелок".

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

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

  • Геометрические графы и их приложения.
  • Алгебраические графы и их приложения.
  • Кто впервые ввел и изучал графы?
  • Сравнительный анализ форм представления графов.
  • Наиболее экономические структуры представления графов.
  • Расчеты на графовых структурах.
  • Генеалогическое дерево, его построение для своего рода.
  • Сетевые графики и их история. Приложения сетевых графиков.
  • Метод ПЕРТ (PERT).
  • Когнитивные схемы (карты).
    • Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^