XV Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Правильная раскраска графа - верное решение задачи

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Первушин В.И. 1

---

1МБОУ "Средняя общеобразовательная школа №125 с углублённым изучением математики"

Первушина Н.А. 1

---

1МБОУ "Средняя общеобразовательная школа №125 с углублённым изучением математики"

Работа в формате PDF

1.1 MB

Автор работы награжден дипломом победителя II степени

Диплом школьникаСвидетельство руководителя

ВЕДЕНИЕ

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

Родоначальником теории графов считается Леонард Эйлер. В 1736 году он предложил решение задачи о кёнигсбергских мостах, ставшей одной из классических задач теории графов. Не менее известной стала задача «о четырех красках»,предложенная Френсисом Гутри в 1852 году. В настоящее время графы применяются практически во всех науках: это различные модели в виде деревьев (иерархий), сетевые модели и др.

В современном мире задачи планирования производства, распределения потоков товаров, составления учебных расписаний и транспорта с целью минимизации расходов или времени являются актуальными. Поэтому и методы решения этих задач требуют изучения и правильного применения, в связи с чем являются актуальными. Среди способов решения перечисленных задач много алгоритмов с использованием раскраски графов.

Гипотеза исследования: правильная раскраска графа приводит к верному решению соответствующей задачи.

Цельпроекта: изучение основных задач и алгоритмов раскраски графов, разработка программы для правильной раскраски.

Задачи исследования:

1) изучить математическую модель граф и способы его описания;

познакомиться с задачами раскраски графа и основными понятиями;

изучить основные типы алгоритмов раскраски и выбрать алгоритм для решения задачи проекта;

выбрать среду программирования;

разработать схему и написать программу раскраски вершин графа;

провести тестирование работы программы, сделать выводы, подтвердить или опровергнуть гипотезу исследования.

Объект исследования – задачи раскраски графов.

Предмет исследования: алгоритмы решения задач раскраски и их практическая реализация.

Методы исследования:изучение литературы и Интернет-ресурсов, извлечение знаний, систематизация информации и анализ.

Результаты проекта будут интересны и полезны людям, планирующим решать задачи составления расписаний занятий, оптимизации компьютерных сетей или объёмов памяти и др. Практическая значимость настоящей работы в том, что разобраны практические примеры задач на раскраску графа и создана программа для персональной электронно-вычислительной машины (ПЭВМ), которую можно применять для решения подобных задач. Срок работы над проектом – 3 месяца.

Продукт проекта: программа для ПЭВМ для решения задачи раскраски графа.

ГЛАВА 1 Теоретическое обоснование исследования

Граф и способы его описания

1.1.1 Понятия граф и плоский граф

Граф – это плоская фигура, состоящая из вершин (точек плоскости) и рёбер (линий), соединяющих некоторые пары вершин.

Граф, изображённый на плоскости, называется плоским, если его рёбра не пересекаются в точках, отличных от вершин графа [1].

Множество вершин графа обозначают буквой V, а сами вершины обычно нумеруют римскими числами: V = {I, II, III, IV, V, …}. Множество рёбер графа обозначают буквой E, а сами ребра обычно нумеруют арабскими числами: E = {1, 2, 3, 4, 5, …}. Можно также использовать буквы и цифры.

На рисунке А.1 Приложения А приведён пример нумерации вершин и рёбер плоского графа. Далее рассматриваются графы, ребра которых не имеют направления, т.е. неориентированные графы. Если плоскость разрезать по рёбрам плоского графа, то она распадётся на связные части, которые называют гранями [1]. На рисунке А.2 Приложения А приведён плоский граф с пятью гранями.

Способы описания графов

Матрица смежности графа – это квадратная матрица (таблица) строкам и столбцам которой соответствуют вершины графа. Если две вершины соединяются, то в матрице ставится 1, если не соединяются – 0. Матрица смежности симметричная относительно главной диагонали, т.к. соединения вершин указываются дважды, например, I – II и II – I. В таблице А.1 приведена матрица смежности графа рисунка А.1 Приложения А.

Список рёбер графа – это таблица из двух строк, в первой строке указываются ребра, а во второй – вершины, которые это ребро соединяет. В таблице А.2 приведен список рёбер графа рисунка А.1 Приложения А.

Матрица инцидентности графа – это прямоугольная матрица (таблица) строкам которой соответствуют ребра графа, а столбцам – вершины. Если ребро соединяет вершины, то ставятся 1 около соответствующих вершин. Если в графе есть петля, то напротив соответствующей вершины ставят 2. Если соединений нет, то ставится 0. В таблице А.3 приведена матрица инцидентности графа рисунка А.1 Приложения А.

1.2 Некоторые задачи и алгоритмы раскраски графа

1.2.1 Задача о раскраске карты

Требуется раскрасить каждую страну на карте мира в какой-либо цвет так, чтобы две любые страны, имеющие границу, были раскрашены в разные цвета. Количество красок должно быть минимальным [1]. Граница между странами – это ребро графа. В этой задаче страны – это вершины графа, эти страны соединяются ребром, если граничат. Требуется раскрасить этот граф так, чтобы две соседние вершины не получили одинакового цвета.

Для примера, выполним раскраску политической карты части Европы (см. рисунок Б.1 Приложение Б). Пронумеруем страны как вершины графа: I – Германия, II – Польша, III – Беларусь, IV – Украина, V – Чехия, VI – Словакия, VII – Австрия, VIII – Венгрия, IX – Швейцария, X – Словения, XI – Хорватия, XII – Румыния, XIII – Молдавия. На рисунке Б.2 Приложения Б по условию задачи построен плоский граф. Две соседние страны (вершины) соединены ребром, если соответствующие страны имеют границу ненулевой длины.

Начнём раскрашивать с вершины II. Пусть у неё будет первый цвет. Тогда соседние с ней I и V вершины раскрасим во второй и третий цвета. Соответственно, VI вершина получает второй цвет и т.д. Трёх цветов недостаточно, т.к. вершина VIII имеет соединение с вершинами уже окрашенными в три цвета. Необходим четвёртый цвет. Минимальное количество цветов для раскраски графа – 4.

На рисунке Б.3 Приложения Б приведена карта после раскраски. Действительно, две соседние страны окрашены в разные цвета. Задача решена.

1.2.2 Задача об экономии памяти

Необходимо написать программу для вычисления функции нескольких переменных . Вычисление этой функции разбито на ряд блоков, имеющих свои входные и выходные переменные. Пусть значение переменной занимает одну ячейку памяти. Требуется определить минимальное число ячеек, необходимое для хранения переменных [2]?

Схема вычисления функции и «время жизни» каждой переменной приведены на рисунке В.1 Приложения В.

Построим граф по условию задачи. Вершины графа – это переменные: V = {a, b, c, d, e, f, g, h}. Соединим вершины ребром, если времена их жизни пересекаются. Полученный граф приведён на рисунке В.2 Приложения В. Раскрасим его вершины минимальным количеством красок. Начнем раскрашивать с вершины a. Результат раскраски приведён на рисунке В.2 Приложения В.

Каждые две соседние вершины окрашены в разные цвета. Цветов для раскраски понадобилось 4, поэтому необходимо 4 ячейки памяти. Задача решена.

1.2.3 Задача о составлении расписания

В учебном центре необходимо провести несколько занятий за кратчайшее время. Условия: 1) длительность занятий одинакова, 2) занятия в одной и той же группе по разным предметам не могут проводиться одновременно или один и тот же преподаватель в разных группах не может проводить занятия. Пусть группы – это 9А, 9Б и 9В классы школы. Предметы: физика, русский язык, физкультура, химия. Запишем условие в таблицу Г.1 Приложения Г, где каждое занятие в конкретном классе, по конкретному предмету обозначим отдельным номером. Это будут вершины графа. Также в таблице укажем занятия, которые нельзя проводить одновременно.

Граф, соответствующий задаче, приведён на рисунке Г.1 Приложения Г

Каждые две соседние вершины окрашены в разные цвета. Цветов для раскраски понадобилось 4, поэтому необходимо 4 урока, чтобы провести все занятия. Задача решена. Расписание приведено в таблице Г.2 Приложения Г.

1.2.4 Раскраска вершин, ребер и граней. Правильная раскраска

Раскраска вершин – главная задача раскраски графов, все остальные задачи в этой области могут быть сведены к ней [1]. В настоящей исследовательской работе будем рассматривать только раскраску вершин.

Раскраска в теории графов – это частный случай разметки графа.

Задача раскраски: требуется раскрасить вершины графа в минимальное количество цветов так, чтобы любые две смежные вершины не получили одинакового цвета.

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

В задачах п. 1.2.1 – 1.2.3 выполнена правильная раскраска минимальным количеством цветов.

1.2.5 Хроматическое число графа. Проблема четырёх красок

Хроматическое число графа – минимальное число красок, которое требуется для правильной раскраски графа. Во всех рассмотренных задачах =4.

В конце XIX в, пытаясь раскрасить карту округов Англии, Френсис Гутри сформулировал проблему четырёх красок, отметив, что четырёх цветов достаточно, чтобы раскрасить карту так, чтобы любые две смежные области имели разные цвета. Альфред Кемпе в 1880 году опубликовал доказательство, и в течение 10 лет проблема четырёх красок считалась решённой.

Окончательное доказательство было предъявлено в 1977 году Кеннетом Аппелем и Вольфгангом Хакеном на основе компьютерного перебора различных плоских графов и выполнения их раскраски. Доказательство теоремы четырёх красок – одно из первых доказательств с использованием компьютера [1].

1.2.6 Алгоритмы раскраски графа

Среди известных алгоритмов раскраски графов можно выделить следующие [1]:

1 Точный алгоритм

Такие алгоритмы можно применять только для графов с малым количеством вершин. Максимальное количество красок совпадает с количеством вершин графа n, следовательно, необходимо рассмотреть nⁿ комбинаций расстановки цветов по вершинам в графе.

2 Стягивание вершин

Такие алгоритмы позволяют из исходного графа построить граф с меньшим количеством вершин. Например, вершины a и b удаляются и заменяются вершиной ab, куда направляются рёбра как вершины a, так и вершины b.

3 Жадная раскраска

Такой алгоритм упорядочивает вершины v₁, v₂, v₃, …, v_n и последовательно присваивает доступный цвет, не использовавшийся для окраски соседних вершин, либо добавляет новый.

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

Описать алгоритм раскраски можно последовательностью шагов:

1 Упорядочить вершины от наибольшей степени к наименьшей.

2 Окрасить первую вершину в цвет 1.

3 Выбрать цвет окраски 1.

4 Пока не окрашены все вершины, выполнять:

4.1 Окрасить в выбранный цвет вершину, которая не смежная с другой, уже окрашенной в этот цвет.

4.2 Выбрать следующий цвет.

В [4] предложен быстрый алгоритм для решения задачи о раскраске графа с использованием битовых операций. Он относится к алгоритмам стягивания вершин и работает на основе битовых операций над матрицей смежности. Алгоритм интересный и простой в реализации.

1.2.7 Быстрый алгоритм раскраски с использованием битовых операций

Авторы алгоритма работают с матрицей смежности и полагают, что любая вершина графа соединяется сама с собой, поэтому на главной диагонали матрицы будут стоять единицы. Между двумя вершинами может быть только одно ребро.

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

А – матрица смежности графа (см. таблицу 1.1), только на главной диагонали (из левого верхнего в правый нижний угол) стоят 1.

i, j – номера строк или столбцов матрицы А, ;

n– размер матрицы А (число строк или столбцов), ;

, , , – элементы матрицы А, первый индекс – номер строки, второй индекс – номер столбца.

Алгоритм раскраски:

1 Начиная с первой строки матрицы А (j = 1), производится поиск неокрашенной несмежной вершины. Для несмежной вершины в i-ом столбце будет стоять 0.

2 Все соседи вершины i добавляются к соседям вершины j, т.е. происходит стягивание. В результате получается обновлённая j-я строка матрицы А. Математически это можно заменить операцией ИЛИ (дизъюнкцией, логическим сложением) двоичных наборов, соответствующих строкамj и i.

3 Продолжаем поиск нулей в j-ой строке и так добавляем новые вершины в первую цветовую группу.

4 Если набор в первую цветовую группу закончился, т.е. нет больше нулей с рассматриваемой строке, то происходит переход к следующей строке матрицы А, если соответствующая вершина была ещё не окрашена.

5 Алгоритм останавливается, если всем вершинам графа назначены цвета.

Приведём пример работы алгоритма из [4].

Рассмотрим граф рисунка 1.1.

2

3

4

5

1

6

7

Рисунок 1.1 – Граф для демонстрации работы алгоритма

Построим матрицу смежности для графа рисунка 1.1:

. (1.1)

В соответствии с алгоритмом, в первой строке j = 1 ищем первый (слева направо) ноль. Это столбец с номером 4, т.е. i= 4. Значит вершина 4 несмежная с вершиной 1.

Выполняем логическое сложение строк 1 и 4 матрицы (1.1):

V

(1.2)

Результат (1.2) – это новая строка j = 1. Номера строк (вершин графа) 1 и 4 помещаются в одну цветовую группу:

(1.3)

Составим обновлённую матрицу А и вычеркнем из неё строку 4.

. (1.4)

В первой строке матрицы (1.4) есть ещё ноль, продолжаем набирать вершины в цветовую группу color1. Номер новой несмежной вершины – 6.

Выполняем логическое сложение строк 1 и 6 матрицы (1.4):

V

(1.5)

Результат (1.5) – это новая первая строка. Строка 6 помещаются в одну цветовую группу с 1 и 4:

(1.6)

Поскольку в строке 1 все элементы равны 1, то набор в первую цветовую группу окончен. Строки 1, 4 и 6 вычеркиваются из матрицы А.

Составим обновлённую матрицу А.

. (1.7)

Поскольку первая строка вычеркнута, то переходим ко второй j = 2 и начинаем составлять вторую цветовую группу.

В соответствии с алгоритмом, во второй строке j = 2 ищем первый (слева направо) ноль. Это столбец с номером 5, т.е. i= 5. Значит вершина 5 несмежная с вершиной 2.

Выполняем логическое сложение строк 2 и 5 матрицы (1.7):

V

(1.8)

Результат (1.8) – это новая строка j = 2. Номера строк 2 и 5 помещаются в одну цветовую группу:

(1.9)

Составим обновлённую матрицу А и вычеркнем из неё строку 5.

. (1.10)

Во второй строке матрицы (1.10) есть ещё ноль, продолжаем набирать вершины в цветовую группу color2. Номер новой несмежной вершины – 7.

Выполняем логическое сложение строк 2 и 7 матрицы (1.10):

V

(1.11)

Результат (1.11) – это новая вторая строка. Строка 7 помещаются в одну цветовую группу с 2 и 5:

(1.12)

Набор в цветовую группу color2 закончен, т.е. в строке 2 теперь все 1.

Составим обновлённую матрицу А и вычеркнем из неё строки 2 и 7.

. (1.13)

В матрице (1.13) единственная не вычеркнутая строка 3. В этой строке всего один 0. Это вершина 5, но она уже окрашена (1.12). Поэтому оставшаяся одна вершина 3 получает третий цвет и образует цветовую группу:

(1.14)

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

(1.15)

На основе рассмотренного алгоритма будет разработана программа раскраски вершин графа и применена для подтверждения гипотезы проекта.

ГЛАВА 2 Практические результаты исследования

2.1 Разработка программы раскраски графа

2.1.1 Выбор среды программирования

Из доступных средств программирования я выбрал MatLab (сокращение от английского Matrix Laboratory), т.к. в нём можно работать в большинстве операционных систем. Язык MatLab является высокоуровневым языком программирования, включающим основанные на матрицах структуры данных, широкий спектр функций, интегрированную среду разработки. Среда MatLab объединяет в себе редактор, интерпретатор и отладчик, что позволяет писать, редактировать, выполнять программу и просматривать результаты её работы, не покидая среды MatLab [4].

2.1.2 Разработка схемы программы

На основе алгоритма раскраски, представленного в п. 2.7 проекта, мною была разработана схема программы. При составлении схемы применялся ГОСТ [5] Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.

Cхема программы представлена в приложении Д.

2.1.3 Разработка программы

Для создания программы в MatLab мне потребовалось изучить некоторые его функции [4].

Сама программа в среде MatLab представляет собой m-файл (или script-файл). Он создаётся нажатием кнопки NewScript на панели инструментов File.

Исходные данные для программы (матрицу смежности графа) решено считывать из файла, созданного в приложении Excel. Для этого применяется команда xlsread(‘Имя файла.xlsx’). После считывания, матрица появляется в поле WorkSpaсe, где можно её увидеть и проверить.

В MatLab есть интересный оператор – двоеточие «:». Если запись такая B = А(:,1), то в массив В записываются все элементы из 1-го столбца матрицы А. Если написано х = 1:0,5:5, то переменная х принимает значения от 1 до 5 с шагом 0,5. При определении размера aматрицы А используем оператор size(A,1). Для задания начальных значений матриц color и line применён оператор zeros (a,1) – это матрица-столбец из нулей размером а.

Для программирования пригодился оператор условного перехода if. В MatLab он записывается так:

if <условие>

<операторы>

else

<операторы>

end

Чтобы организовать повторение действий, были использованы операторы цикла for и while.

Текст m-файла MatLab созданный в соответствии со схемой программы, приведённой в приложении Д, представлен в приложении Е.

Пример интерфейса MatLab после выполнения программы приведён в приложении Ж.

2.2 Проверка работоспособности программы на тестовых примерах

Работоспособность программы, а, следовательно, и алгоритма раскраски, описанного в п. 1.2.7, подтвердим на 10-и тестовых примерах. Результаты тестирования приведены в таблице И.1 приложения И.

Приведённые примеры содержат так простые конфигурации графов, имеющие от 2 до 4 вершин, так и более сложные, такие как дерево или графы, построенные для решения рассмотренных в главе 1 задач. Любой из рассмотренных графов оказалось возможно правильно раскрасить. Работоспособность программы подтверждена.

ЗАКЛЮЧЕНИЕ

В ходе выполнения исследовательского проекта удалось познакомиться с графами, понять, как их можно описать и задать. Граф очень удобно использовать для решения различных задач, связанных с оптимизацией, составлением планов и расписаний. В этом я убедился при изучении типовых задач: раскраска карты, экономия ячеек памяти ПЭВМ и составление расписания уроков.

При изучении алгоритмов раскраски мне попался интересный и несложный быстрый алгоритм раскраски с использованием битовых операций. Изучив алгоритм, я составил схему для написания программы на ПЭВМ. В качестве среды программирования решено было воспользоваться MatLab. Освоить его оказалось не сложно.

С помощью разработанной программы можно правильно раскрасить граф, следовательно, верно решить задачу, для которой этот граф был составлен. Гипотеза моего исследования подтверждена.

Все поставленные задачи выполнены, цель исследования достигнута.

В ходе работы над проектом получены новые знания по математике и информатике, а также практические навыки составления схем программ и программирования.

Полученный продукт проекта – программу для ПЭВМ, можно использовать для решения любой задачи, связанной с раскраской графа. Я планирую с помощью этой программы попробовать составить расписание для учеников 1-4 классов. Но сначала надо разработать алгоритм, как составить матрицу смежности графа, а затем придумать, как результат работы программы преобразовать в расписание.

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1 Плоские и планарные графы. Раскраска графов. [Электронный ресурс]. – Режим доступа: https://progr-system.ru/wp-content/uploads/Math/МАПКС-08-ПлоскиеПланарныеГрафыРаскраска.pdf.

2 Дискретная математика. Теория графов. Раскраски. [Электронный ресурс]. – Режим доступа: http://pgap.chat.ru/zap/zap251.htm

3 Ревинская О. Г. Основы программирования в MatLab: учебное пособие – СПб.: БХВ-Петербург, 2016. – 208 с.: ил.

4 Комоско Л. Ф., Бацын М. В. Быстрый алгоритм для решения задачи о раскраске графа с использованием битовых операций. [Электронный ресурс]. – Режим доступа: https://publications.hse.ru/mirror/pubs/share/folder/0rhqzr8ukk/direct/133671897.

5 ГОСТ 19.701-90 (ИСО 5807-85) Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения. Дата введения 01.01.92. [Электронный ресурс]. – Режим доступа: https://base.garant.ru/5369717/

Приложение А

Примеры графов и способы их описания

Таблица А.1 – Матрица смежности графа рисунка А.1

	I	II	III	IV	V	VI
I	0	1	0	0	1	0
II	1	0	1	1	0	0
III	0	1	0	1	0	0
IV	0	1	1	0	1	0
V	1	0	0	1	0	1
VI	0	0	0	0	1	1

Таблица А.2 – Список рёбер графа рисунка А.1

Таблица А.3 – Матрица инцидентности графа рисунка А.1

	I	II	III	IV	V	VI
1	0	0	0	0	0	2
2	0	0	0	0	1	1
3	1	0	0	0	1	0
4	1	1	0	0	0	0
5	0	1	0	1	0	0
6	0	1	1	0	0	0
7	0	0	1	1	0	0
8	0	0	0	1	1	0

Приложение Б

Рисунки к задаче о раскраске географической карты

Рисунок Б.1 – Политическая карта

Р
исунок Б.2 – Граф, соответствующий политической карте и его раскраска

Рисунок Б.3 – Политическая карта после раскраски

Приложение В

Рисунки к задаче об экономии ячеек памяти

Рисунок В.1 – Схема к задаче об экономии ячеек памяти

g

1

a

f

h

1

2

3

b

e

2

3

c

d

3

4

Рисунок В.2 – Граф к задаче об экономии ячеек памяти и его раскраска

Приложение Г

Таблицы и рисунок к задаче о составлении расписания

Таблица Г.1 – Исходные данные для составления расписания занятий

Рисунок Г.1 – Граф к задаче о составлении расписания и его раскраска

Таблица Г.2 – Расписание занятий

Приложение Д

Схема программы раскраски вершин графа

Начало

Считывание матрицы из файла

Считывание матрицы смежности графа из файла *.xlsx

a = size(A,1)

Определение размера считанной матрицы

Начальные данные переменных и массивов

j=1 номер строки

k=1 номер цвета

n=0 номер нулевого элемента

color(a,1) = [0 0 … 0]

матрица цветов

line(a,1) = [0 0 … 0]

матрица отметок вычеркнутых строк

Р=0 произведение элементов матрицы

color(a,1)

while 1

P < 0

Пока все вершины не будут окрашены

color(j) < 1

да

нет

color(j) = k

line(j) = 1

i = 1

while 2

i ≤ a

Поиск нулей в строке.

Пока не будут просмотрены все элементы строки

A(j, i) = 0

и

line(i) < 1

да

нет

Если в j-ой строке под номером i ноль, и i-я строка не вычеркнута

n = i

for

ii = 1:1:a

Запоминается номер нулевого элемента

Цикл по элементам строк j и n.

А

В

С

Присвоение вершине j цвета k и «вычёркивание» j-ой строки матрицы

А

A(j,ii) =A(j,ii) V A(n,ii)

Логическое сложение (ИЛИ) строк j и n.

for

color(n) = k

line(n) = 1

Присвоение вершине n цвета k и «вычёркивание» n-ой строки матрицы

i = i + 1

while 2

Переход к следующему элементу j-ой строки

k = k + 1

Если нулей в строке j больше нет, то переходим к следующему цвету

j = j + 1

Переход к следующей строке матрицы

Р = prod(color)

Вычисляется произведение элементов матрицы color(a,1)

while 1

Вывод результата в MatLab

Конец

В

С

Приложение Е

Текст программы раскраски вершин графа

A = xlsread('A.xlsx'); % Считывание матрицы

a = size(A,1); % Определение размера матрицы

% НАЧАЛЬНЫЕ ДАННЫЕ

j = 1; % номер строки

n = 0; % номер нулевого элемента

color = zeros(a,1); % матрица цветов

line = zeros(a,1); % матрица отметок вычеркнутых строк

k = 1; % первый цвет

P = 0; % произведение цветов

while(P < 1) % пока произведение цветов 0

if (color(j) < 1) % j-ый элемент color без цвета

color(j) = k; % цвет j-ой строки k

line(j) = 1; % вычёркиваем j-ю строку

i = 1;

% ПОИСК НУЛЕВОГО ЭЛЕМЕНТА

while (i <= a)

% Если в строке появился ноль и она не вычеркнута

if (A(j,i) == 0)&&(line(i) < 1)

n = i; % запонинаем номер нулевого элемента

% СЛОЖЕНИЕ СТРОК

for ii=1:1:a

% операция ИЛИ и запись результата в первую строку

A(j,ii) = or(A(j,ii),A(n,ii));

end

color(n) = k; % цвет n-ойстроки k

line(n) = 1; % вычёркиваем n-ю строку

i = i + 1; % переход к следующему элементу в строке

else

i = i + 1;% переход к следующему элементу в строке

end

end

k = k + 1; % переход на следующий цвет

end

j = j + 1; % переход на следующую строку

P = prod(color); % произведение элементов в color

end % while

color % вывод результата на экран

Приложение Ж

Пример интерфейса MatLab

Т аблица И.1 – Результаты работы программы на тестовых примерах