Acyclic graphs and trees An acyclic graph is a graph with no cycles a tree is an acyclic connected graph 3 Acyclic, unconnected Cyclic, connected not tree not tree The number of arcs in a tree is always one less than the number of nodes Proof: start with arbitrary node and each time you add an arc you add a node >n nodes and N-1 links. If you add an arc without adding a node the arc must go to a node already in the tree and hence form a cycleAcyclic graphs and trees • An acyclic graph is a g raph with no cycles. • A tree is an acyclic connected graph. 1 2 4 3 1 2 3 1 2 3 Acyclic, unconnected Cyclic, connec ted not tree not tree • The number of arcs in a tree is always one less than the number of nodes – Proof: start with arbitrary node and each time you add an arc you add a node => N nodes and N-1 links. If you add an arc without addin g a node, the arc must g o to a n o d e already in the tree and h e n ce form a cycle Eytan Modiano Slide 7