Graphs PDF

## Graphs - Directed graph: - Undirected graph - Complete graph: Each vertex connected with every other vertices - Complete directed - No. of vertices = n - No. of edge = n*(n-1) - Complete undirected - No. of vertices = n - No. of edge = n(n-1) / 2 ### Adjacency Matrix - Vertice...

## Graphs - Directed graph: - Undirected graph - Complete graph: Each vertex connected with every other vertices - Complete directed - No. of vertices = n - No. of edge = n*(n-1) - Complete undirected - No. of vertices = n - No. of edge = n(n-1) / 2 ### Adjacency Matrix - Vertices are rows - Edges: Incidence matrix - Vertices are columns - Edges are rows | | A | B | C | D | E | |---|---|---|---|---|---| | A | 0 | 1 | 0 | 1 | 0 | | B | 1 | 0 | 1 | 1 | 0 | | C | 0 | 1 | 0 | 0 | 1 | | D | 1 | 1 | 0 | 0 | 0 | | E | 0 | 0 | 1 | 0 | 0 | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8| |---|---|---|---|---|---|---|---|---| | A | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | | B | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | | C | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | | D | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | | E | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | ### Weighted Directed Graph: | | A | B | C | D | E | |---|---|---|---|---|---| | A | 0 | 4 | 0 | 0 | 0 | | B | 0 | 0 | 2 | 1 | 0 | | C | 0 | 0 | 0 | 0 | 8 | | D | 5 | 0 | 0 | 0 | 0 | | E | 0 | 0 | 0 | 10 | 0 | - A: 13 - C - D - E | | A | B | C | D | E | |---|---|---|---|---|---| | A | 0 | 4 | 0 | 0 | 0 | | B | 0 | 0 | 2 | 1 | 0 | | C | 0 | 0 | 0 | 0 | 8 | | D | 5 | 0 | 0 | 0 | 0 | | E | 0 | 0 | 0 | 10 | 0 | A---------4-------->B | | \ | | 2 | | / | | C | | V-----------------8--------------->E | | 5 | V----------->D ## Adjacency Matrix - Given, Find - Incidence Matrix | | A | B | C | D | E | |---|---|---|---|---|---| | A | 0 | 1 | 1 | 0 | 0 | | B | 1 | 0 | 1 | 1 | 0 | | C | 1 | 1 | 0 | 0 | 1 | | D | 0 | 1 | 0 | 0 | 1 | | E | 0 | 0 | 1 | 1 | 0 | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |---|---|---|---|---|---|---|---|---| | A | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | | B | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | | C | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | | D | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | | E | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | ### BFS (Breadth First Search) - Queue(FIFO) **Start:** A-----> B----->C----->D----->E | | | | V V V S S S | | V V G H | V F **Goal:** A---------------->B---------------->S---------------->C---------------->G | | | | | | V V V V V G D E H E | | | | | V V V V H F E F | V H ** Path Found:** A->B->S->C->G->D->E->H ## DFS (Depth First Search) - Stack(LIFO) **Start:** A----->B----->C----->D----->E | | | | V V V S S S | | V V G H | V F **Goal:** A----->B----->S----->C----->D------->E ---->H | | | | | | | | V V V V V V V G D E H E H H | V S **Path Found:** A->B->S->C->D->E->H ## Isomorphism - 1: Equal no. of vertices - 2: Equal no. of edges - 3: Degree - 4: Adjacent vertices should be the same degree ## Ex. 1 - No. of vertices = 3 - Degree = (3,2|3,2), (3,3,2,2) | | A | B | C | D | |---|---|---|---|---| | A | 0 | 1 | 1 | 1 | | B | 1 | 0 | 0 | 1| | C | 1 | 0 | 0 | 1 | | D | 1 | 1 | 1 | 0 | G1 and G2 are Isomorphic. G3 is not Isomorphic. ## Ex. 2 - No. of vertices = v - No. of edges = v - Degree = (3,3,3,3,2,2,2,2),(3,2,3,2,3,2,3,2) G1 and G2 are not isomorphic. ## Ex. 3 | | U1 | U2 | U3 | U4 | U5 | U6 | |---|---|---|---|---|---|---| | U1 | 0 | 1 | 0 | 1 | 0 | 1 | | U2 | 1 | 0 | 1 | 0 | 1 | 0 | | U3 | 0 | 1 | 0 | 1 | 0 | 1 | | U4 | 1 | 0 | 1 | 0 | 1 | 0 | | U5 | 0 | 1 | 0 | 1 | 0 | 1 | | U6 | 1 | 0 | 1 | 0 | 1 | 0 | | | V1 | V2 | V3 | V4 | V5 | V6 | |---|---|---|---|---|---|---| | V1 | 0 | 1 | 0 | 1 | 0 | 1 | | V2 | 1 | 0 | 1 | 0 | 1 | 0 | | V3 | 0 | 1 | 0 | 1 | 0 | 1 | | V4 | 1 | 0 | 1 | 0 | 1 | 0 | | V5 | 0 | 1 | 0 | 1 | 0 | 1 | | V6 | 1 | 0 | 1 | 0 | 1 | 0 | - U1 = V5 - U2 = V2 - U3 = V3 - U4 = V6 - U5 = V4 - U6 = V1 The two graphs are Isomorphic.