-1
$\begingroup$

I have seen in some text books that they have started talking about a tree and then they use the terms such as vertices and edges and treat is as a graph.

What makes a graph a graph and what makes a tree a tree? I am getting the impression that a tree is a subset of a graph but what are these properties that make a graph a tree?

Is there a way to classify a graph from a tree?

$\endgroup$
  • 2
    $\begingroup$ Trees are connected Graphs without cycles. $\endgroup$ – Aristu Oct 22 '16 at 20:05
  • 4
    $\begingroup$ Did you have a look on Wikipedia? $\endgroup$ – Juho Oct 22 '16 at 20:22
  • $\begingroup$ is that it? what about the type of edges they have? Are cross edges allowed? Can one node have two parents? $\endgroup$ – user1932405 Oct 22 '16 at 20:41
  • 1
    $\begingroup$ You can always draw a tree without crossings. And yes a node may have more than a single parent. You can also think of (connected) trees as any graphs of |V|+1 edges, where |V| is the number of vertices. $\endgroup$ – jgyou Oct 22 '16 at 20:50
  • 1
    $\begingroup$ @jgyou You mean $|V|-1$ edges. $\endgroup$ – Yuval Filmus Oct 22 '16 at 21:59
2
$\begingroup$

An unrooted tree is a connected acyclic graph, that is a graph in which any two vertices are connected, and which contains no cycles. In particular, it's a graph.

A rooted tree is a tree in which one of the vertices has been designated as root. Every other vertex has a parent, which is its unique neighbor closer to the root. Its other neighbors are known as its children.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ can you please clarify what kind of edges a tree and a graph can have? Also by your definition of "unique neighbour" does that mean that tree children must have a single unique parent? $\endgroup$ – user1932405 Oct 22 '16 at 22:13
  • $\begingroup$ Yes, but I bet that Wikipedia did a better job. In short, though, a graph is specified by a set of vertices, and for every two vertices $x,y$, whether the edge $(x,y)$ exists or not. That's all. Graphs do not come with any kind of drawing. $\endgroup$ – Yuval Filmus Oct 22 '16 at 22:14
  • $\begingroup$ yes thats fine but what I mean is tree-edges, back-edges and cross-edges I was under the impression you could only have tree edges in a tree, is that true? $\endgroup$ – user1932405 Oct 22 '16 at 22:20
  • 2
    $\begingroup$ This terminology comes from the DFS algorithm, and describes its output. DFS indeed finds a spanning tree in every connected graph. A tree would indeed have only tree-edges in the classification produced by DFS. $\endgroup$ – Yuval Filmus Oct 22 '16 at 22:23
  • 1
    $\begingroup$ Right, a connected graph is a tree if DFS only finds tree-edges. $\endgroup$ – Yuval Filmus Oct 22 '16 at 22:30

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.