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

Метод выделения максимального дерева

Читайте также:
  1. I этап Подготовка к развитию грудобрюшного типа дыхания по традиционной методике
  2. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  3. I. Методические основы
  4. I. Методические основы оценки эффективности инвестиционных проектов
  5. I. Предмет и метод теоретической экономики
  6. I. Что изучает экономика. Предмет и метод экономики.
  7. II. Метод упреждающего вписывания
  8. II. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
  9. II. Методы непрямого остеосинтеза.
  10. II. Проблема источника и метода познания.
  11. II. Рыночные методы.
  12. II. УЧЕБНО-МЕТОДИЧЕСКАЯ КАРТА ДИСЦИПЛИНЫ

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

Метод выделения максимального дерева основан на последовательном исключении из цепи определённых звеньев согласно следующим правилам:

§ На каждом шагу из цепи в произвольном порядке исключается одно звено;

§ Если исключение звена приводит к нарушению односвязности графа (то есть граф разбивается на две изолированных части, либо появляются «висящие» узлы), то звено возвращается в цепь;

§ Если при исключении звена граф не теряет односвязности, звено остаётся исключённым;

§ Переходим к следующему шагу.

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


1 | 2 | 3 | 4 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)