Студопедия

КАТЕГОРИИ:

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



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




Читайте также:
  1. III. Операции над матрицами
  2. АНАЛИЗ ВНЕШНЕЙ СРЕДЫ ОРГАНИЗАЦИИ КАК ОТКРЫТОЙ СИСТЕМЫ. МАТРИЦА STEP-АНАЛИЗА И ДРУГИЕ ИНСТРУМЕНТЫ.
  3. Андай матрицаның кері матрицасы болады?
  4. Биологическая роль эмоций. Виды эмоциональных состояний. Теории эмоций. Вегетативные и соматические компоненты эмоций. Роль эмоций в целенаправленной деятельности человека.
  5. Блок-схема осциллографа.
  6. В. Человеческий капитал: компоненты, оценка, способы формирования
  7. Глава 1. Междисциплинарная матрица социологии
  8. Глава II. Внутридисциплинарная матрица социологии
  9. Городская система озеленения. Комплексная зеленая зона города. Размеры, структура, функции, основные компоненты
  10. Действия над матрицами

Определение: Граф (орграф) называется связным(сильно связным), если для любых двух его вершин 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; просмотров: 282; Нарушение авторских прав







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