• Home
  • /
  • Blog
  • /
  • 2 Essential Concepts of Graph Explained for Kids Advantage

2 Essential Concepts of Graph Explained for Kids Advantage

Adjacency Matrix and Path Matrix

This post is also available in: हिन्दी (Hindi)

A graph with n nodes can be represented in the form of a square matrix of order n. Graphs find applications in many areas such as airline scheduling, directions on a map, solving sudoku puzzles, search engine algorithms, social media marketing.

In this article, you will learn two very important concepts of matrices – Adjacency Matrix and Path Matrix.

Adjacency Matrix and Path Matrix of a Graph

A network usually consists of hundreds or thousands of nodes connected to one another by edges. These networks can be represented as graphs, a type of data structure. Have you ever wondered how a path between two nodes is established to facilitate uninterrupted communication? 

coding-for-kids-ebook-cover

Get Instant Access To 

Coding For Kids eBook

A must read for every parent

Country
  • Afghanistan 93
  • Albania 355
  • Algeria 213
  • American Samoa 1-684
  • Andorra 376
  • Angola 244
  • Anguilla 1-264
  • Antarctica 672
  • Antigua & Barbuda 1-268
  • Argentina 54
  • Armenia 374
  • Aruba 297
  • Australia 61
  • Austria 43
  • Azerbaijan 994
  • Bahamas 1-242
  • Bahrain 973
  • Bangladesh 880
  • Barbados 1-246
  • Belarus 375
  • Belgium 32
  • Belize 501
  • Benin 229
  • Bermuda 1-441
  • Bhutan 975
  • Bolivia 591
  • Bosnia 387
  • Botswana 267
  • Bouvet Island 47
  • Brazil 55
  • British Indian Ocean Territory 246
  • British Virgin Islands 1-284
  • Brunei 673
  • Bulgaria 359
  • Burkina Faso 226
  • Burundi 257
  • Cambodia 855
  • Cameroon 237
  • Canada 1
  • Cape Verde 238
  • Caribbean Netherlands 599
  • Cayman Islands 1-345
  • Central African Republic 236
  • Chad 235
  • Chile 56
  • China 86
  • Christmas Island 61
  • Cocos (Keeling) Islands 61
  • Colombia 57
  • Comoros 269
  • Congo - Brazzaville 242
  • Congo - Kinshasa 243
  • Cook Islands 682
  • Costa Rica 506
  • Croatia 385
  • Cuba 53
  • Cyprus 357
  • Czech Republic 420
  • Denmark 45
  • Djibouti 253
  • Dominica 1-767
  • Ecuador 593
  • Egypt 20
  • El Salvador 503
  • Equatorial Guinea 240
  • Eritrea 291
  • Estonia 372
  • Ethiopia 251
  • Falkland Islands 500
  • Faroe Islands 298
  • Fiji 679
  • Finland 358
  • France 33
  • French Guiana 594
  • French Polynesia 689
  • French Southern Territories 262
  • Gabon 241
  • Gambia 220
  • Georgia 995
  • Germany 49
  • Ghana 233
  • Gibraltar 350
  • Greece 30
  • Greenland 299
  • Grenada 1-473
  • Guadeloupe 590
  • Guam 1-671
  • Guatemala 502
  • Guernsey 44
  • Guinea 224
  • Guinea-Bissau 245
  • Guyana 592
  • Haiti 509
  • Heard & McDonald Islands 672
  • Honduras 504
  • Hong Kong 852
  • Hungary 36
  • Iceland 354
  • India 91
  • Indonesia 62
  • Iran 98
  • Iraq 964
  • Ireland 353
  • Isle of Man 44
  • Israel 972
  • Italy 39
  • Jamaica 1-876
  • Japan 81
  • Jersey 44
  • Jordan 962
  • Kazakhstan 7
  • Kenya 254
  • Kiribati 686
  • Kuwait 965
  • Kyrgyzstan 996
  • Laos 856
  • Latvia 371
  • Lebanon 961
  • Lesotho 266
  • Liberia 231
  • Libya 218
  • Liechtenstein 423
  • Lithuania 370
  • Luxembourg 352
  • Macau 853
  • Macedonia 389
  • Madagascar 261
  • Malawi 265
  • Malaysia 60
  • Maldives 960
  • Mali 223
  • Malta 356
  • Marshall Islands 692
  • Martinique 596
  • Mauritania 222
  • Mauritius 230
  • Mayotte 262
  • Mexico 52
  • Micronesia 691
  • Moldova 373
  • Monaco 377
  • Mongolia 976
  • Montenegro 382
  • Montserrat 1-664
  • Morocco 212
  • Mozambique 258
  • Myanmar 95
  • Namibia 264
  • Nauru 674
  • Nepal 977
  • Netherlands 31
  • New Caledonia 687
  • New Zealand 64
  • Nicaragua 505
  • Niger 227
  • Nigeria 234
  • Niue 683
  • Norfolk Island 672
  • North Korea 850
  • Northern Mariana Islands 1-670
  • Norway 47
  • Oman 968
  • Pakistan 92
  • Palau 680
  • Palestine 970
  • Panama 507
  • Papua New Guinea 675
  • Paraguay 595
  • Peru 51
  • Philippines 63
  • Pitcairn Islands 870
  • Poland 48
  • Portugal 351
  • Puerto Rico 1
  • Qatar 974
  • Romania 40
  • Russia 7
  • Rwanda 250
  • Réunion 262
  • Samoa 685
  • San Marino 378
  • Saudi Arabia 966
  • Senegal 221
  • Serbia 381 p
  • Seychelles 248
  • Sierra Leone 232
  • Singapore 65
  • Slovakia 421
  • Slovenia 386
  • Solomon Islands 677
  • Somalia 252
  • South Africa 27
  • South Georgia & South Sandwich Islands 500
  • South Korea 82
  • South Sudan 211
  • Spain 34
  • Sri Lanka 94
  • Sudan 249
  • Suriname 597
  • Svalbard & Jan Mayen 47
  • Swaziland 268
  • Sweden 46
  • Switzerland 41
  • Syria 963
  • Sao Tome and Principe 239
  • Taiwan 886
  • Tajikistan 992
  • Tanzania 255
  • Thailand 66
  • Timor-Leste 670
  • Togo 228
  • Tokelau 690
  • Tonga 676
  • Trinidad & Tobago 1-868
  • Tunisia 216
  • Turkey 90
  • Turkmenistan 993
  • Turks & Caicos Islands 1-649
  • Tuvalu 688
  • U.S. Outlying Islands
  • U.S. Virgin Islands 1-340
  • UK 44
  • US 1
  • Uganda 256
  • Ukraine 380
  • United Arab Emirates 971
  • Uruguay 598
  • Uzbekistan 998
  • Vanuatu 678
  • Vatican City 39-06
  • Venezuela 58
  • Vietnam 84
  • Wallis & Futuna 681
  • Western Sahara 212
  • Yemen 967
  • Zambia 260
  • Zimbabwe 263
How Old Is Your Child?
  • Less Than 5 Years
  • 5 - 8 Years
  • 9 - 13 Years
  • 14 - 18 Years
  • 18+ Years

To understand this, one should know two basic concepts of graphs.

  • Adjacency Matrix
  • Path Matrix

1. Adjacency Matrix in Graph Theory

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

Elements of an adjacency matrix are either 0 or 1. If a pair of nodes have a common edge(i.e., nodes are connected), it is represented by 1. If a pair of nodes do not have a common edge(i.e., nodes are not connected), it is represented by 0.

Let’s now understand how undirected and directed graphs are represented by an adjacency matrix.

Adjacency Matrix – Undirected Graph

Adjacency Matrix and Path Matrix
Undirected Graph

In this graph node A is adjacent to nodes B and C. Similarly, node B is adjacent to nodes A and C; node C is adjacent to nodes A, B, and D; node D is adjacent to node C.

The adjacency matrix of the above graph is

Adjacency Matrix and Path Matrix

In the above matrix, since there is a path from A to C as well as from C to A, therefore, entry for A to C and C to A is 1. The same is true for other nodes.

In the case when a node is connected to itself by a loop. (Node C has a loop).

Adjacency Matrix and Path Matrix
Undirected Graph with Loop
Adjacency Matrix and Path Matrix
Is your child struggling with Maths?
frustrated-kid
We can help!
Country
  • Afghanistan 93
  • Albania 355
  • Algeria 213
  • American Samoa 1-684
  • Andorra 376
  • Angola 244
  • Anguilla 1-264
  • Antarctica 672
  • Antigua & Barbuda 1-268
  • Argentina 54
  • Armenia 374
  • Aruba 297
  • Australia 61
  • Austria 43
  • Azerbaijan 994
  • Bahamas 1-242
  • Bahrain 973
  • Bangladesh 880
  • Barbados 1-246
  • Belarus 375
  • Belgium 32
  • Belize 501
  • Benin 229
  • Bermuda 1-441
  • Bhutan 975
  • Bolivia 591
  • Bosnia 387
  • Botswana 267
  • Bouvet Island 47
  • Brazil 55
  • British Indian Ocean Territory 246
  • British Virgin Islands 1-284
  • Brunei 673
  • Bulgaria 359
  • Burkina Faso 226
  • Burundi 257
  • Cambodia 855
  • Cameroon 237
  • Canada 1
  • Cape Verde 238
  • Caribbean Netherlands 599
  • Cayman Islands 1-345
  • Central African Republic 236
  • Chad 235
  • Chile 56
  • China 86
  • Christmas Island 61
  • Cocos (Keeling) Islands 61
  • Colombia 57
  • Comoros 269
  • Congo - Brazzaville 242
  • Congo - Kinshasa 243
  • Cook Islands 682
  • Costa Rica 506
  • Croatia 385
  • Cuba 53
  • Cyprus 357
  • Czech Republic 420
  • Denmark 45
  • Djibouti 253
  • Dominica 1-767
  • Ecuador 593
  • Egypt 20
  • El Salvador 503
  • Equatorial Guinea 240
  • Eritrea 291
  • Estonia 372
  • Ethiopia 251
  • Falkland Islands 500
  • Faroe Islands 298
  • Fiji 679
  • Finland 358
  • France 33
  • French Guiana 594
  • French Polynesia 689
  • French Southern Territories 262
  • Gabon 241
  • Gambia 220
  • Georgia 995
  • Germany 49
  • Ghana 233
  • Gibraltar 350
  • Greece 30
  • Greenland 299
  • Grenada 1-473
  • Guadeloupe 590
  • Guam 1-671
  • Guatemala 502
  • Guernsey 44
  • Guinea 224
  • Guinea-Bissau 245
  • Guyana 592
  • Haiti 509
  • Heard & McDonald Islands 672
  • Honduras 504
  • Hong Kong 852
  • Hungary 36
  • Iceland 354
  • India 91
  • Indonesia 62
  • Iran 98
  • Iraq 964
  • Ireland 353
  • Isle of Man 44
  • Israel 972
  • Italy 39
  • Jamaica 1-876
  • Japan 81
  • Jersey 44
  • Jordan 962
  • Kazakhstan 7
  • Kenya 254
  • Kiribati 686
  • Kuwait 965
  • Kyrgyzstan 996
  • Laos 856
  • Latvia 371
  • Lebanon 961
  • Lesotho 266
  • Liberia 231
  • Libya 218
  • Liechtenstein 423
  • Lithuania 370
  • Luxembourg 352
  • Macau 853
  • Macedonia 389
  • Madagascar 261
  • Malawi 265
  • Malaysia 60
  • Maldives 960
  • Mali 223
  • Malta 356
  • Marshall Islands 692
  • Martinique 596
  • Mauritania 222
  • Mauritius 230
  • Mayotte 262
  • Mexico 52
  • Micronesia 691
  • Moldova 373
  • Monaco 377
  • Mongolia 976
  • Montenegro 382
  • Montserrat 1-664
  • Morocco 212
  • Mozambique 258
  • Myanmar 95
  • Namibia 264
  • Nauru 674
  • Nepal 977
  • Netherlands 31
  • New Caledonia 687
  • New Zealand 64
  • Nicaragua 505
  • Niger 227
  • Nigeria 234
  • Niue 683
  • Norfolk Island 672
  • North Korea 850
  • Northern Mariana Islands 1-670
  • Norway 47
  • Oman 968
  • Pakistan 92
  • Palau 680
  • Palestine 970
  • Panama 507
  • Papua New Guinea 675
  • Paraguay 595
  • Peru 51
  • Philippines 63
  • Pitcairn Islands 870
  • Poland 48
  • Portugal 351
  • Puerto Rico 1
  • Qatar 974
  • Romania 40
  • Russia 7
  • Rwanda 250
  • Réunion 262
  • Samoa 685
  • San Marino 378
  • Saudi Arabia 966
  • Senegal 221
  • Serbia 381 p
  • Seychelles 248
  • Sierra Leone 232
  • Singapore 65
  • Slovakia 421
  • Slovenia 386
  • Solomon Islands 677
  • Somalia 252
  • South Africa 27
  • South Georgia & South Sandwich Islands 500
  • South Korea 82
  • South Sudan 211
  • Spain 34
  • Sri Lanka 94
  • Sudan 249
  • Suriname 597
  • Svalbard & Jan Mayen 47
  • Swaziland 268
  • Sweden 46
  • Switzerland 41
  • Syria 963
  • Sao Tome and Principe 239
  • Taiwan 886
  • Tajikistan 992
  • Tanzania 255
  • Thailand 66
  • Timor-Leste 670
  • Togo 228
  • Tokelau 690
  • Tonga 676
  • Trinidad & Tobago 1-868
  • Tunisia 216
  • Turkey 90
  • Turkmenistan 993
  • Turks & Caicos Islands 1-649
  • Tuvalu 688
  • U.S. Outlying Islands
  • U.S. Virgin Islands 1-340
  • UK 44
  • US 1
  • Uganda 256
  • Ukraine 380
  • United Arab Emirates 971
  • Uruguay 598
  • Uzbekistan 998
  • Vanuatu 678
  • Vatican City 39-06
  • Venezuela 58
  • Vietnam 84
  • Wallis & Futuna 681
  • Western Sahara 212
  • Yemen 967
  • Zambia 260
  • Zimbabwe 263
Age Of Your Child
  • Less Than 6 Years
  • 6 To 10 Years
  • 11 To 16 Years
  • Greater Than 16 Years

Adjacency Matrix – Directed Graph

Adjacency Matrix and Path Matrix
Direct Graph with Loop

Consider a directed graph as shown above. There is a path from node A to node B, but there doesn’t exist any direct path from node B to node A. Similarly there is a path from node C to node A but no such path between node A to node C.

Now consider a pair of nodes B and C. There is a direct path from node B to node C as well as from node C to node B. The adjacency matrix of the above graph is represented as

Adjacency Matrix and Path Matrix

Path Matrix in Graph Theory

A path matrix in a data structure is a matrix representing a graph, where each value in $m^th$ row and $n^th$ column project whether there is a path from node $m$ to node $n$. The path may be direct or indirect. It may have a single edge or multiple edges.

To understand what is path matrix in data structure, let’s consider the following graph

Adjacency Matrix and Path Matrix
Directed Graph

The adjacency matrix of the above graph is 

CodingHero - 2 Essential Concepts of Graph Explained for Kids Advantage

If we consider the pair of nodes B and E. From the above adjacency matrix, we find that there is no direct path between B and E. But there exists a  path from B and E through C. Such a path is known as a path of length 2. Similarly, a path of length 3 will have 2 intermediate nodes. In general, a path of length n will have (n – 1) intermediate nodes. 

To obtain a path matrix of length 2, the adjacency matrix is multiplied by itself.

Adjacency Matrix and Path Matrix

From the above matrix, we find that there exists a path of length 2 between A to B, E to B, A to C, D to C, C to D, and B to E.

Again multiplying the path matrix of length 2 with the adjacency matrix gives a path matrix of length 3.

Adjacency Matrix and Path Matrix

From the above matrix, we find that there exists a path of length 3 between C to B, A to C, E to C, B to D, A to E, and D to E.

In general, to generate the matrix of the path of length n, take the matrix of the path of length (n – 1), and multiply it with the matrix of a path of length 1.

Types of Coordinate Systems

Practice Problems

1. The number of elements in the adjacency matrix of a graph having 7 vertices is __
a) 7
b) 14
c) 36
d) 49

2. Adjacency matrix of all graphs is symmetric.
a) False
b) True

FAQs

What is the sum of the elements of column i of the adjacency matrix of a graph?

The sum of the elements of column i of the adjacency matrix of a graph is the degree of vertex i.

What is a matrix function?

A function that maps a matrix to another matrix.

What are the areas in which matrices can be applied?

Matrices have varied applications in many fields, including electrical engineering, computer science, seismic surveys, scientific studies, etc.

Conclusion

The adjacency matrix is a connection matrix containing rows and columns used to represent a simple labeled graph. Path matrix in data structure, the element on the $i^{th}$ row and $j^{th}$ column is 1 if there’s a path from $i^{th}$ vertex to $j^{th}$ in the graph, and 0 if there is not. The adjacency and path matrices are used in optic science to account for refraction and reflection and are also useful in electrical circuits and quantum physics.

Recommended Reading

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}
>