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

2) Для данного набора слов визуализировать граф, ребра которого соединяют слова на расстоянии не больше динамически заданного k. В качестве функции расстояния между словами взять редакторское расстояние Левенштейна EditDistance. Вершины пометить словами.

3) На плоскости Лобачевского в модели верхней полуплоскости реализовать поиск аналога ЕМОД – минимального остовного дерева во взвешенном полном графе, весовая функция которого задается расстоянием в смысле Лобачевского. Напомним, что расстояние в этой модели может быть вычислено по формуле

ρ (z, w) = ln((|z-(OverBar[w])|+|z-w|)/(|z-(OverBar[w])|-|z-w|))

Предусмотреть возможность добавления-удаления граничных точек-локаторов.

4) На плоскости Лобачевского в модели Пуанкаре в круге реализовать поиск аналога ЕМОД – минимального остовного дерева во взвешенном полном графе, весовая функция которого задается расстоянием в смысле Лобачевского. Напомним, что расстояние в этой модели может быть вычислено по формуле

ρ (z, w) = ln((|1-z(OverBar[w])|+|z-w|)/(|1-z(OverBar[w])|-|z-w|))

Предусмотреть возможность добавления-удаления граничных точек-локаторов.

5) Напромним, что гамильтоновым циклом в графе называется цикл, проходящий через все вершины графа ровно по одному разу. Множества вершин и ребер каждого многогранника, очевидно, задают граф. Используя встроенную функцию FindHamiltonianCycle или HamiltonianCycle, выяснить, какие из пяти графов платоновых тел содержат гамильтоновы циклы. Визуализировать найденные циклы на трехмерных реализациях графов-многогранников. (Графы многогранников можно найти в базах  FiniteGraphs или PolyhedronData.)

6) Графом Кэли группы G для системы ее образующих {(Subscript[g, 1]),... , (Subscript[g, k])} называется ориентировнный  граф, множество вершин которого совпадает с G, и ребро с меткой (Subscript[g, i]) идет из вершины x в вершину y, если и только если x (Subscript[g, i])=y. Обычно при визуализации, ребра, соответствующие разным образующим, изображают разными цветами. Визуализировать граф Кэли для прямого произведения циклических групп (Subscript[Z, p])×(Subscript[Z, q]) с образующими (0,1) и (1,0). Предусмотреть возможность выбора разных p и q.

7) Два графа называются изоморфными, если существует такая биекция f, отождествляющая их множества вершин, что две вершины первого графа соединены ребром, если и только если соединены ребром их f-образы. Два графа с одинаковым количеством вершин изоморфны, если и только если их матрицы смежности сопряжены с помощью некоторой перестановочной матрицы (т.е. графы совпадают после перенумерации вершин). Напишите программу проверки изоморфности двух графов. Визуализируйте все неизоморфные графы с ({{n, ≤ 5}}) вершинами.

8) Каждый граф можно нарисовать без самопересечений в трехмерном пространстве, расположив вершины графа равномерно на некоторой прямой, а каждое ребро – подходящей кривой, лежащей в своей двумерной плоскости, проходящей через эту прямую. Напишите програму, визуализирующую случайный граф таким образом. Предусмотрите возможность менять количество вершин, вероятность появления ребер, а также возможность переупорядочивать вершины на прямой.

9) Каждой триангуляции диагоналями (т.е. разбиению на треугольники попарно не пересекающимися диагоналями) выпуклого многоугольника соответствует двойственное дерево, а именно, граф, множество вершин которого – это множество треугольников, причем две вершины соединены, если и только если треугольники имеют общую сторону. Степени вершин полученного дерева равны 1 или 3. Оказывается, каждому такому дереву с n вершинами степени 1 соответствует триангуляция диагоналями выпуклого n-угольника.  Написать программу, визуализирующую эту связь, и перечисляющую всевозможные триангуляции и соответствующие деревья с заданным числом вершин степени 1.

10) Построить граф делимости натуральных чисел, взяв в качестве множества вершин натуральные числа от 2 до N и соединив вершину n с вершиной  k ориентировным ребром, если и толко если n делит k. Выделить цветом простые числа. Является ли этот граф связным? Если нет – раскрасить связные компоненты. Есть ли в этом графе циклы? Предусмотреть возможность выбора N.

11) Для случайной перестановки  π множества из n элементов визуализировать ее разложение на независимые циклы, построив ориентированны граф с множеством вершин {1,..., n} , и множеством ребер (k, π(k)). Предусмотреть возможности изменять n, менять π, и возводить π в степень.

12) Каждое дерево может быть задано так называемым кодом Прюфера, который получается так.  Пусть дано дерво T с множеством вершин V ={1,... , n}. Листом дерева называется любая его вершина степени 1. Легко показать, что каждое дерево с n≥2 вершинами имеет не менее двух листьев. Чтобы записать код Прюфера дерева T, выберем его лист с наименьшим номером и выпишем номер единственной соседней с ним вершины, не являющейся листом. Выкинем выбранный лист и повторим процедуру до тех пор, пока дерево не превратится в ребро (теперь выбор не возможен). В результате получим упорядоченный набор вида {(Subscript[p, 1]), ..., (Subscript[p, n-2])}, где (Subscript[p, i]) – натуральные числа, не превосходящие n.  В частности, код дерева с двумя вершинами – это пустой список. Напишите программу, визуализирующую пошаговое построение кода Прюфера по случайному дереву с динамически заданным количесвтом вершин. Можно использовать функцию CodeToLabeledTree и обратную к ней.

13) На плоскости с так называемым манхеттанским расстоянием реализовать поиск аналога ЕМОД – минимального остовного дерева во взвешенном полном графе, весовая функция которого задается манхеттанским расстоянием, которое, напомним, вычисляется по формуле

ρ (((Subscript[x, 1]),(Subscript[y, 1])),( (Subscript[x, 2]),(Subscript[y, 2]))) = |(Subscript[x, 1])-(Subscript[x, 2])|+|(Subscript[y, 1])-(Subscript[y, 2])|.

Предусмотреть возможность добавления-удаления граничных точек-локаторов.

14) Дополнением  графа G=(V,E) назвается граф G'=(V,E'), множество ребер которого – это дополнение к множеству ребер исходного графа по отношению к семейству всех двухэлементных подмножеств множесва V. Граф называется самодополнительным, если он изоморфен своему дополнению. Написать программу, визуализирующую случайный граф и его дополнение. Построить с помошью нее пример самодополнительного графа, организовав перебор графов с заданным количеством вершин.

15) Связный граф, содержащий в точности один цикл, называется 1-деревом. Напишите программу отыскания в связном взвешенном графе остовного 1-дерева наименьшего веса. Исходный граф выбирайте случайным образом. Предусмотрите возможность динамического изменения весов ребер посредством ползунков.

16) Граф называется эйлеровым, если в нем существует циклический маршрут, проходящий через каждое ребро  графа, причем ровно один раз. Такой цикл называется эйлеровым.  Эйлеров граф можно получить из случайного связного графа добавлением одной вершины, смежной в точности со всеми вершинами исходного графа нечетной степени. Реализовать алгоритм построение такого графа. Найти эйлеров цикл (EulerianCycle), перенумеровать ребра в соответствие с движением по нему и отобразить эти номера, а также визуализировать обход графа по эйлерову циклу посредством изменения цвета ребер.

17) Для шахматной доски размера m × n визуализировать (где возможно) обход всех ее клеток шахматным конем. Использовать понятие гамильтонова цикла в графе и соответствующую функцию  FindHamiltonianCycle или HamiltonianCycle.