Графы. Вершины и рёбра. Продолжение (Вероятность и статистика)

Итак, графы – это рисунки, которые состоят из точек и линий, соединяющих эти точки.

Каждая пара точек в графе может быть соединена линиями. Линия указывает на связь между двумя точками.

Точки называются вершинами графа, а линиями рёбрами. Ребро может иметь направление, которое указывается стрелочкой. У графа обязательно есть вершины. Граф без рёбер называется пустым.

Направленная линия (со стрелкой) называется дуга. Линия ненаправленная (без стрелки) называется ребро. Линия, выходящая из некоторой вершины и входящая в неё же, называется петля.

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

Неориентированный граф - граф, вершины которого соединены ребрами. С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений.

Граф, отражающий отношение «переписываются» между объектами класса «дети»

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

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

Граф, отражающий отношение «пишет письма».

Взвешенный граф

Взвешенный граф - граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).

Связные и несвязные графы

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

Полный граф

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

Информационные модели на графах

Иерархия - это расположение частей или элементов целого в порядке от высшего к низшему.

Отношения подчиненности в древнем Египте

Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.

Классификация компьютеров

Сеть

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