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

Граф - неформально - схема, состоящая из точек и соединяющих эти точки отрезков прямых или кривых.

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

Дерево

Tree

Дерево - граф с одной вершиной (корневой вершиной), в которую нет входящих ребер, а в каждую другую вершину входит только одно ребро.

Дуга

Дуга - в теории графов - ориентированное ребро графа. На рисунках направление перехода по дуге, обозначается стрелкой.

Маршрут

Маршрут - в теории графов - путь между вершинами графа, проходящий вдоль ребер.

Ориентированный граф

Ориентированный граф - граф, вершины которого соединены направленными ребрами (дугами).

Петля

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

Связный граф

Связный граф - граф, в котором между каждая пара вершин соединена хотя бы одним путем.

Сеть

Сеть - в теории графов - связный ориентированный граф.

Соседние вершины

Смежные вершины

Соседние вершины - в теории графов - вершины графа, соединенные ребром.

Теория графов

Теория графов - область дискретной математики, объектом изучения которой являются графы.

Матрица весов

Матрица весов. Граф, в котором ребру сопоставлено число , называется взвешенным графом, а число называется весом ребра .

Клики

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

Матрица смежностей

Матрица смежностей. Одним из наиболее распространенных машинных представлений простого графа является матрица смежностей или соединений.

Изоморфизм

Два графа называются изоморфными, если существует взаимно однозначное соответствие , такое, что тогда и только тогда, если , то есть существует соответствие между вершинами графа и вершинами графа , сохраняющее отношение смежности.

Планарность

Граф называют планарным, если существует такое изображение на плоскости его вершин и ребер, что:

• каждая вершина изображается отдельной точкой на плоскости;
• каждое ребро изображается простой кривой, имеющей концевые точки ;
• эти кривые пересекаются только в общих концевых точках. Задача определения того, можно ли изобразить граф на плоскости без пересечения ребер, имеет большой практический интерес (например, при конструировании интегральных схем или печатных плат необходимо выяснить, можно ли окончательную схему вложить в плоскость).

Вставка

Вставка - простейшая сортировка вставками проходит через этапы : на этапе имя вставляется на свое правильное место среди .