Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
2018-01-30 | 163 |
5.00
из
|
Заказать работу |
|
|
Графы формально описывают множество близких ситуаций. Самым привычным примером служит карта автодорог, на которой изображены перекрестки и связывающие их дороги. Перекрестки являются вершинами графа, а дороги — его ребрами. Графы могут быть ориентированы (подобно улицам с односторонним движением) или взвешены, когда каждой дороге приписана стоимость путешествия по ней (если, например, дороги платные).
С формальной точки зрения граф представляет собой упорядоченную пару множеств G = (V, Е), первое из которых состоит из вершин (узлов) графа, а второе — из его ребер. Ребро связывает между собой две вершины. При работе с графами часто решается вопрос, как проложить путь из ребер от одной вершины графа к другой. В этом случае говорят о движении по ребру, что означает переход из вершины А графа в другую вершину 5, связанную с ней ребром АВ (ребро графа, связывающее две вершины, для краткости обозначается этой парой вершин). В этом случае говорят, что ребро А примыкает к ребру В или что эти две вершины соседние.
Граф может быть ориентированным или нет. Ребра неориентированного графа, чаще всего называемого просто графом, можно проходить в обоих направлениях (рис. 14.26). В этом случае ребро — это неупорядоченная пара вершин, его концов.
5
Граф G = ({1, 2, 3, 4, 5 }, {{1, 2}, {1, 3 }, Рис. 14.26. Неориентированный граф
В ориентированном графе, или орграфе, ребра представляют собой упорядоченные пары вершин: первая вершина — это начало ребра, вторая — его конец (рис. 14.27).
Полный граф — это граф, в котором каждая вершина соединена со всеми остальными. Количество ребер в полном графе без петель с N вершинами равно (Л/2 -ЛГ)/2. В полном ориентированном графе разрешается переход из любой вершины в любую другую. Поскольку в графе переход по ребру разрешается в обоих направ-
|
14.4. Представление и обработка данных разного типа 421
лениях, а переход по ребру в орграфе — только в одном, в полном орграфе в два раза больше ребер, то есть их количество равно N2 - N.
4 *—'
Ориентированный
Рис. 14.27. Ориентированный граф
Подграф (VS,ES) графа или орграфа (VyE) состоит из некоторого подмножества вершин, Vs С V, и некоторого подмножества ребер, их соединяющих, Es С Е.
Путь в графе или орграфе — это последовательность ребер, по которым можно поочередно проходить. Другими словами, путь из вершины А в вершину В начинается в Л и проходит по набору ребер до тех пор, пока не будет достигнута вершина В. С формальной точки зрения путь из вершины Vx в вершину Vy — это последовательность ребер графа:
Необходимо, чтобы любая вершина встречалась на таком пути не более, чем однажды. У всякого пути есть длина — количество ребер в нем. Длина пути АВ, ВС, СДДЕ равна 4.
Граф или орграф называется связным, если всякую пару узлов можно соединить по крайней мере одним путем. Цикл — это путь, который начинается и кончается в одной и той же вершине. В ациклическом графе или орграфе циклы отсутствуют. Связный ациклический граф называется неукорененным деревом. Структура неуко-рененного дерева такая же, как и у дерева, только в нем не выделен корень. Однако каждая вершина неукорененного дерева может служить его корнем.
Информацию о графах или орграфах в пригодном для обработки компьютерными алгоритмами виде можно хранить двумя способами: в виде матрицы примыканий и в виде списка примыканий^.
Матрица примыканий обеспечивает быстрый доступ к информации о ребрах графа, однако, если в графе мало ребер, эта матрица будет содержать гораздо больше пустых клеток, чем заполненных. Длина списка примыканий пропорциональна числу ребер в графе, однако при пользовании списком время получения информации о ребре увеличивается.
|
1 В определенных конкретных случаях может потребоваться представления и в других формах, также пригодных к обработке на компьютере: в виде матриц инцидентности или матриц смежности, а также других структур для представления «веса» и «цвета» связей, пометок вершин и т. д.
|
|
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!