Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Дисциплины:
2018-01-05 | 183 |
5.00
из
|
Заказать работу |
|
|
Подграфом графа G (ориентированного графа D) называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G (D).
Подграф называется собственным, если он отличен от самого графа.
Говорят, что вершина w ориентированного графа D (графа G) достижима из вершины v, если либо w = v, либо существует путь (маршрут) из v в w.
Граф (ориентированный граф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w.
Компонентой связности графа G (сильной связности ориентированного графа D) называется его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (ориентированного графа D).
Матрицы достижимости и связности
Пусть A (D) – матрица смежности ориентированного псевдографа D =(V, X) (или псевдографа G =(V, X)), где V ={ v 1,…, v n}. Обозначим через Ak =[ a ( k ) ij ] k -ю степень матрицы смежности A (D).
Элемент a ( k ) ij матрицы Ak ориентированного псевдографа D =(V, X) (псевдографа G =(V, X)) равен числу всех путей (маршрутов) длины k из vi в vj.
Матрица достижимости ориентированного графа D − квадратная матрица T (D)=[ tij ] порядка n, элементы которой равны
Матрица сильной связности ориентированного графа D − квадратная матрица S (D)=[ sij ] порядка n, элементы которой равны
Матрица связности графа G − квадратная матрица S (G)=[ sij ] порядка n, элементы которой равны
Пусть G =(V, X) – граф, V ={ v 1,…, v n}, A (G) – его матрица смежности. Тогда
S (G)=sign[ E + A + A 2+ A 3+… A n-1] (E - единичная матрица порядка n).
Утверждение 3. Пусть D =(V, X) – ориентированный граф, V ={ v 1,…, v n}, A (D) – его матрица смежности. Тогда
1) T (D)=sign[ E + A + A 2+ A 3+… A n-1],
2) S (D)= T (D)& TT (D) (TT -транспонированная матрица, &- поэлементное умножение).
|
Расстояния в графе
Пусть - граф (или псевдограф). Расстоянием между вершинами называется минимальная длина пути между ними, при этом , , если не пути.
Расстояние в графе удовлетворяют аксиомам метрики
1) ,
2) (не в ориентированном графе)
3)
4) в связном графе (не в ориентированном графе).
Пусть связный граф (или псевдограф).
Диаметром графа G называется величина .
Пусть .
Максимальным удалением (эксцентриситетом) в графе G от вершины называется величина .
Радиусом графа G называется величина
Центром графа G называется любая вершина такая, что .
Образ и прообраз вершины и множества вершин
Пусть ориентированный граф - некоторая вершина .
Обозначим - образ вершины ;
- прообраз вершины ;
- образ множества вершин V1;
- прообраз множества вершин V1.
Нагруженные графы
Нагруженный граф − ориентированный граф D =(V, X), на множестве дуг которого определена не которая функция , которую называют весовой функцией.
Цифра над дугой (см. рис. 5)− вес дуги (цена дуги).
Рис. 5.
Обозначения: для любого пути П нагруженного ориентированного графа D через l (П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).
Величина l называется длиной пути.
Если выбрать веса равными 1, то придем к ненагруженному графу.
Путь в нагруженном ориентированном графе из вершины v в вершину w, где v ¹ w, называется минимальным, если он имеет наименьшую длину.
Аналогично определяется минимальный маршрут в нагруженном графе.
Введем матрицу длин дуг C (D)=[ cij ] порядка n, причем
Свойства минимальных путей в нагруженном ориентированном графе
1) Если для " дуги , то " минимальный путь (маршрут) является простой цепью;
2) если минимальный путь (маршрут) то для " i, j: путь (маршрут) тоже является минимальным;
3) если − минимальный путь (маршрут) среди путей (маршрутов) из v в w, содержащих не более k +1 дуг (ребер), то − минимальный путь (маршрут) из v в u среди путей (маршрутов), содержащих не более k дуг (ребер).
|
Деревья и циклы
Граф G называется деревом если он является связным и не имеет циклов.
Граф G называется лесом если все его компоненты связности - деревья.
Свойства деревьев:
Следующие утверждения эквивалентны:
1) Граф G есть дерево.
2) Граф G является связным и не имеет простых циклов.
3) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.
4) " две различные вершины графа G можно соединить единственной (и при этом простой) цепью.
5) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл
Утверждение 4. Если у дерева G имеется, по крайней мере, 1 ребро, то у него найдется висячая вершина.
Утверждение 5. Пусть G связный граф, а − висячая вершина в G, граф получается из G в результате удаления вершины и инцидентного ей ребра. Тогда тоже является связным.
Утверждение 6. Пусть G - дерево с n (G) вершинами и m (G) ребрами. Тогда m (G)= n (G)-1.
Утверждение 7. Пусть G – дерево. Тогда любая цепь в G будет простой.
Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Пусть G – связный граф. Тогда остовное дерево графа G должно содержать n (G)-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер.
Число − цикломатическое число графа G.
|
|
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!