З

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

Задача анализа свойств состояний(Data flow analysis problem)
- Рассматривается полурешетка свойств (L,[sqcap]), не содержащая бесконечных цепей, множество преобразователей свойств F и функция M, сопоставляющая каждой дуге u анализируемого уграфа G=(V,U) функцию эффекта дуги M(u)[include] F. Прямая З.а.с.с формулируется как задача нахождения так называемой полной разметки - такой функции A:V[rarr] L, что

A(p)=[sqcap] {f[_alpha] (a[_0]):[alpha] - путь от начальной вершины до p}
где a[_0] - некоторое свойство, сопоставляемое начальной вершине уграфа, а f[_alpha] - функция эффекта пути, полученная композицией функций эффектов составляющих его дуг. Указанная задача алгоритмически неразрешима и допускает эффективное решение лишь для узких своих подклассов, таких, как, например, дистрибутивные З.а.с.с., в которых состоит F только из дистрибутивных функций. Поэтому обычно рассматриваются алгоритмы нахождения приближенных решений задачи, связанных с нахождением корректных разметок - таких B:V[rarr] L, что B(p)[sqin] f[_alpha] (a[_0]) для любых вершины p и пути [alpha] из a[_0] в p.
В отличие от прямой обратная З.а.с.с. предполагает известным начальное свойство для конечной вершины уграфа и обратное направление применения функций эффектов дуг.
В общей постановке с каждой дугой уграфа могут связываться функции ее эффектов как в прямом, так и обратном направлении.
Другие названия - задача потокового анализа и задача глобального анализа потока данных.
Литература:[Касьянов]

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

Задача китайского почтальона (Chinese postman's problem)
- во взвешенном графе найти цикл, проходящий через каждое ребро по крайней мере один раз и такой, что для него суммарная длина (длина каждого ребра учитывается столько раз, сколько это ребро встречается в цикле) минимальна. Если граф эйлеров, то любой эйлеров цикл дает оптимальное решение задачи.
Литература:[Кристофидес]

Задача коммивояжера(Traveling salesman problem)
-r Коммивояжер должен посетить каждый из n городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти кратчайший маршрут, зная расстояния между каждой парой городов. Математическая постановка этой задачи состоит в следующем: в полном взвешенном графе требуется найти гамильтонов цикл (или цепь) наименьшего веса (длины).
Данная задача является NP-полной; для ее решения не существует эффективного алгоритма. Важность этой задачи связана с тем, что к ней сводятся многие другие задачи; в связи с чем она играет роль эталонной задачи.
Литература:[Лекции], [Кристофидес]

Задача о бродячем торговце - то же, что и Задача коммивояжера.

Задача о кенигсбергских мостах(Koenigsberg's bridges problem)
- задача обхода всех семи мостов города Кенигсберга (ныне Калининграда) таким образом, что каждый мост проходится в точности один раз. Задача была поставлена и решена Эйлером в 1736 г. в виде общей проблемы теории графов: при каких условиях связный граф содержит цикл, проходящий через каждое его ребро?
Литература:[Лекции]

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

Задача NP-полная - см. NP-полная задача.

Задача о свадьбах(Marriage problem)
- Известно некоторое множество X юношей, каждый из которых знаком с несколькими девушками. При каких условиях можно женить юношей так, чтобы каждый из них женился на знакомой ему девушке? Математическая постановка задачи состоит в нахождении в двудольном графе (X,Y,E) паросочетания, покрывающего X.
Литература:[Лекции]

Задача NP-сложная - см. NP-полная задача.

Задача NP-трудная - см. NP-полная задача.

Задача Штейнера на графах(Steiner's problem in graphs)
- Задача отыскания во взвешенном графе дерева наименьшего веса, покрывающего выделенное подмножество вершин. Другие вершины могут стягиваться деревом или нет в зависимости от требования минимизации веса дерева.
Литература:[Кристофидес]

Задача Штейнера на плоскости - то же, что и Евклидова задача Штейнера.

Задача унификации(Unification problem)
- по двум описаниям X и Y определить, можно ли найти объект Z, который удовлетворяет обоим описаниям.
Обычно уточняется как задача нахождения по данным двум термам, содержащим переменные, такой подстановки термов вместо переменных, которая превратила бы исходные термы в идентичные. В том случае, когда такая подстановка для термов существует, она называется унификатором, а термы называются унифицируемыми. Если термы унифицируемы, то у них может быть много унификаторов, но всегда существует и единственен наибольший общий унификатор, из которого с помощью композиций подстановок можно получить все другие унификаторы.
Литература:[Евстигнеев-Касьянов]

Замкнутая окрестность(Closed neighbourhood)
- окрестность вершины v, пополненная вершиной v; иначе подграф, порожденный вершиной v и всеми смежными с ней вершинами.
Литература:[Харари]

Замкнутая цепь - то же, что и Цикл.

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

Замкнутый путь - то же, что и Контур.

Замыкание графа(Closure of graph)
- n-вершинный граф, получаемый из исходного последовательным соединением пар несмежных вершин, сумма степеней которых не менее n, пока это возможно.
Литература:[Свами-Тхуласираман]

Замыкание графа транзитивное - см. Транзитивное замыкание графа.

Замыкание графа рефлексивно-транзитивное - см. Рефлексивно-транзитивное замыкание графа.

Заходящая дуга(Input arc)
- заходящая в вершину v дуга - это дуга, конец которой есть вершина v.
Литература:[Лекции], [Берж]

Звезда - см. Звездный граф.

Звездный граф(Starred graph)
- полный двудольный граф K[_1,n]; в случае n = 3 используются названия "лапа" и "гроздь".
Литература:[Харари]

Звездный многоугольник(Starred polygon)
- помеченный граф с множеством вершин {v[_0], v[_1], ... , v[_p][_-] [_1]}, у которого из смежности вершин v[_0] и v[_i] следует, что для всех k = 1, ... , p-1 вершина v[_k] смежна с v[_k][_+] [_i], где индексы берутся по модулю p.
Литература:[Харари-Палмер]

Зернистость - то же, что и Крупность.

Знак графа(Sign of a graph)
- произведение весов ребер в графе, где каждому ребру приписан вес +1 или -1.
Литература:[Харари-Палмер]

Знаковый помеченный граф(Signed labeled graph)
- граф, у которого каждое ребро помечено либо меткой +, либо меткой -.
Литература:[Харари-Палмер]

Зона(Zone, strongly connected region)
- нетривиальный сильно связный подграф; зона называется одновходовой, если она имеет единственную входную вершину, и многовходовой, если она имеет не менее двух таких вершин.
Другое название - сильно связная область.
Литература:[Касьянов],[Евстигнеев-Касьянов]

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