Комбинаторные конфигурации

Тема 5 КОМБИНАТОРНЫЕ ЗАДАЧИ

Пример.

Представление графа в ЭВМ матрицей смежности.

Представления иллюстрируются на конкретных примерах графа G и орграфа D, диаграммы которых представлены на рис. 5.

Рис. 5. Диаграммы графа (слева) и орграфа (справа), используемых в качестве примеров

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

Представим граф G и орграф D матрицами смежности.

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

Дата добавления: 2015-05-26