Медиа Портал :: Теория Графов

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

Главная

Новости

Delphi

C&C++

Графы..

Web-design

Математика

Исходники

Lisp&Prolog

Ссылки

Указатель базовых терминов и определений Теории Графов (около 316 понятий + комбинаторный анализ)

Основной базой для построения данного указателя явился курс "Теория Графов и Комбинаторика" , который нам довелось прослушать в МЭИ (ТУ). Кроме того, использовался словарь составленный Нечепуренко и др.
О всех неполадках в работе словаря прошу мне написать - csIvan@yandex.ru

Введите слово для поиска в базе:

Результаты поиска: нет вхождений

Теория графов - математический язык для формализованного определения понятий, связанных с анализом и синтезом структур систем и процессов.
Теория графов - теоретическая основа структурной информатики.
Граф (GRAPH) - вообще говоря, пара G=(V, E), где V -непустое множество вершинами , а E - множество пар e_i=(v_i1, v_i2), v_ij ОV,которые задают ребра. Обычно V называют множеством вершин, а E - множеством ребер. Обычно граф изображают на плоскости в виде точек (вершин) и соединяющих их линий (ребер).
Вершина графа - элемент множества вершин графа.
Ребро графа - элемент множества ребер графа.
Дуга - ориентированное ребро.
Число вершин - мощность множества вершин р=|V|
Число ребер - мощность множества ребер q=|E|
Две вершины называятся смежными , если существует соединяющее их ребро.
Ребра называятся смежными , если они опираются на общую вершину .
Вершина графа v и некоторое его ребро e называются инцидентными, если e=(v,w) или e=(w,v), где w - некоторая вершина графа.
Петля - ребро инцедентное одной вершине (единственной). Может быть несколько петель.
Висячее ребро - ребро, инцедентное висячей вершине.
Мультиребро - множество ребер, инцедентных одной и той же паре вершин (u,v).
Мощность мультиребра - число ребер в мультиребре.
Окрестность вершины - Г!(v)={u V: {u,v} ОE}
Степень вершины - число инцедентных ей ребер.(Обозначается deg(v)) Очевидно, что deg(v)=|Г(v)|
Вес вершины - любое число (действительное, целое или рациональное), которое устанавливается в соответствие данной вершине по каким-либо логическим соображениям.
Вес ребра - любое число (действительное, целое или рациональное), которое устанавливается в соответствие данной вершине по каким-либо логическим соображениям.
Эксцентриситет вершины ecc(v) - максимальное расстояние от v до других вершин графа.
Диаметр графа diam(G) - максимальный эксцентриситет его вершин.
Граф называют однородным , если степени всех его вершин одинаковы.
На заметку: Во всяком графе число вершин нечетной степени всегда четно.
Цепь в графе G={V,E} - последовательность вершин v₀,v₁ ,...v_n -такая , что n>0 и v_i,v_jсоединены ребром.(i=0..n-1;j=i+1) n - длина цепи. Если вершины входящие в цепь различны , то цепь - простая , иначе - составная.
Цикл - замкнутая цепь.
Обход графа - цикл проходящий через все вершины графа по одному разу.
Связный граф - граф в котором из любой вершины можно найти цепь в любую другую вершину. Несвязный граф - распадается на компоненты связности (максимальные связные подграфы)
Точка сочленения - вершина, удаление которой из графа увеличивает его число компонент связности.
Мост - ребро графа, удаление которого увеличивает число его компонент связности.
Корень (root) - обычно так называют специально выделенную по тем или иным причинам вершину дерева.
Висячая вершина - вершина, которая инцедентна динственному ребру.
Радиус графа - наименьший из эксцентриситетов его вершин.
Центральная вершина - вершина, эксцентриситет которой равен радиусу.
Периферийная вершина - вершина, эксцентриситет которой равен диаметру.
Цикломатическое число графа n(G) - наименьшее число ребер , удаление которых оставляет граф без циклов, образуя остов (каркас) графа. Легко доказывается,что n(G)=q-p+y , где y - число компонент связности графа G.
Подграф - часть графа G=(V, E) - граф G'=(V',E'), для которого V'<V, E'<E и две несмежные вершины в G не смежны в G'.
Частичный граф графа G=(V, E) - граф Н'=(V',E'), для которого V'<V, E'<E .
Однотипный фрагмент - вершина, ребро, несколько вершин или ребер и т.п.
Обыкновенный граф (SIMPLE GRAPH) - граф, не содержащий мультиребер и петель.
Полный граф (FULL GRAPH) - это обыкновенный граф G=(V, E), в котором любая пара вершин смежна. Обозначается K_p, где р=|V|, при этом |E|=p(p-1)/2.
Мультиграф (MultiGraph) - граф,содержащий мультиребера или петли.
Пустой граф - граф G=(V,E), в котором |E|=Ж
Тривиальный граф - граф G=(V,E), в котором |E|=0 и |V|=1
Ациклический граф (лес) - обыкновенный граф без циклов.
Дерево (tree) - связный ациклический граф.
Полный двудольный граф - двудольный граф G=(A₁, A₂, E), у которого любая пара вершин хA₁ и уA₂ смежна. Обозначается K_m,n, где m=|A₁|, n=|A₂|, |E|=mЧn.
Граф-звезда - полный двудольный граф K_1,n.
Орграф - ориентированный граф - граф ребра которого имеют некоторое направление.
Неориентированный граф - граф ребра которого не имеют направления (двусторонние).
Планарный граф - граф для которого можно построить укладку на плоскости без пересечений ребер.
Плоский граф - граф для которого построена укладку на плоскости без пересечений ребер.
Удаление вершины. Из графа удаляется вершина вместе с инцидентными ребрами.

Добавление вершины. К заданному множеству вершин (х₁, x₂, ... , x_k) добавляется новая вершина y, смежная с х₁, x₂, ... , x_k.
Разбиение (расщепление) вершины орграфа. Вместо вершины х, в которую входят дуги u₁¹, u₂¹, ..., u_k¹ и выходят дуги u₁⁰, u₂⁰, ... , u_n⁰, в граф добавляется упорядоченная пара смежных вершин (х', х''), таких, что в х' входят дуги u_i¹, а из х'' выходят дуги u_j⁰.
Достижимость (соединимость, связность) вершин. Вершина х достижима из у, если существует маршрут из х в у.
Односторонняя связность вершин. Вершины х и у односторонне связны в орграфе G, если х достижима из у или наоборот.
Сильная связность вершин. Вершины х и у сильно связны в орграфе G, если они взаимно достижимы.
Стягивание вершин. Заданное множество вершин объединяется в одну вершину, а полученные петли удаляются.
Две вершины s и t k-соединимы, если существует k независимых (s, t)-цепей.
Смежность ребер. Два ребра r₁ и r₂ смежны тогда и только тогда, когда существует по крайней мере одна вершина, инцидентная r₁ и r₂.
Удаление (ребра) дуги. В графе удаляется ребро без инцидентных вершин.
Ориентация ребра. Пара вершин, инцидентная ребру, упорядочивается.
Добавление ребра (дуги). Для заданной пары вершин х, у добавляется ребро (х, у).
Стягивание ребра (дуги) - вершины х и у, инцидентные заданному ребру, стягиваются.
Подразбиение ребра (дуги). Удаляется заданное ребро u=(х, у) и добавляется цепь (x₁, u₁, z, u₂, у).

n-раскрашиваемый граф - граф G, у которого хроматическое число c(G)=n.
n-хроматический (n-дольный) граф (n-chromatic graph) - граф G, у которого хроматическое число c(G)=n.
Граф однозначно раскрашиваемый - граф G, у которого c(G)=n и любая n-раскраска графа G порождает одно и то же разбиение множества вершин Х.
Граф бихроматический (двудольный граф, граф Кенига) (bipartite graph) - 2-хроматический граф или граф, не содержащий нечетных циклов.
Многополюсная сеть (многополюсник) - сеть с выделенными вершинами.
Двуполюсная сеть - сеть с двумя выделенными вершинами.
Сильносвязный орграф (сильный орграф) (strongly connected graph) - орграф, у которого любые две вершины взаимодостижимы.
Односторонне связный орграф (односторонний орграф) - орграф, у которого любая пара вершин односторонне связна.
Слабосвязный орграф (слабый орграф) - орграф, который после дезориентации дуг будет связным.
Транзитивное замыкание орграфа - орграф G'= (X, RИR'), полученный добавлением дуг R' к орграфу G=(X, R) так, что G' становится транзитивным.
Транзитивный орграф - орграф G=(X, R), у которого из существования дуг (х_i, x_j) и (x_j, x_k) следует существование дуги (x_i, x_k).
Симметричный граф - орграф, в котором из существования дуги из х_iв x_j следует существование дуги из x_j в х_i.
Антисимметричный граф - орграф, у которого отсутствует дуга из х_iв x_j, если существует дуга из x_j в х_i.
k-связный граф (k-вершинно-связный граф) - граф G, который при удалении любых k-1 вершин остается связным. Обозначается w(G) = k.
k-реберно-связный граф - граф G, который при удалении любых k-1 ребер остается связным. Обозначается l(G)=k.
Случайный граф - случайная величина, значениями которой являются графы. (Иногда и такое бывает...)
Интервальный граф - граф, у которого вершинам можно поставить в соответствие интервалы (отрезки прямой) и две вершины интервального графа смежны тогда и только тогда, когда пересечение соответствующих им интервалов непусто.
Нестационарный граф - функция от времени, значениями которой являются графы.
Однородный или регулярный (k-регулярный) граф - граф, все вершины которого имеют одну и ту же степень, равную k.
Оптимальный по вероятности связности мультиграф - граф, обладающий максимальным значением вероятности связности среди всех (n, m)-графов и с одинаковыми надежностями ребер.
Эйлеров граф (Eulerian graph) - связный граф, не содержащий вершин нечетной степени.
(n, m)-граф - граф, имеющий в точности n -вершин и m -ребер.
Тождественный граф - граф, группа автоморфизмов которого состоит из единственного автоморфизма (тождественного).
Транзитивный граф (transitive graph) - граф, группа автоморфизмов которого транзитивна на вершинах.
Симметрический граф - граф, группа автоморфизмов которого действует транзитивно как на вершинах, так и на ребрах.
Тождественно-критический граф - тождественный граф, добавление одной вершины к которому превращает его в транзитивный граф.
Сильнорегулярный граф - регулярный граф, каждая смежная (несмежная) пара вершин которого имеет одинаковое количество общих соседей m(l).
Граф Кели - транзитивный граф с ориентацией ребер и их раскраской, задающий таблицу умножения группы с заданными порождающими элементами таким образом, что:

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

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

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

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

Дополнительный граф к графу G - граф ~G называется дополнительным, если он содержит то же множество вершин, что и G, и две вершины в G смежны тогда и только тогда, когда эти вершины несмежны в G.
Реберный граф графа (line graph) G=(X, U) - граф U(G)=(U, Е) называются реберным, если каждой вершине uU(G) сопоставлено ребро uU и две вершины в U(G) смежны тогда и только тогда, когда соответствующие ребра смежны в графе G.
Граф инциденций обыкновенного графа G=(X, U) - двудольный граф I(G) = (X, U, Е), у которого вершины в первой доле совпадают с множеством X, а вершины второй доли соответствуют ребрам U графа G. Две вершины в I(G) смежны тогда и только тогда, когда соответствующие им элементы инцидентны в G.
Тотальный граф графа G=(X, U) - граф T(G) =(ХИU, Е) называется тотальным, если каждой вершине T(G) сопоставлен элемент (вершина или ребро) графа G и две вершины в T(G) смежны тогда и только тогда, когда соответствующие элементы графа G смежны или инцидентны.
Двойственный граф - каждой грани q_i плоского графа ставится в соответствие вершина z_i двойственного графа (мультиграфа). Две вершины z_i и z_j соединяются ребром u, если соответствующее ребро принадлежит граням q_i и q_j в исходном графе.
Массив степеней вершин - матрица стока, i-й элемент которой равен степени x_i вершины графа G.
Матрица расстояний (кратчайших цепей) графа (reachability matrix) G - квадратная матрица D={d_ij}, в которой элемент d_ij=r(x_i, x_j), т.е. численно равен расстоянию от вершины x_i до вершины x_j в графе G. Если из x_i недостижима вершина x_j, то d_ij=Ґ.
Число вершинной связности графа G - наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
Число реберной связности графа G - наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.
Обхват графа - длина его минимального цикла.
Окружение графа - длина его самого длинного простого цикла.
Хроматическое число (chromatic number) c(G) - наименьшее число n, для которого граф G имеет n-раскраску.
Хроматический класс c'(G) - наименьшее число n, для которого существует реберная n-раскраска.
Ахроматическое число Y(G) - наибольшее число n, для которого существует полная n-раскраска графа G.
Кликовое число (плотность) (clique number) - максимальный по числу вершин размер клики в графе G.
Число реберной независимости b(G) - наибольшее число ребер в независимых множествах ребер графа G.
Число вершинной независимости (число внутренней устойчивости, неплотность) h(G) - наибольшее число вершин в независимых множествах вершин графа G.
Доминирующее число (число внешней устойчивости) - наименьшее число вершин в доминирующем множестве.
Число вершинного покрытия (опора) - наименьшее число вершин в вершинном покрытии.
Число реберного покрытия - наименьшее число ребер в реберном покрытии графа.
Средний диаметр - сумма кратчайших расстояний между всеми парами вершин графа, деленная на число пар вершин.
V-соединимость - максимальное число вершинно-независимых цепей (путей) между любой парой вершин графа, причем длины, не большей диаметра графа.
E-соединимость - максимальное число реберно-независимых цепей (путей) между любой парой вершин графа, причем длины, не большей диаметра графа.
Число тождественной стабильности - минимальная мощность экстремального подмножества тождественной стабильности графа.
Число нетождественной стабильности - максимальная мощность экстремального подмножества нетождественной стабильности графа.
Инварианты графа - характеристика, инвариантная относительно изоморфизмов графа.
Полный инвариант графа - характеристика, задающая граф с точностью до изоморфизма графов.
Характеристический инвариант графа - спецификация множества однотипных фрагментов графа по характеристике, инвариантной относительно изоморфизма графов.
Локальный характеристический инвариант графа - спецификация множества вершин графа по характеристике, инвариантной относительно изоморфизма графов.
Квазиглобальный характеристический инвариант графа - спецификация множества всех n-ок вершин графа по характеристике, инвариантной относительно изоморфизма графов, где 2Јn<p=|X|.
Глобальный характеристический инвариант графа - спецификация множества всех n-ок вершин графа, где n=р=|X| по характеристике, инвариантной относительно изоморфизма графов.
Изоморфизм графов. Два графа G=(X, U) и L=(X', U') изоморфны, если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохраняющие смежность и ориентацию для дуг.
Подразделение графа G - граф, который может быть получен из G путем конечного числа подразделений ребер.
Гомеоморфизм графов. Два графа G₁ и G₂ гомеоморфны, если у них существуют изоморфные подразделения.
Укладка графа на поверхность S в трехмерном эвклидовом пространстве - построение изоморфного G графа L, лежащего на S вершинами (точками), ребрами (непрерывными линиями конечной длины) и дугами (ориентированными линиями конечной длины), причем линии на поверхности S не пересекаются.
Раскраска [вершинная ] (colouring) - приписывание цветов (натуральных чисел) вершинам графа, такое, что никакие две смежные вершины не получают одинаковые цвета (числа).
n-раскраска - раскраска, в которой используется n цветов.
Раскраска реберная (edge-colouring) - приписывание цветов ребрам графа, такое, что никакие два смежных ребра не получают одинакового цвета.
n-раскраска реберная (n-colouring) - раскраска ребер, использующая точно n цветов.
Полная раскраска - раскраска вершин графа, такая, что для любых двух цветов найдутся две смежные вершины, окрашенные в эти цвета.
Раскраска точная - раскраска с использованием минимального числа красок, т. е. число красок равно хроматическому числу графа G или хроматическому классу графа G.
Раскраска приближенная - раскраска с использованием красок, количество которых больше или равно минимально возможному числу.
Изоморфное вложение (изоморфизм подграфу). Граф G₂ изоморфно вложим в граф G₁, если в графе G₁ существует подграф, изоморфный графу G₂.
Максимальное изоморфное пересечение - максимальный по мощности вершин общий подграф, содержащийся в каждом из рассматриваемых графов.
Генерация графов - процедура построения графа.
Объединение графов (помеченных графов) G₁=(X₁, U₁) и G₂=(X₂, U₂) - граф G₁ИG₂, множеством вершин которого является Х=X₁ИX₂, а множеством ребер U=U₁ИU₂.
Пересечение графов (помеченных графов) G₁=(X₁, U₁) и G₂=(X₂, U₂) - граф G₁ЗG₂, множеством вершин которого является Х=X₁ЗX₂, а множеством ребер U=U₁ЗU₂, где U₁ и U₂- множество неупорядоченных пар вершин.
Соединение графов G₁=(X₁, U₁) и G₂=(X₂, U₂) таких, что X₁ЗX₂=Ж, U₁ЗU₂=Ж - граф G₁+G₂, который состоит из G₁ИG₂ИK(X₁, X₂), где K(X₁, X₂) - полный двудольный граф с множеством вершин X₁ и X₂ в долях.
Сумма графов G₁=(X₁, U₁) и G₂=(X₂, U₂) - граф G₁ґG₂, состоящий из множества вершин Х=X₁ґX₂ и две вершины s=(x₁, x₂) и t=(y₁, y₂) (s, t X, x₁, y₁X₁, x₂, y₂ X₂) смежны в G₁ґG₂ тогда и только тогда, когда x₁=y₁ и x₂ смежна с y₂ или x₂=y₂ и x₂ смежна с y₁.
Симметрическая разность графов G₁ и G₂ - граф G₁ЕG₂=G₁ИG₂ - G₁ЗG₂.
Разность графов (помеченных графов) - граф G₁-G₂, который получается из G₁ удалением элементов, соответствующих графу G₂.
Композиция графов (лексикографическое произведение графов) G₁=(X₁, U₁) и G₂=(X₂, U₂) - граф G=G₁[G₂], состоящий из множества вершин Х=X₁ґX₂, и две вершины s=(x₁, x₂) и t=(y₁, y₂) смежны в G тогда и только тогда, когда x₁ смежна с y₁ или x₁=y₁ и x₂ смежна с y₂.
Перечисление графов - подсчет числа неизоморфных графов в заданном классе (с заданными характеристиками).
Конструктивное перечисление графов - получение полного списка графов в заданном классе.
Автоморфизм графа (automorphism) - изоморфизм графа G на себя.
Группа автоморфизмов графа - совокупность всех автоморфизмов графа с композицией (умножением) в качестве групповой операции.
Вершинная группа графа - группа автоморфизмов, действующая на вершинах графа.
Реберная группа графа - группа автоморфизмов, действующая на ребрах графа.
Тождественная группа графа - группа автоморфизмов, состоящая из тождественного автоморфизма.
Транзитивная группа графа - группа автоморфизмов, в которой для любой пары вершин существует автоморфизм, отображающий одну вершину в другую.
Симметрическая группа графа - группа автоморфизмов, включающая р! автоморфизмов графа G.
Регулярная группа графа - транзитивная по вершинам полурегулярная группа графа.
Полурегулярная группа графа - группа автоморфизмов, в которой стабилизатор (фиксатор) любой вершины является тождественным автоморфизмом.
k-транзитивная группа графа - группа автоморфизмов графа, в котором для любой пары упорядоченных наборов из k различных вершин существует автоморфизм, отображающий один из них в другой.
Изоморфные группы графов. Группы Aut(G₁) и Aut(G₂) изоморфны, если для любых автоморфизмов x₁, x₂ Aut(G₁) выполняется равенство h(x₁, x₂) = h(x₁)h(x₂), где h: Aut(G₁)"Aut(G₂).
Комбинаторно-эквивалентные группы графов - группы графов с совпадающими цикловыми индексами.
Порядок группы графа (число симметрии графа) - число автоморфизмов в группе графа.
Орбита вершины группы графа - подмножество множества вершин X, состоящее из всех таких элементов x_i из X, что xx=x₁ для некоторого автоморфизма xAut(G).
Степень группы графа - мощность множества вершин графа G₁, на котором действует группа Aut(G).
Ранг группы графа - число орбит фиксатора вершины в транзитивной группе Aut(G).
Подстепени группы графа - совокупность чисел элементов в каждой орбите фиксатора вершины для транзитивной группы графа.
Подгруппа группы графа - подмножество автоморфизмов графа, замкнутое относительно групповой операции композиции.
Порождающее множество группы графа - совокупность автоморфизмов, на основе которых можно построить все автоморфизмы графа.
Таблица композиций автоморфизмов - квадратная таблица размерности |Aut(G₁)|ґ|Aut(G₂)|, включающая результат умножения каждой пары автоморфизмов графа.
Фиксатор вершины х группы графа - подгруппа группы графа, состоящая из всех автоморфизмов, оставляющих вершину х неподвижной.
Фиксатор подмножества Х*МХ группы графа - подгруппа группы графа, состоящая из пересечения фиксаторов, принадлежащих X*.
Стабилизатор подмножества Х*МХ группы графа - подгруппа графа, состоящая из всех автоморфизмов, оставляющих подмножество X* неподвижным.
Правый смежный класс. Для заданного xAut(G) правый смежный класс Hx обозначает множество всех элементов вида hx, где h пробегает H.
Остов графа (остовное дерево, покрывающее дерево, каркас) (spanning tree) - суграф графа G, не содержащий циклов и имеющий столько же компонент [связности ], что и G.
Сильная компонента орграфа G - максимальный подграф орграфа G, в котором любая пара вершин сильно связна.
k-компонента (максимальная по включению) - часть графа, в котором любая пара вершин k-соединима.
Полный подграф (complete subgraph) - подграф, в котором каждая пара вершин смежна.
Клика (clique) - полный подграф графа G, такой, что в G не существует вершины, смежной со всеми вершинами данного подграфа [т.е. это максимальный полный подграф ].
Пустой подграф (внутренне-устойчивое множество вершин) - подграф графа G, в котором любая пара вершин несмежна.
Дерево Штейнера (Steiner's tree) - часть графа без циклов, связывающая заданное множество вершин.
Треугольник графа - полный подграф, состоящий из трех вершин.
Односторонняя компонента орграфа - максимальный подграф, для любых двух вершин которого по крайней мере одна достижима из другой.
Слабая компонента орграфа - максимальный слабый подграф графа.
Маршрут или путь - чередующаяся последовательность x₁, u₁, x₂, u₂, ... , x_k вершин x_i и ребер u_i, обладающая тем свойством, что любая пара соседних элементов инцидентна.
Цепь (trail, path) - маршрут, в котором все ребра различны.
Простая цепь - цепь, в которой все вершины различны.
Цикл (cycle) - цепь, у которой начальная и конечная вершины совпадают.
Простой цикл - простая цепь, у которой концевые вершины совпадают.
Ориентированная цепь - цепь орграфа G, в которой ориентация дуг (ребер) совпадает.
Контур (elementary circuit) - ориентированная цепь, у которой начальная и конечная вершины совпадают.
Эйлерова цепь (Euler path) - цепь, содержащая все ребра графа в точности один раз.
Эйлеров цикл (Euler cycle) - эйлерова цепь, у которой начальная и конечная вершины совпадают.
Гамильтонова цепь (Hamilton path) - простая цепь, которая содержит все вершины графа.
Гамильтонов цикл (Hamilton cycle) - гамильтонова цепь, у которой начальная и конечная вершины совпадают.
Независимые (вершинно-непересекающиеся, вершинно-независимые) маршруты - множество маршрутов, у которых все элементы различны (быть может, кроме конечных вершин).
Реберно-независимые (реберно-непересекающиеся) маршруты - множество маршрутов, у которых ребра (дуги) различны, т.е. не существует ребра, которое одновременно принадлежит нескольким маршрутам.
(s, t)-цепь (путь) ((s, t)-path) - цепь, у которой вершины s и t концевые.
Разрез (сечение графа) (cut-set) - множество элементов, удаление которых увеличивает число компонент (односторонних компонент, слабых компонент) связности графа.
Простой разрез - разрез, у которого любое собственное подмножество элементов не является разрезом.
Смешанный разрез - разрез, элементами которого выступают как ребра (дуги), так и вершины.
Реберный разрез - все элементы разреза ребра (дуги).
Вершинный разрез. Все элементы разреза - вершины.
(s, t)-разрез - разрез, при удалении которого вершина t не достижима из s.
Независимое множество элементов (упаковка) [независимое множество вершин или ребер] (independent vertex or link set) - множество ребер (дуг) или вершин, попарно несмежных.
Покрытие (covering) - множество X' вершин (U' ребер), такое, что каждое ребро (вершина) инцидентна хотя бы одной вершине из X' (ребру U').
Максимальная упаковка - максимально возможное число элементов в соответствующей упаковке.
Минимальное покрытие - минимально возможное число элементов в соответствующем покрытии.
Независимое множество вершин (внутренне устойчивое множество, пустой подграф) (independent vertex set) - множество X' вершин, в котором никакие две вершины несмежны.
Максимальное независимое множество вершин (maximal independent vertex set) - такое независимое множество вершин, что при добавлении в него любой другой вершины графа это множество перестает быть независимым.
Примечание: "максимальность" в смысле данного определения означает не максимальную мощность, а "нерасширяемость" множества; в общем случае граф может иметь несколько максимальных независимых множества вершин разной мощности.
Паросочетание (независимое множество ребер) (matching, independent link set) - множество U' ребер, в котором никакие два ребра несмежны.
Совершенное паросочетание (perfect matching) - такое паросочетание, что любая вершина графа инцидентна некоторому ребру этого паросочетания.
Доминирующее множество вершин (внешне устойчивое множество) - множество X' вершин, таких, что каждая вершина, не принадлежащая X', смежна с вершиной из X'.
Вершинное покрытие (опора) - множество X' вершин, таких, что всякое ребро инцидентно вершине из X'.
Реберное покрытие (покрывающий суграф) [доминирующее множество ребер ] (edge covering) - множество U' ребер, таких, что всякая вершина инцидентна ребру из U'.
Экстремальное подмножество нетождественной стабильности - подмножество вершин графа, относительного которого фиксатор группы нетождественный, но добавление любой вершины из оставшихся приводит к тождественному фиксатору.
Экстремальное подмножество тождественной стабильности - подмножество вершин графа, относительно которого фиксатор группы тождественный, но удаление любой вершины из подмножества приводит к нетождественному фиксатору.
Минимальный разрез - разрез с наименьшим числом элементов.
Минимальная цепь - (s, t)-цепь с минимальным числом ребер.
Максимальный разрез - разрез с наибольшим числом элементов среди всех простых разрезов графа.
Максимальная цепь - простая (s, t)-цепь с максимально возможным числом ребер.
Максимальная клика - клика с максимально возможным числом вершин среди клик графа.
Минимальное дерево Штейнера - дерево Штейнера с минимально возможным суммарным весом ребер.
Максимальное паросочетание - паросочетание с максимально возможным числом ребер в паросочетании данного графа (числом реберной независимости).
Фундаментальный цикл (контур) - цикл, определяемый некоторым остовом и хордой графа (орграфа).
Минимальный цикл (обхват) - цикл с минимально возможным числом ребер среди всех циклов графа.
Расстояние между вершинами s и t - равно длине минимальной (s, t)-цепи.
i-й ярус вершин - подмножество вершин, находящихся на расстоянии i от заданной вершины.
Одноцветный класс - множество всех вершин одного цвета.
Взвешенный граф - граф, вершинам и/или (обычно) ребрам которого поставлены в соответствие целые или вещественные числа (веса).
Вес (длина) - денотат [значение ] числа, поставленного в соответствие взвешенному элементу.
Величина (разреза, цепи, цикла и т. п.) - суммарный вес элементов, входящих в данное подмножество.
Наибольшее паросочетание - паросочетание с наибольшей величиной.
Критический путь - (s, t)-путь в ациклическом орграфе наибольшей величины.
Кратчайшая цепь - (s, t)-цепь с наименьшей величиной.
Расстояние между вершинами s и t - величина кратчайшей (s, t)-цепи. Если s и t несоединимы, то расстояние между этими вершинами равно Ґ.
Вес цикла - величина цикла.
Отрицательный цикл - цикл, который имеет отрицательную величину.
Длина маршрута (цепи, пути) - величина маршрута.
Дерево кратчайших цепей - корневое остовное дерево, в котором расстояния от корня до всех остальных вершин равны соответствующим расстояниям в исходном графе.
Наибольший разрез (максимальный) - простой разрез с наиболее возможной величиной.
Наименьший разрез (минимальный) - простой разрез с минимально возможной величиной.
Минимальное (наименьшее, кратчайшее) остовное дерево - остовное дерево с минимально возможной величиной.
Висячая вершина - вершина, которая не имеет инцидентных ребер.
Хорда - ребро графа, не принадлежащее остову.
Два графа изоморфны ,если они отличаются лишь нумерацией своих вершин.G1=(V1,E1) G2=(V2,E2) G1~G2 (изоморфны) , если существует взаимнооднозначное соответствие между множествами их вершин, сохраняющее отношение смежности.Граф G1 изоморфен графу G2 , если :

Подходы к поиску изоморфной подстановки: переборный или эвристический.
ПРИГ - задача распознания изоморфизма.Подходы к решению ПРИГ:
1. переборные методы:
1.1 прямой перебор;
1.2 направленный перебор
2. непереборные методы:
2.1 Разработка теории сокращения и ликвидации перебора
Перебор сокращается с использованием:
1 глобальных инвариантов
2 квазиглобальных инвариантов
3 локальных инвариантов
Характеристика методов:
1 Переборный
2 Непереборный
Для большинства существуют простые и эффективные алгоритмы ,которые позволяютразличать граафы на основе инвариантов и выделять изоморфную подстановку.
Элементы комбтнаторного анализа.

Комбинаторный анализ включает три раздела:
1 Теория перечислений.
2 Теория порядка.
3 Теория конфигурацийй.
Теория перечислений.
Определения:
Правило равенства: Если N и R конечные множества и существует биекция между ними то |N|=|R|
Правило суммы: Если конечное множество состоящее из конечных попарно непересекающихся множеств то

Мультимножество - множество на множестве S вместе с функцией задающей кратность элементов S , где Обычно обозначается : (мультимножество k на S)

Даны два множества N и R и отображение . Тогда тройка (f,N,R) называется морфизмом. |N|=n |R|=r
Наша цель - разбиение морфизмов на классы с последующим перечислением и упорядочением перечисленных классов. Под перечислением классов будем понимать перечисление числа элементов в нем . Конструктивное перечисление отображений - перечисление этих отображений с дальнейшим их подсчетом. Отображению сопоставим образ im(f) и ядро ker(f)

, т.е. ядро отображения f - это разбиение множества индуцированное отношением эквивалентности.

Различаем 4 класса отображений:
1 Произвольное

2 Сюрьективное

3 Инъективное
для всех a ,a*
4 Биективное
, где f инъективна и сюрьективна одновременно.
Если множества N и R конечны , то

Элементы теории порядка.

Отношение на множестве X - есть частичный порядок , если имеют место
рефлексивность :x<=x для всех х Х
транзитивность : x<=y, y<=z => x<=z для всех x,y,z X
Если x<=y и y<=x то x=y
Если x<=y но то x<y и имеет место строгий линейный порядок
Отображение называют монотонным если оно сохраняет отношение порядка. (если a<=b то f(a)<=f(b) для всех a,b N)

Метод включения - исключения.
Основная теорема - обобщение общеизвестной формулы:

Теорема (включения - исключения).

Доказательство: Индукция по n. При n=1 теорема справедлива (очевидно). Предположим что для произвольных подмножеств справедливо:

Применяя эту формулу к объединению:

получаем:

и следовательно:

Ч.т.д