11.8. ориентированные графы
11.8. ориентированные графы
В ориентированных графах на ребрах задано направление, т.е. у каждого ребра фиксируются начало и конец. Такие направленные ребра называются дугами.
Цепью в ориентированном графе называется такая последовательность дуг, ведущих от вершины ру к вершине рп, в которой каждые две соседние дуги имеют общую вершину и никакая дуга не встречается более одного раза.
Если направление цепи совпадает с направлением всех принадлежащих ей дуг, то цепь называется путем.
Цепь, путь и цикл в произвольном графе называются простыми, если они не проходят ни через одну свою вершину более одного раза. Длиной цепи, пути, цикла называется число содержащихся в них дуг.
Сетью называется граф, каждой дуге которого поставлено в соответствие некоторое число (или несколько чисел).
Многие практические задачи могут быть решены с помощью теории графов. Рассмотрим примеры.
Задача размещения. В некотором районе имеется п населенных пунктов, соединенных друг с другом сетью шоссейных дорог. Нужно построить станцию технического обслуживания автомобилей вблизи шоссейной дороги. Расположение станции должно быть удобно для жителей всех населенных пунктов. Например, можно потребовать, чтобы сумма расстояний от станции до населенных пунктов была минимальной.
315
Легко представить эту задачу с помощью графа. Населенные пункты представляются вершинами графа, а шоссейные дороги — дугами, которые их соединяют. Станция технического обслуживания должна быть расположена на одной из дуг графа.
Задача почтальона. Почтальон ежедневно забирает письма на почте, разносит их адресатам и возвращается обратно на почту. Путь, пройденный почтальоном, должен быть как можно короче.
Улицы представляются дугами некоторого графа. Задача почтальона заключается в том, чтобы найти самый короткий маршрут обхода всех дуг графа.
Задача строительства дорог. Имеется и городов, которые нужно соединить между собой новыми дорогами (не обязательно каждые два города должны быть связаны друг с другом непосредственно). Известна стоимость прокладки дороги между любыми двумя городами. Требуется составить проект строительства дорог минимальной стоимости.
Очевидно, что каждый город представляется вершиной графа, а дорога — дугой, соединяющей вершины. Каждой дуге ставится в соответствие число, равное стоимости строительства данной дороги. Требуется построить некоторое покрывающее дерево графа минимальной стоимости.
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы