Умова

Ви прилітаєте до незнайомої країни у місто А, проте вам потрібно потрапити до міста Б. Вам відомо, що у цій невеликій країні є лише 6 міст. З кожного міста можливо доїхати до будь-якого іншого єдиним можливим шляхом. З якою ймовірністю з міста А існує пряма дорога до міста Б (тобто без відвідання інших міст)?

Розв’язок

Розв’яжемо більш загальну задачу: для випадку, коли в країні \(n\) міст, \(n\ge 2\) . Математичною моделлю цієї країни слугуватиме граф, де вершинам відповідатимуть міста, а ребрам – дороги між ними. З властивостей, що наведені в умові, зрозуміло, що цим графом буде дерево, а саме – кістякове дерево повного графа \(K_n\).

Отже, простір елементарних подій складатиметься з неорієнтованих графів, кожен з яких задається як пара: множина вершин та множина ребер. У нашому випадку множина вершин для всіх графів буде однаковою, тобто \(V=\left\{ 1,\,2,\,...\,,\,n \right\}\) (нехай місту А відповідає номер 1, а місту Б – номер 2). У такому випадку: $$\Omega = \{G(V,E)\ ~|~ \text{де}~ G - \text{дерево}\}.$$ Подію \( X \) = {існує пряма дорога між А та Б} формалізуємо наступним чином: $$X=\left\{ G(V,E)\in \Omega \,|\ \ (1,2)\in E \right\}.$$

За формулою Келі маємо, що кількість кістякових дерев повного графа з \(m \) вершинами дорівнює \({m^{m - 2}}\) (цей факт неважко довести, використовуючи код Прюфера або матричну теорему Кірхгофа), тому $$|\Omega |\; = {n^{n - 2}}.$$ Залишилось з’ясувати, як саме влаштовані елементи події \( X\). Оберемо деякий граф \(G \in X\), він є деревом та містить ребро \( (1,\,2) \). Розіб’ємо його на два підграфи \({G_1}({V_1},{E_1})\) та \({G_2}({V_2},{E_2})\). До першого віднесемо вершину 1 та всі вершини, до яких існує шлях з першої, не відвідуючи вершину 2; до другого підграфу віднесемо решту вершин. З побудови та властивостей графів, що розглядаються, маємо:

1) \(1 \in {V_1}\) , \(2 \in {V_2}\);

2) дані підграфи теж будуть за своєю структурою деревами;

3) якщо в першому підграфі \(i\) вершин, то у другому графі \((n - i)\) вершин.

Також, маючи лише інформацію про підграфи, можна однозначно відновити граф \(G\): для цього достатньо об’єднати їх та додати ребро \( (1,\,2) \). Отже, між графами існує бієкція та їх кількості рівні.

Використавши вищенаведені властивості, маємо, що $$|X| = \sum\limits_{i = 1}^{n - 1} {C_{n - 2}^{i - 1} \cdot {i^{i - 2}} \cdot {{(n - i)}^{n - i - 2}}} .$$

Тепер за класичним визначенням ймовірності: $$P(X) = \frac{{|X|}}{{|\Omega |}}.$$

Підставивши у формулу \(n = 6\), маємо, що $$P(X) = \frac{{C_4^0 \cdot {1^{ - 1}} \cdot {5^3} + C_4^1 \cdot {2^0} \cdot {4^2} + C_4^2 \cdot {3^1} \cdot {3^1} + C_4^3 \cdot {4^2} \cdot {2^0} + C_4^4 \cdot {5^3} \cdot {1^{ - 1}}}}{{{6^4}}} = \frac{{432}}{{1296}} = \frac{1}{3}.$$

Відповідь: \( \dfrac{1}{3}. \)

Перевірка Для перевірки отриманого результату напишемо програму мовою Javascript.

Спочатку згадаємо, що будь-який граф можна задати бінарною матрицею, а граф кістякового дерева повного графа \(K_6\) має рівно \(6-1=5\) ребер і є зв'язним. Наступна функція перевірятиме бінарну матрицю на відповідність цим умовам:

function isSpanningTree(matrix) {
    const n = matrix.length;
    
    if (n !== 6) {
        return false; // Має бути 6 вершин
    }

    // Перевірка симетричності матриці
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] !== matrix[j][i]) {
                return false;
            }
        }
    }

    // Підрахунок кількості ребер
    let edgeCount = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (matrix[i][j] === 1) {
                edgeCount++;
            }
        }
    }

    if (edgeCount !== 5) {
        return false; // Кістякове дерево має містити 5 ребер
    }

    // Перевірка на зв'язність і відсутність циклів
    let visited = new Array(n).fill(false);
    let parent = new Array(n).fill(-1);
    
    function isCyclic(v) {
        let stack = [v];
        visited[v] = true;
        
        while (stack.length > 0) {
            let node = stack.pop();
            
            for (let i = 0; i < n; i++) {
                if (matrix[node][i] === 1) {
                    if (!visited[i]) {
                        visited[i] = true;
                        stack.push(i);
                        parent[i] = node;
                    } else if (parent[node] !== i) {
                        return true; // Цикл знайдено
                    }
                }
            }
        }
        return false;
    }

    if (isCyclic(0)) {
        return false; // Якщо знайдено цикл
    }

    // Перевірка зв'язності
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            return false; // Якщо є неперевірені вузли, граф не є зв'язним
        }
    }

    return true; // Успішно перевірено, що це кістякове дерево
}

// Приклад використання:
let matrix = [
    [0, 1, 0, 0, 1, 0],
    [1, 0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0, 0],
    [0, 0, 1, 0, 1, 0],
    [1, 0, 0, 1, 0, 1],
    [0, 0, 0, 0, 1, 0]
];

console.log(isSpanningTree(matrix)); // Виведе false

let matrix = [
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0],
    [0, 0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 1],
    [1, 1, 0, 0, 1, 0]
];

console.log(isSpanningTree(matrix)); // Виведе true

Тепер ми можемо зробити перевірку одним з двох варіантів:

Перший підхід: генерувати (випадково) симетричну бінарну матрицю розмірності \(6\times 6\), у якої на діагоналі лише нулі, а вище діагоналі 5 одиниць та 10 нулів, та перевіряти виконання умови \(matrix[0][1] == 1 \) (існування прямого шляху між містами А та Б):

function generateSymmetricMatrix() {
    const n = 6;
    let matrix = Array.from({ length: n }, () => Array(n).fill(0));

    // Список позицій вище діагоналі
    let positions = [];
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            positions.push([i, j]);
        }
    }

    // Перемішуємо список позицій
    for (let i = positions.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [positions[i], positions[j]] = [positions[j], positions[i]];
    }

    // Вибираємо перші 5 позицій для одиниць
    for (let k = 0; k < 5; k++) {
        const [i, j] = positions[k];
        matrix[i][j] = 1;
        matrix[j][i] = 1;
    }

    return matrix;
}

function printMatrix(matrix) {
    matrix.forEach(row => console.log(row.join(' ')));
}

// Приклад використання: генеруємо та друкуємо одну матрицю
// let matrix = generateSymmetricMatrix();
// printMatrix(matrix);

let m = 0
let n = 0
const N = 100000

for(let i=0; i<N; i++){
    let matrix = generateSymmetricMatrix();
    if(isSpanningTree(matrix)){
        n++;
        if(matrix[1][2] == 1) m++;
    }
}

console.log("m/n =", m/n);

Результат роботи цієї програми:

m/n = 0.3322724527249919

підтверджує правильність отриманого результату.

Другий підхід: перебрати усі підходящі матриці і порахувати, скільки серед них мають виконання умови \(matrix[0][1] == 1 \):

function generateAllSymmetricMatrices() {
    const n = 6;
    const positions = [];
    const matrices = [];

    // Список позицій вище діагоналі
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            positions.push([i, j]);
        }
    }

    // Генерація всіх комбінацій 5 позицій з 15
    const allCombinations = getCombinations(positions, 5);

    // Створення матриць на основі кожної комбінації
    allCombinations.forEach(combination => {
        const matrix = Array.from({ length: n }, () => Array(n).fill(0));

        combination.forEach(([i, j]) => {
            matrix[i][j] = 1;
            matrix[j][i] = 1;
        });

        if(isSpanningTree(matrix)) matrices.push(matrix);
    });

    return matrices;
}

// Функція для генерації всіх комбінацій k елементів з масиву
function getCombinations(array, k) {
    const combinations = [];

    function helper(start, combo) {
        if (combo.length === k) {
            combinations.push(combo.slice());
            return;
        }

        for (let i = start; i < array.length; i++) {
            combo.push(array[i]);
            helper(i + 1, combo);
            combo.pop();
        }
    }

    helper(0, []);
    return combinations;
}

// Функція для друку матриці
function printMatrix(matrix) {
    matrix.forEach(row => console.log(row.join(' ')));
}

// Генеруємо та друкуємо всі матриці
let count = 0;
const allMatrices = generateAllSymmetricMatrices();
console.log("Кількість матриць:", allMatrices.length);
allMatrices.forEach((matrix, index) => {
    console.log(`Матриця ${index + 1}:`);
    printMatrix(matrix);
    console.log('');
    if(matrix[1][2] == 1) count++;
});
console.log('count =', count);

Результат роботи цієї програми:

Кількість матриць: 1296
Матриця 1:
0 1 1 1 1 1
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0

Матриця 2:
0 1 1 1 1 0
1 0 0 0 0 1
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
0 1 0 0 0 0

...

Матриця 1296:
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 0 0 1
1 1 1 1 1 0

count = 432

підтверджує правильність отриманого результату, бо \(432/1296 = 1/3\).