Это пособие предназначено для студентов, изучающих курс дискретной математики и (или) теории графов. С его помощью Вы освоите тему "Правильная раскраска рёбер графа". Прямо из этого пособия Вы можете посчитать своё ИДЗ, даже если у Вас нет на компьютере MATLAB. Если же у Вас есть MATLAB, перейдите на эту страницу: там у Вас есть возможность вмешаться в сценарий (программу) вычислений. Здесь же задача о правильной раскраске рёбер графа решается путём сведения к задаче целочисленного линейного программирования.

Обратите внимание: пакет GLPK, используемый в скрипте данной страницы, позволяет решать задачи только небольшой размерности!

Введём обозначения:

• n=|V| − размер графа (количество вершин);
• m=|E| − мощность графа (количество рёбер);
• p_i − степень вершины v_i: количество инцидентных ей рёбер;
• f_i=p_i(p_i−1)/2 − количество различных пар рёбер, инцидентных вершине v_i;
• e − вектор-столбец длины m; каждый его элемент e_k может принимать целочисленные значения от 1 до m − это номер цвета k-го ребра;
• e₀ = max(e₁, e₂, ..., e_m) − вспомогательная переменная (максимальный номер цвета);
• v − бинарный вектор-столбец длины f₁+f₂+...+f_n; каждый его элемент v_ij соответствует паре рёбер, соединяющейся в i-й вершине, и может принимать значения 0 или 1.

Тогда задача о правильной раскраске рёбер графа может быть сформулирована как задача целочисленного линейного программирования:

Минимизируется (1) максимальный (2) номер цвета ребра (3). При этом цвета любой пары рёбер, инцидентных одной вершине, должны отличаться не менее чем на единицу (4, 5, 6).

Для правильной работы с этой страницей Ваш браузер должен поддерживать сценарии Java Script. Включите их.

Введите исходные данные в находящиеся ниже области ввода. В первой области нужно (точнее, можно) ввести координаты вершин для рисования графа. Они задаются в виде матрицы n×2: в первом столбце − x-е координаты, во втором − y-е. Числа можно задавать целые, с десятичной точкой или в экспоненциальной форме. Числа разделяйте пробелами. Общее количество строк в этой области ввода определяет размер графа n − количество вершин. Эти исходные данные (координаты вершин) не являются обязательными: если их не задать, то граф будет рисоваться в виде правильного n-угольника, а количество вершин будет определяться максимальным номером вершины в следующей области ввода.

Следующая область ввода − обязательная для заполнения. В ней определяется структура графа. Каждое ребро в графе соединяет две вершины. Номера этих вершин задаются в виде матрицы m×2 в этой области ввода. Какую вершину считать первой, а какую второй − не имеет значения. В этих столбцах должны быть натуральные числа от 1 до n включительно. Числа разделяйте пробелами.