Ненаправленный (мульти) граф (алгоритм Гирхольцера)

Question

Я очень застрял в циклической структуре моего графика для прохождения тура Эйлера.

Это график, который я рисую, помните, что он ненаправленный, поэтому путешествие от N1 до N4 - это то же самое, что путешествие от N4 до N1 (не хочу покровительствовать, просто пытаясь увеличить свои шансы на помощь).

Способ решения этой проблемы - найти коллекцию закрытых туров. Тогда, если каждая линия была использована, и мы нашли множество закрытых туров, то был найден тур Эйлера.

Это изображение графика, с которым я работаю вместе с представлением 2d массива

http://i306.photobucket.com/albums/nn269/MCTWEED15/Untitled-5.png

Как вы можете видеть рядом с моим прекрасным изображением, существует двумерный массив целых чисел, представляющих ребра между вершинами. Моя проблема заключается в создании цикла, который при запуске перейдет к любой вершине и закончится обратно в начальной точке (для закрытого тура). Должен быть математический, логический способ сделать это.

Мне нужно, цикл через строку, я думаю. Если позиция в матрице [столбец] [строка]> 0 (т.е. есть ссылка), то матрица [строка] [столбец] - убрать одну ссылку, но я все еще не уверен, как это послужит мне при сборе ссылок для закрытый тур

Мне очень жаль объяснение. Я пытался объяснить мою проблему как можно лучше, если вам нужна дополнительная информация, чтобы попытаться помочь, пожалуйста, дайте мне знать

спасибо

Answer 1

• Проверьте, словарные вершины (множественное число: вершины / вершины) - это то, что вы также называете узлами. Связи между вершинами называются ребрами. Вы перепутали это в своем описании массива.
• Ваш двумерный массив называется "матрицей смежности", и, строго говоря, тот, что на вашем изображении, недопустим, так как отсутствуют несколько значений
• Прежде чем пытаться рассчитать тур Эйлера, вы можете сделать некоторые проверки здравомыслия

Проверка работоспособности

1. Проверьте, имеют ли все вершины четную степень
2. Проверьте, подключен ли график

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

Например, предоставленный вами график не может содержать тур Эйлера, поскольку N2 и N4 имеют неравномерную степень. . Ваше изображение отличается от предоставленной матрицы смежности (упустив это из виду). График, представленный на основе матрицы смежности, содержит маршрут Эйлера.

Еще следуйте этому рецепту:

Be G = ( V , E ) вашего графа, который связан и содержит только вершины с четной степенью

1. Выберите произвольную вершину x из G
2. Создание действительного тура Эйлера K1 начиная с x в G (используется только подмножество всех ребер E )
3. Удалить все ребра, используемые K1
4. Выберите вершину y из K1 , которая все еще имеет степень> 0
5. Создайте еще один тур Эйлера Kn , начиная с y из оставшегося подмножества ребер в E
6. Повторяйте, пока не будут использованы края
7. Теперь вы получите свой тур Эйлера, начав с первого найденного вами тура "sub" -Euler K1 и включив другие маршруты "sub" -Euler, найденные на соответствующих перекрестках

например. учитывая эту матрицу смежности, представляющую G , мы находим в туре Эйлера (с именем H )

   V1 V2 V3 V4 V5
V1  0  0  2  0  0
V2  0  0  1  1  2
V3  2  1  0  1  0
V4  0  1  1  0  0
V5  0  2  0  0  0

1.) Старт с V1 = x

2.) K1 = (V1, V3, V1)

3.) Удалите края в K1 из G

Обновлена ​​матрица смежности

   V1 V2 V3 V4 V5
V1  0  0  0  0  0
V2  0  0  1  1  2
V3  0  1  0  1  0
V4  0  1  1  0  0
V5  0  2  0  0  0

4.) V3 = y (находится в K1 и имеет степень = 2)

5.) K2 = (3,4,2,3)

3.) Удалить K2 ребер

Обновлена ​​матрица смежности

   V1 V2 V3 V4 V5
V1  0  0  0  0  0
V2  0  0  0  0  2
V3  0  0  0  0  0
V4  0  0  0  0  0
V5  0  2  0  0  0

4.) V2 = y (находится в K2 и имеет степень = 2

5.) K3 = (2,5,2)

6.) Все используемые края

7.) Начиная с x = V1 мы строим H

* 1 138 * H * * = 1 139 (1,3

Здесь происходит первое пересечение с другим туром «суб» - Эйлера ( K2 ), и мы включаем его. Таким образом

H = (1,3,4,2

Другое пересечение (с K3 ) мы включаем это тоже

H = (1,3,4,2,5,2

Мы включили весь тур и продолжим тот, на котором мы ранее следовали ( K2 )

H (1,3,4,2,5,2,3

Здесь K2 заканчивается, мы возвращаемся в тур K1 и следуем за ним.

* ** +1171 +1172 * H * * = 1173 (1,3,4,2,5,2,3,1) * +1174 *

Готово. Тур Эйлера найден

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