![]() CATEGORIES: BiologyChemistryConstructionCultureEcologyEconomyElectronicsFinanceGeographyHistoryInformaticsLawMathematicsMechanicsMedicineOtherPedagogyPhilosophyPhysicsPolicyPsychologySociologySportTourism |
Representing graphsOne way to represent a graph without multiple edges is to list all the edges of this graph. Another way to represent a graph with no multiple edges is to use adjacency lists, which specify the vertices that are adjacent to each vertex of the graph. Example. Use adjacency lists to describe the simple graph given in Figure below.
Example. Represent the directed graph by listing all the vertices that are the terminal vertices of edges starting at each vertex of the graph.
Adjacency matrices Suppose that Example. Use an adjacency matrix to represent the graph shown in Figure below.
Solution: We order the vertices as a, b, c, d. The matrix representing this graph is Example. Draw a graph with the adjacency matrix Solution: Adjacency matrices can also be used to represent undirected graphs with loops and with multiple edges. A loop at the vertex ai is represented by a 1 at the (i, i)th position of the adjacency matrix. When multiple edges are present, the adjacency matrix is no longer a zero-one matrix, since the (i, j)th entry of this matrix equals the number of edges that are associated to Example. Use an adjacency matrix to represent the pseudograph shown in Figure below.
Solution: The adjacency matrix using the ordering of vertices a, b, c, d is
Date: 2015-01-02; view: 1406
|