Итак, графы – это рисунки, которые состоят из точек и линий, соединяющих эти точки.
Каждая пара точек в графе может быть соединена линиями. Линия указывает на связь между двумя точками.
Точки называются вершинами графа, а линиями рёбрами. Ребро может иметь направление, которое указывается стрелочкой. У графа обязательно есть вершины. Граф без рёбер называется пустым.
Направленная линия (со стрелкой) называется дуга. Линия ненаправленная (без стрелки) называется ребро. Линия, выходящая из некоторой вершины и входящая в неё же, называется петля.
Неориентированный граф.
Неориентированный граф - граф, вершины которого соединены ребрами. С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений.
Ориентированный граф (орграф)
Ориентированный граф - граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы односторонних отношений.
Взвешенный граф
Взвешенный граф - граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).
Связные и несвязные графы
Связный граф можно нарисовать не отрывая карандаша от бумаги.
Полный граф
Граф называется полным, если каждая вершина связана со всеми другими вершинами графа. Если полный граф имеет n вершин, то количество ребер будет равно
Информационные модели на графах
Иерархия - это расположение частей или элементов целого в порядке от высшего к низшему.
Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.
Сеть
Цепь – путь по вершинам и ребрам, включающий любое ребро графа не более одного раза. Цикл – цепь, начальная и конечная вершины которой совпадают. Граф с циклом называют сетью.
