Дискретная математика. Комбинаторика. Ерош И.Л. - 33 стр.

UptoLike

Составители:

Рубрика:

3. Пусть имеются два вектора, соответствующие центрам класте-

ров: X: 10111001 и Y: 00101111. Вычислите меру Танимото, определяю-

щую расстояние между этими кластерами. Если вектор X принять за

исследуемый вектор, а в векторе Y допускать одиночные искажения

признаков, то можно определить минимальное расстояние до границ

кластера. Найдите все векторы кластера с центром Y и определите

минимальное расстояние между X и “ближайшим” к нему вектором из

кластера Y.

2.7. Теория графов

Теория графов относится к области дискретной математики и зани-

мается изучением геометрических связей между объектами. Основ-

ным объектом теории является граф, однако при решении многих задач

в ХХ веке широко стали применяться другие термины: карта, сеть, ком-

плекс, диаграмма, лабиринт. Теория графов тесно связана с различны-

ми разделами математики: топологией, алгеброй, теорией вероятнос-

тей, теорией чисел и, конечно, с комбинаторикой.

Приведем некоторые примеры задач теории графов, которые реша-

ются комбинаторными методами.

1. Имеется n участников шахматного турнира. Сколько партий дол-

жно быть сыграно, чтобы каждый участник сыграл со всеми остальны-

ми? Любой турнир между n участниками (командами) может быть пред-

ставлен в виде графа, при этом после окончания турнира граф является

полным. Каждый участник (вершина графа) играет со всеми остальны-

ми (их число n – 1), а поскольку число участников равно n, то всего игр

n(n – 1)/2.

2. Комбинаторные задачи сортировки часто изображаются в виде

графов типа “дерево”.

3. Не решенная аналитически задача Гамильтона об обходе всех вер-

шин связного графа в точности по одному разу для определения числа

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