Элементы теории множеств, операции над ними. Инъективные и сюръективные отображения. Отношение эквивалентности. Элементы теории кодирования, графов. Представление графов в памяти компьютера. Пример нахождения кода Харари графа. Задачи о раскраске.
Дискретная математика Методические указания для самостоятельной работы студентов очной формы обучения Математика. Дискретная математика: методические указаниядля самостоятельной работы студентов очной формы обучения (I семестр).Все больше в обязательную программу учебных заведений включаются курсы теории множеств, математической логики, комбинаторики, теории графов и их фрагменты. Специалисты в области современных компьютерных технологий уже осознали, что эти разделы математики являются фундаментом для построения необходимой сейчас хорошей теории математического обеспечения информационных технических систем.Решение а) используя определение степени вершины, выясним, какие степени имеют вершины А и В. Аналогично, и вершина В имеет степень 3. б) используем алгоритм решения задачи о нахождении кратчайшего пути из А в Вв смысле наименьшего количества ребер: Вершине А припишем индекс 0. Среди вершин, смежных с В, обязательно найдется вершина с индексом (n - 1) (одна или несколько), возвращаемся в эту вершину и продолжаем этот процесс. Среди вершин, смежных с В, обязательно найдется вершина С, для которой выполняется точное равенство (если бы , то индекс можно было бы еще уменьшить, если бы для всех смежных вершин, то непонятно, откуда взялся индекс .) Поскольку индексы все время уменьшаются, то через несколько шагов придем в вершину с индексом 0, т.е. в вершину А.Граф допускает-цветную раскраску вершин, если его вершины можно раскрасить красками так, чтобы никакие две смежные вершины не имели бы одинаковый цвет. Минимальное число , при котором граф допускает-раскраску вершин, называется хроматическим числом графа (обозначается ). Расположить вершины по убыванию их степеней и первую из неокрашенных вершин окрасить в цвет . Просмотреть вершины в порядке убывания степеней и окрасить в цвет № все вершины, которые несмежны с вершинами, уже окрашенными в цвет № . Правильная раскраска ребер графа - это раскраска ребер графа некоторым количеством цветов так, чтобы никакие два инцидентных ребра графа не были окрашены в одинаковые цвета.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
