Образ и прообраз вершины и множества вершин
Пусть ориентированный граф - некоторая вершина .
Обозначим - образ вершины ; - прообраз вершины ; - образ множества вершин 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.
Популярное: Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (803)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |