Комбинаторика и алгебра логики
Как было показано выше, сама структура кубов обеспечивает широкое их применение при изучении и интерпретации свойств булевых наборов и булевых функций, заданных на них, поскольку многие свойства данных объектов проявляются именно на соседних наборах.
Теория кодирования
Единичные n — мерные кубы являются наиболее удобным объектом для изучения свойств и иллюстрации структуры двоичных кодов, наиболее распространенных в практических приложениях.
Задачи
1. Найти число рёбер в кубе Вn.
2. Задан куб В4. Какова минимальная длина пути в нем из вершины (1101) в вершину (0110) ?
3. Доказать, что если две вершины куба Вn не соединены ребром, то расстояние Хэмминга между соответствующими булевыми векторами`an,`b n лежит в интервале [2,n].
4. В кубе Вn выделены два непересекающихся шара с одинаковым радиусом. Каков может быть максимальный радиус данных шаров?
Сети
Определение. Псевдограф G = (V, X), у которого выделено некоторое множество из k вершин Р = {v1 ,…, vk} — полюсов, называют k — полюсной сетью. Обозначают данную сеть как Г = (Р, V, X) , Г = ({v1 ,…,vk }, V, X)либо Г = (v1 ,…,vk). Вершины сети, отличные от полюсов, называют внутренними. Простые цепи, соединяющие полюсы сети, называют цепями сети. Цепи сети минимально возможной длины называют кратчайшими.
На практике наибольшее применение нашли одно— и двухполюсные сети. Деревья с выделенной корневой вершиной (корневые) являются однополюсными сетями. Рассмотрим основные примеры применения сетей.
Дата добавления: 2015-10-05; просмотров: 984;