Вот проблема:
Там связаны графа с узлами, представляющими количество людей. У каждого узла / человека есть мнение по теме, например, Трамп против Клинтона, бумажные книги против Киндла и т. Д.
Цель состоит в том, чтобы каждый узел в графе разделял одно и то же мнение, выбирая конкретное подмножество узлов в определенной последовательности.
Если большинство друзей человека А поддерживают Трампа, а человек А поддерживает Клинтона. если человек А выбран, его / ее мнение изменится на козырное.
Если мнения друзей человека разделены поровну, то вы можете решить мнение выбранного человека.
У меня заканчиваются идеи о том, как доказать это достижимо. Может быть, некоторые из вас могут дать мне несколько советов.
graphs
graph-theory
social-networks
paperpin
источник
источник
Ответы:
Это известно как динамика большинства . Обычно предполагается, что все узлы принимают мнение большинства одновременно, и это известно как синхронная модель. Для произвольного правила разрыва связи это сходится либо к фиксированной точке, либо к циклу длины 2; см., например, страницы 5-6 «Гиносара и Хольцмана». Действие большинства на бесконечных графиках: строки и куклы . Если вы разрываете связи предвзято, то динамика, вероятно, всегда сходится.
То, что вы описываете, - это асинхронная модель, в которой правило большинства применяется последовательно, а не параллельно. В этом случае процесс всегда сходится. См., Например, Тамуз и Теслер , хотя их методы, вероятно, для вас излишни, поскольку в вашем случае вы выбираете последовательность, тогда как в их случае последовательность выбирается случайным образом.
источник
Это вообще не достижимо. Рассмотрим синий и красный треугольник, связанный с одним ребром. Какой бы узел вы ни выбрали, он сохранит свой прежний цвет.
В общем, если у вас есть большие монохромные кластеры с небольшим количеством связей между ними, график является стабильным.
источник