5GL

Задачи по теории графов

Задача 1.

Постройте граф отношения "x+y =<7" на множестве М={1,2,3,4,5,6}. Определите его свойства.

Посмотреть решение (pdf, 134 Кб)

Задача 2.

Найти кратчайшие пути в орграфе от первой вершины ко всем остальным, используя алгоритм Дейкстры. Постройте дерево кратчайших путей.

Посмотреть решение (pdf, 196 Кб)

Задача 3.

Найти максимальный поток и минимальный разрез в транспортной сети, используя алгоритм Форда-Фалкерсона (алгоритм расстановки пометок) Построить граф приращений. Проверить выполнение условия максимальности построенного полного потока. Источник - вершина 1, сток - вершина 8.

Посмотреть решение (pdf, 282 Кб)

Задача 4.

Постройте остовное дерево минимального веса, используя алгоритмы Прима и Краскала. С помощью матрицы Кирхгоффа найдите количество (неизоморфных) остовных деревьев, используя пакеты компьютерной математики (например, MathCAD, Mathematica, MatLab).

Посмотреть решение (pdf, 173 Кб)

  5GL

Знаете ли Вы, что "гравитационное линзирование" якобы наблюдаемое вблизи далеких галактик (но не в масштабе звезд, где оно должно быть по формулам ОТО!), на самом деле является термическим линзированием, связанным с изменениями плотности эфира от нагрева мириадами звезд. Подробнее читайте в FAQ по эфирной физике.

Bourabai Research Institution home page

Bourabai Research - Технологии XXI века Bourabai Research Institution