It is obvious that the representational power of graphs are huge.
Is there a problem that cannot be represented using graph?

I have recently asked this question to my students and no answers came up. I could not answer this either.

For instance:
Problem: Finding the shortest path between two given cities in a country.
Graph type: Directed, weighted.
Vertices: Cities.
Edges: An edge $(i,j)$ indicates there is a way from city $i$ to city $j$ and weight of $(i,j)$ indicates the distance between cities $i$ and $j$.

Problem: Expressing your feelings using crayons.
Graph type: Directed, weighted.
Vertices: Neurons in the brain.
Edges: Values of electronic signals being transmitted among neurons.
Output: Interpretation of the signals by the brain.
(Just kidding)

Edit: Problem in this post means, a problem that can be solved using computers.

  • 6
    $\begingroup$ Define "scenario" and "represent". With loose definitions, the representational power of a sequence of !s is just as great. If you take !!! to be a number in unary, convert in to binary and interpret as a text file. $\endgroup$ – Karolis Juodelė May 26 '14 at 20:19
  • 1
    $\begingroup$ "Express your feelings using crayons." $\endgroup$ – Raphael May 26 '14 at 21:20
  • $\begingroup$ @Raphael please see my edit. $\endgroup$ – padawan May 26 '14 at 21:40
  • $\begingroup$ What about "sum of three (or more) given numbers"? $\endgroup$ – mrmowji May 27 '14 at 1:03
  • 1
    $\begingroup$ @Mowji Represent the natural number $i$ by any graph on $i$ vertices and sum by disjoint union. $\endgroup$ – David Richerby May 27 '14 at 7:50

It's trivial to encode natural numbers as graphs (represent $n$ by a path of length $n$, or by $K_n$) so anything that can be represented as numbers can be represented as graphs.

  • $\begingroup$ No, that answer is too easy for me. Numbers have structure, mathematical context, they are not just counting. If you need numbers in a context a faithful representation should naturally represent that context. For example there should be a nice interpretation for "this number is prime". $\endgroup$ – Hendrik Jan May 27 '14 at 22:52
  • $\begingroup$ @HendrikJan Peano got a long way by defining the natural numbers as the closure of $0$ under the successor operation: there's a lot you can do with "just counting". If you represent $n$ by $K_n$, then $n$ is prime iff it can't be written as a strong product except as $K_1\boxtimes K_n$. $\endgroup$ – David Richerby May 27 '14 at 23:40
  • $\begingroup$ You are right on both these counts. Still I stress the comment by Karolis above: "represent" has to be defined and chosen in a natural way to fit the context. We can represent a Turing machine program by a labelled graph easily, but that doesn't make the halting problem into a graph problem. $\endgroup$ – Hendrik Jan May 27 '14 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.