Connected graph a graph is connected if a path exists between each pair of nodes Connected Unconnected An unconnected graph can be separated into two or more connected components
Connected graph • A graph is connected if a path exists between each pair of nodes. 1 2 4 3 1 2 3 Connected Unconnected • An unconnected graph can be separated into two or more connected components. Eytan Modiano Slide 6
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 cycle
Acyclic 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