www.studassist.ru

Теория графов - раздел дискретной математики, изучающий свойства графов.

Search:


(n, m)-граф - граф, имеющий в точности n -вершин и m -ребер.

(s, t)-разрез - разрез, при удалении которого вершина t не достижима из s.

(s, t)-цепь (путь) ((s, t)-path) - цепь, у которой вершины s и t концевые.

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

i-й ярус вершин - подмножество вершин, находящихся на расстоянии i от заданной вершины.

k-вершинно-связный граф - граф G, который при удалении любых k-1 вершин остается связным. Обозначается w(G) = k.

k-компонента (максимальная по включению) - часть графа, в котором любая пара вершин k-соединима.

k-реберно-связный граф - граф G, который при удалении любых k-1 ребер остается связным. Обозначается l(G)=k.

k-регулярный граф - граф, все вершины которого имеют одну и ту же степень, равную k.

k-связный граф - k-вершинно-связный граф.

k-соединимость - Две вершины s и t k-соединимы, если существует k независимых (s, t)-цепей.

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

n-дольный граф (n-chromatic graph) - n-хроматический граф.

n-раскраска - раскраска, в которой используется n цветов.

n-раскраска реберная (n-colouring) - раскраска ребер, использующая точно n цветов.

n-раскрашиваемый граф - граф G, у которого хроматическое число c(G)=n.

n-хроматический граф (n-chromatic graph) - граф G, у которого хроматическое число c(G)=n.

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

Автоморфизм графа (automorphism) - изоморфизм графа G на себя.

Антисимметричный граф - орграф, у которого отсутствует дуга из хi в xj, если существует дуга из xj в хi.

Ахроматическое число Y(G) - наибольшее число n, для которого существует полная n-раскраска графа G.

Ациклический граф (лес) - обыкновенный граф без циклов.

Бихроматический граф (bipartite graph) - 2-хроматический граф или граф, не содержащий нечетных циклов.

Величина (разреза, цепи, цикла и т. п.) - суммарный вес элементов, входящих в данное подмножество.

Вершина графа - элемент множества вершин графа.

Вершинная группа графа - группа автоморфизмов, действующая на вершинах графа.

Вершинное покрытие (опора) - множество X' вершин, таких, что всякое ребро инцидентно вершине из X'.


Вес (длина) - денотат (значение) числа, поставленного в соответствие взвешенному элементу.

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

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

Вес цикла - величина цикла.

Взвешенный граф - граф, вершинам и/или (обычно) ребрам которого поставлены в соответствие целые или вещественные числа (веса).

Висячая вершина - вершина, которая инцедентна динственному ребру.

Висячая вершина - вершина, которая не имеет инцидентных ребер.

Висячее ребро - ребро, инцедентное висячей вершине.

Внешне устойчивое множество вершин - Доминирующее множество вершин.

Внутренне устойчивое множество вершин - Независимое множество вершин (independent vertex set).

Гамильтонов цикл (Hamilton cycle) - гамильтонова цепь, у которой начальная и конечная вершины совпадают.

Гамильтонова цепь (Hamilton path) - простая цепь, которая содержит все вершины графа.

Генерация графов - процедура построения графа.

Глобальный характеристический инвариант графа - спецификация множества всех n-ок вершин графа, где n=р=|X| по характеристике, инвариантной относительно изоморфизма графов.

Гомеоморфизм графов - Два графа G1 и G2 гомеоморфны, если у них существуют изоморфные подразделения.

Граф (GRAPH) - вообще говоря, пара G=(V, E), где V-непустое множество вершинами , а E-множество пар ei=(vi1, vi2), vij ОV,которые задают ребра. Обычно V называют множеством вершин, а E-множеством ребер. Обычно граф изображают на плоскости в виде точек (вершин) и соединяющих их линий (ребер).

Граф инциденций обыкновенного графа G=(X, U) - двудольный граф I(G) = (X, U, Е), у которого вершины в первой доле совпадают с множеством X, а вершины второй доли соответствуют ребрам U графа G. Две вершины в I(G) смежны тогда и только тогда, когда соответствующие им элементы инцидентны в G.

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


граф Кенига - Бихроматический граф.

Граф с полурегулярной группой - однородный граф, удаление любой вершины из которого приводит к построению тождественного графа

Граф с регулярной группой - транзитивный граф, удаление одной вершины из которого приводит к построению тождественного графа.

Граф-звезда - полный двудольный граф K1,n.

Группа автоморфизмов графа - совокупность всех автоморфизмов графа с композицией (умножением) в качестве групповой операции.

Двойственный граф - каждой грани qi плоского графа ставится в соответствие вершина zi двойственного графа (мультиграфа). Две вершины zi и zj соединяются ребром u, если соответствующее ребро принадлежит граням qi и qj в исходном графе.

Двудольный граф - Бихроматический граф.

Двуполюсная сеть - сеть с двумя выделенными вершинами.

Дерево (tree) - связный ациклический граф.

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

Дерево Штейнера (Steiner's tree) - часть графа без циклов, связывающая заданное множество вершин.

Диаметр графа diam(G) - максимальный эксцентриситет его вершин.

Длина маршрута (цепи, пути) - величина маршрута.

Добавление вершины - К заданному множеству вершин (х1, x2, ... , xk) добавляется новая вершина y, смежная с х1, x2, ... , xk.

Добавление ребра (дуги) - Для заданной пары вершин х, у добавляется ребро (х, у).

Доминирующее множество вершин - множество X' вершин, таких, что каждая вершина, не принадлежащая X', смежна с вершиной из X'.

доминирующее множество ребер - Реберное покрытие (edge covering).

Доминирующее число - наименьшее число вершин в доминирующем множестве.

Дополнительный граф к графу G - граф ~G называется дополнительным, если он содержит то же множество вершин, что и G, и две вершины в G смежны тогда и только тогда, когда эти вершины несмежны в G.

Достижимость вершин - (соединимость, связность) Вершина х достижима из у, если существует маршрут из х в у.

Дуга - ориентированное ребро.

Изоморфизм графов - Два графа G=(X, U) и L=(X', U') изоморфны, если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохраняющие смежность и ориентацию для дуг.

Изоморфное вложение (изоморфизм подграфу) - Граф G2 изоморфно вложим в граф G1, если в графе G1 существует подграф, изоморфный графу G2.

Изоморфные группы графов - Группы Aut(G1) и Aut(G2) изоморфны, если для любых автоморфизмов x1, x2 Aut(G1) выполняется равенство h(x1, x2) = h(x1)h(x2), где h: Aut(G1)"Aut(G2).

Инварианты графа - характеристика, инвариантная относительно изоморфизмов графа.

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

инцидентность вершины и ребра - Вершина графа v и некоторое его ребро e называются инцидентными, если e=(v,w) или e=(w,v), где wнекоторая вершина графа.

Каркас - Остов графа.

Квазиглобальный характеристический инвариант графа - спецификация множества всех n-ок вершин графа по характеристике, инвариантной относительно изоморфизма графов, где 2Јn

Клика (clique) - полный подграф графа G, такой, что в G не существует вершины, смежной со всеми вершинами данного подграфа [т.е. это максимальный полный подграф ].

Кликовое число (clique number) - максимальный по числу вершин размер клики в графе G.

Комбинаторно-эквивалентные группы графов - группы графов с совпадающими цикловыми индексами.

Композиция графов (лексикографическое произведение графов) G1=(X1, U1) и G2=(X2, U2) - граф G=G1[G2], состоящий из множества вершин Х=X1ґX2, и две вершины s=(x1, x2) и t=(y1, y2) смежны в G тогда и только тогда, когда x1 смежна с y1 или x1=y1 и x2 смежна с y2.

Конструктивное перечисление графов - получение полного списка графов в заданном классе.

Контур (elementary circuit) - ориентированная цепь, у которой начальная и конечная вершины совпадают.

Контур графа - Фундаментальный цикл графа.

Корень (root) - обычно так называют специально выделенную по тем или иным причинам вершину дерева.

Кратчайшая цепь - (s, t)-цепь с наименьшей величиной.

кратчайших цепей - Матрица расстояний.

Критический путь - (s, t)-путь в ациклическом орграфе наибольшей величины.

Локальный характеристический инвариант графа - спецификация множества вершин графа по характеристике, инвариантной относительно изоморфизма графов.

Максимальная клика - клика с максимально возможным числом вершин среди клик графа.

Максимальная упаковка - максимально возможное число элементов в соответствующей упаковке.

Максимальная цепь - простая (s, t)-цепь с максимально возможным числом ребер.

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

Максимальное независимое множество вершин (maximal independent vertex set) - такое независимое множество вершин, что при добавлении в него любой другой вершины графа это множество перестает быть независимым. Примечание: "максимальность" в смысле данного определения означает не максимальную мощность, а "нерасширяемость" множества; в общем случае граф может иметь несколько максимальных независимых множества вершин разной мощности.

Максимальное паросочетание - паросочетание с максимально возможным числом ребер в паросочетании данного графа (числом реберной независимости).

Максимальный разрез - разрез с наибольшим числом элементов среди всех простых разрезов графа.

Маршрут или путь - чередующаяся последовательность x1, u1, x2, u2, ... , xk вершин xi и ребер ui, обладающая тем свойством, что любая пара соседних элементов инцидентна.

Массив степеней вершин - матрица стока, i-й элемент которой равен степени xi вершины графа G.

Матрица расстояний графа (reachability matrix) G - квадратная матрица D={dij}, в которой элемент dij=r(xi, xj), т.е. численно равен расстоянию от вершины xi до вершины xj в графе G. Если из xi недостижима вершина xj, то dij=Ґ.

Минимальная цепь - (s, t)-цепь с минимальным числом ребер.

Минимальное (наименьшее, кратчайшее) остовное дерево - остовное дерево с минимально возможной величиной.

Минимальное дерево Штейнера - дерево Штейнера с минимально возможным суммарным весом ребер.

Минимальное покрытие - минимально возможное число элементов в соответствующем покрытии.

Минимальный разрез - разрез с наименьшим числом элементов.

Минимальный цикл графа - цикл с минимально возможным числом ребер среди всех циклов графа.

Многополюсная сеть (многополюсник) - сеть с выделенными вершинами.

Мост - ребро графа, удаление которого увеличивает число его компонент связности.

Мощность мультиребра - число ребер в мультиребре.

Мультиграф (MultiGraph) - граф,содержащий мультиребера или петли.

Мультиребро - множество ребер, инцедентных одной и той же паре вершин (u,v).

Наибольшее паросочетание - паросочетание с наибольшей величиной.

Наибольший разрез (максимальный) - простой разрез с наиболее возможной величиной.

Наименьший разрез (минимальный) - простой разрез с минимально возможной величиной.

Независимое множество вершин (independent vertex set) - множество X' вершин, в котором никакие две вершины несмежны.

Независимое множество вершин или ребер - Независимое множество элементов (independent vertex or link set).

Независимое множество ребер - Паросочетание (matching, independent link set).

Независимое множество элементов (independent vertex or link set) - множество ребер (дуг) или вершин, попарно несмежных.

Независимые (вершинно-непересекающиеся, вершинно-независимые) маршруты - множество маршрутов, у которых все элементы различны (быть может, кроме конечных вершин).

Неориентированный граф - граф ребра которого не имеют направления (двусторонние).

Несогласованный граф - граф, группа автоморфизмов которого транзитивна по ребрам, но не транзитивна по вершинам.

Нестационарный граф - функция от времени, значениями которой являются графы.

Обхват графа - длина его минимального цикла.

Обхват графа - Минимальный цикл графа.

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

Объединение графов (помеченных графов) G1=(X1, U1) и G2=(X2, U2) - граф G1ИG2, множеством вершин которого является Х=X1ИX2, а множеством ребер U=U1ИU2.

Обыкновенный граф (SIMPLE GRAPH) - граф, не содержащий мультиребер и петель.

Однозначно раскрашиваемый граф - граф G, у которого c(G)=n и любая n-раскраска графа G порождает одно и то же разбиение множества вершин Х.

Однородный граф - Граф называют однородным , если степени всех его вершин одинаковы. Замечание: Во всяком графе число вершин нечетной степени всегда четно.

Однородный или регулярный - k-регулярный граф.

Односторонне связный орграф - орграф, у которого любая пара вершин односторонне связна.

Односторонний орграф - Односторонне связный орграф.

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

Односторонняя связность вершин - Вершины х и у односторонне связны в орграфе G, если х достижима из у или наоборот.

Однотипный фрагмент - вершина, ребро, несколько вершин или ребер и т.п.

Одноцветный класс - множество всех вершин одного цвета.

Окрестность вершины - Г!(v)={u V: {u,v} ОE}

Окружение графа - длина его самого длинного простого цикла.

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

Орбита вершины группы графа - подмножество множества вершин X, состоящее из всех таких элементов xi из X, что xx=x1 для некоторого автоморфизма xAut(G).

Орграф - ориентированный граф

Ориентация ребра - Пара вершин, инцидентная ребру, упорядочивается.

Ориентированная цепь - цепь орграфа G, в которой ориентация дуг (ребер) совпадает.

Ориентированный граф - граф ребра которого имеют некоторое направление.

Остов графа (spanning tree) - суграф графа G, не содержащий циклов и имеющий столько же компонент [связности ], что и G.

Остовное дерево - Остов графа.

Отрицательный цикл - цикл, который имеет отрицательную величину.

Паросочетание (matching, independent link set) - множество U' ребер, в котором никакие два ребра несмежны.

Пересечение графов (помеченных графов) G1=(X1, U1) и G2=(X2, U2) - граф G1ЗG2, множеством вершин которого является Х=X1ЗX2, а множеством ребер U=U1ЗU2, где U1 и U2-множество неупорядоченных пар вершин.

Перечисление графов - подсчет числа неизоморфных графов в заданном классе (с заданными характеристиками).

Периферийная вершина - вершина, эксцентриситет которой равен диаметру.

Петля - ребро инцедентное одной вершине (единственной). Может быть несколько петель.

Планарный граф - граф для которого можно построить укладку на плоскости без пересечений ребер.

Плоский граф - граф для которого построена укладку на плоскости без пересечений ребер.

Плотность графо - Кликовое число.

Подграф - часть графа G=(V, E)граф G'=(V',E'), для которого V'

Подгруппа группы графа - подмножество автоморфизмов графа, замкнутое относительно групповой операции композиции.

Подразбиение ребра (дуги) - Удаляется заданное ребро u=(х, у) и добавляется цепь (x1, u1, z, u2, у).

Подразделение графа G - граф, который может быть получен из G путем конечного числа подразделений ребер.

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

Покрывающее дерево - Остов графа.

покрывающий суграф - Реберное покрытие (edge covering).

Покрытие (covering) - множество X' вершин (U' ребер), такое, что каждое ребро (вершина) инцидентна хотя бы одной вершине из X' (ребру U').

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

Полный граф (FULL GRAPH) - это обыкновенный граф G=(V, E), в котором любая пара вершин смежна. Обозначается Kp, где р=|V|, при этом |E|=p(p-1)/2.

Полный двудольный граф - двудольный граф G=(A1, A2, E), у которого любая пара вершин хA1 и уA2 смежна. Обозначается Km,n, где m=|A1|, n=|A2|, |E|=mЧn.

Полный инвариант графа - характеристика, задающая граф с точностью до изоморфизма графов.

Полный подграф (complete subgraph) - подграф, в котором каждая пара вершин смежна.

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

Порождающее множество группы графа - совокупность автоморфизмов, на основе которых можно построить все автоморфизмы графа.

Порядок группы графа (число симметрии графа) - число автоморфизмов в группе графа.

Правый смежный класс - Для заданного xAut(G) правый смежный класс Hx обозначает множество всех элементов вида hx, где h пробегает H.

Простая цепь - цепь, в которой все вершины различны.

Простой разрез - разрез, у которого любое собственное подмножество элементов не является разрезом.

Простой цикл - простая цепь, у которой концевые вершины совпадают.

Пустой граф - граф G=(V,E), в котором |E|=Ж

Пустой подграф - Независимое множество вершин (independent vertex set).

Пустой подграф (внутренне-устойчивое множество вершин) - подграф графа G, в котором любая пара вершин несмежна.

Радиус графа - наименьший из эксцентриситетов его вершин.

Разбиение вершины орграфа - Вместо вершины х, в которую входят дуги u11, u21, ..., uk1 и выходят дуги u10, u20, ... , un0, в граф добавляется упорядоченная пара смежных вершин (х', х''), таких, что в х' входят дуги ui1, а из х'' выходят дуги uj0.

Разность графов (помеченных графов) - граф G1-G2, который получается из G1 удалением элементов, соответствующих графу G2.

Разрез (сечение графа) (cut-set) - множество элементов, удаление которых увеличивает число компонент (односторонних компонент, слабых компонент) связности графа.

Ранг группы графа - число орбит фиксатора вершины в транзитивной группе Aut(G).

Раскраска [вершинная] (colouring) - приписывание цветов (натуральных чисел) вершинам графа, такое, что никакие две смежные вершины не получают одинаковые цвета (числа).

Раскраска приближенная - раскраска с использованием красок, количество которых больше или равно минимально возможному числу.

Раскраска реберная (edge-colouring) - приписывание цветов ребрам графа, такое, что никакие два смежных ребра не получают одинакового цвета.

Раскраска точная - раскраска с использованием минимального числа красок, т. е. число красок равно хроматическому числу графа G или хроматическому классу графа G.

Расстояние между вершинами - Расстояние между вершинами s и t равно длине минимальной (s, t)-цепи.

Расстояние между вершинами - Расстояние между вершинами s и t величина кратчайшей (s, t)-цепи. Если s и t несоединимы, то расстояние между этими вершинами равно Ґ.

Расщепление вершины орграфа - Разбиение вершины орграфа.

Реберная группа графа - группа автоморфизмов, действующая на ребрах графа.

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

Реберное покрытие (edge covering) - множество U' ребер, таких, что всякая вершина инцидентна ребру из U'.

Реберный граф графа (line graph) G=(X, U) - граф U(G)=(U, Е) называются реберным, если каждой вершине uU(G) сопоставлено ребро uU и две вершины в U(G) смежны тогда и только тогда, когда соответствующие ребра смежны в графе G.

Реберный разрез - все элементы разреза ребра (дуги).

Ребро графа - элемент множества ребер графа.

Регулярная группа графа - транзитивная по вершинам полурегулярная группа графа.

Связность вершин - (соединимость, достижимость) Вершина х достижима из у, если существует маршрут из х в у.

Связный граф - граф в котором из любой вершины можно найти цепь в любую другую вершину. Несвязный графраспадается на компоненты связности (максимальные связные подграфы)

Сильная компонента орграфа G - максимальный подграф орграфа G, в котором любая пара вершин сильно связна.

Сильная связность вершин - Вершины х и у сильно связны в орграфе G, если они взаимно достижимы.

Сильнорегулярный граф - регулярный граф, каждая смежная (несмежная) пара вершин которого имеет одинаковое количество общих соседей m(l).

Сильносвязный орграф (strongly connected graph) - орграф, у которого любые две вершины взаимодостижимы.

Сильный орграф - Сильносвязный орграф.

Симметрическая группа графа - группа автоморфизмов, включающая р! автоморфизмов графа G.


Симметрический граф - граф, группа автоморфизмов которого действует транзитивно как на вершинах, так и на ребрах.

Симметричный граф - орграф, в котором из существования дуги из хi в xj следует существование дуги из xj в хi.

Слабая компонента орграфа - максимальный слабый подграф графа.

Слабосвязный орграф (слабый орграф) - орграф, который после дезориентации дуг будет связным.

Слабый орграф - Слабосвязный орграф.

Случайный граф - случайная величина, значениями которой являются графы. (Иногда и такое бывает...)

Смежность ребер - Два ребра r1 и r2 смежны тогда и только тогда, когда существует по крайней мере одна вершина, инцидентная r1 и r2.

Смежные вершины - Две вершины называятся смежными , если существует соединяющее их ребро.

Смежные ребра - Ребра называятся смежными , если они опираются на общую вершину .

Смешанный разрез - разрез, элементами которого выступают как ребра (дуги), так и вершины.

Совершенное паросочетание (perfect matching) - такое паросочетание, что любая вершина графа инцидентна некоторому ребру этого паросочетания.

Соединение графов G1=(X1, U1) и G2=(X2, U2) таких, что X1ЗX2=Ж, U1ЗU2=Ж - граф G1+G2, который состоит из G1ИG2ИK(X1, X2), где K(X1, X2)-полный двудольный граф с множеством вершин X1 и X2 в долях.

Соединимость вершин - (достижимость, связность) Вершина х достижима из у, если существует маршрут из х в у.

Средний диаметр - сумма кратчайших расстояний между всеми парами вершин графа, деленная на число пар вершин.

Стабилизатор подмножества Х*МХ группы графа - подгруппа графа, состоящая из всех автоморфизмов, оставляющих подмножество X* неподвижным.

Степень вершины - число инцедентных ей ребер.(Обозначается deg(v)) Очевидно, что deg(v)=|Г(v)|

Степень группы графа - мощность множества вершин графа G1, на котором действует группа Aut(G).

Стягивание вершин - Заданное множество вершин объединяется в одну вершину, а полученные петли удаляются.

Стягивание ребра (дуги) - вершины х и у, инцидентные заданному ребру, стягиваются.

Сумма графов G1=(X1, U1) и G2=(X2, U2) - граф G1ґG2, состоящий из множества вершин Х=X1ґX2 и две вершины s=(x1, x2) и t=(y1, y2) (s, t X, x1, y1X1, x2, y2 X2) смежны в G1ґG2 тогда и только тогда, когда x1=y1 и x2 смежна с y2 или x2=y2 и x2 смежна с y1.

Таблица композиций автоморфизмов - квадратная таблица размерности |Aut(G1)|ґ|Aut(G2)|, включающая результат умножения каждой пары автоморфизмов графа.

Теория графов - математический язык для формализованного определения понятий, связанных с анализом и синтезом структур систем и процессов.

Теория графов - теоретическая основа структурной информатики.

Тождественная группа графа - группа автоморфизмов, состоящая из тождественного автоморфизма.

Тождественно-критический граф - тождественный граф, добавление одной вершины к которому превращает его в транзитивный граф.

Тождественный граф - граф, группа автоморфизмов которого состоит из единственного автоморфизма (тождественного).

Тотальный граф графа G=(X, U) - граф T(G) =(ХИU, Е) называется тотальным, если каждой вершине T(G) сопоставлен элемент (вершина или ребро) графа G и две вершины в T(G) смежны тогда и только тогда, когда соответствующие элементы графа G смежны или инцидентны.

Точка сочленения - вершина, удаление которой из графа увеличивает его число компонент связности.

Транзитивная группа графа - группа автоморфизмов, в которой для любой пары вершин существует автоморфизм, отображающий одну вершину в другую.

Транзитивное замыкание орграфа - орграф G'= (X, RИR'), полученный добавлением дуг R' к орграфу G=(X, R) так, что G' становится транзитивным.

Транзитивный граф (transitive graph) - граф, группа автоморфизмов которого транзитивна на вершинах.

Транзитивный орграф - орграф G=(X, R), у которого из существования дуг (хi, xj) и (xj, xk) следует существование дуги (xi, xk).

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

Тривиальный граф - граф G=(V,E), в котором |E|=0 и |V|=1

Удаление вершины - Из графа удаляется вершина вместе с инцидентными ребрами.

Удаление ребра (дуги) - В графе удаляется ребро без инцидентных вершин.

Укладка графа на поверхность S в трехмерном эвклидовом пространстве - построение изоморфного G графа L, лежащего на S вершинами (точками), ребрами (непрерывными линиями конечной длины) и дугами (ориентированными линиями конечной длины), причем линии на поверхности S не пересекаются.

Упаковка - Независимое множество элементов (independent vertex or link set).

Фиксатор вершины х группы графа - подгруппа группы графа, состоящая из всех автоморфизмов, оставляющих вершину х неподвижной.

Фиксатор подмножества Х*МХ группы графа - подгруппа группы графа, состоящая из пересечения фиксаторов, принадлежащих X*.

Фундаментальный цикл графа - цикл, определяемый некоторым остовом и хордой графа (орграфа).

Характеристический инвариант графа - спецификация множества однотипных фрагментов графа по характеристике, инвариантной относительно изоморфизма графов.

Хорда - ребро графа, не принадлежащее остову.

Хроматический класс c'(G) - наименьшее число n, для которого существует реберная n-раскраска.

Хроматическое число (chromatic number) c(G) - наименьшее число n, для которого граф G имеет n-раскраску.

Центральная вершина - вершина, эксцентриситет которой равен радиусу.

Цепь (trail, path) - маршрут, в котором все ребра различны.

Цепь в графе G={V,E} - последовательность вершин v0,v1 ,...vnтакая , что n>0 и vi,vj соединены ребром.(i=0..n-1; j=i+1) nдлина цепи. Если вершины входящие в цепь различны , то цепьпростая , иначесоставная.

Цикл - замкнутая цепь.

Цикл (cycle) - цепь, у которой начальная и конечная вершины совпадают.

Цикломатическое число графа n(G) - наименьшее число ребер , удаление которых оставляет граф без циклов, образуя остов (каркас) графа. Легко доказывается,что n(G)=q-p+y , где yчисло компонент связности графа G.

Частичный граф графа G=(V, E) - граф Н'=(V',E'), для которого V'

Число вершин - мощность множества вершин р=|V|

Число вершинного покрытия (опора) - наименьшее число вершин в вершинном покрытии.

Число вершинной независимости h(G) - наибольшее число вершин в независимых множествах вершин графа G.

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

число внешней устойчивости - Доминирующее число.

число внутренней устойчивости, неплотность - Число вершинной независимости h(G).

Число нетождественной стабильности - максимальная мощность экстремального подмножества нетождественной стабильности графа.

Число ребер - мощность множества ребер q=|E|

Число реберного покрытия - наименьшее число ребер в реберном покрытии графа.

Число реберной независимости b(G) - наибольшее число ребер в независимых множествах ребер графа G.

Число реберной связности графа G - наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.

Число тождественной стабильности - минимальная мощность экстремального подмножества тождественной стабильности графа.

Эйлеров граф (Eulerian graph) - связный граф, не содержащий вершин нечетной степени.

Эйлеров цикл (Euler cycle) - эйлерова цепь, у которой начальная и конечная вершины совпадают.

Эйлерова цепь (Euler path) - цепь, содержащая все ребра графа в точности один раз.

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

Экстремальное подмножество тождественной стабильности - подмножество вершин графа, относительно которого фиксатор группы тождественный, но удаление любой вершины из подмножества приводит к нетождественному фиксатору.

Эксцентриситет вершины ecc(v) - максимальное расстояние от v до других вершин графа.
Рейтинг@Mail.ru Яндекс.Метрика