GRAPH REPRESENTATION

 

Representation[edit]

A graph is an abstraction of relationships that emerge in nature; hence, it cannot be coupled to a certain representation. The way it is represented depends on the degree of convenience such representation provides for a certain application. The most common representations are the visual, in which, usually, vertices are drawn and connected by edges, and the tabular, in which rows of a table provide information about the relationships between the vertices within the graph.

Visual: Graph drawing[edit]

Main article: Graph drawing

Graphs are usually represented visually by drawing a point or circle for every vertex, and drawing a line between two vertices if they are connected by an edge. If the graph is directed, the direction is indicated by drawing an arrow. If the graph is weighted, the weight is added on the arrow.

A graph drawing should not be confused with the graph itself (the abstract, non-visual structure) as there are several ways to structure the graph drawing. All that matters is which vertices are connected to which others by how many edges and not the exact layout. In practice, it is often difficult to decide if two drawings represent the same graph. Depending on the problem domain some layouts may be better suited and easier to understand than others.

The pioneering work of W. T. Tutte was very influential on the subject of graph drawing. Among other achievements, he introduced the use of linear algebraic methods to obtain graph drawings.

Graph drawing also can be said to encompass problems that deal with the crossing number and its various generalizations. The crossing number of a graph is the minimum number of intersections between edges that a drawing of the graph in the plane must contain. For a planar graph, the crossing number is zero by definition. Drawings on surfaces other than the plane are also studied.

There are other techniques to visualize a graph away from vertices and edges, including circle packings, intersection graph, and other visualizations of the adjacency matrix.

Tabular: Graph data structures[edit]

Main article: Graph (abstract data type)

The tabular representation lends itself well to computational applications. There are different ways to store graphs in a computer system. The data structure used depends on both the graph structure and the algorithm used for manipulating the graph. Theoretically one can distinguish between list and matrix structures but in concrete applications the best structure is often a combination of both. List structures are often preferred for sparse graphs as they have smaller memory requirements. Matrix structures on the other hand provide faster access for some applications but can consume huge amounts of memory. Implementations of sparse matrix structures that are efficient on modern parallel computer architectures are an object of current investigation.[33]

List structures include the edge list, an array of pairs of vertices, and the adjacency list, which separately lists the neighbors of each vertex: Much like the edge list, each vertex has a list of which vertices it is adjacent to.

Matrix structures include the incidence matrix, a matrix of 0's and 1's whose rows represent vertices and whose columns represent edges, and the adjacency matrix, in which both the rows and columns are indexed by vertices. In both cases a 1 indicates two adjacent objects and a 0 indicates two non-adjacent objects. The degree matrix indicates the degree of vertices. The Laplacian matrix is a modified form of the adjacency matrix that incorporates information about the degrees of the vertices, and is useful in some calculations such as Kirchhoff's theorem on the number of spanning trees of a graph. The distance matrix, like the adjacency matrix, has both its rows and columns indexed by vertices, but rather than containing a 0 or a 1 in each cell it contains the length of a shortest path between two vertices.

Comments

Post a Comment

Popular posts from this blog

Functions between metric spaces

Image
  Functions between metric spaces [ edit ] Euler diagram  of types of functions between metric spaces. Unlike in the case of topological spaces or algebraic structures such as  groups  or  rings , there is no single "right" type of  structure-preserving function  between metric spaces. Instead, one works with different types of functions depending on one's goals. Throughout this section, suppose that  ( � 1 , � 1 )  and  ( � 2 , � 2 )  are two metric spaces. The words "function" and "map" are used interchangeably. Isometries [ edit ] Main article:  Isometry One interpretation of a "structure-preserving" map is one that fully preserves the distance function: A function  � : � 1 → � 2  is  distance-preserving [12]  if for every pair of points  x  and  y  in  M 1 , � 2 ( � ( � ) , � ( � ) ) = � 1 ( � , � ) . It follows from the metric space axioms that a distance-preserving function is injective. A bijective distance-preserving function is calle
Read more

Quasi-isometries

Image
  Quasi-isometries [ edit ] Main article:  Quasi-isometry A  quasi-isometry  is a map that preserves the "large-scale structure" of a metric space. Quasi-isometries need not be continuous. For example,  � 2  and its subspace  � 2  are quasi-isometric, even though one is connected and the other is discrete. The equivalence relation of quasi-isometry is important in  geometric group theory : the  Švarc–Milnor lemma  states that all spaces on which a group  acts geometrically  are quasi-isometric. [15] Formally, the map  � : � 1 → � 2  is a  quasi-isometric embedding  if there exist constants  A  ≥ 1  and  B  ≥ 0  such that 1 � � 2 ( � ( � ) , � ( � ) ) − � ≤ � 1 ( � , � ) ≤ � � 2 ( � ( � ) , � ( � ) ) + �  for all  � , � ∈ � 1 . It is a  quasi-isometry  if in addition it is  quasi-surjective , i.e. there is a constant  C  ≥ 0  such that every point in  � 2  is at distance at most  C  from some point in the image  � ( � 1 ) . Notions of metric space equivalence [ edit ] See also
Read more