Учи Кванты! → Курс → Задача без кванта

Где эта задача живёт и как её решают без перебора

Сговор контрагентов из прошлого урока это лишь одно из обличий задачи о плотном подграфе. Та же математика ловит отмывание денег, находит белковые комплексы и вычисляет ботоферм. Здесь мы посмотрим на эти обличья, а затем разберём приём, которым задачу решают на практике: жадный пилинг, добирающийся до нашей шестёрки за двадцать шагов вместо тридцати восьми тысяч проверок.

Та же задача в других одеждах

Стоит сменить подписи под вершинами, и аудиторская история превратится в любую из десятка других. Банковский антифрод ищет группы счетов, гоняющие деньги по кругу: у схем отмывания предательски плотный след в графе переводов, и промышленные системы вроде FlowScope ловят именно его. Биологи строят сети взаимодействия белков, где плотный узел это белковый комплекс, молекулярная машина из десятка деталей. Платформы соцсетей вычисляют ботофермы: тысячи аккаунтов, дружно лайкающих друг друга, образуют неестественно плотный клубок. А рекомендательные сервисы ищут плотные сообщества из покупателей и товаров, чтобы понять, что предложить вам следующим.

Во всех этих историях граф разный, а вопрос один: где в сети группа, связанная плотнее, чем позволяет случай? Поэтому приём, работающий на одной задаче, тут же переносится на остальные.

Это платный урок курса. Дальше — интерактив: виджеты, схемы и контрольные вопросы. Продолжение — в полном курсе «Учи Кванты!»: открыть полный курс.