2. Число внутренней устойчивости.

Множество вершин графа называется независимым, если никакие две из них не соединены между собой ребрами. Среди независимых множеств существует хотя бы одно максимально независимое, содержащее максимальное число вершин. Это число вершин называется числом независимости для данного графа (или числом его внутренней устойчивости).

Максимальное число вершин в дополнении равно 8, то есть это и есть число внутренней устойчивости. Таким образом, на доске размером 5 на 5 наибольшее число слонов, которые бы не били друг друга равно восьми.

Заключение

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

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

32