Связанные понятия
Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь. Другими словами, нет изолированной вершины ( такой, которая не имеет соответствующих ей рёбер (называется "ребра, инцидентные вершине 1" (или 2) ).
Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.
Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.
Дерево — это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице).
Подробнее: Глоссарий теории графов Упоминания в литературе
Поместим на вершину куба пирамиду. У наших многогранников есть общая грань, и их следует изобразить как две точки (два объема), соединенные одной из линий (грань, которая соединяет объемы). У куба осталось пять свободных граней (пять линий), а у пирамиды – четыре (четыре линии). Аналогично можно изобразить любые комбинации различных
многогранников: объемные полиэдры становятся точками, или узлами, а плоские грани – линиями, соединяющими узлы. Математики называют такие диаграммы графами.
в) оба луча нумеруются от 1 до N, начиная с их крайних верхних точек и до
точек, соседних с вершиной. При этом сама вершина тоже может быть пронумерована. Например, если на обоих лучах по 15 точек, то вершине будет присвоен номер 16.
По всеобщему признанию, литература и искусство являются частью человеческой культуры. Ценность же математики, как правило, видят в её практических приложениях. Но наличие практических приложений не должно препятствовать тому, чтобы и математика рассматривалась как часть человеческой культуры. Да и сами эти приложения, если брать древнейшие из них – такие как, скажем, использование египетского треугольника (т. е. треугольника со сторонами 3, 4, 5) для построения прямого угла – также принадлежат общекультурной сокровищнице человечества. (Кому, чьей сокровищнице принадлежит шестигранная форма пчелиных сот, обеспечивающая максимальную вместимость камеры при минимальном расходе воска на строительство её стен, – этот вопрос мы оставляем читателю для размышления.) В Древнем Египте, чтобы получить прямой угол, столь необходимый при строительстве пирамид и храмов, поступали следующим образом. Верёвку делили на 12 равных частей, точки деления, служащие границами между частями, помечали, а концы верёвки связывали. Затем за верёвку брались три человека, удерживая её в трёх точках, отстоящих друг от друга на 3, 4 и 5 частей деления. Далее верёвку натягивали до предела – так, чтобы получился треугольник. По теореме, обратной к теореме Пифагора, треугольник оказывался прямоугольным, причём тот человек, который стоял между частью длины 3 и частью длины 4, оказывался в
вершине прямого угла этого треугольника.
И наконец, моделирование на основе кусков ( patch modelling) является еще одним распространенным способом создания объектов. Последние в этом случае формируются из кусков поверхностей, представляющих собой фрагменты обычной сетки, заключенные в составленную из сплайнов Безье треугольную или четырехугольную рамку. Построение модели осуществляется путем манипуляции вершинами, расположенными по углам куска, и исходящими из этих вершин касательными векторами. Можно сшивать куски между собой и
отделять вершины и элементы (рис. 1.13).
Объедините все сплайны в одну форму командой Attach (Присоединение) из свитка Geometry (Геометрия) – обязательно в том же порядке, в каком будет создаваться поверхность, то есть от самого нижнего сплайна к самому верхнему. Затем перейдите на уровень редактируемых вершин, активизировав в дереве подобъектов строку Vertex (Вершина), и в области Display (Показывать) свитка Selection (Выделение) установите флажок Show Vertex Numbers (Показать нумерацию вершин). Как видно из рис. 1.19, все сплайны имеют разное
количество вершин и порядок построения (по часовой стрелке и против часовой стрелки).
Связанные понятия (продолжение)
Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.
Полный двудольный граф (биклика) — специальный вид двудольного графа, у которого любая вершина первой доли соединена со всеми вершинами второй доли вершин.
Двудо́льный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.
В теории графов
паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.
В теории графов графом-циклом называется граф, состоящий из единственного цикла, или, другими словами, некоторого числа вершин, соединённых замкнутой цепью. Граф-цикл с n вершинами обозначают как Cn. Число вершин в Cn равно числу рёбер и каждая вершина имеет степень 2, то есть любая вершина инцидентна ровно двум рёбрам.
Подробнее: Граф-цикл
Остовное дерево графа состоит из минимального подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрам.
Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.
Плана́рный граф — граф, который может быть изображён на плоскости без пересечения рёбер. Иначе говоря, граф планарен, если он изоморфен некоторому плоскому графу, то есть графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — непересекающиеся кривые на ней. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, так называемая внешняя грань.
Гамильто́нов граф — математический объект теории графов. Представляет собой граф (набор точек и соединяющих их линий), который содержит гамильтонов цикл. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу.
Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.
Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики являются одной из основных концепций теории графов и используются во многих других математических задачах и построениях с графами. Клики изучаются также в информатике — задача определения, существует ли клика данного размера в графе (Задача о клике) является NP-полной. Несмотря на эту трудность, изучаются многие алгоритмы для поиска клик.
Подробнее: Клика (теория графов)
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
Подробнее: Рёберный граф
В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества...
Подробнее: Граф гиперкуба
Окрестность часто обозначается как NG(v) или (если известно, о каком графе идёт речь) N(v). То же самое обозначение окрестности может использоваться для ссылки на множество смежных вершин, а не на соответствующий порождённый подграф. Окрестность, описанная выше, не включает саму вершину v и об этой окрестности говорят как об открытой окрестности вершины v. Можно определить окрестность, включающую v. В этом случае окрестность называется закрытой и обозначается как NG. Если не указано явно, окрестность...
Мост — ребро в теории графов, удаление которого увеличивает число компонент связности. Такие рёбра также известны как разрезающие рёбра, разрезающие дуги или перешейки. Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле.
В теории графов графом пересечений называется граф, представляющий схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств.
Подробнее: Граф пересечений
В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.
Подробнее: Внешнепланарный граф
Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связны. Две вершины s и t любого графа сильно связны, если существует ориентированный путь из s в t и ориентированный путь из t в s.
Подробнее: Компонента сильной связности в орграфе
Кубический граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.
Автоморфизм графа есть отображение множества вершин на себя, сохраняющее смежность. Множество таких автоморфизмов образует вершинную группу графа или просто группу графа. Группа подстановок на множестве ребер называется реберной группой графа, которая тесно связана с вершинной...
Визуализация или отображение графов, как ответвление теории графов, относящееся к топологии и геометрии — двумерное представление графа. В основном, это графическое представление укладки графа на плоскость (как правило, допускается пересечение рёбер), направленное, обычно, на удобное отображение некоторых свойств графа, или моделируемого объекта.
Сильно регулярный граф является дистанционно-регулярным с диаметром 2, но только в том случае, когда μ не равно нулю.
Характеризация запрещёнными графами — это метод описания семейства графов или гиперграфов путём указания подструктур, которым запрещено появляться внутри любого графа в семействе.
Раскраска графов находит применение и во многих практических областях, а не только в теоретических задачах. Помимо классических типов проблем, различные ограничения могут также быть наложены на граф, на способ присвоения цветов или на сами цвета. Этот метод, например, используется в популярной головоломке Судоку. В этой области всё ещё ведутся активные исследования.
В теории графов неориентированный граф H называется минором графа G, если H может быть образован из G удалением рёбер и вершин и стягиванием рёбер.
Подробнее: Минор графа
Хромати́ческое число ́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G).
Ориентация неориентированного графа — это назначение направлений каждому ребру, что превращает исходный граф в ориентированный граф.
В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер (их также называют «параллельными»), то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром (тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две).
Подробнее: Мультиграф
Граф решётки — это граф, рисунок которого, вложенный в некоторое евклидово пространство Rn, образует регулярную мозаику. Это подразумевает, что группа биективных преобразований, переводящая граф в себя, является решёткой в теоретико-групповом смысле.
Подробнее: Решётка (теория графов)
Эйлеров цикл — эйлеров путь, являющийся циклом, то есть замкнутый путь, проходящий через каждое ребро графа ровно по одному разу.
В теории графов граф сравнимости — это неориентированный граф, в котором пары элементов соединены ребром, если эти элементы сравнимы в некотором частичном порядке. Графы сравнимости также называют транзитивно-ориентируемыми графами, частично упорядочиваемыми графами и графами вложенности.
В теории графов стягивание ребра — это операция, которая удаляет ребро из графа, а до этого связанные ребром вершины сливаются в одну вершину. Стягивание ребра является фундаментальной операцией в теории о минорах графов. Отождествление вершин — другая форма этой операции с более слабыми ограничениями.
Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм...
Периферийный цикл в неориентированном графе является, интуитивно, циклом, который не отделяет любую часть графа от любой другой части. Периферийные циклы (или, как они сначала назывались, периферийные многоугольники, поскольку Тат называл циклы «многоугольниками»), первым изучал Тат и они играют важную роль в описании планарных графов и в образовании циклических пространств непланарных графов.
Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа.
Обхват в теории графов — длина наименьшего цикла, содержащегося в данном графе. Если граф не содержит циклов (то есть является ациклическим графом), его обхват по определению равен бесконечности.
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины (5 и более рёбер).
Подробнее: Совершенный граф
В теории графов
граф называется хордальным, если каждый из его циклов, имеющих четыре ребра и более, имеет хорду (ребро, соединяющее две вершины цикла, но не являющееся его частью).
Зада́ча о кратча́йшем пути ́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
Число очередей графа — это инвариант графа, определённый аналогично стэковому числу (толщине книги) и использующий упорядочение FIFO (первый вошёл, первый вышел, очередь) вместо упорядочения LIFO (последним вошёл, первым вышел, стэк).
Граф Кэли — граф, который строится по группе с выделенной системой образующих. Назван в честь Артура Кэли.
В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом...
Подробнее: Корона (теория графов)
Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач.
Дистанционно-регулярный граф — регулярный граф такой, что для любых двух вершин v и w число вершин с расстоянием j от v и расстоянием k от w зависят только от j, k и i = d(v, w).
Упоминания в литературе (продолжение)
Если предложенная для фиксации точка является частью какой-либо фигуры, то в зависимости от направления прилежащих линий отклонение зрительной оси от заданного направления может оказаться то большим, то меньшим. Так, при предъявлении четырех изолированных точек-стимулов, расположенных в вершинах квадрата со стороной 40°, отклонение зрительной оси составляет 2–2,5°. Если эти точки соединены прямыми линиями, образующими квадрат, отклонение увеличивается
до 3–3,5°. При фиксации вершин косоугольного ромба отклонение для острых углов оказывается большим, чем для тупых (рисунок 1.7).
Являясь единой частью и, своего рода, связующим звеном подземной «условной» и видимой пирамидами, основание призвано обеспечить энергетическую взаимосвязь между характерными точками: подземной и надземной вершинами и фокусом. Следовательно, его профиль должен быть симметричным относительно линии ас, т. е. иметь выпуклость
в сторону, противоположную вершине реальной пирамиды. Поэтому проектировать основание следует как двояковыпуклую линзу, что логически сочетается с функциональным назначением конструкции. В соответствии с особенностями двояковыпуклой линзы, нижняя поверхность будет являться зеркальным отображением надземного профиля основания, имеющего радиус кривизны R3 = 21,40061154 ? К.
Создайте новую сцену и задайте сантиметры в качестве единиц измерений. Сделайте активным окно Top (Сверху) и постройте сплайновый прямоугольник (объект-лекало) шириной 40 см и высотой 20 см. За 40 см мы примем высоту ножки стула до обечайки, на которой держится сиденье. Создайте четыре сплайновые формы, как показано на рис. 2.21. Две верхние формы (помечены на рисунке как A и B) будут линиями ножки стула в двух разных проекциях, прямая линия (C) – начальной лофтинговой формой лофт-объекта, а прямоугольник (D) – формой сечения. К лофтинговой форме можно применить более чем одну форму сечения. При этом важно помнить, что
количество вершин в данных формах должно быть идентичным. Кроме того, начальные вершины и порядок нумерации также должны совпадать, чтобы не получилось перекручивание формы. Необходимо следить и за тем, чтобы длина всех линий была по возможности равной.
Кроме того, Международная система единиц содержит две достаточно важные дополнительные единицы, необходимые для измерения плоского и телесного углов. Так, единица плоского угла – это радиан, или сокращенно рад, представляющий собой угол между двух радиусов окружности, длина дуги между которыми равняется радиусу окружности. Если речь идет о градусах, то радиан равен 57°17' 48''. А стерадиан, или ср, принимаемый за единицу телесного угла, представляет собой,
соответственно, телесный угол, расположение вершины которого фиксируется в центре сферы, а площадь, вырезаемая данным углом на поверхности сферы, равна площади квадрата, сторона которого равна длине радиуса сферы. Другие дополнительные единицы СИ используются для формирования единиц угловой скорости, а также углового ускорения и т. д. Радиан и стерадиан используются для теоретических построений и расчетов, поскольку большая часть значимых для практики значений углов в радианах выражаются трансцендентными числами. К внесистемным единицам относятся следующие:
Обратите внимание на то, что треугольники выбирают так, что одна из сторон должна быть параллельна одной из диагоналей
матрицы, тогда вершины треугольников укажут нужные тройки чисел, включая тройки чисел диагоналей.
В пустыне с барханами столь естественного способа уже нет. Можно в качестве координатной выбрать сетку из мировых линий самых быстрых бусинок, но есть и другие варианты. Один из них – нарисовать нечто вроде параллелей и меридианов, аналогично тому, как они изображаются на поверхности Земли. Этот способ похож на рисование прямых в случае плоской пустыни.
Другой вариант – из вершины каждого бархана рисуются лучи во все стороны, а перпендикулярно им изображаются уровни высот. В этом случае необходимо как-то идентифицировать координатные сетки в областях между барханами, но этот вопрос сейчас не очень важен для нас. К слову сказать, так рисуются геодезические карты.
Приведенные выше примеры построения в различных системах координат демонстрируют возможности
ввода абсолютных значений вершин – точек, отсчитываемых от начала координат. Такая методика не всегда удобна и поэтому в большинстве случаев при разработке чертежа используют относительные координаты точек. Согласно этому режиму за начало отсчета принимаются координаты последней введенной точки, т. е. начало координат как бы «переносится» в точку, которая была введена на предыдущем шаге построения или редактирования объекта, и следующая координата будет вычисляться уже от нее.
Вершины подводных гор имеют коническую или куполообразную форму. Склоны крупных гор, как правило, выгнуты вверх. Угол крутизны редко превышает 14°. У объектов меньших размеров данный параметр может достигать 35°. Подводные горы от вершины до основания покрыты в основном слоем морских осадков.
Линия водораздела проводится перпендикулярно к горизонталям. Нужно учитывать, что в самых высоких местах хребтов и вершин линия водораздела делит пополам пространство, заключенное между замкнутой горизонталью,
если не указана отметка вершины.
Кумулятивная кривая (кривая сумм) – ломаная, составленная по последовательно суммированным, т.е. накопленным частотам или относительным частотам. При построении кумулятивной кривой дискретного признака на ось абсцисс наносятся значения признака, а ординатами служат нарастающие итоги частот. Соединением
вершин ординат прямыми линиями получают кумуляту. При построении кумуляты интервального признака на ось абсцисс откладываются границы интервалов и верхним значениям присваивают накопленные частоты. Кумулятивную кривую называют полигоном накопленных частот.
В строке находит завершение метрическая схема дротткветта. Существенно,
что все ее три вершины равноправны, т. е. могут быть выделены аллитерацией и/или хендингом. Во фьордунге находят завершение звуковые повторы дротткветта. Строка и фьордунг выделяются при этом только как формальные, но не смысловые единства. Напротив, хельминг выделяется прежде всего как смысловое единство: это минимальная композиционная единица, в которой находит завершение синтаксический орнамент, образуемый переплетаемыми и вставными предложениями (ср. выше образец дротткветтной висы).
Не останавливаясь на многочисленных данных о наличии закономерностей, описываемых числами Фибоначчи, в строении многих видов животных, основное внимание уделим человеку. Общее число костей скелета человека близко к 233, т. е. к одному из чисел Фибоначчи. Позвоночник человека состоит из 33 (34) позвонков (у позвоночных животных их насчитывается 34 или 55), грудина – из 3 костей. Череп включает 8 костей, конечности представлены 3 сегментами. Кисть насчитывает 8 костей запястья и 5 – пясти, 5 пальцев, каждый палец имеет три фаланги, за исключением большого пальца. Трудно предположить, что все это случайные совпадения. Более вероятно наличие определенной закономерности развития организма, от
простейших до «вершины эволюции» – человека. Дискретность «по Фибоначчи» прослеживается не только в скелете, но и в других органах. В теле человека насчитывают 630 мышц, составляющих 0,4 его массы. Следует отметить, что 610 является числом Фибоначчи, а 0,382 соответствует золотой пропорции при делении меньшей части на целое. Делая первый шаг, человек приводит в движение 300 мышц, в том числе 144 на позвоночном столбе (144 – число Фибоначчи). От головного мозга отходят 12 пар нервов, а от спинного – 31 пара. В строении головного мозга различают 7 частей: кора, мозолистое тело, мозжечок, мозговой желудочек, мост, продолговатый мозг, гипофиз. В основании головного мозга выделяют 8 частей, выполняющих различные функции. В теле человека насчитывается 8 различных желез внутренней секреции (Суббота А. Г., 1994a).
Горные породы, формирующие кору Земли, как мы помним, бывают изверженные – первичные, образовавшиеся при охлаждении и затвердевании магмы, и осадочные – вторичные, образовавшиеся в результате эрозии и накопления осадков на дне водоемов. Осадочные породы почти полностью покрывают поверхность суши, формируя (в числе прочего) значительную часть высочайших горных систем. Это означает, что порода, из которой слагаются
ныне вершины Альп или Гималаев, когда-то формировалась под водой, ниже уровня моря. Поразительно, не так ли? Хотя любой геолог считает это обстоятельство совершенно тривиальным.
Не менее важна проблема измерения времени. Оно основано на вращении Земли вокруг Солнца и своей оси. Поскольку земная орбита – это эллипс, то скорость движения Земли по ней неравномерна, вследствие чего и скорость видимого движения Солнца по эклиптике тоже отличается неравномерностью. Светила в течение суток в своем видимом движение два раза пересекают небесный меридиан. Момент, когда центр светила пересекает небесный меридиан,
называется кульминацией (от лат. culmen – вершина») светила. Она бывает верхней и нижней. Момент первой называется истинным полднем, момент второй – истинной полночью. Промежуток же между ними – полусутками. И верхняя, и нижняя кульминации могут приниматься за начало или конец промежутка времени (суток), который астролог выбирает в качестве единицы.
Сделать это можно так. От линии середины вытачки проведите вспомогательные перпендикуляры влево и вправо на величину половины раствора вытачки.
Соедините эти точки с вершиной вытачки, получая вытачку с уравненными сторонами. И последнее: подправьте линию талии. Он должна подходить к концам перпендикуляров. При складывании или застрачивании вытачки линия талии принимает исходное положение.