Студопедия Главная Случайная страница Обратная связь

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

Понятие связности. Компоненты связности.




Вершины в приведенных выше обозначениях называются концами пути и связан-ными или соединенными путем L. Отдельным термином выделяют тот факт, что две вершины графа могут быть связаны некоторым путем: их называют связанными. Например, в графе

a1

 

a2 a3 . a4

 

a5

 

вершины a3 и a5 связаны (путем ), а вершины a4 и a1 нет.

Граф, в котором связанны любые две вершины, называется связным. Таким образом, выше приведен пример графа несвязного. Связной компонентой графа называется такой его подграф, который является сам по себе графом связным и при этом совпадающим с любым другим содержащим его связным подграфом. Таким образом, связный граф обладает единст-венной связной компонентой - это он сам. А вот приер графа с тремя связными компонетами (имена вершин не имеют значения):


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

Вот схематическое изображение простого цикла:

А вот схематическое изображение цикла, не являющегося простым:

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

Орграф называется связным, если в нем любые две вершины связаны.

Определение: Граф (Орграф) G связен, если любая пара его вершин u,v может быть соединена цепью (путем) от u к v. В противном случае, граф G несвязен. Компонента связности графа G есть наибольший по числу ребер связный подграф графа G.

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

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

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

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

 

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

На рис. 3.17 показан односторонне связный ориентированный псевдограф и ассоциированный с ним псевдограф.

Рис. 3.17

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

Орграф рис.3.17 является слабо связным.







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


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2021 год . (0.001 сек.) русская версия | украинская версия