Графы
Сочетания с повторениями.
Если в сочетаниях некоторые элементы (или все) могут оказаться одинаковыми, то такие сочетания называются сочетаниями с повторениями. Их число определяется по формуле: .
Задача: сколько наборов из 7 пирожных можно составить, если в продаже имеется 4 сорта пирожных?
Решение: имеем сочетания с повторениями из четырех по 7 по, их число: .
Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Дело в том, что теория графов предоставляет очень удобный язык для описания программных (да и многих других) моделей.
Этот тезис можно пояснить следующей аналогией. Понятие отношения также можно полностью выразить через понятие множества. Однако независимое определение понятия отношения удобнее - введение специальных терминов и обозначений упрощает изложение теории и делает ее более понятной.
То же относится и к теории графов. Стройная система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные и тонкие вещи.
|
|
Особенно важно наличие наглядной графической интерпретации понятия графа. Само название «граф» подразумевает наличие графической интерпретации. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы.