Рубрики

Китайский почтальон или маршрут инспекции | Комплект 1 (введение)

Проблема китайского почтальона — это вариация задачи Эйлера для неориентированных графов. Euler Circuit — это закрытая прогулка, которая охватывает все ребра, если начальная и конечная позиции одинаковы. Задача китайского почтальона определена для связного и ненаправленного графа. Проблема состоит в том, чтобы найти кратчайший путь или цепь, которая хотя бы раз посещает каждое ребро графа.

Если входной граф содержит схему Эйлера, то решением проблемы является схема Эйлера

Ненаправленный и связный граф имеет эйлеров цикл, если « все вершины имеют четную степень ».

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

Если входной граф НЕ содержит схему Эйлера

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

2) В взвешенном графе минимальный общий вес ребер для дублирования, чтобы данный граф преобразовывался в граф с циклом Эйлера.

Algorithm to find shortest closed path or optimal 
Chinese postman route in a weighted graph that may
not be Eulerian.
step 1 : If graph is Eulerian, return sum of all 
         edge weights.Else do following steps.
step 2 : We find all the vertices with odd degree 
step 3 : List all possible pairings of odd vertices  
         For n odd vertices total number of pairings 
         possible are, (n-1) * (n-3) * (n -5)... * 1
step 4 : For each set of pairings, find the shortest 
         path connecting them.
step 5 : Find the pairing with minimum shortest path 
         connecting pairs.
step 6 : Modify the graph by adding all the edges that  
         have been found in step 5.
step 7 : Weight of Chinese Postman Tour is sum of all 
         edges in the modified graph.
step 8 : Print Euler Circuit of the modified graph. 
         This Euler Circuit is Chinese Postman Tour.   

Иллюстрация:

               3
        (a)-----------------(b)
     1 /  |                  |  \1
      /   |                  |   \
     (c)  | 5               6|   (d)
      \   |                  |   /
     2 \  |         4        |  /1
        (e)------------------(f)
As we see above graph does not contain Eulerian circuit
because is has odd degree vertices [a, b, e, f]
they all are odd degree vertices . 

First we make all possible pairs of odd degree vertices
[ae, bf], [ab, ef], [af, eb] 
so pairs with min sum of weight are [ae, bc] :
ae = (ac + ce = 3 ),  bf = ( ad + df = 2 ) 
Total : 5

We add edges ac, ce, ad and df to the original graph and
create a modified graph.


Optimal chinese postman route is of length : 5 + 23 = 
28 [ 23 = sum  of all edges of modified graph ]

Chinese Postman Route :  
a - b - d - f - d - b - f - e - c - a - c - e - a 
This route is Euler Circuit of the modified graph. 


Ссылки:

https://en.wikipedia.org/wiki/Route_inspection_problem
http://www.suffolkmaths.co.uk/pages/Maths%20Projects/Projects/Topology%20and%20Graph%20Theory/Chinese%20Postman%20Problem.pdf

Эта статья предоставлена Nishant Singh . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Китайский почтальон или маршрут инспекции | Комплект 1 (введение)

0.00 (0%) 0 votes