Исходные понятия четких псевдографов

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

Если же объект не является матроидом, то существует функция w такая, что S не будет называтся независимым множеством с наибольшим весом.

Теорема. Если объект ‹V,J› есть матроид, то множество S найденное жадным алгоритмом является независимым множеством с наибольшим весом.

Основные понятия четких и н6ечетких графов.

В понятие псевдограф включаются следующие понятия:

§ простой (обыкновенный) граф (нет кратных ребер, петлей)- однородный гиперграф

§ тривиальный (пустой) гиперграф

§ мультиграф (однородный гиперграф с кратными ребрами)

§ граф тождественных отношений (гиперграф, ребра которого есть одноэлементные множества)

Взвешенный орграф (s =‹V, U›) в приложениях часто называют направленным сигнальным графом, а неограф (s =‹V, U›) линейным (структурным) графом.

Согласно Бурбаки граф определяется формулой s Ì V ²(V- собственное множество, V ²-подмножество декартова произведения)

Описание графа в смысле Бержа и Кернинга устраняет возможные недоразумения в понятии псевдографа с изолированными вершинами. Граф в смысле Бержа описывается так ‹V₁, V₂, S›, V_1È V₂= V, V_1Ç V₂=Æ, т.е. как двудольный.

Примечание:

Дополнением графа называется граф такой, что s È s =V², s Ç s =Æ. Объединенное дополнение графа V² есть все множество картежей декартового произведения.

В смысле Кенига граф описывается как отношение инциндентности и часто называется бихроматическим двудольным графом.

Примечания:

1) Неограф может раасматриваться как орграф, все дуги которого нестрого параллельны

=

Строго параллельны, не параллельны

‹V_i, V_j› {V_i, V_j}={‹V_i, V_j›,‹V_i, V_j› }

Примером такого представления может служить схема метрополитена, где двухстороннее движение поездов изображается ребрами.

2) Смешанный граф есть множество вершин (s =‹V, U, U›)

3) Степень вершин орграфа есть сумма полустепеней захода и исхода дуг.

degV_i = degV_i⁺ + degV_i^-

4) Среди вершин, инцидентных ребрам (дугам), различают следующие: граничные, висячие,

начальные, конечные, внутренние (промежуточные), голые, изолированные, вершины сочленения.

Примеры:

Def. Транзитивным замыканием é ^V_i орграфе называется множество вершин, в которые можно прийти из данной вершины по некоторому пути.

Формально транзитивное замыкание é ^V_i={V_i}È é V_{iÈ é} {é V_i}È …

Орграф называется сильно связанным, если любая вершина есть транзитивное замыкание для любой другой, т.е. для любых двух вершин такого графа существует путь из одной в другую. Очевидно, неограф всегда сильно связан.

Бинарное отношение в орграфе (есть путь из V_i в V_J) является отношением частичного порядка на множестве вершин, т.е. оно транзитивно и рефлексивно. Бинарное отношение в неоргафе (существует путь из V_i в V_J и из V_J в V_i) есть отношение эквивалентности, т.е. оно рефлексивно, симметрично и транзитивно.

Подграф графа (s =‹V,é ›) называется максимально сильно связанным, если не существует сильно связанного подграфа, строго содержащегося в данном подграфе.

Нечеткое подмножество имеет вид

{‹V_i,V_j› Î V²: Ms ‹V_i,V_j› Î M}

M- множество степеней принадлежности элементов декартову произведению.

Ms ‹V_i,V_j› - степень принадлежности пары графу (см. понятие нечеткого отношения на множестве).

Нечеткий превдограф может быть задан тремя способами: графически, таблично, и рисунком(?).Граф задан, если есть его матрица смежности, достижимости и инцидентности.

	V1	V2	V3	V4	V5	V6
V1
V2
V3
V4
V5
V6

Дата добавления: 2014-01-06