Это пособие предназначено для студентов, изучающих курс дискретной математики и (или) теории графов. С его помощью Вы освоите тему "Правильная раскраска рёбер графа". Прямо из этого пособия Вы можете посчитать своё ИДЗ, даже если у Вас нет на компьютере MATLAB. Если же у Вас есть MATLAB, перейдите на эту страницу: там у Вас есть возможность вмешаться в сценарий (программу) вычислений. Здесь же задача о правильной раскраске рёбер графа решается путём сведения к задаче целочисленного линейного программирования.
Обратите внимание: пакет GLPK, используемый в скрипте данной страницы, позволяет решать задачи только небольшой размерности!
Введём обозначения:
- n=|V| − размер графа (количество вершин);
- m=|E| − мощность графа (количество рёбер);
- pi − степень вершины vi: количество инцидентных ей рёбер;
- fi=pi(pi−1)/2 − количество различных пар рёбер, инцидентных вершине vi;
- e − вектор-столбец длины m; каждый его элемент ek может принимать целочисленные значения от 1 до m − это номер цвета k-го ребра;
- e0 = max(e1, e2, ..., em) − вспомогательная переменная (максимальный номер цвета);
- v − бинарный вектор-столбец длины f1+f2+...+fn; каждый его элемент vij соответствует паре рёбер, соединяющейся в i-й вершине, и может принимать значения 0 или 1.
Тогда задача о правильной раскраске рёбер графа может быть сформулирована как задача целочисленного линейного программирования:
Минимизируется (1) максимальный (2) номер цвета ребра (3). При этом цвета любой пары рёбер, инцидентных одной вершине, должны отличаться не менее чем на единицу (4, 5, 6).
Для правильной работы с этой страницей Ваш браузер должен поддерживать сценарии Java Script. Включите их.
Введите исходные данные в находящиеся ниже области ввода. В первой области нужно (точнее, можно) ввести
координаты вершин для рисования графа. Они задаются
в виде матрицы
Следующая область ввода − обязательная для заполнения. В ней определяется структура графа.
Каждое ребро в графе соединяет две вершины. Номера этих вершин задаются в виде матрицы
x (пробел) y |
v1 (пробел) v2 |