 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Гиперграф
|
Читайте также: |
ГГ такое обобщение графа, в котором каждому ребру соответствует не пара вершин как в обычном графе, а произвольное подмножество вершин.
Данная модель обычно используется при решении задачи компоновки. Это связано с тем, что при компоновке контакты всегда распределяются в блок вместе с элементами, которым они инцидентны. Поэтому на ГКС можно исключить множество элементарных ребер 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 –й(–му) цепи (элементу).
Поиск по сайту: