Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Другие методы, предложенные для поиска кратчайших гамильтоновых циклов – алгебраический метод, основанный на работе Йоу, Даниэльсона и Дхавана (включает в себя построение всех простых цепей с помощью последовательного перемножения матриц), метод перебора Робертса и Флореса (метод перебора имеет дело с одной цепью, непрерывно продлеваемой вплоть до момента, когда либо становится ясно, что эта цепь не может привести к гамильтонову циклу. Тогда цепь модифицируется некоторым систематическим способом, после чего продолжается поиск гамильтонова цикла. Другой подход – мультицепной метод, предложенный Селби.
ТЕОРИЯ ГРАФОВ.
Основные понятия теории графов. Определения.
Граф G задается множеством точек или вершин x1, x2, …xn (которое обозначается через X) и множеством линий или ребер a1, a2, …am (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается парой (X,A).
Если ребра из множества А ориентированны, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называют ориентированным графом. Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Граф в этом случае обозначается парой G=(X, Г).
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Ориентированной цепью называется такой путь, в котором каждая дуга используется не больше одного раза. Простой цепью называется такой путь, в котором каждая вершина используется не более одного раза. Очевидно, что простая орцепь является также орцепью, но обратное уже неверно.
Иногда дугам графа G сопоставляются (приписываются) числа - дуге (xi,xj) ставится в соответствие некоторое число ci j, называемое весом, или длинной. Тогда граф G называется графом со взвешенными дугами. Иногда веса приписываются вершинам xi графа, и тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. При рассмотрении пути , представленного последовательностью дуг, за его вес (или длину) принимается число , равное сумме весов всех дуг, входящих в , т.е. .
Гамильтонов цикл в орграфе – это ориентированный цикл (контур), проходящий ровно один раз через каждую вершину графа (т.е. простая орцепь).
Если G = (X, A) – неориентированный граф с n вершинами, то остовным деревом (или, короче, остовом) графа G называется всякий остовный подграф G, являющийся деревом (т.е. графом не имеющим циклов, в котором каждая пара вершин соединена одной и только одной простой цепью). Например, если G – граф, показанный на рис.1а, то графы на рис.1.б,в являются остовом этого графа.
Дата публикования: 2014-12-08; Прочитано: 523 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!