11.8. ориентированные графы

11.8. ориентированные графы: Справочник по математике для экономистов, В.И. Ермаков, 2007 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Предназначен для студентов экономических вузов. Может быть использован аспирантами и преподавателями вузов и колледжей, а также экономистами различных специальностей в практической работе.

11.8. ориентированные графы

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

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

В ориентированных графах циклом называется путь, начало и конец

которого совпадают. На рис. 11.12

дуги (alt а4, а5) образуют цепь, а дуги (alt a2, as) — путь. Последовательность дуг (ад, а2, а3) составляет

цикл, а последовательность (alt a2, р„с ц ^

ос+) не является циклом.

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

Длиной цепи, пути, цикла называется число содержащихся в них дуг.

Сетью называется граф, каждой дуге которого поставлено в соответствие некоторое число (или несколько чисел).

Многие практические задачи могут быть решены с помощью теории графов. Рассмотрим некоторые примеры.

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

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

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

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

Задача строительства дорог. Имеется п городов, которые нужно соединить между собой новыми дорогами (не обязательно каждые два города должны быть связаны друг с другом непосредственно). Известна стоимость прокладки дороги между любыми двумя городами. Требуется составить проект строительства дорог минимальной стоимости.

Очевидно, что каждый город представляется вершиной графа, а дорога — дугой, соединяющей вершины. Каждой дуге ставится в соответствие число, равное стоимости строительства соответствующей дороги. Требуется построить некоторое «покрытие» графа минимальной стоимости.

Справочник по математике для экономистов

Справочник по математике для экономистов

Обсуждение Справочник по математике для экономистов

Комментарии, рецензии и отзывы

11.8. ориентированные графы: Справочник по математике для экономистов, В.И. Ермаков, 2007 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Предназначен для студентов экономических вузов. Может быть использован аспирантами и преподавателями вузов и колледжей, а также экономистами различных специальностей в практической работе.