Определение путей в графе

Задача определения путей в графах

Решение целого ряда практических задач, описываемых в тер­минах графов, зависит от существования некоторой цепи, соеди­няющей данную вершину с какой-либо другой. Например, в качест­ве вершин графа можно рассматривать исходные позиции или со­стояния некоторой головоломки или игры, а ребра будут указывать возможные ходы из одной позиции в другую. Ребро будет неориен­тированным или ориентированным в зависимости от того, обратим переход или нет.

Граф G(X) с двумя отмеченными вершинами x_i, x_j назы­вается (x_i, x_j) – плоским, если граф G^¢(X)=G(X)È(x_i, x_j), полученный до­бавлением к G(X) ребра (x_i, x_j), является плоским.

Рассмотрим алгоритм определения пути, ведущего из вершины x_i в x_j плоского графа. Если x_i не является вершиной никакого про­стого цикла, то при определении алгоритма пути из x_i в x_j в графе G(X) всегда выбирается самый левый или правый коридор (ребро) (рис. 3.33).

– путь при выборе левого коридора;

– путь при выборе правого коридора.

Аналогичный алгоритм определения пути в прадереве предпо­лагает следующие действия. Из корня идти по какой-либо ветви насколько возможно далеко, затем возвратиться на какой-нибудь перекресток и отправиться по новому направлению (еще не прой­денному) и т.д. Искомый путь из x_i в x_j будет состоять из всех тех ребер, которые в процессе поиска были пройдены по одному разу.

При определении пути в произвольном графе, не являющемся прадеревом, приходим к предыдущему случаю следующим образом. Если, пройдя по некоторому ребру g, попадаем на уже пройденный ранее перекресток х, то ребро g «отсекается» от одной из своих концевых точек. После отсечения ребра, пройденные хотя бы один раз, образуют прадерево.

Рис. 3.33. Определение пути в графе

При определении пути в графе с помощью алгоритма Тарри необходимо в данном алгоритме пользоваться правилом:

а) не проходить дважды по одному ребру в одном и том же направлении;

б) находясь в вершине х, не выбирать того ребра, которое при­вело в данную вершину в первый раз (если есть возмож­ность друго­го выбора).