# Tag Info

28

When doing a DFS, any node is in one of three states - before being visited, during recursively visiting its descendants, and after all its descendants have been visited (returning to its parent, i.e., wrap-up phase). The three colors correspond to each of the three states. One of the reasons for mentioning colors and time of visit and return is to ...

28

Tree Examples (image): A: B: ‾‾ ‾‾ 1 1 / / \ 2 2 3 / 3 This is an example that fits your scenario, Tree A root׳s value is 1, having a left child with value 2, and his left child has also a left child with value 3. Tree B root׳s value is 1, ...

23

Wikipedia has the answer: All types of edges appear in this picture. Trace out DFS on this graph (the nodes are explored in numerical order), and see where your intuition fails. This will explain the diagram:- Forward edge: (u, v), where v is a descendant of u, but not a tree edge.It is a non-tree edge that connects a vertex to a descendent in a DFS-tree....

23

Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue. The “frontier” is the set of all nodes in the search data structure. The queue will will iterate through all nodes on the frontier sequentially, thus iterating across the breadth of the frontier. DFS will always ...

16

If looking for the key 60 we reach a number $K$ less than 60, we go right (where the larger numbers are) and we never meet numbers less than $K$. That argument can be repeated, so the numbers 10, 20, 40, 50 must occur along the search in that order. Similarly, if looking for the key 60 we reach a number $K$ larger than 60, we go leftt (where the smaller ...

12

Transposing the adjecency matrix $A$ does $\qquad A[i,j] = 1 \iff A^T[j,i] = 1$. In terms of graphs, that means $\qquad u \to_G v \iff v \to_{G^T} u$. In other words, transposing reverses the direction of all edges. Note that $G^T$ has the same strong components as $G$. The algorithm you are looking at is Kosaraju's algorithm. Be carful with your notion ...

12

All parts of proving the claim hinge on 2 crucial properties of trees with undirected edges: 1-connectedness (ie. between any 2 nodes in a tree there is exactly one path) any node can serve as the root of the tree. Choose an arbitrary tree node $s$. Assume $u, v \in V(G)$ are nodes with $d(u,v) = diam(G)$. Assume further that the algorithm finds a node $x$ ...

11

It is NP-complete to even decide whether any path exists. It is clearly possible to verify any given path is a valid path in the given graph. Thus the bounded-length problem is in NP, and so is its subset, the any-path problem. Now, to prove NP-hardness of the any-path problem (and thus of the bounded-length problem), let's reduce SAT-CNF to this problem: ...

11

A path of length $n$ consists of $n$ line segments in the plane. You want to find all intersections between these line segments. This is a standard problem that has been studied in depth in the computer graphics literature. A simple algorithm is the following: for each pair of line segments, check whether they intersect (using a standard geometric ...

10

There are exponentially many such routes. Think of a sequence of $n$ diamonds. At each diamond, you can go either left or right, independently of what you do at all other diamonds. This leads to $2^n$ paths, each of which is non-intersecting. Now the complete graph on those vertices contains all of these paths, plus some more, so this is a lower-bound on ...

10

The intuition behind is very easy to understand. Suppose I have to find longest path that exists between any two nodes in the given tree. After drawing some diagrams we can observe that the longest path will always occur between two leaf nodes( nodes having only one edge linked). This can also be proved by contradiction that if longest path is between two ...

9

A DFS traversal in an undirected graph will not leave a cross edge since all edges that are incident on a vertex are explored. However, in a directed graph, you may come across an edge that leads to a vertex that has been discovered before such that that vertex is not an ancestor or descendent of the current vertex. Such an edge is called a cross edge.

9

No, it's not limited to binary trees. Yes, pre-order and post-order can be used for $n$-ary trees. You simply replace the steps "Traverse the left subtree.... Traverse the right subtree...." in the Wikipedia article by "For each child: traverse the subtree rooted at that child by recursively calling the traversal function". We assume that the for-loop ...

9

This represents a difference between the kinds of problems the CS algorithms community usually uses BFS to solve, vs the kinds of problems the CS artificial intelligence community usually uses BFS to solve. The algorithms community typically is focused on the case where we have a finite graph, and where we're going to run some algorithm that probably visits ...

9

Your algorithm is known as greedy coloring. Wikipedia gives an example of a bipartite graph, the crown graph, where the greedy coloring can produce a coloring using $n/2$ colors (for the worst ordering). For random $G(n,1/2)$ graphs, the greedy coloring typically produces a coloring using double the optimal number of colors.

8

A depth first search on a directed graph can yield 4 types of edges; tree, forward, back and cross edges. As we are looking at undirected graphs, it should be obvious that forward and back edges are the same thing, so the only things left to deal with are cross edges. A cross edge in a graph is an edge that goes from a vertex $v$ to another vertex $u$ such ...

8

The book is counting the number of times each line is executed throughout the entire execution of a call of DFS, rather than the number of times it is executed in each call of the subroutine DFS-VISIT. Perhaps the following simpler example will make this clear: PROCEDURE A(n) 1 global = 0 2 for i from 1 to n: 3 B(i) 4 return global PROCEDURE B(i) 1 ...

8

The bounds $O(|V|+|E|)$ and $O(b^d)$ are talking about different things. The former is appropriate when you know what $V$ and $E$ are in advance, and they're both finite. The latter is appropriate when the graph is only defined implicitly and may be infinite, or where you've decided in advance that you're only going to search to a fixed depth. An ...

8

Lets assume you consider trees of $n$ nodes. Now take any binary tree with $n$ nodes and name the nodes according to their pre-order numbering. Then clearly the pre-order sequence of the tree will be $1,2,\dots,n$. This means that we can name the nodes of any binary tree structure so that it will generate the same pre-order sequence as that of another ...

8

Counting argument The number of unlabeled binary trees of $n$ nodes is the $n^\text{th}$ Catalan number $C_n=(2n)!/(n!(n+1)!).$ For example there are 5 binary trees of 3 nodes, o o o o o / / / \ \ \ o o o o o o . / \ ...

7

First of all, it depends a bit how you can access your data to say which algorithms works best. Anyway, I would suggest to determine the heights in a top-down fashion rather than bottom-up. I personally think that a top-down approach is conceptually nicer and easier to analyze. For any vertex $v$ in the forest it is true that \text{height}(v)=\begin{...

7

Let $G$ be strongly connected. Run BFS (!) from an arbitrary vertex $s$. BFS creates a leveled tree where level of a vertex $v$ is it's directed distance from $s$. If while running BFS you have never seen an edge $(u,v)$ that goes between levels of the same parity then $G$ is bipartite. The parity of the level of $u$ defines the partition that $u$ belongs to....

7

You basically have two choices: "cheating" by embedding a queue in the nodes, and simulating BFS with higher complexity. Embedded-Queue Cheating If you look at virtually any description of BFS, e.g., this one on Wikipedia, then you can see that the algorithm adds attributes to nodes. E.g., the Wikipedia version adds to each node the attributes distance and ...

7

This is proved by Cook and McKenzie. We make use of the following notation: $\deg(v)$ is the degree of a vertex $v$. $N(v,1),\ldots,N(v,\deg(v))$ is some fixed ordering of the neighbors of $v$. We construct a sequence $v_1,v_2,\ldots$ of nodes starting with $v_1 = s$ and $v_2 = N(s,1)$ (if $\deg(s) = 0$ then $s$ is connected to $t$ iff $s = t$). Given $v_{... 7 It depends on what exactly you call DFS. Consider for example the algorithm DFS-iterative described in Wikipedia, and suppose that you run it on a tree so that you don't have to keep track of which nodes you have already visited. Suppose that you run it on a complete$b$-ary tree of depth$m$. We can identify nodes in their tree with words over$[b]$of ... 6 In the long run, it's really better to understand the graph theory terminology, but for now, here is an explanation of Christofides's algorithm. I'm not an expert in this area so I can't offer much by way of intuition. Also, I should note that by now, better algorithms are known for some variants, see for example the recent survey by Vygen. We denote the ... 6 Here is one approach. Given leaves$\alpha,\beta$, first compute the depths$d(\alpha),d(\beta)$of both leaves (to compute the depth of a leaf, measure how many times you need to apply the parent operation until you reach the root). Suppose without loss of generality that$d(\alpha) \geq d(\beta)$. Replace$\alpha$with$\alpha$'s$(d(\alpha) - d(\beta))$'... 6 I would suggest the following approach. Maintain a data structure$H$of$(i,j, g(i,j))$triples so that you can efficiently find and remove a triple$(i,j,w)$that minimises$w$. Maintain a partition$P$of nodes$V = \{1,2,\dotsc,N\}$. Maintain a tree$T$. We will maintain the invariant that$T$contains some edges of the tree that we are trying to ... 6 No, there isn't (not unless P=NP). Take an unweighted directed graph on$n$vertices, and set all of the edge weights to$-1$. Now there is a simple cycle of weight$-n\$ if and only if there is a Hamiltonian circuit in the original graph. But detecting the existence of Hamiltonian circuits is NP-hard. Therefore your problem is NP-hard, too.

Only top voted, non community-wiki answers of a minimum length are eligible