Площадные пространственные объекты поверхности

Полигоны представляют площадные пространственные объекты с постоянной высотой типа озера или океана или используются, чтобы разграничить проектную границу, отсечь или стереть части триангуляции. Полигоны могут также быть разделены на жесткие и мягкие. К набору массовых точек применяется алгоритм триангуляции Делоне, чтобы создать начальную TIN. Эта TIN отражает общую форму поверхности, но еще недостаточно изображает резкие изменения топографии типа потоков и гребней.

Когда добавлены линии перегиба, то в пересечениях с начальными ребрами создаются новые узлы, если те ребра представляют ребра разрыва. TIN обновляется, чтобы включить эти новые узлы. Теперь TIN уточняется, чтобы моделировать области постоянных высот и границы интерполяции. После того, как TIN достигла этой стадии, вы можете исследовать ее и прибавлять любые дополнительные линии перегиба, массовые точки или полигоны, чтобы далее исправлять и улучшать модель поверхности TIN.

TIN может быть изображена условными знаками, показывающими высоту, экспозицию склона, крутизну, или другие характеристики поверхности. На этой карте показаны высоты.

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

Жесткие линии перегиба или полигоны символизируют пространственные объекты, которые соответствуют существенному изменению крутизны.

Мягкие линии перегиба или полигоны представляют пространственные объекты поверхности, которые не отмечают нарушение наклона, но прибавляют ребра к TIN, чтобы лучше моделировать поверхность

33. Основные понятия теории графов. Степень вершины. Пути, контуры, маршруты, цепи, циклы.

В общем смысле граф G представляется как множество вершин или узлов V, соединённых рёбрами E. В строгом определении графом называется такая пара множеств G = (V, E), где V есть подмножество любого счётного множества, а E — подмножество V × V.

Рис. 1 – Пример графа

Граф, в котором направление ребер, соединяющих вершины, не выделяется называется неориентированным; граф, в котором задается направление ребер, называется ориентированным. Ребра графа, для которых задано их направление, называются дугами.

Ориентированный граф или орграф G = (V, E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v → w ведёт от вершины v к вершине w, при этом вершина w смежная с вершиной v.

Дугу между вершинами i и j (i, j V), будем обозначать (i, j). Число дуг графа будем обозначать m(V=(v₁, v₂, …, v_m)).

Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми рёбрами (дугами), соединяющими вершины из этого множества. Если в графе удалить часть рёбер (дуг), то получим частичный граф.

Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) – инцидентным соответствующим вершинам.

Граф, в котором для каждой пары вершин v_i, v_j, существует ребро, инцидентное v_i и инцидентное v_j (каждая вершина соединена ребром с любой другой вершиной) называется полным графом.

Граф, для которого из (i, j) V следует (j, i) V называется симметричным. Если из (i, j) V следует (j, i) V, то соответствующий граф называется антисимметричным.

Вершины в графе могут отличаться друг от друга тем, скольким рёбрам они принадлежат (инцидентны).

Степенью вершины называется число рёбер графа, которым инцидентна эта вершина. Степень графа ещё называют его валентностью и обозначают d(v). Вершина графа, для которой d(v) = 0, является изолированной, для которой d(v) = 1 - висячей.

Вершина называется нечётной, если d(v) - нечётное число. Вершина называется чётной, если d(v) - чётное число. Степень каждой вершины полного графа на единицу меньше числа его вершин.

В графе G(V, E) сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа. Число нечётных вершин любого графа чётно. Во всяком графе с n вершинами, где n 2, всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

Если в графе с n вершинами (n 2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдётся либо в точности одна вершина степени 0, либо в точности одна вершина степени n - 1.

Маршрут в графе — это чередующаяся последовательность вершин и рёбер v₀, e₁, v₁, e₂, v₂,..., e_k, v_k, в которой любые два соседних элемента инцидентны. Если v₀=v_k, то маршрут замкнут, иначе открыт.

Путь — последовательность рёбер в неориентированном графе или дуг в ориентированном графе, такая, что конец одной дуги (ребра) является началом другой дуги (ребра). Иначе, путь – это последовательность вершин и дуг (рёбер), в которой каждый элемент инцидентен предыдущему и последующему. Может рассматриваться как частный случай маршрута.

Простой путь – путь, в котором ни одна дуга не встречается дважды.

Контур – путь, у которого конечная вершина совпадает с начальной вершиной.

Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).

Цепь в графе — маршрут, все рёбра которого различны. Если все вершины (а тем самым и рёбра) различны, то такая цепь называется простой (элементарной). В цепи v₀, e₁,..., e_k, v_k вершины v₀ и v_k называются концами цепи. Цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v, обозначается . Для орграфов цепь называется орцепью.

Замкнутая цепь называется циклом.

Можно определить простые и элементарные цепи.

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

Простая цепь (цикл, путь, контур), содержащая все рёбра (дуги) графа называется эйлеровой цепью.

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

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

34. Ориентированные графы. Плоские графы.

Если элементы множества Е графа G(V, E) - упорядоченные пары, то граф называется ориентированным или орграфом.

Ребро e графа G называется ориентированным, если одну вершину считают началом ребра, а другую – концом, на рисунке его изображают стрелкой между вершинами. Таким образом, граф, все рёбра которого ориентированы, называется ориентированным графом.

Одна и та же вершина ориентированного графа может служить началом для одних рёбер и концом для других, поэтому различают две степени вершины: степень выхода и степень входа.

Степенью выхода вершины орграфа называется число выходящих из вершины рёбер.

Степенью входа вершины орграфа называется число входящих в вершину рёбер.

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

Изолированной вершиной называется вершина, у которой и степень входа и степень выхода равна 0.

Источником называется вершина, степень выхода которой положительна, а степень входа равна 0.

Стоком называется вершина, степень входа которой положительна, а степень выхода равна 0.

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

Простым путём в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза.

Замкнутый путь в ориентированном графе называется ориентированным циклом или контуром.

Длиной пути называется число рёбер в этом пути.

Полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одним ориентированным ребром.

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

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

Мультиграфом называется граф, в котором пара вершин соединяется несколькими различными рёбрами. Для ориентированного мультиграфа вершины v_i и v_j могут соединяться несколькими рёбрами в каждом из направлений.

Граф G(V, E) называется плоским, если на плоскости его можно изобразить так, что все пересечения его рёбер являются вершинами графа G(V, E).

В качестве характеристики плоского представления графа вводится понятие грани.

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

35. Операции над графами.

Рассмотрим графы G₁(V₁, E₁) и G₂(V₂, E₂).

а) Дополнением графа G₁(V₁, E₁) называется граф G1(V1, E1), множеством вершин которого является множество V1, а множеством его рёбер является множество E1 = {eÎ V1 ´ V2: eÏ E1}.

б) Объединением графов () 1 1 1 G V, E и G2 (V2, E2) при условии, что V1 Ç V2 = Æ; E1 Ç E2 = Æ, называется граф G1(V1, E1)È G2 (V2, E2), множеством вершин которого является множество V1 È V2, а множеством его рёбер является множество. 1 2 E È E

в) Пересечением графов () G1 V1, E1 и G2 (V2, E2) называется граф G1(V1, E1)Ç G2 (V2, E2), множеством вершин которого является множество V1 Ç V2, а множеством его рёбер является множество E1Ç E2.

г) Суммой по модулю два графов () 1 1 1 G V, E и G2 (V2, E2) при условии, что V1 Ç V2 = Æ; E1 Ç E2 = Æ, называется граф G1(V1, E1)Å G2(V2, E2), множеством вершин которого является множество V1 È V2, а множеством его рёбер – множество E1 Å E2. Т. е. этот граф не имеет изолированных вершин и состоит только из рёбер, присутствующих либо в первом графе, либо во втором графе, но не в обоих графах одновременно.

36. Способы задания графов.

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

Аналитический способ задания графов Граф G(V, E) задан, если задано множество элементов V и отображение E множеств V в V. Отображение Е может быть как однозначным, так и многозначным.

Пусть дано множество V = {v1, v2,...vn}, которое имеет мощность V = n.

Для того чтобы задать отображение Е на V, необходимо каждому элементу vi Î V поставить в соответствие некоторое подмножество множества V, которому соответствует отображение Е. Это подмножество обозначают через Evi. Поэтому Evi Ì V. Совокупность двух объектов: множества V и отображение Е на V задаёт некоторый граф.

Другой формой аналитического способа задания является задание графа как совокупности множества элементов V и подмножества множества упорядоченных пар vi, v j Î V ´ V.

Геометрический способ задания графов

Множество элементов V графа G изображают кружками, это множество вершин. Каждую вершину vi Î V соединяют линиями с теми вершинами vi Î V, для которых выполняется условие vi Î Evi. Множество линий, которое соответствует множеству упорядоченных пар vi, v j, есть множество рёбер.

Матричный способ задания графов

Квадратная матрица

элементами которой являются нули и единицы, а также некоторое число m, называется матрицей смежности графа G(V, E) тогда и только тогда, когда её элементы образуются по следующему правилу: элемент aij, стоящий на пересечении vi - й строки и v j - го столбца, равен единице, если имеется ребро, идущее из вершины vi в вершину v j, и aij равен нулю в противном случае. Элемент aij равен единице, если при вершине vi имеется петля, и равен нулю в противном случае. Элемент aij равен некоторому числу m, где m – число рёбер графа, идущее из вершины vi в вершину v j.

Таким образом, если граф G(V, E) задан одним из указанных способов: аналитическим, геометрическим или матричным, всегда можно перейти к любому другому способу задания. Наиболее часто для задания графа используется аналитический и матричный способы, а геометрический способ служит для иллюстрации полученных результатов.

37. Сетевые модели. Обзор применения сетевых моделей. Основные определения.

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

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

2. Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог.

3. Определение максимальной пропускной способности трубопровода для транспортировки угольной пульпы от угольных шахт к электростанциям.

4. Определение схемы транспортировки нефти от пунктов нефтедобычи к нефтеперерабатывающим заводам с минимальной стоимостью транспортировки.

5. Составление временного графика строительных работ (определение дат начала и завершения отдельных этапов работ).

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

1. Алгоритм нахождения минимального остовного дерева.

2. Алгоритм нахождения кратчайшего пути.

3. Алгоритм определения максимального потока.

4. Алгоритм минимизации стоимости потока в сети с ограниченной пропускной способностью (пример 4).

5. Алгоритм нахождения критического пути.

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