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

Гиперграф

Читайте также:
  1. Алгоритм слежения за целью.
  2. Общая характеристика алгоритмов компоновки конструктивных модулей
  3. ПОСЛЕДОВАТЕЛЬНЫЙ АЛГОРИТМ КОМПОНОВКИ

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

Данная модель обычно используется при решении задачи компоновки. Это связано с тем, что при компоновке контакты всегда распределяются в блок вместе с элементами, которым они инцидентны. Поэтому на ГКС можно исключить множество элементарных ребер W и F. При этом каждая цепь описываемая множеством контактов будет описываться множеством инцидентных ей элементов.

,

где E – множество элементов схемы;

U – множество ребер, при этом каждое ребро представляет собой подмножество элементов, инцидентных цепи vi. Для схемы примера (рис. 2.1) эти подмножества имеют вид:

ГГ для схемы примера (рис. 2.1) представлен на рисунке 2.3.

Рис. 2.3

ГГ может быть описан с помощью матрицы инцидентности H.

Для схемы примера (рис. 2.1) матрица инцидентности имеет вид:

      v1 v2 v3 v4
    e0        
H = e1        
    e2        
    e3        

 

Более удобно описывать ГГ с помощью списка цепей по элементам и списка элементов по цепям.

Список цепей по элементам представляется последовательностью чисел, определяющих номера цепей, причем подпоследовательность чисел, выделенная знаком “ ;” (точка с запятой), содержит номера цепей инцидентных одному элементу схемы.

Список элементов по цепям каждой подпоследовательностью чисел задает номера элементов, инцидентных некоторой цепи.

Вместо одного списка элементов по цепям с разделителями (“ ;”) можно использовать два списка SP и RSP вида:

Аналогично для списка цепей по элементам:

При использовании пар списков SP–RSP или ST–RST в позициях начиная с RSP[i] (RST[i]) до RSP[i+1]-1 (RST[i+1]-1) в списке SP (ST) определяются номера элементов (цепей), инцидентных i –й(–му) цепи (элементу).

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |

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



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