mikeem em's Bookmarks tagged graphs →  View Popular

The objective:

• 
  turn it into a graph all of whose vertices have even degree



• 
  by adding some new edges which are "duplicates" of currently existing
  edges:

Here's the Konigsberg graph:

• 
  of course, such a tour is a compromise between





• 
  one the one hand, no tour and



• 
  on the other, building new bridges



• 
  and only approximates a real Euler circuit . . .



• 
  but it's the best we can do for the poor folks of Konigsberg!

• 
  remember:





• 
  added edges must be duplicates of existing edges



• 
  we're not asking that the Konigsbergers actually build new bridges



• 
  we're just allowing some bridges to be recrossed



• 
  and this rule is not just for Konigsberg; it holds for all eulerizations



• 
  so here's a no-no;  it is NOT
  an eulerization:

• 
  if the objective is to construct an Euler circuit that traverses
  as few edges as possible



• 
  we want to add as few edges as possible



• 
  adding as few edges as possible is called an optimal eulerization