Конспект лекций по предмету "Теория графов"

Узнать цену работы по вашей теме


Вес и длина пути

Иногда дугам графа сопоставляют числа ai сi , называемые весом или длиной, или стоимостью или ценой. В каждом конкретном случае выбирается то слово, которое ближе подходит по смыслу задачи.
Граф G, описываемый тройкой вида
G = (X, A, С),
где Х = { хi }, i =1, 2, 3, ..., n – множество вершин,
А = { ai }, i = 1, 2, 3, ..., m – множество дуг,
С = {Ci}, i = 1, 2, 3, ..., m – множество характеристик дуг, называется графом со взвешенными дугами.
Пример такого графа приведен на рис. 8.2,а. При рассмотрении пути M, представленного последовательностью дуг(a1, a2, ..., aq), за его вес (или длину, или стоимость) принимается число L(M), равное сумме весов всех дуг, входящих в путь, т. е. L(M)= (ci) для всех ai M.
Длиной (или мощностью) пути называется число дуг, входящих в него. Чаще всего термин "длина" употребляется, когда все дуги, входящие в путь, имеют веса, равные 1, т. е. когда вес пути совпадает с его длиной (мощностью).

Рис. 8.2. Взвешенные графы: а – граф со взвешенными дугами; б – граф со взвешенными вершинами; в – взвешенный граф
Граф со взвешенными вершинами – это граф, описываемый тройкой
G = ( X, А, V ),
где Х = { хi }, i = 1, 2, ..., n – множество вершин графа;
А = { ai }, i = 1, 2, ..., m – множество дуг графа;
V ={ vi }, i = 1, 2, ..., n – множество характеристик вершин.
В качестве характеристик вершин могут выступать "стоимость", "мощность", "вес" и т. п. Пример такого графа приведен на рис. 8.2,б. Для графа со взвешенными вершинами в случае представления пути последовательностью вершин весом пути является сумма весов, входящих в этот путь вершин.
И наконец, взвешенный граф определяется четверкой вида G = (Х, А, V, С), т. е. и дуги, и вершины этого графа имеют некоторые характеристики.
Область применения взвешенных графов в качестве моделей довольно обширна: транспортные задачи, задачи оптимизации сети связи и системы перевозок и др. Одной из известнейших оптимизационных задач является нахождение кратчайших путей в графе со взвешенными дугами.


Не сдавайте скачаную работу преподавателю!
Данный конспект лекций Вы можете использовать для создания шпаргалок и подготовки к экзаменам.

Доработать Узнать цену работы по вашей теме
Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем конспект самостоятельно:
! Как написать конспект Как правильно подойти к написанию чтобы быстро и информативно все зафиксировать.

Другие популярные конспекты:

Конспект Основные проблемы и этапы развития средневековой философии
Конспект Проблема познаваемости мира. Гносеологический оптимизм, скептицизм, агностицизм. Взаимосвязь субъекта и объекта познания
Конспект Понятие финансовой устойчивости организации
Конспект Внутренняя политика первых Романовых.
Конспект ПРОБЛЕМЫ КВАЛИФИКАЦИИ ПРЕСТУПЛЕНИЙ
Конспект Понятие мировоззрения, его уровни и структура. Исторические типы мировоззрения
Конспект Синтагматические, парадигматические и иерархические отношения в языке
Конспект Тема 1.2. Плоская система сходящихся сил. Определение равнодействующей геометрическим способом 13
Конспект Происхождение человека. Основные концепции антропосоциогенеза. Антропогенез и культурогенез.
Конспект Общая характеристика процессов сбора, передачи, обработки и накопления информации