Посчитать вер-ть прохождения сигнала в графе

[Yu_K]

Есть некоторая элементная база для проведения сигнала от $S$ к $F$, представленная графом. Элементы, соединяющие вершины графа могут быть работающими или нет с вер-тью $1/2$. Для первого графа (ниже картинка - граф из 8-ми вершин) всего возможных состояний $2^{13}$ с различными вариантами рабочих и нерабочих элементов. Из них ровно половина вариантов пропускает сигнал - т.е. существует путь в графе соединяющий $S$ и $F$, состоящий из работающих элементов - посчитал на ПК просто перебором и анализом всех вариантов. А как быть со вторым графом (тот где 11 вершин) - там вариантов уже $2^{18}$.

И как быть если элементы представляют куб и стартовая вершина соединена с 4-мя вершинами одной грани, а финишная соединена с 4-мя вершинами противоположной грани (для куба на ПК получилось 724 776 варианта пропускают сигнал из общего числа вариантов $2^{20}$ - если не напутал ничего)?

Может как то можно аналитически дать ответ - без ПК - выписать рекуррентные формулы для вероятностей.


\begin{tikzpicture}[thick, node distance=1.5cm, text height=1.5ex, text depth=.25ex, auto] \node[format] (S) {S}; \node[format,right of=S] (3) {3}; \node[format,right of=3] (4) {4}; \node[medium,below of=4] (6) {6}; \node[medium,below of=3] (5) {5}; \node[format,above of=3] (1) {1}; \node[format,above of=4] (2) {2}; \node[format,right of=4] (F) {F}; \path[<->] (S) edge (5);\path[<->] (1) edge (3);\path[<->] (2) edge (4); \path[<->] (S) edge (1);\path[<->] (F) edge (4);\path[<->] (F) edge (6); \path[<->] (S) edge (3); \path[<->] (3) edge (4); \path[<->] (1) edge (2); \path[<->] (3) edge (5); \path[<->] (5) edge (6); \path[<->] (4) edge (6); \path[<->] (F) edge (2); \end{tikzpicture}

\begin{tikzpicture}[thick, node distance=1.5cm, text height=1.5ex, text depth=.25ex, auto] \node[format] (S) {S}; \node[format,right of=S] (4) {4}; \node[format,right of=4] (5) {5}; \node[format,right of=5] (6) {6}; \node[medium,below of=6] (9) {9}; \node[medium,below of=5] (8) {8}; \node[medium,below of=4] (7) {7}; \node[format,above of=4] (1) {1}; \node[format,above of=5] (2) {2}; \node[format,above of=6] (3) {3}; \node[format,right of=6] (F) {F}; \path[<->] (S) edge (7);\path[<->] (1) edge (4);\path[<->] (2) edge (5);\path[<->] (3) edge (6); \path[<->] (S) edge (1);\path[<->] (F) edge (6);\path[<->] (F) edge (9); \path[<->] (S) edge (4); \path[<->] (4) edge (5); \path[<->] (5) edge (6); \path[<->] (4) edge (7); \path[<->] (7) edge (8); \path[<->] (8) edge (9); \path[<->] (5) edge (8); \path[<->] (6) edge (9); \path[<->] (2) edge (1);\path[<->] (2) edge (3);\path[<->] (F) edge (3); \end{tikzpicture}

[helix]

Здравствуйте!
Думаю ваш вопрос относится к теории перколяции (теории протекания, посмотрите в интернете). К сожалению, аналитических методов решения поставленных задач, насколько я знаю, пока нет.