1 of 15

Basics of Graph

AI60007

2 of 15

Basic Definitions

 

 

 

 

 

 

3 of 15

Basic Definitions

  •  

4 of 15

Basic Definitions: Connectivity

  • Walk: Alternating sequence of nodes and edges
    • Length of a walk is the number of edges in the walk
  • Trail: A walk whose edges are distinct
  • Path: A walk whose nodes are distinct

Walk: A🡪B🡪D🡪C🡪B🡪A🡪F

Trail: A🡪B🡪D🡪C🡪A🡪F

Path: A🡪B🡪E🡪D🡪C

5 of 15

Basic Definitions: Connectivity

  •  

 

 

A

C

 

6 of 15

Basic Definitions: Connectivity

Subgraph

 

and

 

 

7 of 15

Basic Definitions: Connectivity

Connected Components

 

At least one path between any pair of nodes

 

A connected graph has only one component

8 of 15

Basic Definitions: Graph Traversal

Traversing the nodes of the graph depth-wise

Depth First Search (DFS)

0

​

​

​

​

​

​

1

3

4

5

​

​

​

Visited

Stack

0

1

​

​

​

​

​

3

4

5

​

​

​

​

Visited

Stack

0

1

3

​

​

​

​

2

6

4

5

​

​

​

Visited

Stack

0

1

3

2

​

​

​

6

4

5

​

​

​

​

Visited

Stack

9 of 15

Basic Definitions: Graph Traversal

Traversing the nodes of the graph breadth-wise

Breadth First Search (BFS)

0

​

​

​

​

​

​

1

3

4

5

​

​

​

Visited

Queue

0

1

​

​

​

​

​

3

4

5

​

​

​

​

Visited

Queue

0

1

3

​

​

​

​

4

5

2

6

​

​

​

Visited

Queue

0

1

3

4

​

​

​

5

2

6

​

​

​

​

Visited

Queue

10 of 15

Graph Isomorphism

Source: Wikipedia

 

11 of 15

Types of Graphs

 

 

 

 

 

 

Heterogeneous

12 of 15

Types of Graphs

 

 

 

 

Bipartite

13 of 15

Types of Graphs

 

Multi-Dimensional

 

 

14 of 15

Types of Graph

 

 

 

 

Signed Graph

15 of 15

Types of Graph

 

Each node and edges

are associated with timestamp

 

Dynamic Graph