П

Панциклический граф(Pancyclic graph)
- граф, содержащий простые циклы всех длин от 3 до n = n(G) включительно.
Литература:[Зыков]

Пара связностей(Pair of connectivities)
- для графа G упорядоченная пара (a,b) таких целых неотрицательных чисел, что в G найдется множество, содержащее a вершин и b ребер, удаление которых делает граф несвязным, и не найдется множества с a - 1 вершинами и b ребрами или a вершинами и b - 1 ребрами, обладающего тем же свойством. Данное понятие обобщает оба понятия вершинной связности и реберной связности.
См. также Функция связности.
Литература: [Харари]

Параллельные ребра - то же, что и Кратные ребра.

Паросочетание(Matching)
- произвольное подмножество попарно несмежных ребер графа. Паросочетание называется максимальным, если оно не содержится в паросочетании с большим числом ребер, и наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа.
Другое название - Независимое множество ребер.
Литература:[Лекции]

Паросочетание вершинно-реберное инцидентное - см. Вершинно-реберное инцидентное паросочетание.

Паросочетание максимальное - см. Паросочетание.

Паросочетание наибольшее - см. Паросочетание.

Паросочетание правильное - см. Правильное паросочетание.

Паросочетание совершенное - см. Совершенное паросочетание.

Паросочетание частичное - см. ?????Частичное паросочетание.

Паросочетания взаимные - см. Взаимные паросочетания.

Переменная вершина(Variable vertex)
- вершина, помеченная некоторой переменной.
Литература:[Евстигнеев-Касьянов]

Перемешанная таблица - см. Информационное множество.

Перенумерованный граф(Evaluated graph)
- граф, вершины которого занумерованы натуральными числами от 1 до n, где n - число вершин в графе, используемыми в качестве имен вершин.
См. также Нумерация вершин; Помеченный граф.
Литература:[Лекции]

Пересечение графов(Intersection of graphs)
- граф G = G[_1] [cap] G[_2], множество вершин которого есть пересечение множеств вершин, а множество ребер - пересечение множеств ребер исходных графов.
Литература:[Алгоритмы]

Перестановочный граф(Permutation graph)
- граф пересечений сегментов в диаграмме пересечений перестановки; для построений последней возьмем по n точек на двух параллельных прямых и соединим прямолинейными отрезками пары точек согласно биекции определяемой перестановкой.
Литература:[Golumbic]

[alpha]-перестановочный граф([alpha]-permutation graph)
- для помеченного графа G и любой подстановки [alpha] из симметрической группы S[_p] граф, представляющий собой объединение двух непересекающихся копий G[_1] и G[_2] графа G, между которыми проведены ребра, соединяющие вершины v[_i] графа G[_1] с вершинами v[_alpha](i) графа G[_2].
Литература:[Харари]

Перечисление графов(Graph enumeration)
- подсчет числа неизоморфных графов в заданном классе (с заданными характеристиками).
Литература:[Алгоритмы]

Перешеек - то же, что и Мост.

Периферийная вершина(Peripheral vertex)
- вершина, эксцентриситет которой равен диаметру графа.
Литература:[Лекции]

q-периферийная вершина(q-peripheral vertex)
- периферийная вершина во взвешенном графе.
Литература:[Зыков]

Петля(Loop)
- дуга или ребро вида (v,v), v [include] V(G), элемент псевдографов. В приложениях, однако, допускается и в орграфах, рассматриваемых как модель системы.
Литература:[Лекции], [Кристофидес]

Планарный граф(Planar graph)
- граф, который может быть изображен на плоскости так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины. Другими словами, граф, изоморфный плоскому графу.
Литература:[Лекции]

Планарный матроид(Planar matroid)
- 1) матроид, являющийся одновременно графическим и кографическим;
2) графический матроид плоского графа.
Справедлива теорема: Матроид является планарным тогда и только тогда, когда он регулярен и не содержит миноров, изоморфных M(K[_5]), M(K[_3,3]) или двойственным им матроидам.
Литература:[Уилсон], [Welsh]

Плоская карта(Plane map)
- связный плоский граф вместе со всеми его гранями.
Литература:[Харари]

Плоская нумерация(Plane numbering)
- такая нумерация вершин, что если вершины графа расположить в целочисленных точках числовой оси, то его дуги можно вложить в плоскость без пересесечений.
Литература:[Евстигнеев]

Плоская триангуляция(Plane triangulation)
- связный плоский граф, каждая грань (в том числе и внешняя) которого является треугольником.
Литература:[Лекции]

Плоский граф(Planar graph)
- граф, изображенный на плоскости так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины.
См. также Планарный граф.
Литература:[Лекции]

(a,b)-плоский граф((a,b)-planar graph)
- такой граф G, что при добавлении ребра (a,b) полученный граф G' можно расположить на плоскости без пересечения ребер.
Литература:[Берж]

Плоское дерево(Planar tree)
- дерево, вложенное в евклидову плоскость.
Литература:[Евстигнеев-Касьянов]

r-плотное дерево(r-dense tree)
- m-арное дерево для r [include] [1 : m], удовлетворяющее условиям:
а) корень дерева по крайней мере бинарен;
б) каждая ненасыщенная вершина, отличная от корня, имеет не менее r насыщенных братьев;
в) все висячие вершины располагаются на одном уровне.
Литература:[Евстигнеев-Касьянов]

Плотность - то же, что и Кликовое число.

Подграф(Subgraph)
- 1. для графа G = (V,E) такой граф H = (W,U), у которого множество вершин W есть подмножество вершин графа G, W [subseteq] V, множество ребер/дуг U есть подмножество множества ребер/дуг E, U [subseteq] E, причем если
(x,y) [include] E и x,y [include] W, то обязательно (x,y) [include] U. Это определение подграфа мы будем называть сильным определением подграфа. Оно восходит к К.Бержу и распространено в большей части русскоязычной литературы.
2. То же, что и часть графа. Это определение будем называть слабым определением подграфа; оно распространено в части русскоязычной и практически во всей англоязычной литературе.
Литература:[Берж], [Зыков], [Харари], [Лекции]

Подграф запрещенный(Forbidden subgraph)
- в уграфе с начальной вершиной p[_0] такой подграф, содержащий три различные вершины p[_1], p[_2] и p[_3], который образован тремя не пересекающимися по внутренним вершинам простыми путями P[_0,1], P[_1,2], P[_1,3], P[_2,3], и P[_3,2], где P[_i,j], обозначает путь от вершины p[_i] до вершины p[_j].
Литература:[Касьянов], [Евстигнеев-Касьянов]

Подграф двусвязный - см. Блок.

Подграф индуцированный - то же, что и Порожденный подграф.

Подграф линейный - см. Линейный подграф графа.

Подграф остовный - см. Остовный подграф.

Подграф порожденный - см. Порожденный подграф.

Подграф четный - то же, что и Четный подграф.

Поддерево(Subtree)
- связный подграф дерева.
Литература:[Лекции]

Поддерево с корнем r (Subtree with the root r)
- поддерево ордерева, порожденное вершиной r и всеми ее потомками.
Литература:[Лекции], [Евстигнеев-Касьянов]

Подобные вершины(Similar verticies)
- вершины a и b такие, что для некоторого автоморфизма [alpha] имеет место равенство [alpha](a) = b.
Литература:[Харари]

Подобные ребра(Similar edges)
- ребра e[_1] и e[_2] такие, что существует автоморфизм [alpha], для которого [alpha] (e[_1]) = e[_2].
Литература:[Харари]

Подразбиение ребра(Subdivision of an edge)
- операция, состоящая из удаления ребра e = (x,y) и добавления двух новых ребер e[_1] = (x,z) и e[_2] = (z,y), где z - новая вершина степени 2.
См. Гомеоморфные графы.
Литература:[Лекции]

Подразбитое ребро(Subdivided edge)
- ребро e = (x,y), замененное в результате применения операции подразбиения ребра на ребра (x,z) и (z,y). Возможно многократное применение операции подразбиения ребра, т.е. замена ребра на простую цепь.
Литература:[Лекции]

Подстепени группы графа(Subdegrees of a graph group)
- совокупность чисел элементов в каждой орбите фиксатора вершины для транзитивной группы графа.
Литература:[Алгоритмы]

Подцепь(Subchain)
- часть цепи, сама являющаяся цепью графа.
Литература:[Лекции]

Поиск в глубину(Depth first search)
- метод ситематического прохождения (посещения) вершин графа, когда за счет продвижений от текущей вершины по ребру вперед (к еще непросмотренной вершине) всегда, когда это возможно, и возвратов от текущей вершины по пройденному ребру назад (к ранее пройденной вершине), если движение вперед от текущей вершины не возможно, осуществляется движение по всем вершинам графа, достижимым из заданной вершины s, с которой начинается поиск.
Поиск в глубину всегда завершается через конечное число шагов в вершине s - начале просмотра; после его завершения все ребра связного графа оказываются разбитыми на два класса: древесные, по которым осуществлялись переходы из посещенных вершин в непосещенные, и ребра касания, замыкающие циклы. Частичный граф, порожденный древесными ребрами, называется деревом поиска в глубину; он является каркасом графа.
Нумерация вершин графа в порядке их первого посещения в процессе поиска в глубину, называется M-нумерацией.
Поиск в глубину в орграфе отличается тем, что при движении вперед дуги проходятся в соответствии с их ориентацией. При этом после завершения обхода дуги оказываются разбитыми на четыре класса: древесные, прямые, замыкающие какой-либо путь из древесных дуг, обратные, замыкающие контур, и поперечные, ведущие в ранее пройденные вершины и не замыкающие ни контур, ни путь из древесных дуг. Частичный орграф, порожденный древесными дугами, является либо корневым растущим ордеревом (дерево поиска в глубину), либо лесом, каждая компонента которого есть корневое растущее дерево.
Поиск в глубину является основой многих алгоритмов исследования структуры графа.
Другие названия -Возвратный ход, бектрекинг.
Литература:[Ахо-Хопкрофт-Ульман], [Касьянов], [Евстигнеев-Касьянов],

Поиск в ширину(Width (breadth) first search)
- метод обхода и разметки вершин графа в следующем порядке: началу обхода s приписываем метку 0, смежным с ней вершинам - метку 1. Теперь рассматриваем поочередно окружения всех вершин с метками 1 и каждой из входящих в эти окружения еще не занумерованных вершин приписываем метку 2 и т.д. Если исходный граф связен, то поиск в ширину пометит все его вершины. Дуги вида (i,i+1) порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом. Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т.д.
См. Топологическая сортировка.
Литература:[Лекции]

Поисковое дерево - см. Информационное множество.

Покрывающее множество вершин(Covering set of vertices)
- множество вершин такое, что каждое ребро имеет хотя бы один конец в этом множестве.
Другое название - накрывающее множество.
Литература:[Оре]

Покрывающий граф(Covering graph)
- часть графа, порождаемая покрывающим множеством вершин.
Другое название - накрывающий граф.
Литература:[Оре]

Покрытие вершинное - см. Вершинное покрытие.

Покрытие реберное - см. Реберное покрытие.

Покрытие путевое - см. Путевое покрытие.

Полином графа характеристический - см. Характеристический полином графа.

Полином графа хроматический - см. Хроматический полином графа.

NP-полная задача(NP-complete problem)
- такая задача A из класса NP всех распознавательных задач, недетерминированно разрешимых за полиномиальное время, что любая задача из NP полиномиально сводится к A.
Литература:[Лекции]

Полная разметка - см. Задача анализа свойств состояний.

Полная раскраска(Complete colouring)
- раскраска, определяемая полным гомоморфизмом; она обладает тем свойством, что для любых двух цветов в графе найдутся смежные вершины, окрашенные в эти цвета.
Литература:[Харари]

Полная система переписывания термов - см. Система переписывания термов.

Полная СПТ - см. Система переписывания термов.

Полный граф(Complete graph)
- граф, у которого каждая пара вершин соединена ребром.
Полный n-вершинный граф обозначается K[_n].
Литература:[Лекции]

Полный граф Бержа(Berge's complete graph)
- ориентированный псевдограф, у которого из каждой вершины в каждую идет ровно одна дуга, а каждой вершине инцидентна одна петля.
Литература:[Зыков]

Полный двудольный граф(Complete bipartite graph)
- двудольный граф, у которого любые две вершины, входящие в разные доли, смежны.
Литература:[Лекции]

Полный k-дольный граф(Complete k-partite graph)
- k-дольный граф, у которого любые две вершины, входящие в разные доли, смежны.
Литература:[Лекции]

Полный набор инвариантов(Complete set of graph invariants)
- набор инвариантов, определяющий граф с точностью до изоморфизма. В настоящее время неизвестно ни одной нетривиальной полной системы инвариантов для графов.
Литература:[Харари]

Полный орграф(Complete directed graph)
- орграф, у которого каждая пара вершин соединена дугой.
Литература:[Лекции]

Полный порядка n гомоморфизм(Complete homomorphism of order n)
- гомоморфизм [phi] такой, что [phi] G = K[_n].
Литература:[Харари]

Полный k-униформный гиперграф(Complete k-uniform hypergraph)
- гиперграф, у которого каждый набор из k вершин является ребром гиперграфа.
Литература:[Лекции]

Полугамильтонов граф(Semihamiltonian graph)
- граф, который содержит простую цепь, проходящую через каждую его вершину. Всякий гамильтонов граф является полугамильтоновым.
Литература:[Уилсон]

Полугруппа графа(Semigroup of graph)
- множество эндоморфизмов графа, т.е. множество гомоморфизмов графа в себя. Хедрлин и Пумтр доказали, что каждая конечная полугруппа с единицей изоморфна полугруппе некоторого графа.
Литература:[Харари]

Полуконтур(Semicycle)
- то же, что и цикл в орграфе.
Литература:[Лекции]

Полунесводимый граф(Semiirreducible graph)
- двудольный граф с V = S [cup] T, имеющий точно одно наименьшее вершинное покрытие M, причем или M [cap] S, или M [cap] T пусто. Верна теорема Харари и Пламмера:
Граф G и его реберное ядро C[_1](G) совпадают тогда и только тогда, когда G является двудольным полунесводимым или несводимым графом.
Литература:[Харари]

Полуостров(Peninsula)
- подграф, соединенный с остальной частью графа перешейком.
Литература:[Оре]

Полупуть(Semipath)
- то же, что и цепь в орграфе. Аналогично, как и для пути, вводятся понятия понятия простого полупути и полуконтура.
Литература:[Лекции],[Касьянов]}

Полурегулярная группа графа(Semiregular group of a graph)
- группа автоморфизмов, в которой стабилизатор (фиксатор) любой вершины является тождественным автоморфизмом.
Литература:[Алгоритмы]

Полустепень захода вершины(Indegree)
- в орграфе - число дуг, заходящих в вершину.
Литература:[Лекции]

Полустепень исхода вершины(Outdegree)
- в орграфе число дуг, исходящих из вершины.
Литература:[Лекции]

Полуэйлеров граф(Semieuler graph)
- граф, в котором существует цепь, проходящая через каждое его ребро. Каждый эйлеров граф является полуэйлеровым.
Литература:[Уилсон]

Полюс(Pole)
- выделенная вершина графа; обычно эти вершины являются истоками (входами) и стоками (выходами) в двухполюсных и многополюсных сетях.
Литература:[Алгоритмы]

Помеченный граф(Labeled graph)
- граф, вершинам которого приписаны метки, например номера 1, 2, ... , n или символы из какого-нибудь алфавита.
Литература:[Лекции]

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

Пороговый граф(Threshold graph)
- пусть IG - множество, элементами которого служат все независимые подмножества вершин графа G и пустое множество; если существуют такие неотрицательные вещественные числа [alpha][_1], [alpha][_2], ..., [alpha][_n], [beta], что множество всех (0,1)-решений неравенства [alpha][_1] x[_1] + [alpha] [_2]x[_2] + ... + [alpha][_n] x[_n] [leq] [beta] совпадает с множеством характеристических векторов элементов множества IG, то граф G называется пороговым.
Литература:[Лекции]

Порождающая грамматика(Production grammar)
- метод определения формального языка, в виде исчисления, позволяющего получить (породить) все цепочки определяемого языка L и только их, а также придать цепочкам ("предложениям") языка полезную структуру, которая может использоваться, например, для придания смысла предложениям языка.
    П.г. - это четверка G = (N, [sigma], P, S), состоящая из конечного множества продукций P, двух непересекающихся алфавитов: алфавита [sigma] терминальных символов (или терминалов), образующих цепочки определяемого языка L, и алфавита N нетерминальных символов (называемых также нетерминалами, синтаксическими переменными или понятиями), используемых при порождении языка L как вспомогательные, а также выделенного символа S [include] N, являющегося начальным (или исходным) символом для вывода цепочек языка L.
    Отношение непосредственной выводимости [LeftRightArrow][_G] на множестве (N [cup][sigma]) [^*] определяется следующим образом: если [alpha][beta][gamma]- цепочка из (N [cup][sigma]) [^*] и [beta] [RightLeftArrow][delta] - правило из P, то [alpha][beta][gamma] [LeftRightArrow][_G] [alpha][delta][gamma].
    Транзитивное замыкание отношения [LeftRightArrow][_G] обозначается через [LeftRightArrow][^+_G] ([phi][LeftRightArrow][^+_G][psi] читается: [psi] выводима из [phi] нетривиальным образом), а его рефлексивное и транзитивное замыкание - через [LeftRightArrow][^*_G] ([phi][LeftRightArrow] [^*_G][psi] читается: [psi] выводима из [phi]).
    Цепочка [alpha] называется выводимой цепочкой грамматики G, если S[LeftRightArrow] [^*_G][alpha].
    Язык, порождаемый грамматикой G (обозначается L(G)) - это множество терминальных выводимых цепочек грамматики G, т.е. L(G)={[smomega] : [smomega] [include][sigma][^*] и S[LeftRightArrow][^*_G] [smomega]}.
    Грамматика G называется:
    (1) праволинейной (или автоматной), если каждое правило из P имеет вид A[LeftRightArrow][alpha] B или A[LeftRightArrow][alpha],
где A,B[include] N и [alpha] [include][sigma][^*];
    (2) контекстно-свободной (или бесконтекстной), если каждое правило из P имеет вид A[LeftRightArrow][alpha],
где A[include] N и [alpha] [include] (N [cup][sigma][^*]);
    (3) контекстно-зависимой (или неукорачивающейся), если каждое правило из P имеет вид [alpha] [LeftRightArrow][beta],
где |[alpha]|[leq] |[beta]|.
Грамматика G, на которую не накладывается ни одно из указанных ограничений, называется грамматикой составляющих (или грамматикой с фразовой структурой).
Литература:[Касьянов-Поттосин], [Евстигнеев-Касьянов]

Порожденный подграф(Induced subgraph)
- подграф, порождаемый заданным множеством вершин, есть подграф в сильном смысле; подграф, порождаемый заданным множеством ребер, есть подграф в слабом смысле.
Литература:[Берж], [Лекции]

Порядок графа(Order of a graph)
- число вершин в графе.
Литература:[Лекции]

Порядок гиперграфа(Order of a hypergraph)
- число вершин в гиперграфе.
Литература:[Лекции]

Порядок группы графа(Order of an automorphism group)
- число автоморфизмов в группе графа.
Другое название - Число симметрии графа.
Литература:[Алгоритмы]

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

Последовательность графа степенная - см. Степенная последовательность графа.

Последовательность графическая - см. Графическая последовательность чисел.

Последовательность правильная - см. Правильная последовательность.

Последовательность расщепляемая - см. Расщепляемая последовательность.

Последовательность сведения(Derived sequence)
- последовательность различных k-производных графов

G[_0] ,G[_1] , G[_2] ,... ,G[_l] ,
в которой G[_l] - предельный граф. l называется длиной последовательности сведения.
Литература: [Касьянов], [Евстигнеев-Касьянов].

Последовательность угадывающая - см. Угадывающая последовательность.

Последовательность униграфическая - см. Униграфическая последовательность.

Поток(Flow)
- целочисленная функция f(e), определенная на множестве E дуг транспортной сети и удовлетворяющая следующим условиям:
1) 0[leq] r(e) [leq] f(e) [leq] c(e), e [include] E;
2) [Formula-10].
    [xinv]                   [yinv]
    Здесь r(e) называется нижней пропускной способностью дуги e, а c(e) - верхней пропускной способностью. Число

[Formula-11]
где s - вход сети, а t - выход, называется величиной или мощностью потока. Поток, величина которого наибольшая среди всех потоков по данной сети, называется наибольшим или максимальным потоком. Аналогично определяется минимальный поток. Для наибольших потоков справедлива теорема Форда-Фалкерсона:
Величина наибольшего потока равна пропускной способности минимального разреза.
Литература:[Берж], [Кристофидес], [Свами-Тхуласираман]

Потомок вершины(Descendent of a vertex)
- для вершины v любая вершина w, достижимая из v; w называется непосредственным потомком вершины v, если существует дуга (v,w). Непосредственный потомок в ордереве часто называют сыном вершины v.
Литература:[Евстигнеев-Касьянов], [Лекции]

Почти однородный граф(Nearly regular graph)
- двудольный (бесконечный) граф G = (V' ,V" ;E), у которого степени вершин в каждой доле имеют вид
s(a' ) = m - d(a' ), s(a'' ) = m - d(a'' ) для a' [include] V' , a'' [include] V'' , где отклонения d(a' ) и d(a'' ) - положительные ии отрицательные целые числа, причем лишь конечное их число отлично от нуля.
Литература:[Оре]

Правило переписывания(Rewriting rule)
- упорядоченная пара термов s, t, обычно записываемая в виде s[RightLeftArrow] t, в которой терм s отличен от переменной и содержит переменные только терма t.
    П.п. используется для порождения на множестве термов отношения редукции;
см. Система переписывания термов.
Литература: [Касьянов-Поттосин], [Евстигнеев-Касьянов].

Правильная нумерация(Proper numbering)
- нумерация F, относительно которой каждый луч является F-лучом.
Литература: [Касьянов], [Евстигнеев-Касьянов].

Правильная последовательность(Well-formed sequence)
- последовательность натуральных чисел длины n, удовлетворяющая следующим условиям:
1) n-1 [geq] d [_1] [geq] d[_2] [geq] ... [geq] d[_n],
2)[Formula-12] - четное число.
Без ограничения общности можно считать, что всякая графическая последовательность чисел правильная.
Литература:[Лекции]

Правильная раскраска(Proper (vertex) colouring)
- раскраска, при которой всякие смежные вершины (смежные ребра) раскрашены в разные цвета.
Литература:[Лекции]

Правильное паросочетание(Proper matching)
- частичное паросочетание {A,M[_A]} в двудольном графе (V,V';E) такое, что после удаления всех вершин из V и V', которые участвуют в M[_A], и всех ребер с концом в этих вершинах остающееся множество V \ A является множеством без дефицита (или с дефицитом, равным нулю) в полученном графе.
Литература:[Оре]

Правильный граф(Well-formed graph)
- орграф, для которого существует покрытие дуг путями, исходящими из входа орграфа.
Литература:[Евстигнеев]

Правильный уграф(Proper control flow graph)
- уграф, все вершины которого лежат на путях от его начальной вершины до конечных вершин.
Литература: [Касьянов], [Евстигнеев-Касьянов].

Правостороннее дерево(Right linear tree)
-
Литература:[Евстигнеев-Касьянов]

Предельный граф(limit graph)
- такой k-производный от исходного графа G граф G[_k], что G[_k]=G[_k+1].
Литература: [Касьянов], [Евстигнеев-Касьянов].

Предок вершины(Predecessor of a vertex)
- для вершины w всякая вершина v, из которой достижима w; v называется непосредственным предком (или предшественником), если существует дуга (v,w); непосредственный предок в ордереве часто называется отцом вершины w.
Литература:[Евстигнеев-Касьянов], [Лекции]

A-представление уграфа - см. Иерархия вложенных альтов.

Предшественник вершины - см. Предок вершины.

Предшественник обязательный - см. Обязательный предшественник.

Преемник вершины - см. Потомок вершины.

Преемник обязательный - см. Обязательный преемник.

Приведенное путевое покрытие(Reduced path covering)
- путевое покрытие P = (p[_1] , ..., p[_k]) удовлетворяющее условиям:
а) ни один путь не является начальным отрезком другого пути в покрытии;
б) ни один путь p[_i] нельзя заменить его начальным отрезком.
Литература:[Евстигнеев]

Примитивный орграф(Primitive directed graph)
- орграф, у которого какая-нибудь степень его матрицы смежности целиком состоит из положительных чисел; орграф примитивен тогда и только тогда, когда длины его простых контуров имеют наибольший общий делитель, равный 1.
Литература:[Харари]

Проблема изоморфизма графов(Isomorhism problem)
- Пусть G и G' - два графа, причем |V(G)| = |V(G')| и |E(G)| = |E(G')|. Требуется установить, изоморфен ли граф G графу G'.
Литература:[Лекции]

Проблема изоморфного подграфа(Subgraph isomorphism problem)
- для двух графов G и G' требуется установить, существует ли в графе G' подграф (частичный граф), изоморфный графу G.
Литература:[Лекции]

Проблема изоморфной вложимости(Isomorphic embedding problem)
- для двух графов G и G' требуется установить, существует ли в графе G' подграф (в сильном смысле, порожденный подграф) изоморфный G.
Литература:[Лекции]

Проблема КЈнига(Konig's problem)
- Установить, какие условия необходимы и достаточны, чтобы для заданной на множестве V группы подстановок Г существовал такой граф G с множеством вершин V, что Aut(G) = Г.
Литература:[Лекции]

Проблема клики(Clique problem)
- заданы граф G и натуральное число c; установить, верно ли неравенство [smomega](G) [geq] c, где [smomega](G) - кликовое число (плотность).
Литература:[Лекции]

Проблема окружения(Circumstance problem)
- существует ли такой граф L = (X,U) для произвольного заданного графа P, что окружение O(L,x) изоморфно графу P для любой вершины x [include] X?
Литература:[Зыков]

Прогрессивно конечный граф(Progressive finite graph)
- орграф, в котором не существует путей бесконечной длины, начинающихся в какой-либо вершине.
Литература:[Берж]

Прогрессивно ограниченный граф(Progressive bounded graph)
- орграф такой, что для некоторого целого числа m длины всех путей, начинающихся в любой вершине, не превосходят m.
Литература:[Берж]

Продукция(Production)
- упорядоченная пара цепочек [alpha], [beta], обычно записываемая в виде [alpha] [RightLeftArrow][beta], в которой [alpha] называется левой частью, а [beta] - правой частью и которая может использоваться для вывода одной цепочки из другой.
См. Порождающая грамматика и Формальный язык.
Другое название - Правило вывода.
Литература: [Касьянов-Поттосин], [Евстигнеев-Касьянов].

Произведение графов(Product of graphs)
- для данных графов G[_1] = (V[_1] , E[_1]) и G[_2] = (V[_2] , E[_2]) произведением называется граф G = (V,E), вершины которого V(G) = V[_1] [times] V[_2] - декартово произведение множеств вершин исходных графов.
Декартово произведение G = G[_1] [box] G[_2] содержит ребра ((x[^1], x[^2]), (y[^1] , y[^2])) [include] E(G[_1] [box] G[_2]) тогда и только тогда, когда (x[^1] ,y[^1] ) [include] E[_1] и x[^2] = y[^2] или x[^1] = y[^1] и (x[^2],y[^2] ) [include] E[_2].
Прямое (тензорное) произведение G = G[_1] [times] G[_2] содержит ребра ((x[^1], x[^2]), (y[^1], y[^2])) [include] E(G[_1] [times] G[_2]) тогда и только тогда, когда (x[^1], y[^1]) [include] E[_1] и (x[^2], y[^2]) [include] E[^2].
Сильное произведение G = G[_1] [otimes] G[_2] содержит все ребра ((x[^1], x[^2]), (y[^1] ,y[^2])) [include] E(G[_1] [otimes] G[_2]), которые есть и в декартовом, и в тензорном произведениях.
Композиция G[_1] [G[_2]] графов содержит ребра ((x[^1], x[^2]), (y[^1], y[^2])) [include] E(G[_1][ G[_2]]) тогда и только тогда, когда
(x[^1], y[^1]) [include] E[_1] или x[^1] = y[^1] и (x[^2], y[^2]) [include] E[_2].
См. также Декартово произведение графов.
    Модульное произведение G[_1] [ldiamond] G[_2] содержит ребра

((x[^1], x[^2]), (y[^1], y[^2])) [include] E(G[_1] [ldiamond] G[_2])

тогда и только тогда, когда x[^1] [neq] y[^1], x[^2] [neq] y[^2] и либо (x[^1],y[^1]) [include] E[_1] и (x[^2],y[^2]) [include] E[_2],
либо (x[^1],y[^1]) [nin] E[_1] и (x[^2],y[^2]) [nin] E[_2].
    Большое модульное произведение G[_1] [Diamond] G[_2] содержит ребра

((x[^1],x[^2]), (y[^1],y[^2])) [include] E(G[_1] [Diamond] G[_2])

тогда и только тогда, когда x[^1] [neq] y[^1], x[^2] [neq] y[^2] и либо (x[^1],y[^1]) [include] E[_1] и (x[^2],y[^2]) [include] E[_2], либо (x[^1],y[^1]) [nin] E[_1].
Литература:[Berge], [Берж], [Оре], [Харари], [Лекции], [Bondy-Murty]

Произведение графов модульное - см. Произведение графов.

Производный граф(Derived graph)
- фактор уграф, полученный из исходного стягиванием в вершины его максимальных интервалов.
Литература: [Касьянов], [Евстигнеев-Касьянов].

k-производный граф(k-derived graph)
- уграф G[_k], совпадающий с исходным уграфом G при k=0 либо являющийся производным от G[^k-1] при k > 0.
Литература: [Касьянов], [Евстигнеев-Касьянов].

Произвольно вычерчиваемый граф(Arbitrarily traceable graph)
- граф такой, что выйдя из вершины x[_0] и соблюдая лишь одно правило - никогда не идти по уже пройденному ребру, - мы неизбежно получим эйлеров цикл. Граф произвольно вычерчиваем из x[_0] в том и только том случае, если степени всех его вершин четны и цикломатическое число [lambda](L \ x[_0]) подграфа L \ x[_0] равно 0.
Литература:[Зыков], [Харари]

Произвольно гамильтонов граф(Arbitrarily hamiltonian graph)
- граф, для которого гамильтонов цикл всегда получается с помощью следующей процедуры: начинаем с произвольной вершины, последовательно переходим в любую смежную вершину, еще не пройденную, и продолжаем до тех пор, пока не исчерпаем все вершины.
Литература:[Харари]

Произвольно проходимый граф(Arbitrarily traverseable graph)
- граф, для которого остовная цепь всегда получается с помощью следующей процедуры: начинаем с произвольной вершины, последовательно переходим в любую смежную вершину, еще не пройденную, и продолжаем до тех пор, пока не исчерпаем все вершины.
Литература:[Харари]

Пропускная способность дуги - см. Поток.

Пропускная способность разреза - то же, что и Величина разреза.

Пропускная способность ребра - см. Поток.

Простая цепь(Simple chain)
- цепь, в которой ни одна вершина не встречается дважды.
Литература:[Лекции]

Простое вращение - см. Вращение простое.

Простой гамак - см. Гамак.

Простой граф(Simple graph)
- 1. Нетривиальный граф G такой, что разложение G = G[_1] [times] G[_2] возможно лишь тогда, когда или G[_1], или G[_2] - тривиальный граф.
2. То же, что и двудольный граф (Берж).
3. То же, что и обыкновенный граф.
Литература:[Харари], [Берж], [Лекции]

Простой контур(Simple cycle)
- контур, в котором ни одна вершина не встречается дважды.
Литература:[Лекции]

Простой путь(Simple path)
- путь, в котором ни одна вершина не встречается дважды.
Литература:[Лекции], [Касьянов]

Простой разрез(Simple cutset)
- разрез, у которого любое собственное подмножество элементов не является разрезом.
Литература:[Алгоритмы]

Простой цикл(Simple circuit)
- цикл, в котором ни одна вершина не встречается дважды.
Литература:[Лекции]

Пространство коциклов матроида(Matroid cocycle space)
- для матроида M множество L[^*], содержащее все коциклы матроида M, объединения попарно непересекающихся коциклов и пустое множество.
Литература:[Лекции]

Пространство разрезов графа(Graph cutset space)
- для графа G множество, содержащее все разрезы графа, объединения попарно непересекающихся разрезов и пустое множество.
Литература:[Лекции]

Пространство циклов графа(Graph circuit space)
- для графа G множество, содержащее все циклы графа, объединения попарно непересекающихся циклов и пустое множество.
Литература:[Лекции]

Пространство циклов матроида(Matroid cycle space)
- для матроида M множество L, содержащее все циклы матроида M, объединения попарно непересекающихся циклов и пустое множество.
Литература:[Лекции]

Прямая дуга - см. Глубинное остовное дерево; Поиск в глубину.

F-прямая дуга(F-direct arc)
- дуга, для которой в заданной нумерации F номер начальной вершины строго меньше номера конечной вршины.
Другое название - F-дуга.
Литература: [Касьянов], [Евстигнеев-Касьянов].

Прямая нумерация - то же, что и M-нумерация.

Псевдовершина(Pseudovertex)
- вершина, образующаяся при стягивании некоторого множества вершин.
Литература:[Алгоритмы]

Псевдограф(Pseudograph)
- пара (V,E), где V - непустое множество вершин, а E - некоторое семейство неупорядоченных вершин (ребер), не обязательно различных. Другими словами, от графа псевдограф отличается тем, что в нем, как и в мультиграфе, допускаются кратные ребра и, кроме того, допускаются петли, причем возможно даже несколько петель при одной вершине.
Литература:[Лекции]

Псевдосимметрический граф(Pseudosymmetric digraph)
- орграф, в котором для каждой вершины полустепень захода равна полустепени исхода; всякий симметрический граф является псевдосимметрическим, но обратное неверно.
Литература:[Берж], [Lov\'{a}sz]

Пустой граф(Empty graph)
- граф, не содержащий ребер. Другие названия - вполне несвязный граф, регулярный степени 0 граф.
Литература:[Лекции]

Пустое дерево - то же, что и Дерево вырожденное.

Путевое покрытие(Path covering)
- 1) множество s-t-путей в орграфе с входом s и выходом t такое, что либо каждая вершина, либо каждая дуга принадлежит хотя бы одному пути из данного множества;
2) множество путей в графе такое, что либо каждая вершина, либо каждое ребро принадлежит хотя бы одному из путей.
Число путей в покрытии называется кратностью, а сумма длин путей - длиной покрытия.
Литература:[Евстигнеев]

Путь(Path)
- в орграфе такая последовательность вершин и дуг S = (v[_0] , e[_1] , v[_1] , ..., e[_n] , v[_n]), что e[_i] = (v[_i-1] , v[_i]) для i = 1, ..., n; и ни одна вершина в ней не встречается дважды; данный путь называется путем из v[_0] в v[_n] длины n с начальной вершиной v[_0], конечной вершиной v[_n] и внутренними вершинами v[_1] , ..., v[_n-1].
Литература:[Лекции],[Касьянов],[Евстигнеев]}

F-Путь(F-path)
- для данной нумерации F вершин орграфа путь, не содержащий F-обратных дуг, т.е. такой путь, у которого F-номера вершин образуют монотонно возрастающую последовательность. Если существует F-путь от v к w, то говорят, вершина w F-достижима из вершины v.
Литература:[Евстигнеев], [Касьянов]

Путь гамильтонов - см. Гамильтонов путь.

Путь кратчайший - см. Кратчайший путь.

Путь критический - см. Критический путь.

Путь простой - см. Простой путь.

k-пучок(k-bunch)
- система k различных простых цепей, соединяющих одну и ту же пару различных вершин и попарно не имеющих других общих вершин.
Литература:[Зыков]

k-пучково изоморфные графы(k-bunch isomorphic graph)
- графы, между ребрами которых можно установить взаимно однозначное соответствие, переводящее k-пучки в k-пучки.
Литература:[Зыков]