рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Сильно связные графы и компоненты графа

Сильно связные графы и компоненты графа - Лекция, раздел Образование, Введение в теорию графов 1. Лекция: Графы и способы их представления Кроме Классификации Типов Графов Данной В П. 3.1 Графы Могут Быть Классифицир...

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

Орграф называется сильно связным, или сильным, если для двух любых различных его вершин хi и xj существует, по крайней мере, один путь, соединяющий эти вершины. Это определение означает также, что любые две вершины сильно связного графа взаимодостижимы. Пример данного графа показан на рис. 6.2,а.

 

Рис. 6.2. Виды графов по связности: а – cильно связный граф; б – односторонне связный граф; в – cлабо связный граф; г – несвязный граф

Орграф называется односторонне связным, или односторонним, если для любых двух различных его вершин хi и xj существует, по крайней мере, один путь из хi в xj или из xj в хi или оба пути существуют одновременно. Граф на рис. 6.2,б не является сильным, так как в нем нет пути из х1 в х3 , но является односторонне связным.

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

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

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

Максимальным подграфом графа G относительно свойства Р называется порожденный подграф Gsm , обладающий этим свойством и такой, что не существует другого порожденного графа Gs , у которого Хs Хsm и который так же обладает свойством Р. Так, например, если в качестве свойства Р взята сильная связанность, то максимальным сильным подграфом графа G является сильный подграф, который не содержится ни в каком другом сильном подграфе. Такой подграф называется сильной компонентой графа. Аналогично, односторонняя компонента представляет собой односторонний максимальный подграф, а слабая компонента – максимальный слабый подграф.

Например, в графе, приведенном на рис. 6.2,б, подграф, состоящий из вершин{х1, х4, х5, х6}, является сильной компонентой графа. С другой стороны подграфы, включающие вершины {х1, х6} и{х1, х5, х6}, не являются сильными компонентами (хотя и являются сильными подграфами), поскольку они содержатся в графе, состоящем из вершин {х1, х4, х5, х6} и, следовательно, не максимальные. В графе, показанном на рис. 6.2,в, подграф не содержит вершины{х1, х4, х5, х6}, является односторонней компонентой.

В графе, приведенном на рис. 6.2,г, оба подграфа, включающие вершины {х1, х5, х6} и {х2, х3, х4} являются слабыми компонентами, и у этого графа только две компоненты.

Из определений сразу же следует, что односторонние компоненты графа могут иметь общие вершины. Сильная компонента должна содержаться по крайней мере в одной односторонней компоненте, а односторонняя компонента содержится в некоторой слабой компоненте данного графа.

 

 


 

 

7. Лекция: Методы разбиения графа на максимальные сильно связные подграфы

 

 

Развернуть
Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Введение в теорию графов 1. Лекция: Графы и способы их представления

Введение в теорию графов Лекция Графы и способы их представления... Приводятся начальные сведения о графах и основные понятия и определения такие как орграф смешанный граф дубликат графа дуга петля полустепени...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Сильно связные графы и компоненты графа

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Основные определения
Граф задается множеством точек или вершин х1, х2, ..., хn и множеством линий или ребер a1, a2, ... , am, соеди

Прямые отображения
Прямым отображением 1-го порядка вершины хi является множество таких вершин графа, для которых существует дуга (хi, xj), т. е Г1( х

Обратные отображения
Обратным отображением 1-го порядка для вершины хiявляется множество элементов xjтаких, что существует дуга(xj, хi), принадлежащая множеству дуг графа, т.

Прямое транзитивное замыкание
Прямым транзитивным замыканием некоторой вершины хi – T+( хi )является объединение самой вершины хiс прямыми отображениями 1-го поря

Обратное транзитивное замыкание
Обратным транзитивным замыканием некоторой вершины хi –T-( хi )является объединение этой вершины с обратными отображениями 1-го, 2-го и т. д. n

Нахождение транзитивных замыканий по матрице смежности
Рассмотрим метод нахождения прямого транзитивного замыкания по матрице смежности, показанной на рис. 3.3,а для вершины х2графа, изображенного на рис. 3.3,б. На 1-м шаге итерации заносим

Достижимость и контрдостижимость
Задач, в которых используется понятие достижимости, довольно много. Вот одна из них. Граф может быть моделью какой-то организации, в которой люди представлены вершинами, а дуги интерпретирую

Нахождение множества вершин, входящих в путь
Если необходимо узнать о вершинах графа, входящих в эти пути, то следует вспомнить определения прямого и обратного транзитивных замыканий. Так как T+(xi) – это множество верши

Матричный метод нахождения путей в графах
Матрица смежности полностью определяет структуру графа. Возведем матрицу смежности в квадрат по правилам математики. Каждый элемент матрицы А2 определяется по формуле a(2)

Доказательство
1. Необходимость. Поскольку множество X разбивается на две части Xа и Xb , то Xа Xb = X и Xа Xb = Ø . Пусть существ

Лекция: Виды подграфов
    Пусть дан граф G = (X, A), где X = {хi}, i = 1, 2, ..., n – множество вершин, A = { ai }, i = 1, 2, ..., m – множество дуг. Подграфом

Метод Мальгранжа
Пусть дан граф G=(X, A), где X={ хi }, i =1, 2, ... , n – множество вершин, а A={ ai }, i =1, 2, ..., m – где множество дуг, описанных матрицей смежности. Алгоритм разбиени

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

Вес и длина пути
Иногда дугам графа сопоставляют числа ai сi , называемые весом или длиной, или стоимостью или ценой. В каждом конкретном случае выбирается то слово, которое ближе подходит по

Орциклы и циклы
Особую группу составляют замкнутые пути. Путь a1, a2, ...,aq называется замкнутым, если в нем начальная вершина a1 и конечная вер

Лекция: Алгоритм Дейкстра поиска кратчайших путей в графе
  Наиболее эффективный алгоритм решения задачи о кратчайшем пути первоначально дал Дейкстра . В общем случае этот метод основан на приписывании вершинам временных пометок, причем поме

Превращение пометки в постоянную
Ш А Г 3. Среди всех вершин с временными пометками найти такую, для которой L(x*i)=min[L(xi)]. Ш А Г 4. Считать пометку вершины x*i

Первая итерация
Ш А Г 2. Найдем прямое отображение для текущей рассматриваемой вершины: Г(р) = Г(х1) = { х2, х7, х8, х9 }. Все вершины, входящие в прямое отоб

Вторая итерация
Граф с текущими значениями меток вершин показан на рис. 9.3   Рис. 9.3. Пометки в конце первой итерации Ш А Г 2. Находим Г(х7) = { х

Третья итерация
Граф с текущими значениями меток вершин показан на рис. 9.4.   Рис. 9.4. Пометки в конце второй итерации Ш А Г 2. Находим Г(х2) = {х

Четвертая итерация
Ш А Г 2. Находим Г(х8) = { х1, х5, х6, х9 }. Метки вершин х5, х6 и х9 временные, следовательно, пересчитываем

Пятая итерация
Ш А Г 2. Находим Г(х4) = { х3, х5, х6, х7 }. Метки вершин х3, х5 и х6 временные, следовательно, пересчитываем

Шестая итерация
Ш А Г 2. Находим Г(х9) = {х1, х2, х6, х7, х8}. Метка вершины х6 временная, следовательно пересчитываем ее значение:

Седьмая итерация
Ш А Г 2. Находим Г(х5) = { х4, х6 }. Метка вершины х6 временная, следовательно, пересчитываем ее значение: L(х6)= min [17, 12 + 10 ]

Восьмая итерация
Ш А Г 2. Находим Г(х6) = { х3, х5, х7, х8, х9 }. Метка вершины х3 временная, следовательно, пересчитываем ее значение:

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги