Технология машиностроения

177 Графом называется фигура, состоящая из точек и линий, соединяющих эти точки. Точки называются вершинами, а линии – ребрами или дугами. Ребро называется ориентированным, если на нем имеется стрелка, указывающая, из какой вершины она исходит и в какую вершину входит. Если стрелки нет, то ребро называется неориентированным. Если вершины соединены несколькими ребрами, то такие ребра называются кратными (рис. 2.49): 1 – неориентированный граф; 2 – ориентированный граф; 3 – кратные ребра). Рис. 2.49. Кратные ребра Последовательность ребер, в которой два соседних ребра имеют общую вершину, называются маршрутом (рис. 2.50). Рис. 2.50. Маршрут А 1 – А 2 – А 3 Если начало и конец маршрута находятся в одной вершине, то такой маршрут называется циклическим (рис. 2.51). Рис. 2.51. Цикл Маршрут называется цепью , если в нем каждое ребро встречается только один раз. Если цепь замкнута, т.е. начинается и оканчивается в одной и той же вершине, то цепь называется циклом . Если каждая вершина графа соединена с другими вершинами некоторой цепью, то граф называется связным. Связный граф, не содержащий циклов и не имеющий кратных ребер, называется деревом.