Concept Byte: Networks

For Use With Lesson 12-2

A finite graph is a set of points, called vertices, connected by curves, or paths.

You can use a matrix to describe a finite graph. The digit “1” indicates a path between two vertices or one vertex and itself. The digit “0” indicates that no path exists between two vertices or from one vertex to itself.

Example 1

Write a matrix A to represent the finite graph. Explain the significance of element a 41 . eh sub 41 , .

Image Long Description

Element a 41 eh sub 41  is 0. It indicates that there is no path between N 4 n sub 4  and N 1 n sub 1

Directed graphs are finite graphs that indicate the direction of a path. The directed graph below represents the information in the map.

Image Long Description

You can use a matrix to represent the information in a directed graph.

Example 2

Write a matrix B to represent the information from the directed graph. Compare elements b 12 b sub 12  and b 21 . b sub 21 , .

To → P Q S T B = From → P Q S T [ 0 1 0 1 0 0 1 1 1 1 0 0 1 0 1 0 ] table with 2 rows and 1 column , row1 column 1 , table with 1 row and 4 columns , row1 column 1 , cap to rightwards arrow p , column 2 q , column 3 s , column 4 t , end table , row2 column 1 , b equals . table with 4 rows and 1 column , row1 column 1 , table with 1 row and 1 column , row1 column 1 , cap from , rightwards arrow , end table p , row2 column 1 , q , row3 column 1 , s , row4 column 1 , t , end table . table with 1 row and 1 column , row1 column 1 , . matrix with 4 rows and 4 columns , row1 column 1 , 0 , column 2 1 , column 3 0 , column 4 1 , row2 column 1 , 0 , column 2 0 , column 3 1 , column 4 1 , row3 column 1 , 1 , column 2 1 , column 3 0 , column 4 0 , row4 column 1 , 1 , column 2 0 , column 3 1 , column 4 0 , end matrix , end table , end table

Element b 12 b sub 12  is 1 and b 21 b sub 21  is 0. The path between P and Q is one way, from P to Q.

Table of Contents