Словарь

Алгоритм — пошаговая последовательность действий по решению задачи.

Вершина — точка графа, где сходится одно или более ребер; также может быть изолированной.

Вес — значение, поставленное в соответствие ребру графа, означающее стоимость, расстояние, время и пр.

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

Гамильтонов граф — граф, в котором существует гамильтонов цикл.

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

Гомеоморфные графы — графы, один из которых получается из другого путем добавления или удаления вершин степени 2. Если в таких графах удалить все вершины степени 2, полученные графы будут одинаковыми.

Грань — область, ограниченная ребрами плоского графа.

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

Дерево — связный граф, не содержащий циклов.

Дуга — ориентированное ребро графа. Изображается стрелкой.

Изоморфные графы — графы, между вершинами и ребрами которых существует взаимно однозначное соответствие, которое сохраняет смежность и инцидентность.

Критический путь — путь максимальной длины в ориентированном графе.

Лес — множество графов, которые являются деревьями.

Матрица инцидентности графа — матрица n x n чисел, элементы которой равны 1, если между соответствующими вершинами имеется ребро, и 0 в противном случае.

Метка — информация, присвоенная вершинам и ребрам графа; например, числа, слова, наименования.

Оптимальное решение — наилучшее решение (согласно некоему количественному показателю) из множества возможных решений.

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

Орграф (ориентированный граф) — граф, все ребра которого являются ориентированными, то есть дугами.

Остовное дерево графа — подграф данного графа с максимально возможным числом ребер, который является деревом.

Петля — дуга или ребро, начало и конец которого находятся в одной и той же вершине.

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

Подграф — граф, содержащий некое подмножество вершин и ребер данного графа.

Полный граф — граф, в котором любая пара вершин соединена ребром.

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

Путь — последовательность смежных ребер или дуг.

Раскраска графа — присвоение цветов вершинам, ребрам или граням графа при выполнении определенных условий.

Ребро — связь между двумя вершинами графа.

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

Сеть — граф, используемый для решения транспортных задач и задач распределения.

Смежные дуги — две дуги, имеющие общую вершину.

Смежные ребра — два ребра, имеющие общую вершину.

Степень вершины — количество ребер графа, сходящихся в данной вершине.

Траектория — то же, что и путь.

Узел — то же, что и вершина.

Цикл — путь, начало и конец которого находятся в одной и той же вершине.

Эйлеров граф — граф, в котором существует эйлеров цикл.

Эйлеров цикл — цикл, проходящий через каждое ребро графа ровно один раз.