# Tagged Questions

30 views

### Preorder Traversal

For Each Preorder Traversal, we have multiple Inorder Traversal. this is True or False Conclusion? every one would help me and add some detail.
37 views

### Visiting Node in BFS and DFS in the same order [closed]

if G be a connected, undirected graph and has at least 3 vertex. we know the order of visiting node from a given vertex in BFS and DFS is the same. which of the following is false? a) G can be a ...
26 views

### Tarjan's algorithm to determine wheter a directed graph has a cycle

I want to know if a directed graph has a cycle; something like 1->2->3->2 ... 1->2->3->4->3... 1->1->1->1... So, I'm considering ...
33 views

### Shortest path between two vertex

How we can find Shortest path between two vertex in a weighted directed acyclic graph that has positive and negative weight. in O(|V|+|E|)? thanks to all.
37 views

### Hanoi Algorithm With Different Nodes

http://en.wikipedia.org/wiki/Tower_of_Hanoi I need help developing a Hanoi algorithm which follows the same rules as the standard game, however the nodes that are transversed is different. In this ...
37 views

### Are minimum cut communities maximal?

I am looking at the paper Graph Clustering and Minimum Cut Trees by Flake et al. Let $G(V, E)$ be some undirected weighted graph. Definition. Let $s, t\in V$ be given. Let $(S, T)$ be the minimum ...
68 views

### Graph theory / vertex-set list representation

If I were to consider a graph with vertex-set V= {1, 2, 3, ... 10} with the edges taken as all the pairs {x, y} of distinct members of V that have a prime factor in common, how would one write the ...
42 views

### Width and height of binary tree is $\theta(n)$?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
43 views

### Graph Degree and Some Condition

If $G$ be a Tree with degree $(5,r,s,1,1,1,1,1)$. (I wrote degree in non-increasing order). why all of this condition is True sometimes (I means on some condition)? I try to find an example that ...
49 views

### Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
19 views

### Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
47 views

### Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
39 views

### Check if there's a cycle in an undirected graph

I'm trying to find an algorithms that checks if there's a cycle in a given undirected graph G=(V,E). But I didn't succeed. Can anyone give me such an algorithm?
80 views

### Shortest path between wikipedia articles

I'm trying to figure out whether it is possible (and if so how) to find the shortest path inside a network from one node to another. I know that there are different possible algorithms to do that the ...
28 views

### Computer program for decomposing a graph into subgraphs?

Obviously there are programs out there that can find perfect matchings. I am interested in finding out if there is a program that can, for instance, tell when graphs like the cube graph $Q_n$, has ...
25 views

30 views

106 views

### How to Enumerate of all simple connected labeled graphs with prescribed degree sequence?

For v=4 vertices, there must be 7 possible graphic sequence (3,3,3,3)(3,3,2,2)(3,2,2,1)(3,1,1,1)(2,2,2,2)(2,2,1,1)(1,1,1,1). From (3,3,3,3), one simple graph(complete) can be found. From(3,3,2,2), 6 ...
128 views

### Finding the shortest/“most negative” closed directed trail in a weighted digraph with negative weights

I'm using the following definition of a "closed directed trail": a closed directed trail is a directed cycle in a digraph where all edges are distinct. Note that vertices may be repeated, so long as ...
At the moment I'm in need to learn how to describe a graph through a logic statement such as:  \forall x\forall y(r(x,y) \to \lnot s(y,x) \land \lnot s(y,x)) \land \exists (s(z,z) \land \lnot ...