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 10Subgraphs • 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