Изоморфи́зм — соотношение между математическими объектами, выражающее общность их строения; используется в разных разделах математики и в каждом из них определяется в зависимости от структурных свойств изучаемых объектов. Обычно изоморфизм определяется для множеств, наделённых некоторой структурой, например, для групп, колец, линейных пространств; в этом случае он определяется как обратимое отображение (биекция) между двумя множествами со структурой, сохраняющее эту структуру, то есть показывающее, что объекты «одинаково устроены» в смысле этой структуры. Если между объектами существует изоморфизм, то они называются изоморфными. Изоморфизм всегда задаёт отношение эквивалентности на классе таких структур.
Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин, и множества их парных связей, называемого множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин.
Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Ориентированный граф — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Взаи́мная блокиро́вка — ситуация в многозадачной среде или СУБД, при которой несколько процессов находятся в состоянии ожидания ресурсов, занятых друг другом, и ни один из них не может продолжать свое выполнение.
Дерево — связный ациклический граф. Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь.
В теории графов теорема Кёнига , доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.
Поиск в глубину — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.
Program (Project) Evaluation and Review Technique — метод оценки и анализа проектов, который используется в управлении проектами.
Технология графосимволического программирования — это технология проектирования и кодирования алгоритмов программного обеспечения, базирующаяся на графическом способе представления программ, преследующую цель полной или частичной автоматизации процессов проектирования, кодирования и тестирования ПО.
В комбинаторной оптимизации под линейной задачей о назначениях на узкие места понимается задача, похожая на задачу о назначениях.
Экспандер — сильносвязный разреженный граф, при этом связность может определяться по вершинам, дугам или спектру.
Граф Хивуда — ненаправленный граф с 14 вершинами и 21 ребром, названный в честь Перси Джона Хивуда.
Семафо́р — примитив синхронизации работы процессов и потоков, в основе которого лежит счётчик, над которым можно производить две атомарные операции: увеличение и уменьшение значения на единицу, при этом операция уменьшения для нулевого значения счётчика является блокирующейся. Служит для построения более сложных механизмов синхронизации и используется для синхронизации параллельно работающих задач, для защиты передачи данных через разделяемую память, для защиты критических секций, а также для управления доступом к аппаратному обеспечению.
Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами. В основном используется в комбинаторике, но также и в теории чисел, линейной алгебре и математическом анализе, а также в информатике и теории информации.
В теории графов разрезающее циклы множество вершин графа — это множество вершин, удаление которых приводит к разрыву циклов. Другими словами, разрезающее циклы множество вершин содержит по меньшей мере по одной вершине из любого цикла графа. Задача о разрезающем циклы множестве вершин является в теории вычислительной сложности NP-полной задачей. Задача входит в список 21 NP-полных задач Карпа. Задача имеет широкое применение в операционных системах, базах данных и разработке СБИС.
В базах данных и обработке транзакций двухфазная блокировка (2PL) — это метод управления параллелизмом, который гарантирует сериализуемость. Это также имя результирующего набора графиков транзакций базы данных (истории). Протокол использует блокировки, применяемые транзакцией к данным, которые могут блокировать другие транзакции от доступа к тем же данным в течение жизни транзакции.
Алгоритм Суурбалле — это алгоритм нахождения двух непересекающихся путей в ориентированном графе с неотрицательными весами, так что оба пути связывают ту же самую пару вершин и имеют минимальную общую длину.
