X-PDF

Связность в графах

Поделиться статьей

Рассмотрим вопрос о связности в графах. Пусть G(X) – неори­ентированный граф. Две вершины хi и xj называются связными, если существует цепь S с концами хi и xj. Если S проходит через некото­рую вершину xk более одного раза, то можно удалить цикл в верши­не xk из цепи S. Отсюда следует, что вершины, связанные цепью, связаны элементарной цепью.

Неориентированный граф называется связным, если любая па­ра его вершин связана. Отношение связности для вершин графа есть отношение эквивалентности
(xi ~ xj, хj ~ хk Û xi ~ хk).

Компонентой связ­ности неориентирован­ного графа G(X) называ­ется подграф НА(А) графа G(X) с множеством вер­шин А Ì X и множеством ребер в G(X), инцидент­ных только вершинам из А, причем ни одна вершина xi Î А не смежна с вершинами из множества Х А (рис. 3.12).

 
 

Рис. 3.12. Граф с двумя компонентами связности

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

Компонентой сильной связности ориентированного графа G(X) называется подграф НА(А) графа G(Х) (подчиняющийся опре­делению сильно связного графа) с множеством вершин А Ì Х и мно­жеством дуг, имеющих начало и конец в А, причем ни одна из вер­шин хi Î А и хj Î X А не смежны между собой (рис. 3.13).

Рис. 3.13. Ориентированный граф с двумя компонентами сильной связности

Очевидно, что ориентированный граф G(X) сильно связан то­гда и только тогда, когда он имеет одну компоненту связности.

Представленная информация была полезной?
ДА
58.58%
НЕТ
41.42%
Проголосовало: 985

На практике широко используются такие виды графов, как де­ревья и прадеревья.

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

 
 

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

Рис. 3.14. Дерево

Лесом называется несвязный граф, каждая компонента связно­сти которого является деревом.

Прадеревом называется ориентированный граф G(X) с корнем х0 Î X, если в каждую вершину хi ¹ х0i Î X) заходит ровно одна дуга, а в корень х0 не заходит ни одна дуга. Прадерево не содержит контуров (рис.3.15).

 
 

Рис. 3.15. Прадерево


Поделиться статьей
Автор статьи
Анастасия
Анастасия
Задать вопрос
Эксперт
Представленная информация была полезной?
ДА
58.58%
НЕТ
41.42%
Проголосовало: 985

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram

ОБРАЗЦЫ ВОПРОСОВ ДЛЯ ТУРНИРА ЧГК

Поделиться статьей

Поделиться статьей(Выдержка из Чемпионата Днепропетровской области по «Что? Где? Когда?» среди юношей (09.11.2008) Редакторы: Оксана Балазанова, Александр Чижов) [Указания ведущим:


Поделиться статьей

ЛИТЕЙНЫЕ ДЕФЕКТЫ

Поделиться статьей

Поделиться статьейЛитейные дефекты — понятие относительное. Строго говоря, де­фект отливки следует рассматривать лишь как отступление от заданных требований. Например, одни


Поделиться статьей

Введение. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси

Поделиться статьей

Поделиться статьей1. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси. Специфика периода феодальной раздробленности –


Поделиться статьей

Нравственные проблемы современной биологии

Поделиться статьей

Поделиться статьейЭтические проблемы современной науки являются чрезвычайно актуальными и значимыми. В связи с экспоненциальным ростом той силы, которая попадает в


Поделиться статьей

Семейство Первоцветные — Primulaceae

Поделиться статьей

Поделиться статьейВключает 30 родов, около 1000 видов. Распространение: горные и умеренные области Северного полушария . многие виды произрастают в горах


Поделиться статьей

Вопрос 1. Понятие цены, функции и виды. Порядок ценообразования

Поделиться статьей

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


Поделиться статьей

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram
Заявка
на расчет