В неориентированном графе понятие дуга, путь, контур заменяются соответственно на ребро, цепь, цикл.

Ребро – отрезок, соединяющий две вершины, цепь – последовательность ребер.

Цикл – конечная цепь, у которой начальная и конечная вершина совпадают.

Граф называется связанным, если любые его две вершины можно соединить цепью.

Граф, который не является связанным, может быть разбит на конечное число связных графов, называемых компонентами, или частями.

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

Точкой сочленения графа называется вершина, удаление которой приводит к увеличению числа его компонент связности.

Приведём примеры использования графов.

Граф на рис. 1 изображает схему дорог между селами и . Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе находится почта и почтальон должен развезти письма в остальные четыре села. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф (рис. 1, внизу), на котором легко увидеть возможные маршруты. Вершина вверху – начало маршрутов. Из нее можно начать путь четырьмя различными способами: в , в , в или в . После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в . Всего способа. Все они на этом графе.

Рис. 1

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

Из полученных 24 чисел наименьшими являются два числа по 28 км, соответствующие маршрутам и . Заметим, что это один и тот же путь, но пройденный в разных направлениях.

Подобные задачи возникают часто при нахождении наилучших вариантов развозки товаров по магазинам, материалов по стройкам.

В строительстве графы используются при планировании проведения работ. Граф, изображенный на рис. 2, называется сетевым графиком строительства. В данном случае он составлен для строительства жилого дома.

Рис. 2

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

Стрелка от работы к работе на графе, изображенном на рис. 2, означает, что работа не может начаться раньше, чем кончится работа . Нельзя начинать монтаж стен, не закончив строить фундамент, чтобы приступить к отделке, нужно иметь на этажах воду, для сварочных работ при монтаже нужно иметь подвод электричества и т.д.

Около вершин графа указаны числа – продолжительность в днях соответствующей работы. Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем (на рис. 2 он выделен коричневым цветом). В нашем случае получаем 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет. В этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т.д. И общее время строительства составит 160 дней, т.е. срок сократится лишь на 10 дней.

Образец решения задач

1 Даны множества: