Tours and Matchings Eulerian graphs Đầu tiên thích hợp vấn đề trong lý thuyết đồ thị là cây cầu Königsberg vấn đề. Nói chung, vấn đề này liên quan đến di chuyển xung quanh một đồ thị là một trong những cố gắng tránh sử dụng cùng một cạnh hai lần. Trong thực tế những vấn đề này Euler xảy ra, ví dụ, trong mạng lưới phân phối tối ưu hóa - chẳng hạn như phát thư, để tiết kiệm thời gian đường phố nên được đi du lịch chỉ một lần. Vấn đề tương tự xảy ra. | 3 Tours and Matchings Eulerian graphs The first proper problem in graph theory was the Konigsberg bridge problem. In general this problem concerns about travels around a graph such that one tries to avoid using the same edge twice. In practice these eulerian problems occur for instance in optimizing distribution networks - such as delivering mail where in order to save time each street should be travelled only once. The same problem occurs in mechanical graph plotting where one avoids lifting the pen off the paper while drawing the lines. e. Definition. a walk w 6162. en is a trail if 6i f 6j for all if j. An Euler trail of a graph G is a trail that visits every edge once. A connected graph G is eulerian if it has a closed trail containing every edge of G. Such a trail is called an Euler tour. Notice that if w 6162 en is an Euler tour and so Eg ei 62 . en also 6j6j i. en6i. 6j-i is an Euler tour for all i E 1 n . A complete proof of the following Euler s Theorem was first given by Hierholzer in 1873. Theorem Euler 1736 Hierholzer 1873 . A connected graph G is eulerian if and only if every vertex has an even degree. Proof. Suppose w u u is an Euler tour. Let V ff Ù be a vertex that occurs fc times in kk. Every time an edge arrives at V another edge departs from V and therefore ỉg v 2k. Also Ig u is even since kk starts and ends at u. Assume G is a nontrivial connected graph such that d G y is even for all V E G. Let w 6162 . .en Vo _ vn with 6i Vị-iVị be a longest trail in G. It follows that all e vnw E Eg are among the edges of kk for otherwise could be prolonged to we. In particular Vo vn that is l k is a closed trail. Indeed if it were vnf Vo andvn occurs fc times inW then d G yn 2 fc 1 1 and that would be odd. IfW is not an Euler tour then since G is connected there exists an edge f VịU E Eg for some i which is not in kk. However now 6i is a trail in G and it is longer than kk. This contradiction to the choice of kk proves the claim. .
