КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Определение 3.6. Максимальный связный подграф G’ графа G называется компонентой связности (или просто компонентой) графа G
Подграфы. Компоненты связности. Определение 3.1. Граф G’ = (V’,U’) называется подграфом графа G = (V,U) (обозначается G’ ⥹ G), если V’ ⊆ V и U’ ⊆ U. Таким образом, каждая вершина в G’ являетсявершиной в G и каждое ребро (дуга) в G’ являетсяребром (дугой) в G. Еслихотя бы одно из отмеченных выше включений V’ ⊆ V или U’ ⊆ U строгое, то подграф G’ называется собственным подграфом графа G. Если V’ = V, то G’ называется остовным подграфом графа G. Пример 3.1. Для орграфа v2 v5 G:
v1 v3 v4 v6 граф v2 G1:
v1 v3 v4 v6
является собственным подграфом орграфа G. Определение 3.2. Подграф G’ = (V’,U’) графа G = (V,U) называется вершиннопорожденным, если V’ ⊆ V и его множество ребер U’ содержит все те ребра графа G, оба конца которых содержатся в V’. Пример 3.2. Выберем во множестве вершин V орграфа G примера 3.1 произвольным образом некоторое подмножество V2 = {v1, v2, v4, v5}. Тогда подграф v2 v5 G2:
v1 v4 графа G является вершиннопорожденным (заданным подмножеством вершин V2). Определение 3.3. Подграф G’ = (V’,U’) графа G = (V,U) называется ребернопорожденным, если U’ ⊆ U и его множество вершин V’ состоит из всех тех вершин графа G, которые являются концевыми для ребер из U’. Пример 3.3. Выберем во множестве ребер U орграфа G примера 3.1 произвольным образом некоторое подмножество U3 = {(v2,v1), (v3,v1), (v2,v4), (v5,v6)}. Тогда подграф
v2 v5 G3:
v1 v3 v4 v6
является ребернопорожденным подграфом орграфа G. Определение 3.4. Граф (орграф) называется связным, если для любой пары вершин графа одна из них достижима из другой. Например, граф G’ примера 2.4 является связным, а граф G3 примера 3.3 связным не является (например, не существует пути между вершинами v1 и v5). Определение 3.5. Подграф G’ графа G называется максимальным, если для любого графа G’’ такого, что G’ ⥹ G’’ ⥹ G следует, что либо G’ = G’’ либо G’’ = G (иными словами, подграф G’ - максимальный подграф в графе G, если не существует собственного подграфа G’’ графа G, для которого подграф G’, в свою очередь, был бы собственным подграфом).
Пример 3..4. Пусть нам задан граф (псевдограф) v1 v2 v3 v4 v5 G:
v6 v7 v8 v9 v10 Тогда, например, подграф v1 v2 v5 G1:
v6 v7 v10 не является компонентой графа G (поскольку не является связным). Подграф v1 v2 G2:
v6 v7 связный, но не является компонентой графа G (поскольку не является максимальным связным подграфом – он является собственным подграфом для связного подграфа G3). Подграф v1 v2 G3:
v6 v7 является компонентой графа G (он не является собственным подграфом ни одного связного подграфа графа G). Подграф G4 графа G не является компонентой графа G (почему?), но является максимальным (и остовным) подграфом G. Здесь G4 – следующий подграф графа G: v1 v2 v3 v4 v5 G4:
v6 v7 v8 v9 v10 Исходный граф G имеет три компоненты связности (компоненты) – G3, G5, G6, где G3 отмечен раньше, а G5 и G6 - следующие подграфы:
v3 v4 v5 G5: G6:
v8 v9 v10
Дата добавления: 2014-12-16; Просмотров: 844; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |