Subgraphs G=(N, A)is a subgraph ofG=(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 Graph G Subgraph of GSubgraphs • 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 8