Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

 

Практическую значимость остовных деревьев дает популярная форма задачи Кэли.

Необходимо соединить n городов железнодорожными линиями так, чтобы не строить лишних дорог. Известна стоимость строительства для каждой пары городов. Какова должна быть сеть дорог, соединяющая все города и имеющая минимальную стоимость? Аналогичные вопросы возникают при проектировании компьютерных сетей.

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

Очевидно, что граф - дерево, в противном случае можно бы было удалить одно ребро, не нарушая связности графа, но уменьшая вес.

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал