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

Раздел Транспорт
/
Компоненты сильной связности графа

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

Выберите учебное заведение

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

Компоненты сильной связности графа - раздел Транспорт, Лекция № 12. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ Понятие Сильной Связности Относится Только К Орграфам. Основ...

Понятие сильной связности относится только к орграфам.

Основание орграфа – неограф с теми же вершинами, но ребрами вместо соответствующих дуг.

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

Вершина u достижима из вершины v, если существует маршрут из v в u.

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

Граф называется ориентируемым, если он является основанием сильно связного графа.

Пример 13.3. Найти компоненты сильной связности графа, изображенного на рис. 13.3.

Рис. 13.3

Решение. Матрица смежности графа имеет вид

В графе 7 дуг, поэтому наибольший путь будет не длиннее семи. Построим матрицу достижимости:

Выделим из этой матрицы главные миноры максимального порядка, не содержащие нули. Если граф связен, то в матрице будут строки, не содержащие нулей. Это строки 2, 4, 6:

Минор со строками и столбцами с этими номерами соответствует одной компоненте связности:

Удалим из матрицы строки и столбцы с этими номерами, Получим минор, соответствующий второй компоненте связности:

Итак, в графе две компоненты сильной связности: подграф с вершинами 1, 3, 5 и подграф с вершинами 2, 4, 6.

Рис. 13.4

На рис. 13.4 (а, б) показаны обе компоненты сильной связности в виде отдельных графов. Общее число ребер в компонентах меньше размера исходного графа. Дуга [2, 3] не вошла ни в одну компоненту.

Развернуть

Открыть в широком формате

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

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

Лекция № 12. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ

Основные определения Каждое ребро e из E инцидентно ровно двум вершинам и... Циклы... Маршрут в котором начало и конец совпадают циклический Циклический маршрут называется циклом если он цепь...

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

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

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

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

Основные определения
Граф – это совокупность двух множеств: вершин

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

Эйлерова цепь
Маршрут в неографе, в котором все ребра разные, называется цепью. Цепь в графе называется эйлеровой, если она содержит все ребра и все вершины графа.

Реберный граф
Рассмотрим два графа G и L(G). Граф G имеет произвольную форму, а вершины графа L(G) расположены на ребрах графа G. В этом случае граф L(G) называется

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

Ранг-полином графа
Ранг графа определяется как , где n – число вершин, k – число компонент связности графа. Ко

Основные определения
Ребро в графе G может быть ориентированным и иметь начало и конец. Такое ребро называется

Маршруты в орграфе
Задачи, связанные с маршрутами в орграфе, имеют большое практическое значение, что и дает стимул к развитию и совершенствованию методов их решения. Наиболее часто встает вопрос о минимальных и макс

Транзитивное замыкание
Прямым (декартовым) произведением множеств A и B называется множество

Основные определения
Дерево – связный граф без циклов. Лес (или ациклический граф) – неограф без циклов. Компонентами леса являются деревья.

Центроид дерева
Ветвь к вершине v дерева – это максимальный подграф, содержащий v в качестве висячей вершины. Вес

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