Посчитать количество кластеров.

ruslan80

Есть конечная гранецентрированная кубическая решётка, в ней выделены некоторые узлы, распределение равномерное по объёму. Соседними считаем узлы, расстояние между которыми a/sqrt(2 где a - размер ячейки. Как можно посчитать среднее количество связных кластеров размера n в зависимости от количества выделенных узлов (или их концентрации, что одно и то же)? Понятно, что связным называем кластер, в котором можно из любого узла дойти до любого другого по соседним.
Пример: одиночные кластеры составляют (1-x)^12 от выделенных узлов, узлы в составе двойных - 12x(1-x)^18, тройные тоже считаются, а вот дальше беда, x - концентрация выделенных узлов.
Спросил для очистки совести, вдруг кто-нибудь подаст хорошую идею :D

seregaohota

(1-x)^12
поясни почему, а то непонятно что ты считаешь. ребра выкидываются и связностьтолько поотрезкам длины a/sqrt(2)?

ruslan80

ребра выкидываются и связностьтолько поотрезкам длины a/sqrt(2)
Да, именно так. Соответственно, у каждого узла 12 соседей и вероятность всех 12 пустышек равна (1-x)^12.

seregaohota

это в углах с целыми координатами 12 соседей, а а в центрах граней с двумя полуцелыми координатами у каждого 4 соседа, а не 12.
или ты в отличие от классической картинки такие узлы с полуцелыми координатами соединяешь новыми ребрами внутри куба?

ruslan80

или ты в отличие от классической картинки такие узлы с полуцелыми координатами соединяешь новыми ребрами внутри куба?
Да, я соединяю со всеми узлами на расстоянии a/sqrt(2).

seregaohota

Как можно посчитать среднее количество связных кластеров размера n в зависимости от количества выделенных узлов
узлы в составе двойных - 12x(1-x)^18
Переформулировка задачи (я взял твою постоянную решетки a=2). В пространстве [math]$\mathbb Z^3$[/math] определим подмножество
[math]$\mathbb A =\{ (x,y,z) | (x,y,z) \in \mathbb Z^3, x+y+z=0 \mod 2\}$[/math]
Соседними назовём точки, разность координат которых равна [math]$0, \pm 1$[/math] (причем только одна разность из трех = 0). Таких точек соседних к заданной всего 12. Соседние и только их соединим ребрами, получим бесконечный граф.
Теперь каждая вершина графа независимо от других может случайным образом пребывает в двух состояниях - окрашена в черный цвет с вероятностью p (= твоему x и в белый с вероятностью q ( = твоему 1-x).
(связным) кластером размера n назовем связный подграф с черными вершинами все соседи которого белые.
Найти вероятность данной вершины и её 12 соседей являться 1-кластером. Найти вероятность данных 2 соседних вершин и их 18 соседей (20 = 2*13 - 6) являться 2-кластером.
Это я пересечения двух множеств из 13 точек (исходной точки и соседей) считаю, со звездочками это те строчки, которые совпадут с точками исходного множества если к первым двум координатам прибавить по 1 в направлении смещения ко второй точке

0 0 0 и соседи 1 1 0 и соседи
x y z x y z
------------- -------------
* 0 0 0 * 1 1 0
1 1 0 2 2 0
1 0 1 2 1 1
0 1 1 1 2 1
-1 1 0 0 2 0
*-1 0 1 * 0 1 1
* 0 -1 1 * 1 0 1
1 -1 0 2 0 0
1 0 -1 2 1 -1
0 1 -1 1 2 -1
*-1 -1 0 * 0 0 0
*-1 0 -1 * 0 1 -1
* 0 -1 -1 * 1 0 -1

С 3-кластерами уже сложнее, т.к. они могут не переводиться один в другой преобразованиями решётки (3 в ряд и треугольник, например). И при подсчетах и определении понятия 3-кластер надо учитывать возможность пересечения как в формуле включения и исключения
 
у меня тогда вероятность 1-кластера [math]$pq^{12}$[/math] (чтобы найти интересующую тебя вероятность надо разделить на p)
у меня тогда вероятность этого моего 2-кластера [math]$p^2q^{18}$[/math] (чтобы найти интересующую тебя вероятность надо разделить, по-видимому (хотя фиг знает, у тебя нет четкого определения - только интуиция на p^2 (ты ещё на 12 умножаешь учитывая в отличие от меня повороты - что существует 12 векторов направления от первой отмеченной-фиксированной вершины ко второй неотмеченной, да и то я не уверен, правильно ли ты делаешь - надо ли вершины считать неразличимыми и тогда ещё делить на 2! т.к. ты каждый такой кластер в пространстве (пару) посчитал 2 раза взяв за отмеченную вершину сначала одну точку, а потом другую с противоположным вектором смещения)
Оставить комментарий
Имя или ник:
Комментарий: