Walks and paths A walk is a sequence of nodes(n1, n2, . nk in which each adjacent node pair is an arc a path is a walk with no repeated nodes Wak(1,2342) Path(1,234) Eytan Modiano
Walks and paths • A walk is a sequence of nodes (n1, n2, ...,nk) in which each adjacent node pair is an arc. • A path is a walk with no repeated nodes. 1 2 4 3 1 2 4 3 Walk (1,2,3,4,2) Path (1,2,3,4) Eytan Modiano Slide 6
Cycles A cycle is a walk(n1, n2, nk) with n1=nk, k>3, and with no repeated nodes except n1= nk cyce(1,2,43,1) Eytan Modiano
Cycles • A cycle is a walk (n1, n2,...,nk) with n1 = nk, k>3, and with no repeated nodes except n1 = nk Cycle (1,2,4,3,1) 1 2 4 3 Eytan Modiano Slide 7
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. Eytan Modiano
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 8
Acyclic graphs and trees An acyclic graph is a graph with no cycles A tree is an acyclic connected graph Acyclic, unconnected clic, 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 graph with no cycles. • A tree is an acyclic connected graph. 1 2 4 3 1 2 3 1 2 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 Eytan Modiano Slide 9
Subgraphs G=(N, A)is a subgraph of G=(N, A)if 1)G is a graph 2 Nis a subset of N 3)A is a subset of A One obtains a subgraph by deleting nodes and arcs from a graph Note: arcs adjacent to a deleted node must also be deleted Graph G Subgraph G of G Slide 10
Subgraphs • G' = (N',A') is a subgraph of G = (N,A) if – 1) G' is a graph – 2) N' is a subset of N – 3) A' is a subset of A • One obtains a subgraph by deleting nodes and arcs from a graph – Note: arcs adjacent to a deleted node must also be deleted 1 2 4 3 1 2 3 – Graph G Subgraph G' of G Eytan Modiano Slide 10