Graflar uning turlari. Daraxtlar. Graflar va ularning turlari

Matrices and Directed Graphs
Consider the directedgraph shown inFigure 10.3.1. Thisgraph can be represented bythe matrix A= (aij) for which aij =the number of arrows from vi to vj, for all i =1,2,3 and j =1,2,3. Thus a11 =1 be cause there is one arrow from v1 to v1,a12 =0 be cause there is no arrow from v1 to v2,a23 =2 be cause there are two arrows from v2 to v3, an d so forth. A iscalled the adjacency matrix of the directed graph. For convenient reference, the rows andcolumns of A are often labeled with the vertices of the graph G.

Matrices and Undirected Graphs

Once you know how to associate a matrix with a directed graph, the definition of the matrixcorresponding to an undirected graph shouldseem natural to you.A s before, you must or der the vertices of the graph, but in thisc ase yous implyset the ijth entry of the adjacency matrix equal to the number of edgesconnecting the ith and jth vertices of the graph.
•Definition Let G be an undirected graph with ordered vertices v1,v2,...,vn. Theadjacency matrix of G is the n×n matrix A= (aij) over the set of nonnegative integers suc h that aij = the number of edgesconnecting vi and vj for all i, j =1,2,...,n.


Isomorphism Graphs

2.Thinking is a momentary dismissal of irrelevancies. — R. Buckminster Fuller, 1969

Recall from Example 10.1.3 that the two drawings shown in Figure 10.4.1 both repre- sent the same graph: Their vertex and edge sets are identical, and their edge-endpoint functions are the same. Call this graph G.

Observe that G$ is a different graph from G (for instance, in G the endpoints of e1 are v1 and v2, whereas in G$ the endpoints of e1 are v1 and v3). Yet G$ is certainly very similar to G. In fact, if the vertices and edges of G$ are relabeled by the functions shown in Figure 10.4.3, then G$ becomes the same as G.

Definition
Let G and G$ be graphs with vertex sets V(G) and V(G$) and edge sets E(G) and E(G$), respectively. G is isomorphic to G if, and only if, there exist one-to-one correspondences g: V(G) → V(G$) and h: E(G) → E(G$) that preserve the edge- endpoint functions of G and G$ in the sense that for all v ∈ V(G) and e ∈ E(G), v is an endpoint of e ⇔ g(v) is an endpoint of h(e).

Example 10.4.1 Showing That Two Graphs Are Isomorphic