Struktur Diskrit : Merepresentasikan Graf dalam List dan Matriks
Representing Graphs
Adjacency List
Specify the vertices that are adjacent to each vertex of the graph.
Adjacency Matrix
Represents graph by a matrix based on the adjacency of vertices
Incidence Matrix
Represents graph by a matrix based on the incidence of vertices and edges.
Adjacency List (Undirected Graph)
Specify the vertices that are adjacent to each vertex of the graph
Adjacency List ( Directed Graph )
List all the vertices that are the terminal vertices of edges starting at each vertex of the graph
Adjacency Matrices
Suppose that G = (V , E) is a simple graph where |V| = n. Suppose that the vertices of G are listed arbitrarily as v1, v2,..., vn.
The adjacency matrix A (or AG) of G, with respect to this listing of the vertices, is the n x n zero–one matrix with 1 as its (i, j )th entry when vi and vj are adjacent, and 0 as its (i, j )th entry when they are not adjacent.
•If its adjacency matrix is A = [aij], then
Adjacency Matrix ( Not Simple Undirected Graph )
Aij is represent by the number of edges that associated to [ai, aj]. A loop at a vertex represent by 1. When multiple edges are present, adjacency matrix is no longer a zero-one matrix. The matrix is symmetric.
Adjacency Matrix ( Directed Graph )
Aij is represent by the number of edges from ai to aj. A loop at a vertex represent by 1. When multiple edges are present, adjacency matrix is no longer a zero-one matrix. The matrix is not symmetric.
Draw Graph from Adjacency Matrix
An adjacency matrix of a graph is based on the ordering chosen for the vertices.
There are n! different adjacency matrices for a graph with n vertices, because there are n! different ordering of n vertices
EXAMPLE: Draw a graph with the given adjacency matrix
Incidence Matrices
The incidence matrix for undirected graph G with n vertices v1, v2, …, vn, and m edges e1, e2, …, em, is the m × n matrix M = [mij], where
Posting Komentar