Graflar uning turlari. Daraxtlar. Graflar va ularning turlari

Definition and Notation
A simple graph is a graph that does not have any loopsor parallel edges. In a simple graph, an edge with endpoints v and w isdenoted{v,w}.
Example 10.1.8 A Simple Graph Draw all simple graphs with the four vertices {u,v,w,x} and two edges, one of which is{u,v}.



Definition A graph H issaid to be a subgraph of a graph G if, and only if, every vertex in H is also a vertex in G, ever y edge in H is also an e dge in G, an d every edge in H has the same en dpoints as it has in G.
Example 10.1.11 Subgraphs List all subgraphs of the graph G with vertexset{v1,v2}and edge set{e1,e2,e3}, where the endpoints of e1 are v1 and v2, the endpoints of e2 are v1 and v2, and e3 is a loop at v1.



The Concept of Degree
The degree of a vertex is the number of endsegments of edges that “sticko ut of” the vertex. We will show that the sum of the degrees of all the vertices in a graph is twice the number of edges of the graph.
10.1 Graphs: Definitions and Basic Properties 635
Definition.Let G be a graph and v a verte x of G. Thedegree of v, denoted deg(v), equals the number of edges that are incident on v, with an edge that is a loop counted twice. The total degree of G is the sum of the degrees of all the vertices of G.
Since an e dge that is a loop isc ounted twice, the degree of a vertexcan be obtained from the drawing of a graph byc ounting how many endsegments of edges are incident on the vertex. This is illustrated below.

Matrices and Directed Graphs

Consider the directedgraph shown inFigure 10.3.1. This graph 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.
Definition
LetG beadirectedgraphwithorderedverticesv1,v2,...,vn.Theadjacencymatrix of G is the n × n matrix A= (aij) over the set of nonnegative integers such that aij =the number of arrows from vi to vj for all i, j =1,2,...,n.

.

10.3 Matrix Representations of Graphs 663
Note that nonzero entries along the main diagonal of an adjacency matrix indicate the presence of loops, and entries larger than 1 correspond to parallel edges. Moreover, if the vertices of a directed graph are reordered, then the entries in the rows andcolumns of the corresponding adjacency matrix are moved around.
Example 10.3.2 The Adjacency Matrix of a Graph The two directed graphsshown below differ only in the ordering of their vertices.
Find their adjacency matrices.