How do we specify a graph? We can list the vertices and edges (with end points), but there are other useful representations. Saying that a graph is loop less means that multiple edges are allowed but loops are not.

Definition.

Let G be a loop less graph with vertex set V (G) = {V₁, . . . , v_n } and edge set E(G) = {e₁, ..., e_m}. The adjacency matrix of G, written  A(G), is the-n-by-n matrix in which entry a_i,j is the number of edges in G with endpoints {V_i, V_j}. The incidence matrix M(G) is the n-by-m matrix in which entry m_i,j is 1 if V_i is an, endpoint of e_j and otherwise is O. If vertex V is an endpoint of edge e, then V and e are incident. The degree of vertex V (in a loop less graph) is the number of incident edges.

1.1. Remark.

An adjacency matrix is determined by a vertex ordering. Every adjacency matrix is symmetric (a_i,j = a_j,i for all i, j). An adjacency matrix

of a simple graph G has entries 0 or 1, with Os on the diagonal. The degree of  v is the sum of the entries in the row for v in either A(G) or M(G). .

1.2. Example.

 For the loop less graph G below, we exhibit the adjacency matrix and incidence matrix that result from the vertex ordering w, x, y, z and

the edge ordering a, b, c, d, e. The degree of y is 4, by viewing the graph or by summing the row for. y in either matrix.

Presenting an adjacency matrix for a graph implicitly names the vertices by the order of the rows; the ith vertex corresponds to the ith row and column. Storing a graph in a computer requires naming. the vertices. Nevertheless, we want to study properties (like connectedness) that do not depend on these names. Intuitively, the structural properties of G and H will be the same if we can rename the vertices of G using the vertices in H so that G will actually become H. We make the definition precise for simple graphs. The renaming is a function from V(G) to V(H) that assigns each element of V(H) to one element of V(G), thus pairing them up. Such a function is a one-to-one correspondence or bijection (see Appendix A). Saying that the renaming turns G into H is saying that the vertex bijection preserves the adjacency relation.

1.3. Definition.

 An isomorphism from a simple graph G to a simple graph H is a bijection f: V(G)→­ V(H) such that uv ϵE(G) if and only if (u)f(v) ϵ E(H). We say "G is-isomorphic to H", written G ­ H, if there is an isomorphism from G to H.

1.4. Example.

The graphs G and H drawn below are 4-vertex paths. Definethe function f: V(G)→ ­V(H) by f(w) = a, f(x) = d, f(y) = b, f(z) = c. To show that f is an isomorphism, we check that f preserves edges and non- edges. Note that rewriting A(G) by placing the rows in the order w, y, z, x and the columns also in that order yields A(H), as illustrated below; this verifies that f is an isomorphism.

Another isomorphism maps w, x, y, z to c, b, d, a, respectively.

1.5. Remark.

Finding isomorphisms. As suggested in Example 1.4 pre- senting the adjacency matrices with vertices ordered so that the matrices are identical is one way to prove that two graphs are isomorphic. Applying a permutation a to both the rows and the columns of A(G) has the effect of reordering the vertices of G. If the new matrix equals A(H), then the permutation yields an isomorphism. One can also verify preservation of the adjacency relation without writing out the matrices. In order for an explicit vertex bijection to be an isomorphism from G to H, the image in H of a vertex v in G must behave in H as v does in G. For example, .they must have the same degree. .

Introduction to Graph Theory Second Edition, Douglas B. West , Indian Reprint, 2002,page(6.8)

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength