Студопедия

КАТЕГОРИИ:

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


Связность графа. Компоненты связности. Матрица связности




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

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

Определение: Псевдографом,ассоциированнымс ориентированнымпсевдографом Д(V, X), называется псевдограф G(V, X0), в котором X0 получается из X заменой всех упорядоченных пар (u,v) на неупорядоченные

Определение: Орграф называется слабосвязным, если связным является ассоциированный с ним псевдограф.

Определение: Граф (орграф), не являющийся связным (сильно связным), называется несвязным.

Определение: Компонентойсвязности (сильной связности) графа, G (орграфа Д), называют его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (орграфа Д).

Количество компонент связности (сильной связности) будем обозначать через p(G) (p(Д))

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

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

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

Замечание. Аналогичное утверждение справедливо и для произвольных псевдографов.

Пусть Д=(V,X) орграф, V={v1,…,vn} – множество вершин.

Определение: Матрицейдостижимости орграфа Д называется квадратная матрица T(Д)=[tij] порядка n, у которой

Определение: Матрицейсильнойсвязности орграфа Д называется квадратная матрица S(Д)=[sij] порядка n, у которой

Определение: Матрицейсвязности графа G называется квадратная матрица S(G)=[sij] порядка n, у которой

Утверждение 1. Пусть дан граф G= (V,X) V={v1,…,vn} Пусть А – матрица смежности. Тогда

S(G)= sign(E+A+A2+…+An-1)=E A ….

где Е – единичная матрица порядка n.

Утверждение 2. Пусть дан орграф Д= (V,X) V={v1,…,vn} А – матрица смежности. Тогда

1) Т(Д)= sign(E+A+A2+…+An-1)=E A ….

2) S(Д)= Т(Д) [Т(Д)]T, где [Т(Д)]T – матрица транспонированная Т(Д).


Поделиться:

Дата добавления: 2015-01-29; просмотров: 539; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты