Связанные понятия
Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.
Дерево — это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.
В теории графов вершиной называется фундаментальная единица, образующая графы — неориентированный граф состоит из множества вершин и множества рёбер (неупорядоченных пар вершин), в то время как ориентированный граф состоит из множества вершин и множества дуг (упорядоченных пар вершин). На рисунках, представляющих граф, вершина обычно обозначается кружком с меткой, ребро — линией, дуга — стрелкой, соединяющей вершины.
Подробнее: Вершина (теория графов)
Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь. Другими словами, нет изолированной вершины ( такой, которая не имеет соответствующих ей рёбер (называется "ребра, инцидентные вершине 1" (или 2) ).
Визуализация или отображение графов, как ответвление теории графов, относящееся к топологии и геометрии — двумерное представление графа. В основном, это графическое представление укладки графа на плоскость (как правило, допускается пересечение рёбер), направленное, обычно, на удобное отображение некоторых свойств графа, или моделируемого объекта.
Упоминания в литературе
В нашей теории отбрасываем рисунки многогранников и оставляем только графы. Математика, описывающая квантовые состояния объема и площади, обеспечивает нас набором правил, указывающих, как линии могут соединять узлы и какие числа могут располагаться в различных местах диаграммы. Каждое квантовое состояние соответствует одному из графов, и каждому графу, удовлетворяющему правилам,
соответствует квантовое состояние. Графы представляют собой удобную краткую запись возможных квантовых состояний пространства.
Сеть (network) – популярнейшее понятие системной биологии, повсеместно пронизывающее современную культуру, не только в рамках биологии или науки в целом[41]. В самом деле, трудно придумать более естественный способ представления связей между многочисленными объектами, чем сеть (в математике рассматриваемую как ориентированный или неориентированный граф). В биологическом контексте узлами (или иначе – вершинами) сети часто представляют гены или белки, а ребрами (связями между узлами) обозначают их взаимодействия, которые могут быть физическими, генетическими или регуляторными (Barabasi and Oltvai, 2004). К настоящему времени разработано множество методов описания и сравнения структур (топологий) сетей (табл. 4–1). Наиболее часто для анализа используется понятие функции распределения степеней вершин, где под степенью вершины понимают число ребер, связывающих эту вершину с другими. Сравнение таких функций, выполненное для сетей различного типа, показало принципиальное отличие биологических сетей (а также многих небиологических, включая Интернет) от случайных графов: случайные графы имеют колоколообразное распределение Пуассона, а для биологических сетей распределения описываются степенной функцией (табл. 4–1). Сети, имеющие степенные
функции распределения степеней вершин, называют масштабно-инвариантными сетями, так как графики их функций внешне не меняются при масштабировании (обратите внимание на прямую линию в двойных логарифмических координатах на табл. 4–1). Такие сети всегда содержат небольшое число вершин с высокими степенями, так называемых хабов (hubs), и большое число слабосвязанных вершин.
В нетопологических ГИС цифруются пространственные объекты, изначально не знающие друг о друге, и построение отношений между ними осуществляется в режиме постпроцесса. В топологических же ГИС фиксация топологических пространственных отношений между объектами (смежности, связности, вложенности и др.) является основой их
конструкции. Топологические системы являются более адекватным инструментом для создания цифровых карт, на основе которых можно производить различные аналитические и статистические операции. Топологические модели позволяют представить всю карту в виде графа. Площади, линии и точки описываются с помощью узлов и дуг. Каждая дуга идет от начального к конечному узлу. Известно, что находится справа и слева.
На второй серии рисунков "Успешный поиск маршрута вывода на миварной сети" (рисунки 12 – 23) показано, как двое пользователей начинают поиск маршрута логического вывода: первый тянет сеть за входные данные, а второй – в другую сторону, за выходные (целевые показатели, объекты). Вследствие этого в процессе вывода задействуются только те объекты и правила, которые необходимы для данного поиска маршрута логического вывода. Таким образом удается избежать полного перебора с циклами и прочими неприятностями традиционных механизмов вывода,
основанных на предикатах или графах. В случае существования маршрута вывода он быстро находится: пользователи его вытягивают в виде мостика и встречаются друг с другом, что отраженно смайликом.
К. Оберауэр с соавт. (Oberauer et al., 2003) предложили модель факторной структуры WMC, в которой рассматриваются три когнитивные функции: параллельная обработка и хранение, относительная интеграция (предварительно названная координацией) и наблюдение. Функция параллельной обработки и хранения соответствует общепринятому определению WMC. Она обычно оценивается с помощью сложных кратковременных задач, в которых участники должны запомнить множество пунктов за короткий период и выполнить обработку информации в промежутках между или после кодирования запоминаемых пунктов. Относительная интеграция определяется как способность строить новые связи между элементами и таким образом создавать структурные репрезентации (Waltz et al., 1999). Элементы могут храниться в памяти, но также
могут быть даны перцептивно. Например, конструирование ментальной модели пространственного множества из некоторого описания (Byrne, Johnson-Laird, 1989), схватывание взаимоотношений из статистического графа (Halford et al., 2004) или «видение» созвездий в скоплении звезд и т. п. Наблюдение относится к контролю когнитивных процессов, включая репрезентацию цели, регулирование критериев ответов и изменение набора задач. Эти регуляторные процессы обычно относятся к категории исполнительных функций.
Связанные понятия (продолжение)
Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.
Раскраска графов находит применение и во многих практических областях, а не только в теоретических задачах. Помимо классических типов проблем, различные ограничения могут также быть наложены на граф, на способ присвоения цветов или на сами цвета. Этот метод, например, используется в популярной головоломке Судоку. В этой области всё ещё ведутся активные исследования.
Остовное дерево графа состоит из минимального подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрам.
Двудо́льный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.
Плана́рный граф — граф, который может быть изображён на плоскости без пересечения рёбер. Иначе говоря, граф планарен, если он изоморфен некоторому плоскому графу, то есть графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — непересекающиеся кривые на ней. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, так называемая внешняя грань.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице).
Подробнее: Глоссарий теории графов
Зада́ча о кратча́йшем пути ́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер (их также называют «параллельными»), то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром (тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две).
Подробнее: Мультиграф
В теории графов
паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.
Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связны. Две вершины s и t любого графа сильно связны, если существует ориентированный путь из s в t и ориентированный путь из t в s.
Подробнее: Компонента сильной связности в орграфе
Направленный ациклический граф (ориентированный ациклический граф, DAG от англ. directed acyclic graph) — орграф, в котором отсутствуют направленные циклы, но могут быть «параллельные» пути, выходящие из одного узла и разными путями приходящие в конечный узел. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса).
Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H.
В теории графов стягивание ребра — это операция, которая удаляет ребро из графа, а до этого связанные ребром вершины сливаются в одну вершину. Стягивание ребра является фундаментальной операцией в теории о минорах графов. Отождествление вершин — другая форма этой операции с более слабыми ограничениями.
Гамильто́нов граф — математический объект теории графов. Представляет собой граф (набор точек и соединяющих их линий), который содержит гамильтонов цикл. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу.
Ориентация неориентированного графа — это назначение направлений каждому ребру, что превращает исходный граф в ориентированный граф.
Эйлеров цикл — эйлеров путь, являющийся циклом, то есть замкнутый путь, проходящий через каждое ребро графа ровно по одному разу.
Поиск в ширину (англ. breadth-first search, BFS) — метод обхода графа и поиска пути в графе. Поиск в ширину является одним из неинформированных алгоритмов поиска.
Полный двудольный граф (биклика) — специальный вид двудольного графа, у которого любая вершина первой доли соединена со всеми вершинами второй доли вершин.
В математике случайный граф — это общий термин для обозначения вероятностного распределения графов. Случайные графы можно описать просто распределением вероятности или случайным процессом, создающим эти графы. Теория случайных графов находится на стыке теории графов и теории вероятностей. С математической точки зрения случайные графы необходимы для ответа на вопрос о свойствах типичных графов. Случайные графы нашли практическое применение во всех областях, где нужно смоделировать сложные сети — известно...
Число очередей графа — это инвариант графа, определённый аналогично стэковому числу (толщине книги) и использующий упорядочение FIFO (первый вошёл, первый вышел, очередь) вместо упорядочения LIFO (последним вошёл, первым вышел, стэк).
Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.
Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные . Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая исключает коэффициенты и члены меньшего порядка. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, т.е. при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения...
Подробнее: Временная сложность алгоритма
Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики являются одной из основных концепций теории графов и используются во многих других математических задачах и построениях с графами. Клики изучаются также в информатике — задача определения, существует ли клика данного размера в графе (Задача о клике) является NP-полной. Несмотря на эту трудность, изучаются многие алгоритмы для поиска клик.
Подробнее: Клика (теория графов)
Хромати́ческое число ́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G).
Разбие́ние мно́жества — это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств.
В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества...
Подробнее: Граф гиперкуба
Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном взвешенном неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
В теории графов графом-циклом называется граф, состоящий из единственного цикла, или, другими словами, некоторого числа вершин, соединённых замкнутой цепью. Граф-цикл с n вершинами обозначают как Cn. Число вершин в Cn равно числу рёбер и каждая вершина имеет степень 2, то есть любая вершина инцидентна ровно двум рёбрам.
Подробнее: Граф-цикл
В теории графов
псевдолес — это неориентированный граф , в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес.
Окрестность часто обозначается как NG(v) или (если известно, о каком графе идёт речь) N(v). То же самое обозначение окрестности может использоваться для ссылки на множество смежных вершин, а не на соответствующий порождённый подграф. Окрестность, описанная выше, не включает саму вершину v и об этой окрестности говорят как об открытой окрестности вершины v. Можно определить окрестность, включающую v. В этом случае окрестность называется закрытой и обозначается как NG. Если не указано явно, окрестность...
Периферийный цикл в неориентированном графе является, интуитивно, циклом, который не отделяет любую часть графа от любой другой части. Периферийные циклы (или, как они сначала назывались, периферийные многоугольники, поскольку Тат называл циклы «многоугольниками»), первым изучал Тат и они играют важную роль в описании планарных графов и в образовании циклических пространств непланарных графов.
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь (путь в неориентированном или ориентированном графе, который проходит все вершины графа ровно один раз) или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны.
В теории графов
глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков ; . Интуитивно, если древесная ширина...
Восходящее планарное представление направленного ациклического графа — это вложение графа в евклидово пространство, в котором рёбра представлены как непересекающиеся монотонно возрастающие кривые. То есть, кривая, представляющая любое ребро, должна иметь свойство, что любая горизонтальная прямая пересекает его максимум в одной точке, и никакие два ребра не могут пересекаться, разве что на концах. В этом смысле это идеальный случай для послойного рисования графа, стиля представления графа, в котором...
Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа.
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
Подробнее: Рёберный граф
Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае...
Граф решётки — это граф, рисунок которого, вложенный в некоторое евклидово пространство Rn, образует регулярную мозаику. Это подразумевает, что группа биективных преобразований, переводящая граф в себя, является решёткой в теоретико-групповом смысле.
Подробнее: Решётка (теория графов)
Мост — ребро в теории графов, удаление которого увеличивает число компонент связности. Такие рёбра также известны как разрезающие рёбра, разрезающие дуги или перешейки. Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле.
Автоморфизм графа есть отображение множества вершин на себя, сохраняющее смежность. Множество таких автоморфизмов образует вершинную группу графа или просто группу графа. Группа подстановок на множестве ребер называется реберной группой графа, которая тесно связана с вершинной...
В теории графов графом пересечений называется граф, представляющий схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств.
Подробнее: Граф пересечений
Граф Кэли — граф, который строится по группе с выделенной системой образующих. Назван в честь Артура Кэли.
Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач.
Упоминания в литературе (продолжение)
Если все показатели, приведенные в графах таблицы, выражены в одной и той же величине, то ее обозначение помещают после заголовка таблицы, через запятую или в скобках. Числовое значение показателя проставляют на уровне последней строки наименования, выравнивая по центру. Цифры в графах таблиц должны проставляться так, чтобы разряды чисел во всей графе были расположены один под другим, если они относятся к одному показателю. В графе должно быть соблюдено, как правило, одинаковое количество десятичных
знаков для всех значений величин. Рекомендуется составлять таблицы, помещающиеся на одной странице. Если таблица не помещается на одной странице, то после заголовка добавляют строку, в которой графы нумеруют. В конце страницы таблицу прерывают, нижнюю горизонтальную линию не проводят. Оставшуюся часть таблицы переносят на другую страницу, перед ней помещают слова «Продолжение таблицы» с указанием номера, повторяют строку с нумерацией граф.
Таблицу с
большим количеством столбцов (граф) можно разделять на части и размещать одну часть под другой на одной странице. При этом, если строки или графы выходят за формат страницы, в первом случае в каждой части повторяют заглавие (то есть названия столбцов), а во втором – боковую часть, то есть названия строк.
Таблицу
с большим количеством граф можно разделять на части и размещать одну часть под другой на одной странице. При этом если строки или графы выходят за формат страницы, то в первом случае в каждой части повторяют заглавие, то есть названия столбцов, а во втором – боковую часть, то есть названия строк.
В первой графе таблицы указан порядковый номер круга; во второй – его площадь; в третьей графе – к какой руке прикладывалась фигура; во всех остальных – начальные буквы фамилий испытуемых и их показания (площадь изображения). Знаком «прав.» отмечены те пробы, при которых испытуемый точнее определял площадь круга правой рукой, знаком «лев.» – те, при которых площадь круга определялась точнее левой рукой, «сим.» обозначает, что показания правой и левой рук равны.
В графу «отметки поверхности земли» вписать отметки всех точек, лежащих на линии АВ (пересечения с горизонталями
и характерные точки). Цифры следует располагать вертикально, точно против соответствующих ординат.
Аналогично, взаимодействию инь-ян квантов с внешним
миром соответствуют графы на рисунке 24.
Каждая таблица должна иметь заголовок, кратко выражающий ее содержание. Графы, содержащие подлежащее, нумеруются заглавными буквами алфавита, а графы, содержащие сказуемое, – арабскими цифрами. Все слова в заголовках подлежащего и сказуемого должны писаться полностью. В
необходимых случаях в заголовках граф нужно указывать единицу измерения показателя При отражении динамики показателей данные нужно располагать в хронологическом порядке.
Как бы сказал математик-дискранщик,
узлы графа превращаются в рёбра, а рёбра в женщин. Сиречь в нервные узлы.