There are different matrix for representation of graphs, for example, incidence matrix, adjacency, etc. any book on graph theory contains detailed description of them. 

let me elaborate a little; actually what i meant by string is a sequence of 0s and 1s like "011010010" that represents a graph; can such a string be constructed for a graph in such a way that the string could be fed to some process to reconstruct the same graph?

in short, consider the string as of a container of all information related to the graph in question; it can be used to rebuild its original graph.

I am not aware of such a representation for general graphs (except via incidence matrices) but it is a standard representation for rooted binary trees. You denote the root by the empty string, left child by 0, right child by 1 and so on. If the vertex is denoted by the word w, its left child (if it exists) is w0, its right child is w1 etc. A vertex u is on a path from the root to some other vertex v iff the word for u is a substring for the word for v.

Hi Hassan....

Both way construction: between graph and string of {0,1} is possible under certain constrains. 

Graph Adjacency matrix string of {0,1}.

Hi Hassan,

I agree with Gurner's answer for simple digraphs.

thank everyone for the answers; are there other ways besides using adjacency matrix to do the same thing?

You'll find that it isn't too difficult to find other ways to encode a graph as a binary string.  Why?  Because, of what a graph is in terms of its combinatorial description.  It's combinatorial description is a set of vertices and a set of pairs of vertices.  If you have any way to recognize when you start/stop reading the next bit of information, you can do it pretty easily if you lay out the scheme.  The "natural" way is what other posters have suggested with an adjacency matrix or an incidence matrix (but it definitely doesn't have to be this way).

The problem with representations gets interesting when it comes to what kind of questions you want to answer (i.e., decision problems) about the encoded graph.

If your graph is undirected, loopless and unweighted, you could represent it as a string by writing the entries above the diagonal of the adjacency matrix one after the other. For example, the path on 4 vertices, having adjacency matrix

[0 1 0 0]

[1 0 1 0]

[0 1 0 1]

[0 0 1 0]

would be coded as "100101". That string would be enough to reconstruct the original graph.

thank you &Alexander

Hassan,

The "String" is kind of high level word in the world of traditional languages. It could be represented by a character array or int array or long array....so on.

Idid not exactly understand the importance of {0,1} inside the string. Are you not wasting a lot of space ?? Can you elaborate the exact problem statement? Why do you need a string, not any other keywords ? Are you implementing something where the API recognizes only String such as File_Read or data_read/write etc?? If it is the situation, there are huge alternatives and the first one is : read in binary mode, so you never require a STRING.

However, Let me give some crude method that may help you to get resolve the problem without going inside deeper mathematics.

First, design the data-structure format of your container:

For graph, get basic Static parameters : Resolution, scaling, offset (if any) , units etc and put inside Header. You can store dynamic data inside Data segment. Starting and delimiter parts are optional.

The data format can be:

Header (Static params): [Resolution (1 Byte), Sample rate/sec (1 Byte or more), X-unit (Fixed bytes), Y-unit (Fixed Bytes)

Data (Dyn params): X-data1(X bytes as defined in header), Y-data1 (X bytes as defined in header), X-data2(X bytes as defined in header), Y-data2 (X bytes as defined in header)...................................

*If you are passing Sample rate, either X or Y parameter may be enough.

X-data1(X bytes as defined in header), Y-data (X bytes as defined in header)

All those data can be easily stored inside a char array or int or double array. 

If you really need a STRING, just check individual bits and set as 0 or 1 in the string. though it is a worst way of implementation.

@Jotiba_Kitturkar thanks; but have you read the earlier answers for this question?

You can represent a graph by using binary strings and also you can represent binary strings by using graphs. The best examples of this kind of graphs were rooted tress, but you can represent them with Hasse diagram too. I have published an article about that an it is excepted but yet not published.

Bipartite graph can be converted to binary string and vice versa.

" Just arbitrarily number the vertices 1,2,3,... and write down the list of pairs (1,1),(1,2), etc that represent the edges (use self-edges to represent isolated vertices, "

To add to this answer by(Peter), (Kindly see the attached image) Supposing a set of n-vertices are connected via edges to a single vertex {A} One can represent such an adjacency (i.e. Adj(A,{V_1,V_2,...})) (if one were only interested in the number of adjacent vertices ) as Adj(1,{0,0,0,...}) or simply 1000... Where everything to the right of 1 is adjacent to the vertex represented by 1.

One can then get creative and have sequences of the form: 1000100, which can be interpreted as everything to the right of each 1 is adjacent to 1.

If say, one of the 0's were to be adjacent to another set of vertices, then one need only replace the 0 with 1 and add another series of zero's within the sequence. A problem arises if these 'new' set if zeros were not adjacent to the left most 1; for instance in: 1001000, if the last three 0's were not adjacent to the first 1 in the sequence, then some means of representing this will be necessary. One could however embed information in structure, i.e. for instance (101), should it occur, can be interpreted as: 'not adjacent to the first 1 in the sequence....'

At a junction where the idea is almost clear but not formal enough to be entirely challenged, one can choose to take one of two possible routes, which is either to reject it as absurd simply because it does not pass the bar of perfection, or to try and understand the 'end goal' and assist in the formalization process.

Two months ago I have given an answer that you can represent a graph by using binary strings and also you can represent binary strings by using graphs. The best examples of this kind of graphs were rooted tress, but you can represent them with Hasse diagram too. I have published an article about that an you can find it atached.