Графы в олимпиадных задачах и задачах по теории вероятностей

Селезнева Светлана Юрьевна

Основные понятия теории графов

Граф — это набор вершин (точек), соединённых рёбрами (линиями). Вершины могут представлять объекты, а рёбра — связи между ними. Например, города и дороги, люди и их знакомства, компьютеры в сети. umschool.net +2

Виды графов:

·         Неориентированный граф — рёбра не имеют направления, по ним можно двигаться в обе стороны. 

·          Ориентированный граф (орграф) — рёбра имеют направление (дуги), движение возможно только в указанном направлении. 

·         Взвешенный граф — рёбрам присвоены веса (числа), которые могут означать расстояние, стоимость и т. д.. 

·         Полный граф — каждая вершина соединена с каждой другой вершиной. habr.com +1

·         Дерево — связный граф без циклов, где между любыми двумя вершинами есть единственный путь. 

 Ключевые термины:

·         Степень вершины — количество рёбер, инцидентных вершине. Петля увеличивает степень на 2. 

·         Путь — последовательность рёбер, соединяющих вершины.

·         Цикл — путь, начинающийся и заканчивающийся в одной вершине.

·         Связный граф — граф, в котором есть путь между любыми двумя вершинами. 

См рисунки в приложении

Применение теории графов в олимпиадных задачах

Графы помогают решать задачи на:

·         Поиск кратчайших путей (алгоритм Дейкстры). 

·         Нахождение гамильтонова цикла (цикл, проходящий через все вершины по одному разу). 

·         Определение минимального разреза или остовного дерева. 

·         Анализ связей и отношений (например, в задачах на знакомства или турниры). 

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

Решение таких задач часто требует построения графа и анализа его свойств, например, связности или количества рёбер. 

Теория графов в теории вероятностей

В теории вероятностей графы используются для:

·         Построения деревьев вероятностей — ориентированных графов, где вершины представляют события, а рёбра — их исходы с указанием вероятностей. 

·         Анализа случайных процессов — например, распространения информации, эпидемий или поведения сложных систем. 

·          Моделирования сетевых взаимодействий в социальных сетях, транспортных системах и других областях. 

 Правило вычисления вероятности по размеченному графу:

1.    Вероятность попадания в конечную вершину равна произведению вероятностей на рёбрах соответствующего маршрута.

2.    Если событие благоприятствует нескольким исходам, вероятности соответствующих вершин складываются. 

Пример: Ковбой видит на стене муху, наудачу хватает первый попавшийся револьвер и стреляет. Найдите вероятность того, что он промахнётся.

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

Советы для решения задач

·         Визуализируйте задачу — нарисуйте граф, чтобы наглядно представить связи и объекты.

·         Используйте алгоритмы — например, обход в ширину или глубину для анализа структуры графа.

·         Применяйте лемму о рукопожатиях — в любом графе количество вершин нечётной степени чётно. 

·         Для вероятностных задач стройте деревья вероятностей и последовательно вычисляйте искомые значения.

Теория графов — мощный инструмент, который помогает решать сложные задачи, упрощая их понимание через визуальные модели. Практика и анализ различных примеров помогут освоить этот метод.