eulerpathsandcircuits(完整版)
【正文】 r of nodes, eventually the whole graph is included. Use the algorithm to find an Euler circuit. Use algorithm – all even? 0 1 0 0 1 21 0 1 0 1 10 1 0 1 1 10 0 1 0 0 11 1 1 0 0 02 1 1 1 0 1A????????? ??????????Euler’s 2nd Theorem If a graph has more than two vertices of odd degree, then it cannot have an Euler path. If a graph is connected and has exactly two vertices of odd degree, then is has at least one Euler path. Any such path must start at one of the odd degree vertices and must end at the other odd degree vertex. Find the Euler Path A detail ? We said that if the number of odd degree vertices ? =0, then Euler circuit ? =2, then path ? What if =1???? A directed graph – Is there an Euler Circuit? Euler for a connected directed graph ? If at each node the number in = number out, then there is an Euler circu
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1