Ориентированный граф — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Семанти́ческая сеть — информационная модель предметной области, имеет вид ориентированного графа. Вершины графа соответствуют объектам предметной области, а дуги (рёбра) задают отношения между ними. Объектами могут быть: понятия, события, свойства, процессы. Таким образом, семантическая сеть — это один из способов представления знаний.
Рибо́за — моносахарид из группы пентоз, бесцветные кристаллы, легко растворимые в воде и имеющие сладкий вкус. Эпимер арабинозы. Открыта в 1905 году.
Древовидная структура является одним из способов представления иерархической структуры в графическом виде.
DAG может означать:
- Диацилглицерин
- Направленный ациклический граф
Графовая вероятностная модель — это вероятностная модель, в которой в виде графа представлены зависимости между случайными величинами. Вершины графа соответствуют случайным переменным, а рёбра — непосредственным вероятностным взаимосвязям между случайными величинами. Графические модели широко используются в теории вероятностей, статистике, а также в машинном обучении.
В теории графов под ациклической раскраской понимается (правильная) раскраска вершин, в которой любой двуцветный подграф не имеет циклов. Ациклическим хроматическим числом A(G) графа G называется наименьшее число цветов, необходимое в любой ациклической раскраске G.
Звёздная раскраска в теории графов — (правильная) раскраска вершин, в которой любой путь из четырёх вершин использует как минимум три различных цвета. Эквивалентное определение — это такая раскраска, при которой любые компоненты связности порождённых подграфов, образованных вершинами любых двух цветов, являются звёздами. Звёздная раскраска была предложена Грюнбаумом.
Миха́лис Яннака́кис — греческий учёный в области компьютерных наук, профессор Колумбийского университета. Известен своими работами в области теории сложности вычислений, баз данных и других смежных областях. Лауреат Премии Кнута (2005). Член Национальной академии наук США (2018).
В теории графов ориентированный граф может содержать ориентированные циклы, кольцо дуг, имеющих одно направление. В некоторых приложениях такие циклы нежелательны, мы можем исключить их и получить направленный ациклический граф. Один из способов исключения дуг — просто удаление дуг из графа. Разрезающий циклы набор дуг или разрезающий циклы набор рёбер — это множество дуг, которые, при удалении их из графа, образуют DAG. Рассматривая под другим углом, это множество, содержащее по меньшей мере одно ребро из каждого цикла графа.
Ациклическая ориентация неориентированного графа — это назначение направлений каждому ребру (ориентация), при которой не образуется какого-либо ориентированного цикла, а потому такая ориентация превращает граф в направленный ациклический граф. Любой граф имеет ациклическую ориентацию.
Сильная ориентация неориентированного графа — это назначение направлений каждому ребру, при котором граф превращается в сильно связный граф.
Ориентированная раскраска графа — это специальный вид раскраски графов. А именно, это назначение цветов вершинам ориентированного графа, которое
- правильное — никакие две смежные вершины не получают один и тот же цвет,
- сохраняется ориентация — если (x, y) и (u, v) являются дугами в графе, то недопустимо, чтобы цвета вершин x и v, а также цвета вершин y и u совпадали.
Ориентация неориентированного графа — это назначение направлений каждому ребру, что превращает исходный граф в ориентированный граф.
Биполярная ориентация или st-ориентация неориентированного графа — это назначение ориентации каждому ребру (ориентации), что превращает граф в направленный ациклический граф с единственным источником s и единственном стоком t, а st-нумерация графа — это топологическая сортировка полученного ориентированного ациклического графа.
Восходящее планарное представление направленного ациклического графа — это вложение графа в евклидово пространство, в котором рёбра представлены как непересекающиеся монотонно возрастающие кривые. То есть, кривая, представляющая любое ребро, должна иметь свойство, что любая горизонтальная прямая пересекает его максимум в одной точке, и никакие два ребра не могут пересекаться, разве что на концах. В этом смысле это идеальный случай для послойного рисования графа, стиля представления графа, в котором монотонные кривые могут пересекаться, но в которых число пересечений минимально.
st-Планарный граф — это биполярная ориентация планарного графа, для которого как источник, так и сток ориентации находятся на внешней грани графа. То есть это ориентированный граф, нарисованный без пересечений на плоскости таким образом, что не имеется ориентированных циклов в графе, точно одна вершина графа не имеет входных дуг, точно одна вершина графа не имеет исходящих дуг, и обе эти две специальные вершины лежат на внешней грани графа.
Послойное рисование графа или иерархическое рисование графа — это способ визуализации графов, в котором вершины ориентированного графа рисуются горизонтальными рядами или слоями с рёбрами, преимущественно направленными вниз. Такой способ известен как стиль Сугиямы визуализации графов, по имени Козо Сугиямы, который первым разрабатывал этот стиль.
Коллайдер — переменная в статистике и причинно-следственных диаграммах, на которую влияют две или более переменных. Название «коллайдер» отражает тот факт, что в графических моделях стрелки от переменных, ведущие в коллайдер, «сталкиваются» в узле, который является коллайдером. Иногда коллайдеры также называют перевёрнутыми вилками.
