Понятие о теории графов

Содержание

3.1. Понятие о теории графов

3.2. Анализ размерных связей деталей с использованием теории графов

3.3. Выбор технологических баз

3.4. Синтез технологического маршрута

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

Понятие о теории графов

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

Любой граф состоит из двух групп элементов: точек и линий, соединяющих эти точки. Придерживаясь стандартной терминологии, точки будем называть вершинами или узлами графа, а линии – ребрами, если они не имеют направления, и дугами, если на них задано направление.

Графом G называется совокупность множества V, элементы которого называются вершинами, и множества А упорядоченных пар вершин, элементы которого называются ребрами. Предполагается, что как множество V, так и множество A содержат конечное число элементов.

Граф обозначается как G = (V, A), где V = {v₁, v₂, …, v_n}, A = { a _ij ½ i, j Î V}. При графическом представлении графа вершины обозначаются кружками, ребра – отрезками прямых, дуги – отрезками прямых с направляющими стрелками. Как правило, вершины обозначаются цифрами или буквами (например, 1, i, j), ребра – либо парой вида (i, j), либо a _ij, указывающей начальную и конечную вершину ребра. Ребро с совпадающими начальной и конечной вершинами называется петлей.

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

Рис.3.1. Пример графа Рис.3.2. Пример дерева

Путем, маршрутом или цепью из узла i в узел j на графе называется последовательность вершин и ребер, в которой конечный узел каждой дуги является начальным узлом следующей (исключая начальную и конечную вершину последовательности). При этом одно и то же ребро может встречаться в маршруте несколь­ко раз. Если в маршруте графа нет ребер, предшествующих некоторой вершине, то она называется начальной вершиной маршрута. Если нет ребер, сле­дующих за некоторой вершине, то такая вершина называется конечной (висящей) верши­ной маршрута. Любая вершина графа, принадлежащая двум соседним ребрам, называется внутренней или промежуточ­ной вершиной.

Пример пути из вершины 1 в вершину 4 (рис.3.1): 1, a ₁₄, 4; 1, a ₁₂, a ₂₅, a ₅₄, 4. Начальная вершина маршрута – 1, конечная вершина – 4.

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

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

Деревом называется граф, не имеющий циклов. Пример дерева представлен на рис. 3.2. Корнем ориентированного дерева называется вершина, из которой ориентированные дуги могут только исходить.

Подграфом графа G = (V, A) называется граф G₁ = (V₁, A₁), у которого V₁Í V, AÍ A₁, причем A₁ = { a _ij ½ i, j Î V₁}.

Графы в памяти ЭВМ представляются в виде массивов или матриц.

Матрицей смежности ориентированного графа G называется квадратная матрица n ´ n (n – число вершин графа), в которой d_ij=1, если существует дуга от вершины i к j, и d_ij=0, если дуги нет. Если граф является неориентированным, то каждое ребро (i, j) Í A можно заменить двумя противоположно направленными дугами. При этом матрица смежности графа будет симметричной.

Матрицей инциденций ориентированного графа G называется квадратная матрица n ´ m (n – число вершин графа, m – количество дуг), в которой d_ik=1, если вершина i является начальной вершиной дуги k, d_ik=–1, если вершина i является конечной вершиной дуги k, и d_ij=0 в противном случае. Если граф является неориентированным, то d_ik=1, если узел i принадлежит ребру j и d_ij=0 в противном случае.