Properties of Graphs

Graphs may be unrestricted, simple, sparse or connected. In unrestricted graphs, the edges have no inherent direction to imply a symmetric relationship between the vertices each edge connects. We may leave edges unweighted and not give these strengths a priori. An unweighted edge is important only in its relationships to other edges. In a simple graph, we forbid multiple edges that connect the same vertices. A forbidden edge would be one that might circle around and then connects a vertex with itself. A graph may be sparse. For an undirected graph the maximal size of E(G) equals (n > 2) = n(n — 1)/2, corresponding to a fully connected or complete graph. Sparseness implies M, the graph's size, ^ n(n — 1)/2. Lastly, we may create a connected graph. In a connected graph, one may move from any vertex to any other vertex by traversing a path of only a finite number of edges. A circulation, be it open or closed, is a connected graph, because a drop of blood from one region may circulate to any other.

0 0

Post a comment